Java 类weka.core.neighboursearch.balltrees.BallNode 实例源码

/**
   * 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);
    }    
  }

/**
 * 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);
  }
}

/**
 * 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;
}