middleoutconstructor.java

矩阵的QR分解算法

   */
  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 newVector = new Vector();
    
    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.elementAt(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.elementAt(i);
        if(i==0)
          bf.append(""+temp.idx);
        else
          bf.append(", "+temp.idx);
      }
    } catch(Exception ex) { ex.printStackTrace(); }
    return bf.toString();
  }
  
  /** 
   * 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: 1.1 $
   */
  protected class TempNode {
    
    /** 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.elementAt(i);
          if(i==0)
            bf.append(""+temp.idx);
          else
            bf.append(", "+temp.idx);
        }
      } catch(Exception ex) { ex.printStackTrace(); }
      return bf.toString();
    }
  }

  /**
   * 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: 1.1 $
   */
  protected class ListNode {
    
    /** 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;
    }
  }
  
  /**
   * 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: 1.1 $
   */
  protected class MyIdxList
    extends FastVector {
    
    /** for serialization. */
    private static final long serialVersionUID = -2283869109722934927L;    
    
    /** Constructor. */
    public MyIdxList() {
      super();
    }
    
    /**
     * Constructor.  
     * @param size The initial capacity of the list. 
     */
    public MyIdxList(int size) {
      super(size);
    }
    
    /**
     * Returns the first element in the list.
     * @return The list's first element.
     */
    public ListNode getFirst() {
      return (ListNode) this.elementAt(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) {
      java.util.Enumeration en = this.elements();
      ListNode temp; int i=0;
      while(en.hasMoreElements()) {
        temp = (ListNode) en.nextElement();
        if(temp.distance < distance)
          break;
        i++;
      }
      this.insertElementAt(new ListNode(idx, distance), i);
    }
    
    /**
     * 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 (ListNode) this.elementAt(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) {
      this.removeElementAt(index);
    }
    
    /**
     * Returns the size of the list.
     * @return The size of the list.
     */
    public int length() {
      return super.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.appendElements(list1);
      temp.appendElements(list2);
      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 {
      java.util.Enumeration en = list.elements();
      ListNode first=null, second=null;
      while(en.hasMoreElements()) {
        if(first==null)
          first = (ListNode) en.nextElement();
        else {
          second = (ListNode)en.nextElement();
          if(first.distance < second.distance)
            throw new Exception("List not sorted correctly." +
                                " first.distance: " + first.distance +
                                " second.distance: " + second.distance +
                                " Please check code.");            
        }
      }
    }
  }
}