content: /*
   *    This program is free software; you can redistribute it and/or modify
   *    it under the terms of the GNU General Public License as published by
   *    the Free Software Foundation; either version 2 of the License, or
   *    (at your option) any later version.
   *
   *    This program is distributed in the hope that it will be useful,
   *    but WITHOUT ANY WARRANTY; without even the implied warranty of
   *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *    GNU General Public License for more details.
   *
   *    You should have received a copy of the GNU General Public License
   *    along with this program; if not, write to the Free Software
   *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   */
  
  /*
   * TopDownConstructor.java
   * Copyright (C) 2007 University of Waikato, Hamilton, New Zealand
   */
  
  package weka.core.neighboursearch.balltrees;
  
  import weka.core.EuclideanDistance;
  import weka.core.Instance;
  import weka.core.Option;
  import weka.core.RevisionUtils;
  import weka.core.TechnicalInformation;
  import weka.core.TechnicalInformationHandler;
  import weka.core.Utils;
  import weka.core.TechnicalInformation.Field;
  import weka.core.TechnicalInformation.Type;
  import weka.core.neighboursearch.balltrees.BallNode;
  
  import java.util.Enumeration;
  import java.util.Vector;
  
  /**
   <!-- globalinfo-start -->
   * The class implementing the TopDown construction method of ball trees. It further uses one of a number of different splitting methods to split a ball while constructing the tree top down.<br/>
   * <br/>
   * For more information see also:<br/>
   * <br/>
   * Stephen M. Omohundro (1989). Five Balltree Construction Algorithms.
   * <p/>
   <!-- globalinfo-end -->
   *
   <!-- technical-bibtex-start -->
   * BibTeX:
   * <pre>
   * &#64;techreport{Omohundro1989,
   *    author = {Stephen M. Omohundro},
   *    institution = {International Computer Science Institute},
   *    month = {December},
   *    number = {TR-89-063},
   *    title = {Five Balltree Construction Algorithms},
   *    year = {1989}
   * }
   * </pre>
   * <p/>
   <!-- technical-bibtex-end -->
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -S &lt;classname and options&gt;
   *  Ball splitting algorithm to use.</pre>
   * 
   <!-- options-end --> 
   * 
   * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
   * @version $Revision: 5953 $
   */
  public class TopDownConstructor
    extends BallTreeConstructor 
    implements TechnicalInformationHandler {
    
    /** for serialization. */
    private static final long serialVersionUID = -5150140645091889979L;
    
    /** 
     * The BallSplitter algorithm used by the TopDown BallTree constructor, if it 
     * is selected. 
     */
    protected BallSplitter m_Splitter = new PointsClosestToFurthestChildren();
  
    /** 
     * Creates a new instance of TopDownConstructor.
     */
    public TopDownConstructor() {
    }
  
    /**
     * Returns a string describing this nearest neighbour search algorithm.
     * 
     * @return 		a description of the algorithm for displaying in the
     *         		explorer/experimenter gui
     */
    public String globalInfo() {
      return 
          "The class implementing the TopDown construction method of "
        + "ball trees. It further uses one of a number of different splitting "
        + "methods to split a ball while constructing the tree top down.\n\n"
        + "For more information see also:\n\n"
        + getTechnicalInformation().toString();
    }
    
    /**
     * Returns an instance of a TechnicalInformation object, containing detailed
     * information about the technical background of this class, e.g., paper
     * reference or book this class is based on.
     * 
     * @return 		the technical information about this class
     */
    public TechnicalInformation getTechnicalInformation() {
      TechnicalInformation result;
      
      result = new TechnicalInformation(Type.TECHREPORT);
      result.setValue(Field.AUTHOR, "Stephen M. Omohundro");
      result.setValue(Field.YEAR, "1989");
      result.setValue(Field.TITLE, "Five Balltree Construction Algorithms");
      result.setValue(Field.MONTH, "December");
      result.setValue(Field.NUMBER, "TR-89-063");
      result.setValue(Field.INSTITUTION, "International Computer Science Institute");
  
      return result;
    }
  
    /**
     * Builds the ball tree top down. 
     * @return The root node of the tree. 
     * @throws Exception If there is problem building
     * the tree.
     */
    public BallNode buildTree() throws Exception {
      BallNode root;
      
      m_NumNodes = m_MaxDepth = 0;
      m_NumLeaves = 1;
      
      m_Splitter.setInstances(m_Instances);
      m_Splitter.setInstanceList(m_InstList);
      m_Splitter.
      setEuclideanDistanceFunction((EuclideanDistance)m_DistanceFunction);
      
      root = new BallNode(0, m_InstList.length-1, 0);
      root.setPivot(BallNode.calcCentroidPivot(m_InstList, m_Instances));
      root.setRadius(BallNode.calcRadius(m_InstList, m_Instances, root.getPivot(), m_DistanceFunction));
      
      splitNodes(root, m_MaxDepth+1, root.m_Radius);
      
      return root; 
    }
      
    /**
     * Recursively splits nodes of a ball tree until 
     * <=m_MaxInstancesInLeaf instances remain in a node.
     * @param node The node to split.
     * @param depth The depth of this node in the tree, 
     * so that m_MaxDepth is correctly updated.
     * @param rootRadius The smallest ball enclosing all
     * the data points.
     * @throws Exception If there is some problem in 
     * splitting.
     */
    protected void splitNodes(BallNode node, int depth, final double rootRadius) throws Exception {
      
      if(node.m_NumInstances <= m_MaxInstancesInLeaf || 
         (rootRadius==0 ? true : node.m_Radius/rootRadius < m_MaxRelLeafRadius))
        return;
      
      m_NumLeaves--;
      m_Splitter.splitNode(node, m_NumNodes);
      m_NumNodes += 2;
      m_NumLeaves += 2;
      
      if(m_MaxDepth < depth)
        m_MaxDepth = depth;
    
      splitNodes(node.m_Left, depth+1, rootRadius);
      splitNodes(node.m_Right, depth+1, rootRadius);
      
      if(m_FullyContainChildBalls) {
        double radius = BallNode.calcRadius(node.m_Left, node.m_Right, 
                                           node.getPivot(), m_DistanceFunction);
        Instance pivot = BallNode.calcPivot(node.m_Left, node.m_Right, m_Instances);
  //      System.err.println("Left Radius: "+node.m_Left.getRadius()+
  //                         " Right Radius: "+node.m_Right.getRadius()+
  //                         " d(p1,p2): "+
  //                         m_DistanceFunction.distance(node.m_Left.getPivot(), node.m_Right.getPivot())+
  //                         " node's old radius: "+node.getRadius()+
  //                         " node's new Radius: "+radius+
  //                         " node;s old pivot: "+node.getPivot()+
  //                         " node's new pivot: "+pivot);
        node.setRadius(radius);
      }    
    }
      
    /**
     * Adds an instance to the ball tree. 
     * @param node The root node of the tree.
     * @param inst The instance to add to the tree.
     * @return The new master index array after adding the 
     * instance. 
     * @throws Exception If there is some problem adding the 
     * given instance to the tree. 
     */
    public int[] addInstance(BallNode node, Instance inst) throws Exception {
      
      double leftDist, rightDist;
      
      if (node.m_Left!=null && node.m_Right!=null) { //if node is not a leaf      
        // go further down the tree to look for the leaf the instance should be in
        
        leftDist = m_DistanceFunction.distance(inst, node.m_Left.getPivot(), 
                                      Double.POSITIVE_INFINITY); //instance.value(m_SplitDim);
        rightDist = m_DistanceFunction.distance(inst, node.m_Right.getPivot(), 
                                      Double.POSITIVE_INFINITY); 
        if (leftDist < rightDist) {
          addInstance(node.m_Left, inst);
          // go into right branch to correct instance list boundaries
          processNodesAfterAddInstance(node.m_Right);
        }
        else {
          addInstance(node.m_Right, inst);
        }
        // correct end index of instance list of this node
        node.m_End++;
      }
      else if(node.m_Left!=null || node.m_Right!=null) {
        throw new Exception("Error: Only one leaf of the built ball tree is " +
                            "assigned. Please check code.");
      }
      else { // found the leaf to insert instance
             
        int index = m_Instances.numInstances() - 1;
        
        int instList[] = new int[m_Instances.numInstances()];
        System.arraycopy(m_InstList, 0, instList, 0, node.m_End+1);
        if(node.m_End < m_InstList.length-1)
          System.arraycopy(m_InstList, node.m_End+2, instList, node.m_End+2, m_InstList.length-node.m_End-1);      
        instList[node.m_End+1] = index;
        node.m_End++;
        node.m_NumInstances++;
        m_InstList = instList;
        
        m_Splitter.setInstanceList(m_InstList);
        
        if(node.m_NumInstances > m_MaxInstancesInLeaf) {
          m_Splitter.splitNode(node, m_NumNodes);
          m_NumNodes += 2;
        }
      }
      return m_InstList;
    }
    
    /**
     * Post process method to correct the start and end 
     * indices of BallNodes on the right of the 
     * node where the instance was added.  
     * @param node The node whose m_Start and m_End 
     * need to be updated.
     */
    protected void processNodesAfterAddInstance(BallNode node) {
      //updating start and end indices for the node
      node.m_Start++;
      node.m_End++;    
      //processing child nodes
      if(node.m_Left!=null && node.m_Right!=null) {
        processNodesAfterAddInstance(node.m_Left);
        processNodesAfterAddInstance(node.m_Right);
      }
    }
    
    /**
     * Returns the tip text for this property.
     * 
     * @return 		tip text for this property suitable for
     * 			displaying in the explorer/experimenter gui
     */
    public String ballSplitterTipText() {
      return 
          "The BallSplitter algorithm set that would be used by the TopDown "
        + "BallTree constructor.";
    }
    
    /** 
     * Returns the BallSplitter algorithm set that would be 
     * used by the TopDown BallTree constructor.
     * @return The BallSplitter currently in use.
     */
    public BallSplitter getBallSplitter() {
      return m_Splitter;
    }
    
    /**
     * Sets the ball splitting algorithm to be used by the 
     * TopDown constructor.
     * @param splitter The BallSplitter to use.
     */
    public void setBallSplitter(BallSplitter splitter) {
      m_Splitter = splitter;
    }
    
    /**
     * Returns an enumeration describing the available options.
     * 
     * @return 		an enumeration of all the available options.
     */
    public Enumeration listOptions() {
      Vector<Option> newVector = new Vector<Option>();
  
      newVector.addElement(new Option(
  	"\tBall splitting algorithm to use.",
  	"S", 1, "-S <classname and options>"));
      
      return newVector.elements();
    }
  
    /**
     * Parses a given list of options.
     * 
     <!-- options-start -->
     * Valid options are: <p/>
     * 
     * <pre> -S &lt;classname and options&gt;
     *  Ball splitting algorithm to use.</pre>
     * 
     <!-- options-end --> 
     * 
     * @param options 	the list of options as an array of strings
     * @throws Exception	if an option is not supported
     */
    public void setOptions(String[] options)
      throws Exception {
  
      super.setOptions(options);
      
      String optionString = Utils.getOption('S', options);
      if(optionString.length() != 0) {
        String nnSearchClassSpec[] = Utils.splitOptions(optionString);
        if(nnSearchClassSpec.length == 0) { 
          throw new Exception("Invalid BallSplitter specification string."); 
        }
        String className = nnSearchClassSpec[0];
        nnSearchClassSpec[0] = "";
  
        setBallSplitter( (BallSplitter)
                              Utils.forName( BallSplitter.class, 
                                             className, nnSearchClassSpec) );
      }
      else {
        setBallSplitter(new PointsClosestToFurthestChildren());  
      }
    }
  
    /**
     * Gets the current settings of KDtree.
     * 
     * @return 		an array of strings suitable for passing to setOptions
     */
    public String[] getOptions() {
      Vector<String>	result;
      String[]		options;
      int			i;
      
      result = new Vector<String>();
      
      options = super.getOptions();
      for (i = 0; i < options.length; i++)
        result.add(options[i]);
      
      result.add("-S");
      result.add(m_Splitter.getClass().getName());
  
      return result.toArray(new String[result.size()]);
    }
    
    /**
     * Returns the revision string.
     * 
     * @return		the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5953 $");
    }
  }
  