defaultmutabletreenode.java

gcc的组建

  /**
   * 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();
  }

  /**
   * isNodeChild
   *
   * @param node TODO
   *
   * @return boolean
   */
  public boolean isNodeChild(TreeNode node)
  {
    if (node == null)
      return false;

    return node.getParent() == this;
  }

  /**
   * getFirstChild
   *
   * @return TreeNode
   */
  public TreeNode getFirstChild()
  {
    return (TreeNode) children.firstElement();
  }

  /**
   * getLastChild
   *
   * @return TreeNode
   */
  public TreeNode getLastChild()
  {
    return (TreeNode) children.lastElement();
  }

  /**
   * getChildAfter
   *
   * @param node TODO
   *
   * @return TreeNode
   */
  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);
  }

  /**
   * getChildBefore
   *
   * @param node TODO
   *
   * @return TreeNode
   */
  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);
  }

  /**
   * isNodeSibling
   *
   * @param node TODO
   *
   * @return boolean
   */
  public boolean isNodeSibling(TreeNode node)
  {
    if (node == null)
      return false;

    return (node.getParent() == getParent()
            && getParent() != null);
  }

  /**
   * getSiblingCount
   *
   * @return int
   */
  public int getSiblingCount()
  {
    if (parent == null)
      return 1;

    return parent.getChildCount();
  }

  /**
   * getNextSibling
   *
   * @return DefaultMutableTreeNode
   */
  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);
  }

  /**
   * getPreviousSibling
   *
   * @return DefaultMutableTreeNode
   */
  public DefaultMutableTreeNode getPreviousSibling()
  {
    if (parent == null)
      return null;

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

    if (index < 0)
      return null;

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

  /**
   * isLeaf
   *
   * @return boolean
   */
  public boolean isLeaf()
  {
    return children.size() == 0;
  }

  /**
   * getFirstLeaf
   *
   * @return DefaultMutableTreeNode
   */
  public DefaultMutableTreeNode getFirstLeaf()
  {
    TreeNode current = this;
    
    while (current.getChildCount() > 0)
      current = current.getChildAt(0);

    return (DefaultMutableTreeNode) current;
  }

  /**
   * getLastLeaf
   *
   * @return DefaultMutableTreeNode
   */
  public DefaultMutableTreeNode getLastLeaf()
  {
    TreeNode current = this;
    int size = current.getChildCount();
    
    while (size > 0)
      {
        current = current.getChildAt(size - 1);
        size = current.getChildCount();
      }

    return (DefaultMutableTreeNode) current;
  }

  /**
   * getNextLeaf
   *
   * @return DefaultMutableTreeNode
   */
  public DefaultMutableTreeNode getNextLeaf()
  {
    if (parent == null)
      return null;

    // TODO: Fix implementation.
    return null;
    //return parent.getChildAfter(this);
  }

  /**
   * getPreviousLeaf
   *
   * @return DefaultMutableTreeNode
   */
  public DefaultMutableTreeNode getPreviousLeaf()
  {
    if (parent == null)
      return null;

    // TODO: Fix implementation.
    return null;
    //return parent.getChildBefore(this);
  }

  /**
   * 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;
           }
       }

    }

}