source: tags/MetisMQIDemo/src/main/java/weka/core/neighboursearch/balltrees/MiddleOutConstructor.java

/*
 *    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.
 */

/*
 * MiddleOutConstructor.java
 * Copyright (C) 2007 University of Waikato, Hamilton, New Zealand
 */

package weka.core.neighboursearch.balltrees;

import weka.core.Instance;
import weka.core.DenseInstance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.Randomizable;
import weka.core.RevisionHandler;
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 java.util.Enumeration;
import java.util.Random;
import java.util.Vector;
import java.util.ArrayList;
import java.util.Iterator;

import java.io.Serializable;

/**
 <!-- globalinfo-start -->
 * The class that builds a BallTree middle out.<br/>
 * <br/>
 * For more information see also:<br/>
 * <br/>
 * Andrew W. Moore: The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data. In: UAI '00: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, San Francisco, CA, USA, 397-405, 2000.<br/>
 * <br/>
 * Ashraf Masood Kibriya (2007). Fast Algorithms for Nearest Neighbour Search. Hamilton, New Zealand.
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- technical-bibtex-start -->
 * BibTeX:
 * <pre>
 * &#64;inproceedings{Moore2000,
 *    address = {San Francisco, CA, USA},
 *    author = {Andrew W. Moore},
 *    booktitle = {UAI '00: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence},
 *    pages = {397-405},
 *    publisher = {Morgan Kaufmann Publishers Inc.},
 *    title = {The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data},
 *    year = {2000}
 * }
 * 
 * &#64;mastersthesis{Kibriya2007,
 *    address = {Hamilton, New Zealand},
 *    author = {Ashraf Masood Kibriya},
 *    school = {Department of Computer Science, School of Computing and Mathematical Sciences, University of Waikato},
 *    title = {Fast Algorithms for Nearest Neighbour Search},
 *    year = {2007}
 * }
 * </pre>
 * <p/>
 <!-- technical-bibtex-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -S &lt;num&gt;
 *  The seed for the random number generator used
 *  in selecting random anchor.
 * (default: 1)</pre>
 * 
 * <pre> -R
 *  Use randomly chosen initial anchors.</pre>
 * 
 <!-- options-end --> 
 * 
 * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
 * @version $Revision: 5987 $
 */
public class MiddleOutConstructor
  extends BallTreeConstructor
  implements Randomizable, TechnicalInformationHandler {

  /** for serialization. */
  private static final long serialVersionUID = -8523314263062524462L;

  /** Seed form random number generator. */
  protected int m_RSeed = 1;
        
  /** 
   * The random number generator for selecting 
   * the first anchor point randomly 
   * (if selecting randomly).
   */
  protected Random rand = new Random(m_RSeed);
 
  /**
   * The radius of the smallest ball enclosing all the data points.
   */
  private double rootRadius = -1;
  
  /** 
   * True if the initial anchor is chosen randomly. False if it is the furthest
   * point from the mean/centroid.
   */
  protected boolean m_RandomInitialAnchor = true;

  /**
   * Creates a new instance of MiddleOutConstructor.
   */
  public MiddleOutConstructor() {
  }

  /**
   * 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 that builds a BallTree middle out.\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;
    TechnicalInformation additional;

    result = new TechnicalInformation(Type.INPROCEEDINGS);
    result.setValue(Field.AUTHOR, "Andrew W. Moore");
    result.setValue(Field.TITLE, "The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data");
    result.setValue(Field.YEAR, "2000");
    result.setValue(Field.BOOKTITLE, "UAI '00: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence");
    result.setValue(Field.PAGES, "397-405");
    result.setValue(Field.PUBLISHER, "Morgan Kaufmann Publishers Inc.");
    result.setValue(Field.ADDRESS, "San Francisco, CA, USA");

    additional = result.add(Type.MASTERSTHESIS);
    additional.setValue(Field.AUTHOR, "Ashraf Masood Kibriya");
    additional.setValue(Field.TITLE, "Fast Algorithms for Nearest Neighbour Search");
    additional.setValue(Field.YEAR, "2007");
    additional.setValue(Field.SCHOOL, "Department of Computer Science, School of Computing and Mathematical Sciences, University of Waikato");
    additional.setValue(Field.ADDRESS, "Hamilton, New Zealand");
    
    return result;
  }

  /**
   * Builds a ball tree middle out. 
   * @return The root node of the tree. 
   * @throws Exception If there is problem building
   * the tree.
   */
  public BallNode buildTree() throws Exception {
    m_NumNodes = m_MaxDepth = m_NumLeaves = 0;
    if(rootRadius == -1) {
      rootRadius = BallNode.calcRadius(m_InstList, m_Instances, 
                                BallNode.calcCentroidPivot(m_InstList, m_Instances),
                                m_DistanceFunction);
    }
    BallNode root = buildTreeMiddleOut(0, m_Instances.numInstances()-1);
    return root;
  }

  /** 
   * Builds a ball tree middle out from the 
   * portion of the master index array given
   * by supplied start and end index.
   * @param startIdx The start of the portion
   * in master index array.
   * @param endIdx the end of the portion in 
   * master index array.
   * @return The root node of the built tree.
   * @throws Exception If there is some 
   * problem building the tree. 
   */
  protected BallNode buildTreeMiddleOut(int startIdx, int endIdx) 
    throws Exception {
        
    Instance pivot;
    double radius;
    Vector<TempNode> anchors;
    int numInsts = endIdx - startIdx + 1;
    int numAnchors = (int) Math.round(Math.sqrt(numInsts));
    
    //create anchor's hierarchy
    if (numAnchors > 1) {
      pivot = BallNode.calcCentroidPivot(startIdx, endIdx, m_InstList,m_Instances);
      radius = BallNode.calcRadius(startIdx, endIdx, m_InstList, m_Instances, 
                                                           pivot, m_DistanceFunction);      
      if(numInsts <= m_MaxInstancesInLeaf || 
         (rootRadius==0 ? true : radius/rootRadius < m_MaxRelLeafRadius)) { //just make a leaf don't make anchors hierarchy 
                BallNode node = new BallNode(startIdx, endIdx, m_NumNodes,pivot, radius);
                return node;
          }
      anchors = new Vector<TempNode>(numAnchors);
      createAnchorsHierarchy(anchors, numAnchors, startIdx, endIdx);

      BallNode node = mergeNodes(anchors, startIdx, endIdx);
      
      buildLeavesMiddleOut(node);
      
      return node;
    }// end anchors hierarchy
    else {
      BallNode node = new BallNode(startIdx, endIdx, m_NumNodes, 
                      (pivot=BallNode.calcCentroidPivot(startIdx, endIdx, 
                                                      m_InstList, m_Instances)), 
                      BallNode.calcRadius(startIdx, endIdx, m_InstList, 
                                          m_Instances, pivot, 
                                          m_DistanceFunction)
                         );
      return node;
    }        
  }
  
  /**
   * Creates an anchors hierarchy from a portion
   * of master index array.
   * 
   * @param anchors The vector for putting the anchors
   * into. 
   * @param numAnchors The number of anchors to create.
   * @param startIdx The start of the portion of master
   * index array.
   * @param endIdx The end of the portion of master 
   * index array.
   * @throws Exception If there is some problem in creating 
   * the hierarchy.
   */
  protected void createAnchorsHierarchy(Vector<TempNode> anchors, final int numAnchors, 
      final int startIdx, final int endIdx) 
    throws Exception {
    
    TempNode anchr1 = m_RandomInitialAnchor ? 
            getRandomAnchor(startIdx, endIdx) : 
            getFurthestFromMeanAnchor(startIdx, endIdx);
                      
    TempNode amax = anchr1; //double maxradius = anchr1.radius;
    TempNode newAnchor;
    Vector<double[]> anchorDistances = new Vector<double[]>(numAnchors-1);
    anchors.add(anchr1);

    //creating anchors
    while(anchors.size() < numAnchors) {
      //create new anchor
      newAnchor = new TempNode();
      newAnchor.points = new MyIdxList();        
      Instance newpivot = m_Instances.instance(((ListNode)amax.points.getFirst()).idx);
      newAnchor.anchor = newpivot;
      newAnchor.idx = ((ListNode)amax.points.getFirst()).idx;

      setInterAnchorDistances(anchors, newAnchor, anchorDistances);
      if(stealPoints(newAnchor, anchors, anchorDistances)) //if points stolen
        newAnchor.radius = ((ListNode)newAnchor.points.getFirst()).distance;
      else
        newAnchor.radius = 0.0;
      anchors.add(newAnchor);

      //find new amax        
      amax = (TempNode)anchors.elementAt(0);
      for(int i=1; i<anchors.size(); i++) {
        newAnchor = (TempNode)anchors.elementAt(i);
        if(newAnchor.radius > amax.radius)
          amax = newAnchor;
      }//end for
    }//end while
  }
  
  /**
   * Applies the middle out build procedure to 
   * the leaves of the tree. The leaf nodes 
   * should be the ones that were created by 
   * createAnchorsHierarchy(). The process
   * continues recursively for the leaves 
   * created for each leaf of the given tree 
   * until for some leaf node <= 
   * m_MaxInstancesInLeaf instances remain
   * in the leaf.
   * 
   * @param node The root of the tree.
   * @throws Exception If there is some problem
   * in building the tree leaves.
   */
  protected void buildLeavesMiddleOut(BallNode node) throws Exception {
    if(node.m_Left!=null && node.m_Right!=null) { //if an internal node
      buildLeavesMiddleOut(node.m_Left);
      buildLeavesMiddleOut(node.m_Right);
    }
    else if(node.m_Left!=null || node.m_Right!=null) {
      throw new Exception("Invalid leaf assignment. Please check code");
    }
    else { //if node is a leaf
      BallNode n2 = buildTreeMiddleOut(node.m_Start, node.m_End);
      if(n2.m_Left!=null && n2.m_Right!=null) {
        node.m_Left = n2.m_Left;
        node.m_Right = n2.m_Right;
        buildLeavesMiddleOut(node); 
        //the stopping condition in buildTreeMiddleOut will stop the recursion,
        //where it won't split a node at all, and we won't recurse here.
      }
      else if(n2.m_Left!=null || n2.m_Right!=null)
        throw new Exception("Invalid leaf assignment. Please check code");
    }
  }

  /**
   * Merges nodes created by createAnchorsHierarchy()
   * into one top node.
   * 
   * @param list List of anchor nodes.
   * @param startIdx The start of the portion of 
   * master index array containing these anchor 
   * nodes. 
   * @param endIdx The end of the portion of master 
   * index array containing these anchor nodes. 
   * @return The top/root node after merging 
   * the given anchor nodes.
   * @throws Exception IF there is some problem in
   * merging.
   */
  protected BallNode mergeNodes(Vector<TempNode> list, int startIdx, int endIdx)
    throws Exception {
    
    for(int i=0; i<list.size(); i++) {
      TempNode n = (TempNode) list.get(i);
      n.anchor = calcPivot(n.points, new MyIdxList(), m_Instances);
      n.radius = calcRadius(n.points, new MyIdxList(), n.anchor, m_Instances);
    }
    double minRadius, tmpRadius; //tmpVolume, minVolume;
    Instance pivot, minPivot=null;
    TempNode parent; int min1=-1, min2=-1;    
    
    while(list.size() > 1) { //main merging loop
      minRadius=Double.POSITIVE_INFINITY;      
      
      for(int i=0; i<list.size(); i++) {
        TempNode first = (TempNode) list.get(i);
        for(int j=i+1; j<list.size(); j++) {
          TempNode second = (TempNode) list.get(j);
          pivot = calcPivot(first, second, m_Instances); 
          tmpRadius = calcRadius(first, second); //calcRadius(first.points, second.points, pivot, m_Instances);    
          if(tmpRadius < minRadius) { //(tmpVolume < minVolume) {
            minRadius = tmpRadius; //minVolume = tmpVolume; 
            minPivot = pivot; 
            min1=i; min2=j; 
            //minInstList = tmpInstList;
          }
        }//end for(j)
      }//end for(i)
      parent = new TempNode();
      parent.left  = (TempNode) list.get(min1);
      parent.right = (TempNode) list.get(min2);
      parent.anchor = minPivot;
      parent.radius = calcRadius(parent.left.points, parent.right.points, minPivot, m_Instances); //minRadius;
      parent.points = parent.left.points.append(parent.left.points, parent.right.points);
      list.remove(min1); list.remove(min2-1);
      list.add(parent);
    }//end while
    TempNode tmpRoot = (TempNode)list.get(list.size()-1);
    
    if((endIdx-startIdx+1)!= tmpRoot.points.length()) {
      throw new Exception("Root nodes instance list is of irregular length. " +
                          "Please check code. Length should " +
                          "be: " + (endIdx-startIdx+1) + 
                          " whereas it is found to be: "+tmpRoot.points.length());
    }
    for(int i=0; i<tmpRoot.points.length(); i++) {
      m_InstList[startIdx+i] = ((ListNode)tmpRoot.points.get(i)).idx;
    }
    
    BallNode node = makeBallTreeNodes(tmpRoot, startIdx, endIdx, 0);
    
    return node;    
  }
  
  /**
   * Makes BallTreeNodes out of TempNodes.
   *  
   * @param node The root TempNode
   * @param startidx The start of the portion of 
   * master index array the TempNodes 
   * are made from. 
   * @param endidx The end of the portion of 
   * master index array the TempNodes are 
   * made from. 
   * @param depth The depth in the tree where 
   * this root TempNode is made (needed when 
   * leaves of a tree deeper down are built 
   * middle out).
   * @return The root BallTreeNode.
   */
  protected BallNode makeBallTreeNodes(TempNode node, int startidx, 
      int endidx, int depth) {
    BallNode ball=null;
    
    if(node.left!=null && node.right!=null) { //make an internal node
      ball = new BallNode(
      startidx, endidx, m_NumNodes, 
      node.anchor,
      node.radius
      );
      m_NumNodes += 1;
      ball.m_Left = makeBallTreeNodes(node.left, startidx, startidx+node.left.points.length()-1, depth+1);
      ball.m_Right= makeBallTreeNodes(node.right, startidx+node.left.points.length(), endidx, depth+1);
      m_MaxDepth++;
    }
    else { //make a leaf node
      ball = new BallNode(startidx, endidx, m_NumNodes,       
      node.anchor, 
      node.radius 
                         );
      m_NumNodes += 1;      
      m_NumLeaves += 1;
    }
    return ball;
  }
    
  /**
   * Returns an anchor point which is furthest from the
   * mean point for a given set of points (instances) 
   * (The anchor instance is chosen from the given
   * set of points).
   * 
   * @param startIdx The start index of the points
   * for which anchor point is required.
   * @param endIdx The end index of the points for
   * which anchor point is required.
   * @return The furthest point/instance from the mean 
   * of given set of points.
   */
  protected TempNode getFurthestFromMeanAnchor(int startIdx, int endIdx) {
    TempNode anchor = new TempNode();
    Instance centroid = BallNode.calcCentroidPivot(startIdx, endIdx, m_InstList, 
                                                   m_Instances);
    Instance temp;
    double tmpr;
    anchor.radius = Double.NEGATIVE_INFINITY;
    for(int i=startIdx; i<=endIdx; i++) {
      temp = m_Instances.instance(m_InstList[i]);
      tmpr = m_DistanceFunction.distance(centroid, temp);
      if(tmpr > anchor.radius) {
        anchor.idx = m_InstList[i];
        anchor.anchor = temp;
        anchor.radius = tmpr;
      }
    }
    
    setPoints(anchor, startIdx, endIdx, m_InstList);
    return anchor;
  }
  
  /** 
   * Returns a random anchor point/instance from a 
   * given set of points/instances.
   * 
   * @param startIdx The start index of the points
   * for which anchor is required.
   * @param endIdx The end index of the points for
   * which anchor is required.
   * @return The random anchor point/instance
   * for the given set of 
   */
  protected TempNode getRandomAnchor(int startIdx, int endIdx) {
    TempNode anchr1 = new TempNode();
    anchr1.idx = m_InstList[startIdx+rand.nextInt((endIdx-startIdx+1))];
    anchr1.anchor = m_Instances.instance(anchr1.idx);
    setPoints(anchr1, startIdx, endIdx, m_InstList);
    anchr1.radius = ((ListNode)anchr1.points.getFirst()).distance;
    
    return anchr1;
  }
  
  /**
   * Sets the points of an anchor node. It takes the
   * indices of points from the given portion of 
   * an index array and stores those indices, together
   * with their distances to the given anchor node, 
   * in the point index list of the anchor node.
   *  
   * @param node The node in which the points are
   * needed to be set.
   * @param startIdx The start of the portion in 
   * the given index array (the master index
   * array).
   * @param endIdx The end of the portion in the
   * given index array. 
   * @param indices The index array.
   */
  public void setPoints(TempNode node, int startIdx, int endIdx, int[] indices) {
    node.points = new MyIdxList();    
    Instance temp; double dist;
    for(int i=startIdx; i<=endIdx; i++) {
      temp = m_Instances.instance(indices[i]);
      dist = m_DistanceFunction.distance(node.anchor, temp);
      node.points.insertReverseSorted(indices[i], dist);
    }
  }

  /**
   * Sets the distances of a supplied new
   * anchor to all the rest of the 
   * previous anchor points.
   * @param anchors The old anchor points.
   * @param newAnchor The new anchor point.
   * @param anchorDistances The vector to
   * store the distances of newAnchor to 
   * each of the old anchors.
   * @throws Exception If there is some 
   * problem in calculating the distances.
   */
  public void setInterAnchorDistances(Vector<TempNode> anchors, TempNode newAnchor,
                                      Vector<double[]> anchorDistances) throws Exception {
    double[] distArray = new double[anchors.size()];
    
    for(int i=0; i<anchors.size(); i++) {
      Instance anchr = ((TempNode)anchors.elementAt(i)).anchor;
      distArray[i] = m_DistanceFunction.distance(anchr, newAnchor.anchor);
    }
    anchorDistances.add(distArray);
  }
  
  /**
   * Removes points from old anchors that
   * are nearer to the given new anchor and
   * adds them to the list of points of the
   * new anchor. 
   * @param newAnchor The new anchor.
   * @param anchors The old anchors.
   * @param anchorDistances The distances
   * of new anchor to each of the old 
   * anchors.
   * @return true if any points are removed
   * from the old anchors
   */
  public boolean stealPoints(TempNode newAnchor, Vector anchors, 
                          Vector anchorDistances) {
                            
    int maxIdx = -1; 
    double maxDist = Double.NEGATIVE_INFINITY;
    double[] distArray = (double[])anchorDistances.lastElement();
    
    for(int i=0; i<distArray.length; i++)
      if(maxDist < distArray[i]) {
        maxDist = distArray[i]; maxIdx = i;
      }
    
    boolean anyPointsStolen=false, pointsStolen=false;
    TempNode anchorI;
    double newDist, distI, interAnchMidDist;
    Instance newAnchInst = newAnchor.anchor, anchIInst;
    for(int i=0; i<anchors.size(); i++) {
      anchorI = (TempNode)anchors.elementAt(i);
      anchIInst = anchorI.anchor;
      
      pointsStolen = false;
      interAnchMidDist = m_DistanceFunction.distance(newAnchInst, anchIInst)/2D;
      for(int j=0; j<anchorI.points.length(); j++) {
        ListNode tmp = (ListNode) anchorI.points.get(j);
        //break if we reach a point whose distance is less than the midpoint
        //of inter anchor distance
        if(tmp.distance < interAnchMidDist)
          break;
        //else test if this point can be stolen by the new anchor
        newDist = m_DistanceFunction.distance(newAnchInst, 
                                              m_Instances.instance(tmp.idx));
        distI = tmp.distance;
        if(newDist < distI) {
          newAnchor.points.insertReverseSorted(tmp.idx, newDist);
          anchorI.points.remove(j);
          anyPointsStolen=pointsStolen=true;
        }
      }
      if (pointsStolen)
        anchorI.radius = ((ListNode)anchorI.points.getFirst()).distance;
    }//end for
    return anyPointsStolen;
  }//end stealPoints()

  /**
  /**
   * Calculates the centroid pivot of a node based on its
   * two child nodes (if merging two nodes).
   * @param node1 The first child.
   * @param node2 The second child.
   * @param insts The set of instances on which the tree 
   * is being built (as dataset header information is 
   * required). 
   * @return The centroid pivot of a node. 
   */
  public Instance calcPivot(TempNode node1, TempNode node2, Instances insts) {
    int classIdx = m_Instances.classIndex();
    double[] attrVals = new double[insts.numAttributes()];
    Instance temp;
    double anchr1Ratio = (double)node1.points.length() / 
                         (node1.points.length()+node2.points.length()),
           anchr2Ratio = (double)node2.points.length() / 
                         (node1.points.length()+node2.points.length());                         ;
    for(int k=0; k<node1.anchor.numValues(); k++) {
      if(node1.anchor.index(k)==classIdx)
        continue;
      attrVals[k] += node1.anchor.valueSparse(k)*anchr1Ratio;
    }
    for(int k=0; k<node2.anchor.numValues(); k++) {
      if(node2.anchor.index(k)==classIdx)
        continue;
      attrVals[k] += node2.anchor.valueSparse(k)*anchr2Ratio;
    }
    temp = new DenseInstance(1.0, attrVals);
    return temp;
  }
  
  /**
   * Calculates the centroid pivot of a node based on 
   * the list of points that it  contains (tbe two 
   * lists of its children are provided).
   * @param list1 The point index list of first child.
   * @param list2 The point index list of second 
   * child.
   * @param insts The insts object on which the tree 
   * is being built (for header information). 
   * @return The centroid pivot of the node. 
   */
  public Instance calcPivot(MyIdxList list1, MyIdxList list2, Instances insts) {
    int classIdx = m_Instances.classIndex();
    double[] attrVals = new double[insts.numAttributes()];
    
    Instance temp;
    for(int i=0; i<list1.length(); i++) {
      temp = insts.instance(((ListNode)list1.get(i)).idx);
      for(int k=0; k<temp.numValues(); k++) {
        if(temp.index(k)==classIdx)
          continue;
        attrVals[k] += temp.valueSparse(k);
      }
    }
    for(int j=0; j<list2.length(); j++) {
      temp = insts.instance(((ListNode)list2.get(j)).idx);
      for(int k=0; k<temp.numValues(); k++) {
        if(temp.index(k)==classIdx)
          continue;
        attrVals[k] += temp.valueSparse(k);
      }
    }
    for(int j=0, numInsts=list1.length()+list2.length(); 
        j < attrVals.length; j++) {
      attrVals[j] /= numInsts;
    }
    temp = new DenseInstance(1.0, attrVals);
    return temp;
  }
  
  /** 
   * Calculates the radius of a node based on its two 
   * child nodes (if merging two nodes).
   * @param n1 The first child of the node.
   * @param n2 The second child of the node.
   * @return The radius of the node. 
   * @throws Exception
   */
  public double calcRadius(TempNode n1, TempNode n2) {
          Instance p1 = n1.anchor, p2 = n2.anchor;
          double radius = n1.radius + m_DistanceFunction.distance(p1, p2) + n2.radius;
          return radius/2;
  }
  
  /**
   * Calculates the radius of a node based on the
   * list of points that it contains (the two lists of 
   * its children are provided). 
   * @param list1 The point index list of first child.
   * @param list2 The point index list of second child.
   * @param pivot The centre/pivot of the node.
   * @param insts The instances on which the tree is 
   * being built (for header info). 
   * @return The radius of the node. 
   */
  public double calcRadius(MyIdxList list1, MyIdxList list2, 
                           Instance pivot, Instances insts) {
    double radius = Double.NEGATIVE_INFINITY;
    
    for(int i=0; i<list1.length(); i++) {
      double dist = m_DistanceFunction.distance(pivot, 
                                              insts.instance(((ListNode)list1.get(i)).idx));
      if(dist>radius)
        radius = dist;
    }
    for(int j=0; j<list2.length(); j++) {
      double dist = m_DistanceFunction.distance(pivot, 
                                              insts.instance(((ListNode)list2.get(j)).idx));
      if(dist>radius)
        radius = dist;
    }
    return radius;
  }
  
  /**
   * Adds an instance to the tree. This implementation of 
   * MiddleOutConstructor doesn't support addition of 
   * instances to already built tree, hence it always
   * throws an exception.
   * @param node The root of the tree to which the 
   * instance is to be added.
   * @param inst The instance to add to the tree.
   * @return The updated master index array after 
   * adding the instance.
   * @throws Exception Always as this implementation of
   * MiddleOutConstructor doesn't support addition of
   * instances after batch construction of the tree.
   */
  public int[] addInstance(BallNode node, Instance inst) throws Exception {
    throw new Exception("Addition of instances after the tree is built, not " +
                        "possible with MiddleOutConstructor.");
  }

  /**
   * Sets the maximum number of instances allowed in a leaf.
   * @param num The maximum number of instances allowed in 
   * a leaf.
   * @throws Exception If the num is < 2, as the method 
   * cannot work for < 2 instances. 
   */ 
  public void setMaxInstancesInLeaf(int num) throws Exception {
    if(num<2)
      throw new Exception("The maximum number of instances in a leaf for " +
                          "using MiddleOutConstructor must be >=2.");
    super.setMaxInstancesInLeaf(num);
  }  

  /**
   * Sets the instances on which the tree is to be built.
   * @param insts The instances on which to build the 
   * ball tree.
   */
  public void setInstances(Instances insts) {
    super.setInstances(insts);
    rootRadius = -1; //this needs to be re-calculated by buildTree()
  }
  
  /**
   * Sets the master index array that points to 
   * instances in m_Instances, so that only this array
   * is manipulated, and m_Instances is left 
   * untouched.
   * @param instList The master index array.
   */
  public void setInstanceList(int[] instList) {
    super.setInstanceList(instList); 
    rootRadius = -1; //this needs to be re-calculated by buildTree()
  }
  
  /**
   * Returns the tip text for this property.
   * 
   * @return            tip text for this property suitable for
   *                    displaying in the explorer/experimenter gui
   */
  public String initialAnchorRandomTipText() {
    return "Whether the initial anchor is chosen randomly.";
  }
  
  /** 
   * Gets whether if the initial anchor is chosen randomly.
   * @return true if the initial anchor is a random one. 
   */
  public boolean isInitialAnchorRandom() {
    return m_RandomInitialAnchor;
  }
  
  /** 
   * Sets whether if the initial anchor is chosen randomly. If not 
   * then if it is the furthest point from the mean/centroid.
   * @param randomInitialAnchor Should be true if the first 
   * anchor is to be chosen randomly.
   */
  public void setInitialAnchorRandom(boolean randomInitialAnchor) {
    m_RandomInitialAnchor = randomInitialAnchor;
  }
  
  /**
   * Returns the tip text for this property.
   * 
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String seedTipText() {
    return "The seed value for the random number generator.";
  }

  /**
   * Returns the seed for random number generator.
   * @return The random number seed.
   */
  public int getSeed() {
    return m_RSeed;
  }
  
  /**
   * Sets the seed for random number generator 
   * (that is used for selecting the first anchor 
   * point randomly).
   * @param seed The seed. 
   */
  public void setSeed(int seed) {
    m_RSeed = seed;
  }
  
  /**
   * 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(
        "\tThe seed for the random number generator used\n"
        + "\tin selecting random anchor.\n"
        + "(default: 1)", 
        "S", 1, "-S <num>"));
    
    newVector.addElement(new Option(
        "\tUse randomly chosen initial anchors.",
        "R", 0, "-R"));
    
    return newVector.elements();
  }

  /**
   * Parses a given list of options.
   * 
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -S &lt;num&gt;
   *  The seed for the random number generator used
   *  in selecting random anchor.
   * (default: 1)</pre>
   * 
   * <pre> -R
   *  Use randomly chosen initial anchors.</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 temp = Utils.getOption('S', options);
    if(temp.length()>0) {
      setSeed(Integer.parseInt(temp));
    }
    else {
      setSeed(1);
    }
    
    setInitialAnchorRandom(Utils.getFlag('R', options));
  }

  /**
   * Gets the current settings of this BallTree MiddleOutConstructor.
   * 
   * @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("" + getSeed());
    
    if(isInitialAnchorRandom())
      result.add("-R");
    
    return result.toArray(new String[result.size()]);
  }
  
  /**
   * Checks whether if the points in an index list
   * are in some specified of the master index array. 
   * @param list The point list.
   * @param startidx The start of the portion in 
   * master index array. 
   * @param endidx The end of the portion in master
   * index array.
   * @throws Exception If some point in the point
   * list is not in the specified portion of master
   * index array. 
   */
  public void checkIndicesList(MyIdxList list, int startidx, int endidx) 
    throws Exception {
    
    boolean found;
    ListNode node;
    for(int i=0; i<list.size(); i++) {
      node = (ListNode)list.get(i);
      found=false;
      for(int j=startidx; j<=endidx; j++) {
        if(node.idx==m_InstList[j]) {
          found=true; 
          break;
        }
      }
      if(!found)
        throw new Exception("Error: Element "+node.idx+" of the list not in " +
                            "the array." +
                            "\nArray: "+printInsts(startidx, endidx)+
                            "\nList: "+printList(list));
    }
  }
  
  /**
   * For printing indices in some given portion
   * of the master index array. 
   * @param startIdx The start of the portion 
   * in master index array. 
   * @param endIdx The end of the portion in 
   * master index array.
   * @return The string containing the indices
   * in specified portion of the master index 
   * array. 
   */
  public String printInsts(int startIdx, int endIdx) {
    StringBuffer bf = new StringBuffer();
    try {
      bf.append("i: ");
      for (int i = startIdx; i <= endIdx; i++) {
        if (i == startIdx)
          bf.append("" + m_InstList[i]);
        else
          bf.append(", " + m_InstList[i]);
      }
    } catch (Exception ex) {
      ex.printStackTrace();
    }
    return bf.toString();
  }
  
  /**
   * For printing indices in a given point list.
   * @param points The point list.
   * @return String containing indices of the
   * points in the point list.
   */
  public String printList(MyIdxList points) {
    if(points==null || points.length()==0) return "";
    StringBuffer bf = new StringBuffer();
    try {
      ListNode temp;
      for(int i=0; i<points.size(); i++) {
        temp = (ListNode) points.get(i);
        if(i==0)
          bf.append(""+temp.idx);
        else
          bf.append(", "+temp.idx);
      }
    } catch(Exception ex) { ex.printStackTrace(); }
    return bf.toString();
  }
  
  /**
   * Returns the revision string.
   * 
   * @return            the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 5987 $");
  }
  
  /** 
   * Temp class to represent either a leaf node or an internal node. Should only 
   * have two children (could be the case one child is an instance and the 
   * other another node). Primarily used for anchor nodes. It stores the
   * points contained in a node together with their distances to the 
   * node's centre/anchor point.
   * 
   * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
   * @version $Revision: 5987 $
   */
  protected class TempNode
    implements RevisionHandler {
    
    /** The anchor point of the node. */
    Instance anchor;
    
    /** The index of the anchor point. */
    int idx;
    
    /** The radius of the node. */
    double radius;
    
    /** The list of points inside the node. */
    MyIdxList points;
    
    /** Node's left child. */
    TempNode left;

    /** Node's right child. */
    TempNode right;
    
    /**
     * Returns a string represention of the node.
     * @return The string representation of the 
     * node.
     */
    public String toString() {
      if(points==null || points.length()==0) return idx+"";
      StringBuffer bf = new StringBuffer();
      try {
        bf.append(idx+" p: ");
        ListNode temp; 
        for(int i=0; i<points.size(); i++) {
          temp = (ListNode) points.get(i);
          if(i==0)
            bf.append(""+temp.idx);
          else
            bf.append(", "+temp.idx);
        }
      } catch(Exception ex) { ex.printStackTrace(); }
      return bf.toString();
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5987 $");
    }
  }

  /**
   * An element of MyIdxList. It stores a points index, and 
   * its distance to some specific point (usually a node's
   * anchor point). 
   * 
   * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
   * @version $Revision: 5987 $
   */
  protected class ListNode
    implements RevisionHandler {
    
    /** The index of the point. */
    int idx = -1;
    
    /** The distance of the point to the anchor.*/
    double distance = Double.NEGATIVE_INFINITY;
    
    /**
     * Constructor. 
     * @param i The point's index. 
     * @param d The point's distance to the 
     * anchor.
     */
    public ListNode(int i, double d) {
      idx = i;
      distance = d;
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5987 $");
    }
  }
  
  /**
   * Class implementing a list. It stores indices of 
   * instances/points, together with their distances to a nodes
   * centre/pivot/anchor, in a (reverse sorted) list.  
   * 
   * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
   * @version $Revision: 5987 $
   */
  protected class MyIdxList implements Serializable, RevisionHandler {

    /** for serialization. */
    private static final long serialVersionUID = -2283869109722934927L;    
    
    /** The array list backing this list */
    protected ArrayList<ListNode> m_List;
    
    /**
     * Constructor.
     */
    public MyIdxList() {
      m_List = new ArrayList<ListNode>();
    }

    /**
     * Constructor for given capacity.
     */
    public MyIdxList(int capacity) {
      m_List = new ArrayList<ListNode>(capacity);
    }

    /**
     * Returns the first element in the list.
     * @return The list's first element.
     */
    public ListNode getFirst() {
      return m_List.get(0);
    }
    
    /**
     * Inserts an element in reverse sorted order in 
     * the list.
     * @param idx The index of the point to insert.
     * @param distance The distance of the point to
     * a node's anchor (this would be used to 
     * determine the sort order).
     */
    public void insertReverseSorted(final int idx, final double distance) {

      int i=0;
      for (ListNode temp : m_List) {
        if(temp.distance < distance)
          break;
        i++;
      }
      m_List.add(i, new ListNode(idx, distance));
    }
    
    /**
     * Returns an element at the specified index in 
     * the list. 
     * @param index The index of the element in the 
     * list.
     * @return The element at the given index.
     */
    public ListNode get(int index) {
      return m_List.get(index);
    }
    
    /** 
     * Removes an element at the specified index 
     * from the list.
     * @param index The index of the element
     * in the list to remove.
     */
    public void remove(int index) {
      m_List.remove(index);
    }
    
    /**
     * Returns the size of the list.
     * @return The size of the list.
     */
    public int length() {
      return m_List.size();
    }
    
    /**
     * Returns the size of the list.
     * @return The size of the list.
     */
    public int size() {
      return m_List.size();
    }
    
    /**
     * Appends one list at the end of the other. 
     * @param list1 The list to which the other
     * list would be appended.
     * @param list2 The list to append to the 
     * other list.
     * @return The new list with list2 appended 
     * to list1.
     */
    public MyIdxList append(MyIdxList list1, MyIdxList list2) {
      MyIdxList temp = new MyIdxList(list1.size()+list2.size());
      temp.m_List.addAll(list1.m_List);
      temp.m_List.addAll(list2.m_List);
      return temp;
    }
    
    /**
     * Checks the sorting of a list.
     * @param list The list whose sorting is
     * to be checked.
     * @throws Exception If the list is not
     * in (reverse) sorted order.
     */
    public void checkSorting(MyIdxList list) throws Exception {
      Iterator<ListNode> en = m_List.iterator();
      ListNode first=null, second=null;
      while(en.hasNext()) {
        if(first==null)
          first = (ListNode) en.next();
        else {
          second = (ListNode)en.next();
          if(first.distance < second.distance)
            throw new Exception("List not sorted correctly." +
                                " first.distance: " + first.distance +
                                " second.distance: " + second.distance +
                                " Please check code.");            
        }
      }
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5987 $");
    }
  }
}