defaultmutabletreenode.java

来自「linux下建立JAVA虚拟机的源码KAFFE」· Java 代码 · 共 1,202 行 · 第 1/2 页

    if (node == null)
      {
        if (depth == 0)
          return null;
        
        return new TreeNode[depth];
      }

    TreeNode[] path = getPathToRoot(node.getParent(), depth + 1);
    path[path.length - depth - 1] = node;
    return path;
  }

  /**
   * getUserObjectPath
   *
   * @return Object[]
   */
  public Object[] getUserObjectPath()
  {
    TreeNode[] path = getPathToRoot(this, 0);
    Object[] object = new Object[path.length];
    
    for (int index = 0; index < path.length; ++index)
      object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject();

    return object;
  }

  /**
   * Returns the root node by iterating the parents of this node.
   *
   * @return the root node
   */
  public TreeNode getRoot()
  {
    TreeNode current = this;
    TreeNode check = current.getParent();
    
    while (check != null)
      {
        current = check;
        check = current.getParent();
      }

    return current;
  }

  /**
   * Tells whether this node is the root node or not.
   *
   * @return <code>true</code> if this is the root node,
   * <code>false</code>otherwise
   */
  public boolean isRoot()
  {
    return parent == null;
  }

  /**
   * getNextNode
   *
   * @return DefaultMutableTreeNode
   */
  public DefaultMutableTreeNode getNextNode()
  {
    // Return first child.
    if (getChildCount() != 0)
      return (DefaultMutableTreeNode) getChildAt(0);

    // Return next sibling (if needed the sibling of some parent).
    DefaultMutableTreeNode node = this;
    DefaultMutableTreeNode sibling;
    
    do
      {
        sibling = node.getNextSibling();
        node = (DefaultMutableTreeNode) node.getParent();
      }
    while (sibling == null &&
           node != null);
    
    // Return sibling.
    return sibling;
  }

  /**
   * getPreviousNode
   *
   * @return DefaultMutableTreeNode
   */
  public DefaultMutableTreeNode getPreviousNode()
  {
    // Return null if no parent.
    if (parent == null)
      return null;
    
    DefaultMutableTreeNode sibling = getPreviousSibling();

    // Return parent if no sibling.
    if (sibling == null)
      return (DefaultMutableTreeNode) parent;

    // Return last leaf of sibling.
    if (sibling.getChildCount() != 0)
      return sibling.getLastLeaf();

    // Return sibling.
    return sibling;
  }

  /**
   * preorderEnumeration
   *
   * @return Enumeration
   */
  public Enumeration preorderEnumeration()
  {
    return new PreorderEnumeration(this);
  }

  /**
   * postorderEnumeration
   *
   * @return Enumeration
   */
  public Enumeration postorderEnumeration()
  {
    return new PostorderEnumeration(this);
  }

  /**
   * breadthFirstEnumeration
   *
   * @return Enumeration
   */
  public Enumeration breadthFirstEnumeration()
  {
    return new BreadthFirstEnumeration(this);
  }

  /**
   * depthFirstEnumeration
   *
   * @return Enumeration
   */
  public Enumeration depthFirstEnumeration()
  {
    return postorderEnumeration();
  }

  /**
   * pathFromAncestorEnumeration
   *
   * @param node TODO
   *
   * @return Enumeration
   */
  public Enumeration pathFromAncestorEnumeration(TreeNode node)
  {
    if (node == null)
      throw new IllegalArgumentException();
    
    TreeNode parent = this;
    Vector nodes = new Vector();
    nodes.add(this);

    while (parent != node && parent != null)
      {
        parent = parent.getParent();
        nodes.add(0, parent);
      }

    if (parent != node)
      throw new IllegalArgumentException();
    
    return nodes.elements();
  }

  /**
   * Returns <code>true</code> if <code>node</code> is a child of this tree 
   * node, and <code>false</code> otherwise.  If <code>node</code> is 
   * <code>null</code>, this method returns <code>false</code>.
   *
   * @param node  the node (<code>null</code> permitted).
   *
   * @return A boolean.
   */
  public boolean isNodeChild(TreeNode node)
  {
    if (node == null)
      return false;

    return node.getParent() == this;
  }

  /**
   * Returns the first child node belonging to this tree node.
   *
   * @return The first child node.
   * 
   * @throws NoSuchElementException if this tree node has no children.
   */
  public TreeNode getFirstChild()
  {
    return (TreeNode) children.firstElement();
  }

  /**
   * Returns the last child node belonging to this tree node.
   *
   * @return The last child node.
   * 
   * @throws NoSuchElementException if this tree node has no children.
   */
  public TreeNode getLastChild()
  {
    return (TreeNode) children.lastElement();
  }

  /**
   * Returns the next child after the specified <code>node</code>, or 
   * <code>null</code> if there is no child after the specified 
   * <code>node</code>.
   *
   * @param node  a child of this node (<code>null</code> not permitted).
   *
   * @return The next child, or <code>null</code>.
   * 
   * @throws IllegalArgumentException if <code>node</code> is not a child of 
   *     this node, or is <code>null</code>.
   */
  public TreeNode getChildAfter(TreeNode node)
  {
    if (node == null || node.getParent() != this)
      throw new IllegalArgumentException();

    int index = getIndex(node) + 1;

    if (index == getChildCount())
      return null;

    return getChildAt(index);
  }

  /**
   * Returns the previous child before the specified <code>node</code>, or 
   * <code>null</code> if there is no child before the specified 
   * <code>node</code>.
   *
   * @param node  a child of this node (<code>null</code> not permitted).
   *
   * @return The previous child, or <code>null</code>.
   * 
   * @throws IllegalArgumentException if <code>node</code> is not a child of 
   *     this node, or is <code>null</code>.
   */
  public TreeNode getChildBefore(TreeNode node)
  {
    if (node == null || node.getParent() != this)
      throw new IllegalArgumentException();

    int index = getIndex(node) - 1;

    if (index < 0)
      return null;

    return getChildAt(index);
  }

  /**
   * Returns <code>true</code> if this tree node and <code>node</code> share
   * the same parent.  If <code>node</code> is this tree node, the method
   * returns <code>true</code> and if <code>node</code> is <code>null</code>
   * this method returns <code>false</code>.
   *
   * @param node  the node (<code>null</code> permitted).
   *
   * @return A boolean.
   */
  public boolean isNodeSibling(TreeNode node)
  {
    if (node == null)
      return false;
    if (node == this)
      return true;
    return (node.getParent() == getParent()
            && getParent() != null);
  }

  /**
   * Returns the number of siblings for this tree node.  If the tree node has
   * a parent, this method returns the child count for the parent, otherwise
   * it returns <code>1</code>.
   *
   * @return The sibling count.
   */
  public int getSiblingCount()
  {
    if (parent == null)
      return 1;

    return parent.getChildCount();
  }

  /**
   * Returns the next sibling for this tree node.  If this node has no parent,
   * or this node is the last child of its parent, this method returns 
   * <code>null</code>.  
   *
   * @return The next sibling, or <code>null</code>.
   */
  public DefaultMutableTreeNode getNextSibling()
  {
    if (parent == null)
      return null;

    int index = parent.getIndex(this) + 1;
    
    if (index == parent.getChildCount())
      return null;

    return (DefaultMutableTreeNode) parent.getChildAt(index);
  }

  /**
   * Returns the previous sibling for this tree node.  If this node has no 
   * parent, or this node is the first child of its parent, this method returns 
   * <code>null</code>.  
   *
   * @return The previous sibling, or <code>null</code>.
   */
  public DefaultMutableTreeNode getPreviousSibling()
  {
    if (parent == null)
      return null;

    int index = parent.getIndex(this) - 1;

    if (index < 0)
      return null;

    return (DefaultMutableTreeNode) parent.getChildAt(index);
  }

  /**
   * Returns <code>true</code> if this tree node is a lead node (that is, it 
   * has no children), and <code>false</otherwise>.
   *
   * @return A boolean.
   */
  public boolean isLeaf()
  {
    return children.size() == 0;
  }

  /**
   * Returns the first leaf node that is a descendant of this node.  Recall 
   * that a node is its own descendant, so if this node has no children then 
   * it is returned as the first leaf.
   *
   * @return The first leaf node.
   */
  public DefaultMutableTreeNode getFirstLeaf()
  {
    TreeNode current = this;
    
    while (current.getChildCount() > 0)
      current = current.getChildAt(0);

    return (DefaultMutableTreeNode) current;
  }

  /**
   * Returns the last leaf node that is a descendant of this node.  Recall 
   * that a node is its own descendant, so if this node has no children then 
   * it is returned as the last leaf.
   *
   * @return The first leaf node.
   */
  public DefaultMutableTreeNode getLastLeaf()
  {
    TreeNode current = this;
    int size = current.getChildCount();
    
    while (size > 0)
      {
        current = current.getChildAt(size - 1);
        size = current.getChildCount();
      }

    return (DefaultMutableTreeNode) current;
  }

  /**
   * Returns the next leaf node after this tree node. 
   *
   * @return The next leaf node, or <code>null</code>.
   */
  public DefaultMutableTreeNode getNextLeaf()
  {
    // if there is a next sibling, return its first leaf
    DefaultMutableTreeNode sibling = getNextSibling();
    if (sibling != null)
      return sibling.getFirstLeaf();
    // otherwise move up one level and try again...
    if (parent != null)
      return ((DefaultMutableTreeNode) parent).getNextLeaf();
    return null;
  }

  /**
   * Returns the previous leaf node before this tree node.
   *
   * @return The previous leaf node, or <code>null</code>.
   */
  public DefaultMutableTreeNode getPreviousLeaf()
  {
    // if there is a previous sibling, return its last leaf
    DefaultMutableTreeNode sibling = getPreviousSibling();
    if (sibling != null)
      return sibling.getLastLeaf();
    // otherwise move up one level and try again...
    if (parent != null)
      return ((DefaultMutableTreeNode) parent).getPreviousLeaf();
    return null;
  }

  /**
   * getLeafCount
   *
   * @return int
   */
  public int getLeafCount()
  {
    int count = 0;
    Enumeration e = depthFirstEnumeration();

    while (e.hasMoreElements())
      {
        TreeNode current = (TreeNode) e.nextElement();
        
        if (current.isLeaf())
          count++;
      }

    return count;
  }

  /** Provides an enumeration of a tree in breadth-first traversal
   * order.
   */
  static class BreadthFirstEnumeration implements Enumeration
  {

      LinkedList queue = new LinkedList();

      BreadthFirstEnumeration(TreeNode node)
      {
          queue.add(node);
      }

      public boolean hasMoreElements()
      {
          return !queue.isEmpty();
      }

      public Object nextElement()
      {
          if(queue.isEmpty())
              throw new NoSuchElementException("No more elements left.");

          TreeNode node = (TreeNode) queue.removeFirst();

          Enumeration children = node.children();
          while (children.hasMoreElements())
              queue.add(children.nextElement());

          return node;
      }
  }

  /** Provides an enumeration of a tree traversing it
   * preordered.
   */
  static class PreorderEnumeration implements Enumeration
  {
	  TreeNode next;

      Stack childrenEnums = new Stack();

      PreorderEnumeration(TreeNode node)
      {
          next = node;
          childrenEnums.push(node.children());
      }

      public boolean hasMoreElements()
      {
          return next != null;
      }

      public Object nextElement()
      {
          if( next == null )
              throw new NoSuchElementException("No more elements left.");

          Object current = next;

          Enumeration children = (Enumeration) childrenEnums.peek();

          // Retrieves the next element.
          next = traverse(children);

          return current;
      }

      private TreeNode traverse(Enumeration children)
      {
          // If more children are available step down.
          if( children.hasMoreElements() )
          {
              TreeNode child = (TreeNode) children.nextElement();
              childrenEnums.push(child.children());

              return child;
          }
          
          // If no children are left, we return to a higher level.
          childrenEnums.pop();

          // If there are no more levels left, there is no next
          // element to return.
          if ( childrenEnums.isEmpty() )
              return null;
          else
          {
              return traverse((Enumeration) childrenEnums.peek());
          }
      }
   }

  /** Provides an enumeration of a tree traversing it
   * postordered (= depth-first).
   */
   static class PostorderEnumeration implements Enumeration
   {

       Stack nodes = new Stack();
       Stack childrenEnums = new Stack();

       PostorderEnumeration(TreeNode node)
       {
           nodes.push(node);
           childrenEnums.push(node.children());
       }

       public boolean hasMoreElements()
       {
           return !nodes.isEmpty();
       }

       public Object nextElement()
       {
           if( nodes.isEmpty() )
               throw new NoSuchElementException("No more elements left!");

           Enumeration children = (Enumeration) childrenEnums.peek();

           return traverse(children);
       }

       private Object traverse(Enumeration children)
       {
           if ( children.hasMoreElements() )
           {
               TreeNode node = (TreeNode) children.nextElement();
               nodes.push(node);

               Enumeration newChildren = node.children();
               childrenEnums.push(newChildren);

               return traverse(newChildren);
           }
           else
           {
               childrenEnums.pop();

               // Returns the node whose children
               // have all been visited. (= postorder)
               Object next = nodes.peek();
               nodes.pop();

               return next;
           }
       }

    }

}