nodebinarytree.java

Java数据结构开发包

	return new PreOrderIterator(this);
    }


  /** 
   * Takes O(N) time from the need to iterate through the tree during 
   * snapshot, where N is the number of elements in the tree
   * @return an iterator over the container's elements in preorder
   */
  public ObjectIterator elements() {
    PositionIterator pi = new PreOrderIterator(this);
    Object elements[] = new Object[size()];
    int elt = 0;
    while (pi.hasNext())
      elements[elt++] = pi.nextPosition().element();
    return new ArrayObjectIterator(elements);
  }


    /** 
     * O(1) time
     */
    public Object replaceElement (Accessor p, Object newElement) throws
    InvalidAccessorException {
	NBTNode toReplaceAt = checkPosition(p);
	return toReplaceAt.replaceElement (newElement);
    }
    

    /**
     *--------------------------------------------------------
     * From interface [Inspectable]Container
     *--------------------------------------------------------
     */

  /** 
     * O(1) time
     */
    public Container newContainer() {
        return new NodeBinaryTree();
    }

    /** 
     * O(1) time
     * @return Number of elements in the container, where each occurrence
     * of a duplicated element adds 1 to the size() of the container.
     */
    public int size() {
      return _size;
    }

    /** 
      * Overridden from AbstractPositionalContainer to be O(1) time.
     * Will always be false under the current definition of the
     * BinaryTree, since a BT is initialized with one external element.
     */
    public boolean isEmpty() {
        return false;
    }

  /**
    * O(1) time
    */
  public boolean contains(Accessor a){
    NBTNode nbtn = null;
    try{
      nbtn = (NBTNode) a;
      return (nbtn.container() == this);
    }
    catch(ClassCastException e){
      return false;
    }
    catch(NullPointerException e){
      throw new InvalidAccessorException("Null position cannot be contained");
    }
  }
  
  public String toString(){

    return ToString.stringfor(this);
  }

    //--------------------------------------------------
    // rest of class is utility methods

  /**
    * Used for resetting the tree to an empty tree after a link
    * or replaceSubtree operation.
    * This method is protected, so other trees can instruct
    * this tree to do so after a link or replaceSubtree operation
    * O(1) time
    */
  protected void resetToEmpty(){
      _supernode = new NBTSuperNode (this, null);
      NBTNode root = new NBTNode (_supernode, (Object)null);
      _size=1;
      _supernode.setRoot (root);
      root.setContainer(this);
  }

  /**
    * Casts the accessor passed in to the appropriate node class
    * for this container; also checks if it is null.
    * Also checks if it belongs to this container.
    *
    * This method is protected to allow it to be overridden to check
    * for container in a different fashion
    * 
    * @return The casted node
    * @param a The accessor to cast
    */
    protected NBTNode checkPosition (Accessor a) throws
    InvalidAccessorException {
	if (a==null) throw new InvalidAccessorException 
			 ("null position");

	if ( ! (a instanceof NBTNode) ) throw new InvalidAccessorException
					  ("position of wrong class: " + a.getClass());

	NBTNode n = (NBTNode) a;

	if (!(n.container()==this))
	  throw new InvalidAccessorException("A different container holds this NBTNode!");

	return n;
    }


  // -------------------------------------------------
  // two nested classes, for the nodes of the tree

  /**
   * This is the class for all user-visible nodes
   * It contains links for its parent, children, and element.
   * It determines its container by asking its parent; the
   * supernode will be at the end of a chain of parents, and it
   * will know. 
   * All methods must be protected so subclasses can override them
   */   
  protected static class NBTNode extends HashtableDecorable
    implements Position {

    /**
     * The parent of this node; never null while position is in tree
     * may be a supernode.
     * @serial
     */
    private NBTNode _parent; 

    /**
     * This node's left child. If this node is external, _left == null
     * @serial
     */
    private NBTNode _left;
    
    /**
     * This node's right child. If this node is external, _right== null
     * @serial
     */ 
    private NBTNode _right;
    
    /**
     * This node's container
     * @serial
     */ 
    private NodeBinaryTree _container;

    /**
     * This node's element. May be null.
     * @serial
     */ 
    private Object _element;
    
    // methods of Position interface
    
    /**
     * O(1) time
     */
    public Object element() {
      return _element;
    }

    /**
     * O(1) time
     * @return  this node's container.
     */
    protected NodeBinaryTree container() {
      return _container;
    }
    
    /**
     * O(1) time
     * @return  this node's parent.
     */
    protected NBTNode parent() { return _parent; }
    
    /**
     * O(1) time
     * @return  this node's left child.
     */
    protected NBTNode left() { return _left; }
    
    /**
     * O(1) time
     * @return this node's right child.
     */
    protected NBTNode right() { return _right; }
    
    /**
     * O(1) time
     * @param child of my children
     * @return  my other child
     * (asserts if the parameter isn't my child)
     */
    protected NBTNode otherChild (NBTNode child) {
      assert _left != null;
      if (child==_left) return _right;
      if (child==_right) return _left;
      assert false : "sibling( node that isn't my child )";
      return null; // compiler isn't quite that smart
    }


    /**
     * O(1) time
     * @return Whether or not this node is internal
     */
    protected boolean isInternal() { return _left != null; }

    /**
     * O(1) time
     * Sets the parameter node as this node's left child
     * @param x node
     */
    protected void setLeft (NBTNode x) { _left = x; }

    /**
     * O(1) time
     * Sets the parameter node as this node's right child
     * @param x node
     */
    protected void setRight (NBTNode x) { _right = x; }

    /**
     * O(1) time
     * Sets the parameter node as this node's parent
     * @param x node
     */
    protected void setParent (NBTNode x) { _parent = x; }

    /**
     * O(1) time
     * Sets the parameter container as this node's container
     */
    protected void setContainer (NodeBinaryTree x) { _container = x; }
	
    /**
     * O(1) time
     * @return whether or not this node is its parent's left child
     */
    protected boolean isLeftChild(){
      if (_parent.isSuperNode())
	return false; // I'm the root!
      if (_parent.left() == this)
	return true;//I'm the left child!
      return false;//I'm the right child!
    }

    /**	
     * O(1) time
     * Makes this node uncontained
     */
    protected void makeUncontained() {
      _container = null; 
      _parent = null; 
      _left = _right = null;
    }

    /**
     * make a new external node
     */
    protected NBTNode (NBTNode parent, Object element) {
      _parent = parent;
      _element = element;
      _left = _right = null;
    }

    /**	
     * O(1) time
     * Expands this node into an internal node
     * Asserts if this node is external
     */
    protected void expand() {
      assert !isInternal();
      _left = new NBTNode (this, (Object)null);
      _left.setContainer(_container);
      _right = new NBTNode (this, (Object)null);
      _right.setContainer(_container);
    }

    /**	
     * O(1) time
     * This method removes this node and its parent, replacing
     * its parent with my sibling
     *
     * This is the asymmetric opposite of expand.
     */
    protected void removeSelfAndAbove() { // asymmetric opposite of expand()
      assert _parent!=null : "removeSelfAndAbove on invalid node";
      assert _left==null : "removeSelfAndAbove() on non-leaf";
      NBTNode gp = _parent.parent();
      NBTNode sib = _parent.otherChild (this);
      gp.setChild (_parent, sib);
      sib.setParent(gp);
      _parent.makeUncontained();
      this.makeUncontained();
    }

    /**	
     * O(1) time
     * Replaces one of my children with a new node
     * protected to allow SuperNode to override it
     * @param currchild My current child
     * @param newchild The node to replace it with
     */
    protected void setChild (NBTNode currchild, NBTNode newchild) {
      if (_left==currchild) {
	_left = newchild;
      }
      else if (_right==currchild) {
	_right = newchild;
      }
      else assert false : "Asked to setChild on not-my-child";
    }


    /**	
     * O(1) time
     * Replaces me with a new node, as far as my parent is concerned
     * protected so restructurable trees can use it
     * @param newSubtree the node to replace me with
     */
    protected void replaceSelf (NBTNode newSubtree) {
      _parent.setChild (this, newSubtree);
      newSubtree.setParent (_parent);
      _parent = null; 
    }


    /**	
     * O(1) time
     * Replaces my element, returning the old element
     * @param newElement my new element
     * @return The element I used to contain
     */
    protected Object replaceElement (Object newElement) {
      Object toReturn = _element;
      _element = newElement;
      return toReturn;	  
    }
	
    /**
     * Used to determine if this node is the super node 
     */
    protected boolean isSuperNode(){
      return false;
    }

    public String toString(){
      return ToString.stringfor(this);
    }
  } 

  
  /**
   * This is the supernode.
   * There is one instance per tree, useful mainly so that container() calls
   * can recur polymorphically up the tree
   * Protected so subclasses can access it
   */
  protected static class NBTSuperNode extends NBTNode {
    
    /**
     * The tree that contains me
     * @serial
     */
    private NodeBinaryTree _tree;
    
    /**
     * That tree's root
     * @serial
     */
    private NBTNode _root;
    
    /**
     * Constructs the super node with its tree and root
     */
    protected NBTSuperNode (NodeBinaryTree t, NBTNode root) {
      super (null, (Object)null);
      _tree = t;
      _root = root;
    }
    
    /**
     * O(1) time
     * Sets this node's root
     * @param root The new root
     */ 
    protected void setRoot (NBTNode root) { 
      _root = root;
    }
    
    /**
     * O(1) time
     * Sets this node's root; any other use of this method is invalid
     * @param currchild The node to replace; hopefully the root
     * @param newchild The new root
     */ 
    protected void setChild (NBTNode currchild, NBTNode newchild) {
      assert _root==currchild;
      _root = newchild;
    }
    
    /**
     * @return this node's container
     */
    protected NodeBinaryTree container() {
      assert false; return null;
    }
    /**
     * Should never be called
     */
    public Object element() { assert false; return null; }
    /**
     * Should never be called
     */
    protected boolean isValid() { assert false; return false; }
    /**
     * Should never be called
     */
    protected NBTNode parent() { assert false; return null; }
    /**
     * Should never be called
     */
    protected NBTNode left() { assert false; return null; }
    /**
     * Should never be called
     */
    protected NBTNode right() { assert false; return null; }
    /**
     * Should never be called
     */
    protected NBTNode otherChild(NBTNode child) {
      assert false; return null;
    }
    /**
     * Should never be called
     */
    protected boolean isInternal() { assert false; return false; }
    /**
     * Should never be called
     */
    protected void setLeft() { assert false; }
    /**
     * Should never be called
     */
    protected void setRight() { assert false; }
    /**
     * Should never be called
     */
    protected void setParent() { assert false; }
    /**
     * Should never be called
     */
    protected void makeUncontained() { assert false; }
    /**
     * Should never be called
     */
    protected void expand()  { assert false; }
    /**
     * Should never be called
     */
    protected void removeSelfAndAbove() { assert false; }
    /**
     * Should never be called
     */
    protected void replaceSelf(NBTNode x) { assert false; }
    /**
     * Should never be called
     */
    protected void swapWithNode (NBTNode x) { assert false; }
    /**
     * Should never be called
     */
    protected Object replaceElement (Object x) {
      assert false; return null;
    }
    /**
     * Used to determine if this node is the super node (overridden)
     */
    protected boolean isSuperNode(){
      return true;
    }
  }
  // class NBTSuperNode
  
  // end of nested classes
  // -------------------------------------------------


}