idtree.java

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

package edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph;

import java.util.Enumeration;




/**
 *  A general tree with nodes containing numeric ID's.
 *
 *  @author Steven J. Zeil
 *  @version 2.0
 */
public class IDTree
{
  /**
   *  Next sibling
   */
  private IDTree next;

  /**
   *  Previous sibling
   */
  private IDTree prev;

  /**
   *  Last in the list of this node's children (children are maintained in
   *  a ring, so lastChild.next is the first child).
   */
  private IDTree lastChild;

  /**
   *  Parent of this node, null if this is a tree root.
   */
  private IDTree theParent;

  /**
   *  Identifier for this node.  All non-root nodes must carry
   *  unique identifiers.
   */
  private String id;


  /**
   * Create a new tree node with the given ID and parent.
   *
   *  @param ID Identifier.  It is the caller's responsibility to ensure
   *            that each non-root node has a unique identifier.
   *  @param Parent  The parent node of the newly constructed one.
   *            This may be null, indicating that the new node will be
   *            a tree root.
   */
  IDTree(String ID, IDTree Parent) 
  {
    next = prev = this;
    lastChild = null;
    theParent = null;
    id = ID;
    theParent.add (this);
  }

  /**
   * Create a new tree root with the given ID.
   * Equivalent to <code>IDTree(ID, null)</code>.
   *
   *  @param ID Identifier.  It is the caller's responsibility to ensure
   *            that each non-root node has a unique identifier.
   */
  IDTree(String ID) 
  {
    next = prev = this;
    lastChild = null;
    theParent = null;
    id = ID;
  }
  
  /**
   * Get the ID of this node
   */
  public String ID()
  {
    return id;
  }
  

  /**
   * Add a node as a child of this one.
   *
   *  @param child Becomes a child of this node. If <code>child</code> is
   *    already a child of some node, it is first removed from that other
   *    node's list of children.
   */
  public void add (IDTree child)
  {
    child.isolate();
    child.theParent = this;
    if (lastChild == null)
      {
	lastChild = child;
	child.next = child.prev = child;
      }
    else
      {
	child.prev = lastChild;
	child.next = lastChild.next;
	lastChild.next.prev = child;
	lastChild.next = child;
	lastChild = child;
      }
    
  }
  
  /**
   * Remove this node from its parent, if any. The node becomes a tree root.
   * This node's children, if any, are unaffected. 
   */
  public void isolate ()
  {
    if (theParent != null)
      {
	if (prev != this)
	  {
	    prev.next = next;
	    next.prev = prev;
	    if (theParent.lastChild == this)
	      theParent.lastChild = prev;
	    next = prev = this;
	    theParent = null;
	  }
	else
	  {
	    theParent.lastChild = null;
	    prev = next = this;
	  }
      }
  }




  /**
   * Parent of this node
   *
   *   @return parent node or null if this is a root
   */
  public IDTree parent() 
  {
    return theParent;
  }
  


  class IDTreeEnumeration implements Enumeration
  {
    /**
     * Current location of this enumeration within the list of children.
     */
    private IDTree position;
    private IDTree last;

    /**
     * Begin an enumeration at the given node. The enumeration will
     * continue through all subsequent siblings of that node.
     *
     * @param parent The parent node whose children are being enumerated.
     */
    IDTreeEnumeration (IDTree parent)
    {
      position = null;
      last = parent.lastChild;
    }
  
    /**
     * True if more sibling nodes remain to be visited.
     */
    public boolean hasMoreElements()
    {
      return (position != last);
    }
    

    /**
     * Return current node and advance enumeration to next position.
     *
     * @return Node at current position (before it is advanced)
     */
    public Object nextElement()
    {
      if (position == null)
	position = last.next;
      else
	position = position.next;
      return position;
    }
  }


  /**
   * Enumerate over all children of this node.
   *
   *   @return Return an enumerator positioned at the first of this node's
   *           children.
   */
  public Enumeration children() 
  {
    return new IDTreeEnumeration(this);
  }

}