nodetree.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 Tree.  The Positions of the tree are
 * the nodes. <p>
 *
 * cut(), link(), and replaceSubtree() are implemented with 
 * O(n) running times
 * to support size() and contains() having O(1) running times.
 * Rank related methods 
 * are O(the maximum number of children per node). The tree is implemented
 * with a internal node data structure which keeps track
 * of the structure of the tree (i.e. links to parents, siblings,
 * and children).
 *
 * @author Galina Shubina (gs)
 * @version JDSL 2.1.1 
 */

public class NodeTree 
  extends AbstractPositionalContainer
  implements Tree {

    /**
     * The stored size of the Tree (never less then one)
     */
    private int size_;

    /**
     * The root node of the Tree
     */
    private NTNode root_;

    /**
     * Cache for positions
     */
    private NTNode[] poscache_;
    

    /**
     * Cache for elements
     */
    private Object[] eltcache_;


  // netsed class(es)
  
    /**
     * Internal tree node. This is a Position that takes care of all
     * children, sibling, and parent linkage.
     */
    private static class NTNode extends HashtableDecorable 
      implements Position {
	
	/**
	 * The parent of this node. It is null only when the tree is a root
	 * or it is uncontained.
	 */
	private NTNode parent_;

	/**
	 * The left sibling of this node in the tree. It is null 
	 * when the node does not have a left sibling or when it is uncontained.
	 */
	private NTNode left_; 

	/**
	 * The right sibling of this node in the tree. It is null when
	 * the node does not have a right sibling or when it is uncontained.
	 */
	private NTNode right_;

	/**
	 * The first child of this node. It does not have any left siblings.
	 * first_ is null if this node does not have any children.
	 */
	private NTNode first_; 

	/**
	 * The last child of this node. It does not have any right siblings.
	 * last_ is null if this node does not have any children.
	 */
	private NTNode last_; 

	/**
	 * The tree containing this node. This value is null if the node
	 * is uncontained.
	 */
	private InspectableContainer container_;

	/**
	 * The number of children this node has. It is zero when
	 * the node is an external node or when it is uncontained.
	 */
	private int num_children_;

	/**
	 * This node's element. May be null.
	 */
	private Object element_;
	
	/**
	 * This node's cache for its children's positions in order.
	 */
	private NTNode[] children_;

	/**
	 * Creates a new external node. 
	 * <p>
	 * O(1) time
	 * @param element element to be at this position
	 * @param c container in which this node is going to be
	 */
	private NTNode(Object element, InspectableContainer c) {
	  super();
	  element_ = element;
	  makeUncontained();
	  container_ = c;
	  num_children_ = 0;
	  children_ = null;
	}

	/**
	 * O(1) time
	 * @return the element stored at this position
	 */
	public Object element() { 
	  return element_; 
	}
	
	public String toString(){
	  return ToString.stringfor((Position)this);
	}

	/**
	 * O(1) time
	 * <p>
	 * Sets this node's parent.
	 */
	void setParent(NTNode parent) { 
	  parent_ = parent;
	}

	/**
	 * O(1) time
	 **/
	void addNumberOfChildren(int n) {
	  assert n>=0;
	  num_children_ += n;
	  if (n != 0)
	    children_ = null;
	}
	
	/**
	 * O(1) time
	 */
	void removeNumberOfChildren(int n) {
	  assert n>=0;
	  num_children_ -= n;
	  if (n != 0)
	    children_ = null;
	}
	

	/**
	 * O(1) time
	 * <p>
	 * Sets this node's left sibling.
	 */
	void setLeftSib(NTNode left) { 
	  left_ = left; 
	}
	
	/**
	 * O(1) time
	 * <p>
	 * Sets this node's right sibling.
	 */
	void setRightSib(NTNode right) { 
	  right_ = right; 
	}

	/**
	 * O(1) time
	 * <p>
	 * Sets this node's first child and invalidate the children cache.
	 */
	void setFirstChild(NTNode first) { 
	  first_ = first; children_ = null;
	}

	/**
	 * O(1) time
	 * <p>
	 * Sets this node's last child and invalidate the children cache.
	 */
	void setLastChild(NTNode last) { 
	  last_ = last; children_ = null;
	}

	/**
	 * O(1) time
	 * <p>
	 * Sets this node's container.
	 */
	void setContainer(InspectableContainer c) { 
	  container_ = c; 
	}
	
	/**
	 * O(1) time
	 * <p>
	 * Sets this node's element.
	 */
	void setElement(Object elt) { 
	  element_ = elt; 
	}

	/**
	 * O(1) time if children cache exists, 
	 * O(the number of children of this node) otherwise.
	 * @return PositionIterator iterator over the children nodes
	 */
	PositionIterator childrenIterator() {
	  int i;
	  NTNode tmp;
	  if (first_ == null)
	    return new ArrayPositionIterator(null);
	  if (children_ == null) {
	    children_ = new NTNode[num_children_];
	    for(i = 0, tmp = first_; i < num_children_; 
		i++, tmp = tmp.rightSib()) {
	      children_[i] = tmp;
	    }
	  } 
	  return new ArrayPositionIterator(children_);
	}

	/**
	 * O(1) time
	 */
	NTNode parent() { return parent_; }

	/**
	 * O(1) time
	 */
	NTNode leftSib() { return left_; }

	/**
	 * O(1) time
	 */
	NTNode rightSib() { return right_; }

	/**
	 * O(1) time
	 */
	NTNode firstChild() { return first_; }

	/**
	 * O(1) time
	 */
	NTNode lastChild() { return last_; }

	/**
	 * O(1) time
	 */
	int numChildren() { return num_children_; }

	/**
	 * O(1) time
	 */
	InspectableContainer container() { return container_; }

	/**
	 * Clears all fields of the node before making it uncontained.
	 * To make it completely uncontained one still has to update
	 * its parent, children, and left and right siblings to stop
	 * pointing to it.
	 * <p>
	 * O(1) time
	 */
	void makeUncontained() {
	  parent_ = null;
	  left_ = null;
	  right_ = null;
	  first_ = null;
	  last_ = null;
	  container_ = null;
	  num_children_ = 0;
	  children_ = null;
	}

	/**
	 * O(1) time
	 * 
	 * @return <i>true</i> if this node is external
	 */
	boolean isExternal() {
	  return (first_ == null);
	}
	
	/**
	 * O(the number of children of the node) time
	 * <p>
	 * Computes the rank of a child of this node.
	 * @param node child of this node
	 * @return rank of node with respect to its parent (this node)
	 */
	int rankOfChild(NTNode node) {
	  int rank = 0;
	  NTNode tmp = first_;
	  for( ; tmp != node; tmp = tmp.rightSib())
	    rank++;
	  return rank;
	}

	/**
	 * O(1)
	 *
	 * Inserts a sequence of nodes into this parents children list.
	 * <p>
	 * This method does the following things:
	 * <ul>
	 * <li> Removes nodes from <code>newLeft</code> to <code>newRight</code>
	 * (inclusive) from they old parent's children list
	 * <li> Removes nodes from <code>sibLeft</code> to <code>sibRight</code> (non inclusive)
	 * from this node's children list (<code>sibLeft</code> and <code>sibRight</code>
	 * must be its children)
	 * <li> Attaches the former children of this node to a new node <code>oldParent</code>
	 * <li> Attaches the nodes from <code>newLeft</code> to <code>newRight</code>