nodetree.java

Java数据结构开发包

	 * (inclusive) to this node's children list between <code>sibLeft</code> and <code>sibRight</code>
	 * </ul>
	 *
	 * @param sibLeft sibling right of which to insert newLeft
	 * @param sibRight sibling left of which to insert newRight
	 * @param newLeft 
	 * @param newRight
	 * @param newParent becomes parent of whatever used to be between 
	 * <code>sibLeft</code> and <code>sibRight</code>, it can be either
	 * a null or a node with no children
	 * 
	 */
	void replace(NTNode sibLeft, NTNode sibRight, NTNode newLeft, NTNode newRight, NTNode newParent) {
	  int cnt_cut; // The number of nodes being cut from between sibLeft and sibRight
	  int cnt_inserted; // The number of nodes being inserted (i.e. from newLeft to newRight inclusive)
	  NTNode tmp;
	  NTNode oldLeft; // The leftmost child to be cut, if any (i.e. the right sibling of sibLeft)
	  NTNode oldRight; // The rightmost child to be cut, if any (i.e. the left sibling of sibRight)

	  oldLeft = ( sibLeft == null ? first_ : sibLeft.rightSib() );
	  oldRight = ( sibRight == null ? last_ : sibRight.leftSib() );

	  // Remove children between sibLeft and sibRight from this node
	  if (oldLeft == sibRight) {
	    assert oldRight == sibLeft;
	    cnt_cut = 0;
	  } else {
	    for(cnt_cut = 0, tmp = oldLeft; tmp != sibRight && tmp != null; 
		tmp = tmp.rightSib(), cnt_cut++) {
	      tmp.setParent(newParent);
	    }
	    if (oldLeft != null) oldLeft.setLeftSib(null);
	    if (oldRight != null) oldRight.setRightSib(null);
	    if (newParent != null) {
	      newParent.addNumberOfChildren(cnt_cut);
	      assert newParent.firstChild() == null;
	      newParent.setFirstChild(oldLeft);
	      newParent.setLastChild(oldRight);
	    }
	    removeNumberOfChildren(cnt_cut);
	  }

	  if (newLeft == null) { 
	    // Nothing to be inserted - just connect sibLeft and sibRight
	    assert newRight == null;
	    cnt_inserted = 0;
	    if (sibLeft == null) first_ = sibRight;
	    else sibLeft.setRightSib(sibRight);
	    if (sibRight == null) last_ = sibLeft;
	    else sibRight.setLeftSib(sibLeft);
	  } else {
	    // Make the nodes to be inserted part of the tree
	    assert newLeft != null && newRight != null;
	    NTNode oldParent = newLeft.parent();
	    for(cnt_inserted = 1, tmp = newLeft; tmp != null; 
		cnt_inserted++, tmp = tmp.rightSib()) {
	      tmp.setParent(this);
	      if (tmp == newRight) break;
	    }
	    assert tmp != null;
	    if (oldParent != null) {
	      // Adjust the old parent of the nodes between newLeft and newRight
	      // to not point or count these nodes anymore
	      oldParent.removeNumberOfChildren(cnt_inserted);
	      if (oldParent.firstChild() == newLeft)
		oldParent.setFirstChild(newRight.rightSib());
	      if (oldParent.lastChild() == newRight)
		oldParent.setLastChild(newLeft.leftSib());
	    }
	    // Adjust old siblings of newLeft and newRight to not
	    // point to them anymore
	    if (newLeft.leftSib() != null)
	      newLeft.leftSib().setRightSib(newRight.rightSib());
	    if (newRight.rightSib() != null)
	      newRight.rightSib().setLeftSib(newLeft.leftSib());
	    // Do the actual linking of these nodes to this node
	    // and this node's list of children
	    addNumberOfChildren(cnt_inserted);
	    if (sibLeft == null) first_ = newLeft;
	    else sibLeft.setRightSib(newLeft);
	    if (sibRight == null) last_ = newRight;
	    else sibRight.setLeftSib(newRight);
	    newLeft.setLeftSib(sibLeft);
	    newRight.setRightSib(sibRight);
	  }
	}
    }

    //////////////////////////////////////////////////////////////////
    // Constructors
    //////////////////////////////////////////////////////////////////

    /**
     * The default constructor for NodeTree, which creates a tree
     * with one node whose element is null. This is the only public
     * constructor.
     */
    public NodeTree() {
      size_ = 1;
      root_ = new NTNode(null, this);
      poscache_ = null;
      eltcache_ = null;
    }
    
    /**
     * Constructor to be used to create new trees in cut and
     * replaceSubtree methods which require part of the tree
     * to be returned as a new tree.
     */
    private NodeTree(NTNode root) {
      root.setParent(null);
      root.setLeftSib(null);
      root.setRightSib(null);
      root_ = root;
      size_ = updateContainer(root_,this);
      poscache_ = null;
      eltcache_ = null;
    }

    //////////////////////////////////////////////////////////////////
    // Methods implemented from InspectableContainer
    //////////////////////////////////////////////////////////////////

    /**
     * O(1) time
     */
    public boolean contains(Accessor a) 
      throws InvalidAccessorException  {
	if (a == null)
	  throw new InvalidAccessorException("A null position cannot be contained.");
	if (! (a instanceof NTNode))
	  return false;            
	if (((NTNode)a).container() == this) 
	  return true;
	else
	  return false;
    }

    /**
     * O(1) time
     */
    public boolean isEmpty() {
      return false;
    }

    /**
     * O(1) time
     */
    public int size() {
      return size_;
    }


    /**
     * O(1) time if cache already exists, O(size of the tree) otherwise
     */
    public ObjectIterator elements() {
      if (eltcache_ == null) {
	int i = 0;
	eltcache_ = new Object[size_];
	PositionIterator posIter = positions();
	while(posIter.hasNext()) {
	  eltcache_[i] = posIter.nextPosition().element();
	  i++;
	}
      }
      return new ArrayObjectIterator(eltcache_);
    }

    //////////////////////////////////////////////////////////////////
    // Methods implemented from Container
    //////////////////////////////////////////////////////////////////

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

    /**
     * O(1) time
     */
    public Object replaceElement(Accessor a, Object newElement) 
      throws InvalidAccessorException {
	NTNode node = checkValid(a);
	// Clear the elements but not the psoition cache
	eltcache_ = null;
	Object old = node.element();
	node.setElement(newElement);
	return old;
    }

    //////////////////////////////////////////////////////////////////
    // Methods implemented from InspectablePositionalContainer
    //////////////////////////////////////////////////////////////////

    /**
     * O(1) time if cache already exists, O(size of the tree) otherwise
     */
    public PositionIterator positions() {
	if (poscache_ == null) {
	  int fromNode, toNode;
	  NTNode tmp;
	  poscache_ = new NTNode[size_];
	  poscache_[0] = root_;
	  for(fromNode = 0, toNode = 1; fromNode < size_; fromNode++) {
	    if (poscache_[fromNode].isExternal())
	      continue;
	    for(tmp = poscache_[fromNode].firstChild(); tmp != null; tmp = tmp.rightSib()) {
	      poscache_[toNode] = tmp;
	      toNode++;
	    }
	  }
	}
	return new ArrayPositionIterator(poscache_);
    }

    //////////////////////////////////////////////////////////////////
    // Methods implemented from PositionalContainer
    //////////////////////////////////////////////////////////////////
    /**
     * O(1) time
     */
    public void swapElements(Position a, Position b) 
      throws InvalidAccessorException {
	NTNode nodea = checkValid(a);
	NTNode nodeb = checkValid(b);
	Object obja = nodea.element();
	nodea.setElement(nodeb.element());
	nodeb.setElement(obja);
    }

    //////////////////////////////////////////////////////////////////
    // Methods implemented from InspectableTree 
    //////////////////////////////////////////////////////////////////

    /**
     * O(1) time
     */
    public boolean isRoot(Position node)
      throws InvalidAccessorException {
	NTNode tnode = checkValid(node);
	return (tnode == root_);
    }

    /**
     * O(1) time
     */
    public boolean isInternal(Position node)
      throws InvalidAccessorException {
	NTNode tnode = checkValid(node);
	return (!tnode.isExternal());
    }
    
    /**
     * O(1) time
     */
    public boolean isExternal(Position node)
      throws InvalidAccessorException {
	NTNode tnode = checkValid(node);
	return tnode.isExternal();
    }

    /**
     * O(1) time
     */
    public Position root() {
	return root_;
    }

    /**
     * O(1) time
     */
    public Position parent(Position node) 
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tnode = checkValid(node);
	if (tnode == root_)
	  throw new BoundaryViolationException("Root of a tree cannot have a parent.");
	return tnode.parent();
    }


    /**
     * O(1) time if cache exists,
     * O(the number of children of the node) otherwise.
     */
    public PositionIterator children(Position node) 
      throws InvalidAccessorException {
	NTNode tnode = checkValid(node);
	return tnode.childrenIterator();
    }

    /**
     * O(the number of children of the node) time
     */
    public PositionIterator siblings(Position node) 
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tnode = checkValid(node), tmp;
	if (tnode == root_)
	  throw new BoundaryViolationException("Root of a tree cannot have any siblings.");
	int numsib = tnode.parent().numChildren()-1, i;
	if (numsib == 0)
	  return new ArrayPositionIterator(null);
	NTNode [] siblings = new NTNode[numsib];
	for(tmp = tnode.parent().firstChild(), i = 0; i < numsib; i++, tmp = tmp.rightSib()) {
	  if (tmp == tnode)
	    i--;
	  else
	    siblings[i] = tmp;
	}
	return new ArrayPositionIterator(siblings);
    }

    /**
     * O(1) time
     */
    public int numChildren(Position node)
      throws InvalidAccessorException {
	NTNode tnode = checkValid(node);
	return tnode.numChildren();
    }

    /**
     * O(1) time
     */
    public Position siblingAfter(Position node)
      throws BoundaryViolationException, InvalidAccessorException {
	 NTNode tnode = checkValid(node);
	 if (tnode == root_)
	   throw new BoundaryViolationException("Root of a tree cannot have any siblings.");
	 NTNode right = tnode.rightSib();
	 if (right == null)
	   throw new BoundaryViolationException("Position is the last child.");
	 return right;
    }

    /**
     * O(1) time
     */
    public Position childAtRank(Position node, int rank)
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tnode = checkValid(node);
	if (rank < 0 || rank >= tnode.numChildren())
	  throw new BoundaryViolationException("Invalid rank of a child.");
	NTNode tmp = tnode.firstChild();
	for(int i=0; i<rank; i++, tmp = tmp.rightSib());
	return tmp;
    }

    /**
     * O(the number of children of the node) time
     */
    public Position siblingBefore(Position node)
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tnode = checkValid(node);
	if (tnode == root_)