nodetree.java

Java数据结构开发包

	  throw new BoundaryViolationException("Root of a tree cannot have any siblings.");
	NTNode left = tnode.leftSib();
	if (left == null)
	  throw new BoundaryViolationException("Position is the first child.");
	return left;
    }

    /**
     * O(1) time
     */
    public Position firstChild(Position node)
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tnode = checkValid(node);
	if (tnode.isExternal())
	  throw new BoundaryViolationException("Position is external.");
	return tnode.firstChild();
    }

    /**
     * O(1) time
     */
    public Position lastChild(Position node)      
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tnode = checkValid(node);
	if (tnode.isExternal())
	  throw new BoundaryViolationException("Position is external.");
	return tnode.lastChild();
    }

    /**
     * O(the number of children of the node) time
     */
    public int rankOfChild(Position child) 
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tnode = checkValid(child);
	if (tnode == root_)
	  throw new BoundaryViolationException("Position is a root.");

	return tnode.parent().rankOfChild(tnode);
    }

    //////////////////////////////////////////////////////////////////
    // Methods implemented from Tree interface
    //////////////////////////////////////////////////////////////////
    //              On the issue of cut and link:
    // cut does not build on replaceSubtree, because it does not need
    // any container checks as well as creation of new objects (other then
    // the return tree) to make it work. Same is true for link: while
    // checks are not an issue here, not using replaceSubtree let's us 
    // avoid creation and update of the return subtree.
    //////////////////////////////////////////////////////////////////
    /**
     * O(size of the cut subtree) time
     */
    public Tree cut(Position p) 
      throws InvalidAccessorException {
	NTNode tnode = checkValid(p);
	NTNode new_node = new NTNode(null, this);
	NTNode parent = tnode.parent();
	if (parent == null) {
	  root_ = new_node;
	} else {
	  parent.replace(tnode.leftSib(), tnode.rightSib(), new_node, new_node, null);
	}
	poscache_ = null;
	eltcache_ = null;
	
	NodeTree new_tree =  new NodeTree(tnode);
	size_ -= new_tree.size()-1;
	return new_tree;
    }

    /**
     * O(size of the new subtree to be linked in) time
     */
    public Object link(Position extNode, Tree t) 
      throws InvalidAccessorException, InvalidContainerException {
	NTNode tnode = checkValid(extNode);
	if (! tnode.isExternal()) 
	  throw new InvalidAccessorException("A tree cannot be linked to an internal node.");
	if (t == null)
	  throw new InvalidContainerException("A null tree cannot be linked.");
	if (! (t instanceof NodeTree))
	  throw new InvalidContainerException("Incompatible type of a tree"); 
	if (t == this)
	  throw new InvalidContainerException("A tree cannot be linked to itself.");
	NTNode subtree_root = (NTNode)t.root();
	int subtree_size = updateContainer(subtree_root, this);

	NTNode parent = tnode.parent();
	poscache_ = null;
	eltcache_ = null;
	((NodeTree)t)._clear();

	if (parent != null)
	  parent.replace(tnode.leftSib(), tnode.rightSib(), subtree_root, subtree_root, null);
	else
	  root_ = subtree_root;
	tnode.makeUncontained();
	size_ += subtree_size-1;
	return tnode.element();
    }

    /**
     * O(size of the new subtree + size of the cut tree) time
     */
    public Tree replaceSubtree(Position node, Tree t)
      throws InvalidAccessorException, InvalidContainerException {
	NTNode old_root = checkValid(node);
	if (t == null)
	  throw new InvalidContainerException("A null tree cannot be linked.");
	NTNode new_root = (NTNode)t.root();
	if (! (t instanceof NodeTree))
	  throw new InvalidContainerException("Incompatible type of tree");
	NodeTree new_tree = (NodeTree)t;
	if (new_tree == this)
	  throw new InvalidContainerException("A tree cannot be linked to itself.");
	int new_size, old_size;
	new_size = new_tree.size();
	new_tree._clear();
	updateContainer(new_root, this);
	NTNode parent = old_root.parent();	
	if (parent == null) {
	  root_ = new_root;
	} else {
	  parent.replace(old_root.leftSib(), old_root.rightSib(), new_root, new_root, null);
	}
	poscache_ = null;
	eltcache_ = null;

	NodeTree to_return = new NodeTree(old_root);
	size_ = size_ - to_return.size() + new_size;
	return to_return;
    }

    /**
     * O(1) time
     */
    public Position insertAfterSibling(Position node, Object elem) 
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tbefore = checkValid(node);
	if (node == root_)
	  throw new BoundaryViolationException("Root cannot have any siblings.");
	poscache_ = null;
	eltcache_ = null;
	size_++;

	NTNode new_node = new NTNode(elem, this);
	tbefore.parent().replace(tbefore, tbefore.rightSib(), new_node, new_node, null);

	return new_node;
    }

    /**
     * O(the number of children of the node) time
     */
    public Position insertChildAtRank(Position node, int rank, Object elem)
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode parent = checkValid(node);
	NTNode tmp;
	if (rank < 0)
	  throw new BoundaryViolationException("A child cannot have negative rank.");
	if (rank == 0) {
	  tmp = null;
	} else {
	  tmp = parent.firstChild();
	  for(int i=0; i < rank-1 && tmp != null; i++, tmp = tmp.rightSib());
	  if (tmp == null)
	    throw new BoundaryViolationException("Rank is greater then the number of children.");
	}
	poscache_ = null;
	eltcache_ = null;
	size_++;

	NTNode new_node = new NTNode(elem, this);
	parent.replace(tmp, (tmp == null ? parent.firstChild() : tmp.rightSib()), 
		       new_node, new_node, null);

	return new_node;
    }

    /**
     * O(1) time
     */
    public Position insertBeforeSibling(Position node, Object elem) 
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode tafter = checkValid(node);
	if (node == root_)
	  throw new BoundaryViolationException("Root cannot have any siblings.");
	NTNode parent = tafter.parent();
	poscache_ = null;
	eltcache_ = null;
	size_++;

	NTNode new_node = new NTNode(elem, this);
	parent.replace(tafter.leftSib(), tafter, new_node, new_node, null);

	return new_node;
    }

    /**
     * O(1) time
     */
    public Position insertFirstChild(Position node, Object elem)
      throws InvalidAccessorException {
	NTNode parent = checkValid(node);
	poscache_ = null;
	eltcache_ = null;
	size_++;	

	NTNode new_node = new NTNode(elem, this);
	parent.replace(null, parent.firstChild(), new_node, new_node, null);
	
	return new_node;
    }

    /**
     * O(1) time
     */
    public Position insertLastChild(Position node, Object elem)
      throws InvalidAccessorException {
	NTNode parent = checkValid(node);
	poscache_ = null;
	eltcache_ = null;
	size_++;

	NTNode new_node = new NTNode(elem, this);
	parent.replace(parent.lastChild(), null, new_node, new_node, null);

	return new_node;
    }

    /**
     * O(1) time
     */
    public Object removeExternal(Position node) 
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode to_remove = checkValid(node);
	if (! to_remove.isExternal()) 
	  throw new BoundaryViolationException("Position is internal.");
	if (to_remove == root_)
	  throw new BoundaryViolationException("Root of a tree cannot be removed.");
	poscache_ = null;
	eltcache_ = null;
	size_--;
	to_remove.parent().replace(to_remove.leftSib(), to_remove.rightSib(), null, null, null);
	to_remove.makeUncontained();
	return to_remove.element();
    }

    /**
     * O(1) time
     */
    public Object contract(Position node)
      throws BoundaryViolationException, InvalidAccessorException {
	NTNode to_remove = checkValid(node);
	if (to_remove == root_)
	  throw new BoundaryViolationException("Root of a tree cannot be contracted.");
	if (to_remove.isExternal())
	  throw new BoundaryViolationException("Cannot contract external node.");

	poscache_ = null;
	eltcache_ = null;
	size_--;
	to_remove.parent().replace(to_remove.leftSib(), to_remove.rightSib(), to_remove.firstChild(),
				   to_remove.lastChild(), null);
	to_remove.makeUncontained();
	return to_remove.element();
    }

    /**
     * O(number of children of a new node) time
     */
    public Position expand(Position fromChild, Position toChild, Object elem) 
      throws InvalidAccessorException {
	NTNode tfrom = checkValid(fromChild);
	NTNode tto = checkValid(toChild), tmp;
	for(tmp = tfrom; (tmp != null) && (tmp != tto); tmp = tmp.rightSib());
	if (tmp == null)
	  throw new InvalidAccessorException("Cannot expand the tree where the second position is not a higher order sibling of the first.");
	poscache_ = null;
	eltcache_ = null;
	size_++;
	
	NTNode newnode = new NTNode(elem, this);
	NTNode oldparent = tfrom.parent();
	if (oldparent != null)
	  oldparent.replace(tfrom.leftSib(), tto.rightSib(), newnode, newnode, newnode);
	else {
	  root_ = newnode;
	  newnode.replace(null, null, tfrom, tto, null);
	}
	return newnode;
    }

    /**
     * Checks whether the accessor is valid and belongs to this container.
     * O(1) assuming container check is O(1).
     * 
     * @param p accessor to be checked out
     * @exception InvalidAccessorException if the accessor is null,
     * or if it is of the wrong class, or it doesn't belong to this container.
     * @return NTNode cast down Position of this container
     */
    private NTNode checkValid(Accessor p)
      throws InvalidAccessorException {
	if (p == null)
	  throw new InvalidAccessorException("A null position cannot be contained.");
	if (! (p instanceof NTNode))
	  throw new InvalidAccessorException("Position of wrong class: " +
					     p.getClass());
	if (((NTNode)p).container() != this) 
	  throw new InvalidAccessorException("Position does not belong to the container.");

	return (NTNode)p;
    }

    /**
     * Updates container variable in the entire subtree rooted at a node. Implemented
     * using basic depth first search down the subtree.
     * @return int size of the tree rooted at node
     */
    private int updateContainer(NTNode node, InspectableContainer c) {
      int size = 0;
      NTNode proc_node;
      for(proc_node = node; proc_node != null;) {
	proc_node.setContainer(c);
	size++;
	if (proc_node.isExternal()) {
	  // backtrack up until find a node with a right sibling or get back to the node.
	  for(; (proc_node != node) && (proc_node.rightSib() == null); proc_node = proc_node.parent());
	  if (proc_node == node)
	    break;
	  proc_node = proc_node.rightSib();
	} else {
	  proc_node = proc_node.firstChild();
	}
      }
      return size;
    }

    /**
     * Clears the tree to a pristine condition of having one empty node.
     */
    private void _clear() {
      size_ = 1;
      root_ = new NTNode(null, this);
      poscache_ = null;
      eltcache_ = null;
    }

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

}