nodebinarytree.java

Java数据结构开发包

/*
  Copyright (c) 1999, 2000 Brown University, Providence, RI
  
                            All Rights Reserved
  
  Permission to use, copy, modify, and distribute this software and its
  documentation for any purpose other than its incorporation into a
  commercial product is hereby granted without fee, provided that the
  above copyright notice appear in all copies and that both that
  copyright notice and this permission notice appear in supporting
  documentation, and that the name of Brown University not be used in
  advertising or publicity pertaining to distribution of the software
  without specific, written prior permission.
  
  BROWN UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR ANY PARTICULAR PURPOSE.  IN NO EVENT SHALL BROWN
  UNIVERSITY BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  PERFORMANCE OF THIS SOFTWARE.
*/

package jdsl.core.ref;

import jdsl.core.api.*;



/**
 * A node-based Binary Tree. The Positions of the tree are
 * the nodes.<p>
 * 
 * contains() is O(1) time; so replaceSubtree, cut, and link are O(S), where S is the
 * number of positions in that subtree.
 * Positions() and elements() are O(N) -- where N is the number of positions
 * in the entire tree.
 * All other methods are O(1) time.
 * <p>
 * Elements can be stored at both internal and external (leaf) nodes.<p>
 *
 * The data structure stores a supernode which in turn stores the root.
 * (this supernode is invisible to the end user)
 *
 * You are only allowed to link in and replaceSubtree with other instances
 * of NodeBinaryTree (or subclasses thereof).
 *
 * @author Ryan Baker (rsb)
 * @author Mark Handy (mdh)
 * @author Benoit Hudson (bh)
 * @version JDSL 2.1.1 
 * @see AbstractPositionalContainer
 * @see BinaryTree
 */

public class NodeBinaryTree extends AbstractPositionalContainer 
implements BinaryTree {
    
  /**
    * The super node which stores the root.
    * (This should _never_ be null)
    */
    private NBTSuperNode _supernode;
    
  /**
    * The size of the tree
    * protected so that RestructurableNodeBinaryTree can access it
    */
  protected int _size;

   /** 
     * Create a tree.  The tree has a single external node
     * at its root, with element <code>null</code>.
     */
    public NodeBinaryTree() {
      _size = 1;
      _supernode = new NBTSuperNode (this, null);
      NBTNode root = new NBTNode (_supernode, (Object)null);
      _supernode.setRoot (root);
      root.setContainer(this);
    }
    
    /** 
     * Create a tree from a set of nodes.  The tree will
     * have as its root the given node.
     *
     * This constructor is protected in order to prevent it
     * from being used except as a result of operations on
     * one tree that create another tree
     *
     * It is assumed that the method calling this will take
     * responsibility for changing the container_ of the
     * various internal NBTNodes, as well as setting _size -- 
     * this way, we can allow
     * O(1) time access where appropriate
     * @param root Root of a tree of existing nodes.
     * @throws InvalidAccessorException when the given root has a parent.
     */
    protected NodeBinaryTree (NBTNode root)throws InvalidAccessorException {
      if (root.parent()!=null)	
	throw new InvalidAccessorException("Given root has a parent.");
        _supernode = new NBTSuperNode(this,root);
	root.setParent(_supernode);
	_size = 0;
    }
    


    /**
     *--------------------------------------------------------
     * From interface BinaryTree
     *--------------------------------------------------------
     */

  /**
    * Takes O(S) time, where S is the number of positions in the new
    * subtree to graft on
    * You are only allowed to link in and replaceSubtree with other instances
    * of NodeBinaryTree (or subclasses thereof)
    */
  public void graftOnLeft( Position subtree, Object eltOfParent, BinaryTree newSibling ){
    NBTNode NBTsubtree = checkPosition(subtree);

    NBTNode graftOnto = NBTsubtree.parent();
    NBTNode newSubtreeRoot = new NBTNode(graftOnto,eltOfParent);
    newSubtreeRoot.setContainer(this);

    if (graftOnto==_supernode)
      _supernode.setRoot(newSubtreeRoot);
    else
      graftOnto.setChild(NBTsubtree,newSubtreeRoot);

    _size+=2;
    newSubtreeRoot.expand();
    newSubtreeRoot.setRight(NBTsubtree);
    NBTsubtree.setParent(newSubtreeRoot);
    link(newSubtreeRoot.left(),newSibling);
  }

  /**
    * Takes O(S) time, where S is the number of positions in the new
    * subtree to graft on
    * You are only allowed to link in and replaceSubtree with other instances
    * of NodeBinaryTree (or subclasses thereof)
    */
  public void graftOnRight( Position subtree, Object eltOfParent, BinaryTree newSibling ){
    NBTNode NBTsubtree = checkPosition(subtree);

    NBTNode graftOnto = NBTsubtree.parent();
    NBTNode newSubtreeRoot = new NBTNode(graftOnto,eltOfParent);
    newSubtreeRoot.setContainer(this);

    if (graftOnto==_supernode)
      _supernode.setRoot(newSubtreeRoot);
    else
      graftOnto.setChild(NBTsubtree,newSubtreeRoot);

    _size+=2;
    newSubtreeRoot.expand();
    newSubtreeRoot.setLeft(NBTsubtree);
    NBTsubtree.setParent(newSubtreeRoot);
    link(newSubtreeRoot.right(),newSibling);
  }

  /**
    * O(1) time
    */
    public void expandExternal (Position mustBeExternal) throws
    InvalidAccessorException {
	NBTNode externalToExpand = checkPosition(mustBeExternal);
	if (externalToExpand.isInternal()) throw new InvalidAccessorException
					       ("You can't expand an internal node");
	externalToExpand.expand(); // now it's internal with two external children
	_size+=2;
    }

  /**
    * O(1) time
    */
    public void removeAboveExternal (Position mustBeExternal) throws
    InvalidAccessorException, BoundaryViolationException {
	NBTNode externalToRemove = checkPosition(mustBeExternal);
	if (isInternal(externalToRemove)) throw new InvalidAccessorException
		("You can't remove above an internal node");
	if (isRoot(externalToRemove)) throw new BoundaryViolationException
		("You can't remove above the root!");
	externalToRemove.removeSelfAndAbove();
	_size-=2;
    }
  
  /**
    * Takes O(S) time, where S is the number of positions in the subtree to cut
    */
    public BinaryTree cut (Position rootOfSubtree)throws InvalidAccessorException {
        // cutting means replacing the subtree with a leaf (i.e., with a newly
        // constructed tree)
        return replaceSubtree (rootOfSubtree,(BinaryTree)newContainer());
    }


  /**
    * Takes O(S) time, where S is the number of positions in this subtree
    * You are only allowed to link in and replaceSubtree with other instances
    * of NodeBinaryTree (or subclasses thereof)
    */
    public Object link (Position mustBeExternal, BinaryTree newSubtree)throws InvalidAccessorException, InvalidContainerException {
	NBTNode x = checkPosition (mustBeExternal);
        if (x.isInternal()) throw new InvalidAccessorException
					     ("You can't link at an internal node");
        replaceSubtree (mustBeExternal, newSubtree);
	return x.element();
    }


  /** 
    * Takes O(S1+S2) time, where S1 and S2 are the number of positions in each subtree
    * You are only allowed to link in and replaceSubtree with other instances
    * of NodeBinaryTree (or subclasses thereof)
    */
    public BinaryTree replaceSubtree (
            Position subtreeRoot,
            BinaryTree newSubtree)throws InvalidAccessorException, InvalidContainerException {
	if (newSubtree==this)
	  throw new InvalidContainerException("You can't link or replaceSubtree a tree into itself!");
	if ( ! (newSubtree instanceof NodeBinaryTree) || (newSubtree==null)) throw
					new InvalidContainerException
					("incompatible type of tree or null tree");

	

        NodeBinaryTree toSwapIn = (NodeBinaryTree) newSubtree;

	updateContainer((NBTNode)toSwapIn.root());

        // get the roots of the subtrees to be swapped
        NBTNode oldSubtreeRoot = checkPosition (subtreeRoot);
        NBTNode newSubtreeRoot = (NBTNode) toSwapIn.root();

	oldSubtreeRoot.replaceSelf (newSubtreeRoot);

        // make a new tree out of the nodes swapped out; the constructor
        // makes a new tree wrapper pointing to oldSubtreeRoot
        // and forces oldSubtreeRoot to point up to its new container
        NodeBinaryTree toReturn = new NodeBinaryTree
	    (oldSubtreeRoot);
	
	toReturn.updateContainer(toReturn.root());

        toSwapIn.resetToEmpty();

        return toReturn;
    }

  /**
    * Recursively changes the container of all nodes in the subtree
    * anchored at root to this container, adding to _size for each
    * node whose container we change
    * Takes O(S) time -- where S is the number of elements in the subtree
    * @param root The node to begin with
    */
  protected void updateContainer(Accessor root)throws InvalidAccessorException{
    NBTNode rootn = null;
    try{
      rootn = (NBTNode)root;
    }
    catch(ClassCastException cce){
      assert false : "Incompatible type of position";
    }
    _size++;
    if (rootn.container()!=null)
      rootn.container()._size--;
    rootn.setContainer(this);
    if (isInternal(rootn)){
      updateContainer(leftChild(rootn));
      updateContainer(rightChild(rootn));
    }
  }

    /**
     *--------------------------------------------------------
     * From interface InspectableBinaryTree
     *--------------------------------------------------------
     */

  /**
    * O(1) time
    */
    public Position leftChild (Position p) throws
    InvalidAccessorException, BoundaryViolationException {
	NBTNode check = checkPosition(p);
	if ( isExternal(check) ) throw new BoundaryViolationException
					("An external node has no children");
	return check.left(); 
    }
    
  /**
    * O(1) time
    */    
    public Position rightChild (Position p) throws
    InvalidAccessorException, BoundaryViolationException {
	NBTNode check = checkPosition(p);
	if ( isExternal(check) ) throw new BoundaryViolationException
					("An external node has no children");
	return check.right(); 
    }
    
  /**
   * O(1) time
   */    
  public Position sibling (Position p) throws
  InvalidAccessorException, BoundaryViolationException {
    PositionIterator pi = siblings(p);
    if (!pi.hasNext())
      throw new BoundaryViolationException("The root has no siblings");
    else
      return pi.nextPosition();
  }
    
    

    /**
     *--------------------------------------------------------  
     * From interface InspectableTree
     *--------------------------------------------------------
     */

  /**
    * O(1) time
    */ 
    public boolean isRoot (Position p) throws InvalidAccessorException {
        checkPosition (p);
        return ( p==root() );
    }

  /**
    * O(1) time
    */ 
    public boolean isInternal (Position p) throws InvalidAccessorException {
        NBTNode check = checkPosition(p);
        return check.isInternal();
    }

  /**
    * O(1) time
    */ 
    public boolean isExternal (Position p) throws InvalidAccessorException {
        return ! isInternal(p);
    }

  /**
    * O(1) time
    */ 
    public Position root() {
        return _supernode._root;
    }

  /**
    * O(1) time
    */ 
    public Position parent (Position p) throws
    InvalidAccessorException, BoundaryViolationException {
	NBTNode check = checkPosition(p);
	if (check==root()) throw new BoundaryViolationException
			       ("parent(root)");
	return check.parent();
    }
    
  /**
    * O(1) time
    */ 
    public PositionIterator children (Position p) throws
    InvalidAccessorException {
        NBTNode padre = checkPosition(p);
        if(isInternal(padre)) {
            Position [] kids = new Position[2];
            kids[0] = padre.left();
            kids[1] = padre.right();
            return new ArrayPositionIterator(kids);
        }
        else {
	  return new ArrayPositionIterator(null);//ext node has no children
        }
    }

  /**
    * O(1) time
    */ 
    public PositionIterator siblings (Position p) throws
    InvalidAccessorException {
      if (isRoot(p))
	throw new BoundaryViolationException("The root has no siblings");

      NBTNode n = checkPosition(p);
      Position [] sib = new Position[1];
      sib[0] = n.parent().otherChild(n);
      return new ArrayPositionIterator(sib);
    }

  /** 
    * O(1) time
    * Can be determined by the inherent nature of the type of node
    * rather than by counting
    */
  public int numChildren(Position node) throws InvalidAccessorException{
    checkPosition(node);
    if (isExternal(node))
      return 0;
    else
      return 2;
  }

  /**
    * O(1) time
    */ 
  public Position siblingAfter (Position node) throws
  BoundaryViolationException, InvalidAccessorException{
    
    NBTNode childnbt = checkPosition(node);

    if (childnbt.isLeftChild())
      return sibling(node);
    else
      if (isRoot(childnbt))
	throw new BoundaryViolationException("This is the root");
      else
	throw new BoundaryViolationException("This is the right child");
  }

  /**
    * O(1) time
    */ 
  public Position siblingBefore (Position node) throws
  BoundaryViolationException, InvalidAccessorException{
    
    NBTNode childnbt = checkPosition(node);

    if (!childnbt.isLeftChild())
      if (isRoot(childnbt))
	throw new BoundaryViolationException("This is the root");
      else
	return sibling(node);
    else
      throw new BoundaryViolationException("This is the left child");
  }
  
  /**
    * O(1) time
    */ 
  public Position firstChild (Position node) throws
  BoundaryViolationException, InvalidAccessorException{
    
    return childAtRank(node,0);
  }

  /**
    * O(1) time
    */ 
  public Position lastChild (Position node) throws
  BoundaryViolationException, InvalidAccessorException{
    
     return childAtRank(node,1);
  }
  
  /**
    * O(1) time
    */ 
  public int rankOfChild (Position child) throws
  BoundaryViolationException, InvalidAccessorException{
  
    NBTNode childnbt = checkPosition(child);

    if (childnbt.isLeftChild())
      return 0;
    else
      if (isRoot(childnbt))
	throw new BoundaryViolationException("This is the root");
      else
	return 1;
  }

  /**
    * O(1) time
    */ 
  public Position childAtRank (Position node, int rank) throws
  BoundaryViolationException, InvalidAccessorException{
  
    NBTNode parent = checkPosition(node);
    
    if (isExternal(parent))
      throw new BoundaryViolationException("This is an external node");

    if (rank == 0)
      return parent.left();
    if (rank == 1)
      return parent.right();

    throw new BoundaryViolationException("Rank "+rank+" is out of bounds -- Binary Trees only have children at ranks 0 and 1.");
      
  }

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


    /** 
      * Takes O(N) time from the need to iterate through the tree during 
      * snapshot, where N is the number of positions in the tree
     * @return PositionIterator of the container in preorder
     */
    public PositionIterator positions() {