1 /* DefaultMutableTreeNode.java --
2 Copyright (C) 2002, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
39 package javax
.swing
.tree
;
41 import gnu
.java
.util
.EmptyEnumeration
;
43 import java
.io
.IOException
;
44 import java
.io
.ObjectInputStream
;
45 import java
.io
.ObjectOutputStream
;
46 import java
.io
.Serializable
;
47 import java
.util
.ArrayList
;
48 import java
.util
.Enumeration
;
49 import java
.util
.LinkedList
;
50 import java
.util
.NoSuchElementException
;
51 import java
.util
.Stack
;
52 import java
.util
.Vector
;
56 * DefaultMutableTreeNode
58 * @author Andrew Selkirk
59 * @author Robert Schuster (robertschuster@fsfe.org)
61 public class DefaultMutableTreeNode
62 implements Cloneable
, MutableTreeNode
, Serializable
64 private static final long serialVersionUID
= -4298474751201349152L;
69 public static final Enumeration EMPTY_ENUMERATION
=
70 EmptyEnumeration
.getInstance();
75 protected MutableTreeNode parent
;
80 protected Vector children
= new Vector();
85 protected transient Object userObject
;
90 protected boolean allowsChildren
;
93 * Creates a <code>DefaultMutableTreeNode</code> object.
94 * This node allows to add child nodes.
96 public DefaultMutableTreeNode()
102 * Creates a <code>DefaultMutableTreeNode</code> object with the given
103 * user object attached to it. This node allows to add child nodes.
105 * @param userObject the user object
107 public DefaultMutableTreeNode(Object userObject
)
109 this(userObject
, true);
113 * Creates a <code>DefaultMutableTreeNode</code> object with the given
114 * user object attached to it.
116 * @param userObject the user object
117 * @param allowsChildren <code>true</code> if the code allows to add child
118 * nodes, <code>false</code> otherwise
120 public DefaultMutableTreeNode(Object userObject
, boolean allowsChildren
)
122 this.userObject
= userObject
;
123 this.allowsChildren
= allowsChildren
;
131 public Object
clone()
135 return super.clone();
136 // TODO: Do we need to do more here ?
138 catch (CloneNotSupportedException e
)
140 // This never happens.
146 * Returns a string representation of this node
148 * @return a human-readable String representing this node
150 public String
toString()
152 if (userObject
== null)
155 return userObject
.toString();
159 * Adds a new child node to this node.
161 * @param child the child node
163 * @throws IllegalArgumentException if <code>child</code> is null
164 * @throws IllegalStateException if the node does not allow children
166 public void add(MutableTreeNode child
)
169 throw new IllegalArgumentException();
171 if (! allowsChildren
)
172 throw new IllegalStateException();
175 child
.setParent(this);
179 * Returns the parent node of this node.
181 * @return the parent node
183 public TreeNode
getParent()
189 * Removes the child with the given index from this node
191 * @param index the index
193 public void remove(int index
)
195 children
.remove(index
);
199 * Removes the given child from this node.
201 * @param node the child node
203 public void remove(MutableTreeNode node
)
205 children
.remove(node
);
211 * @param stream the output stream
213 * @exception IOException If an error occurs
215 private void writeObject(ObjectOutputStream stream
)
218 // TODO: Implement me.
224 * @param stream the input stream
226 * @exception IOException If an error occurs
227 * @exception ClassNotFoundException TODO
229 private void readObject(ObjectInputStream stream
)
230 throws IOException
, ClassNotFoundException
232 // TODO: Implement me.
236 * Inserts given child node at the given index.
238 * @param node the child node
239 * @param index the index.
241 public void insert(MutableTreeNode node
, int index
)
243 children
.insertElementAt(node
, index
);
247 * Returns a path to this node from the root.
249 * @return an array of tree nodes
251 public TreeNode
[] getPath()
253 return getPathToRoot(this, 0);
257 * Returns an enumeration containing all children of this node.
258 * <code>EMPTY_ENUMERATION</code> is returned if this node has no children.
260 * @return an enumeration of tree nodes
262 public Enumeration
children()
264 if (children
.size() == 0)
265 return EMPTY_ENUMERATION
;
267 return children
.elements();
271 * Set the parent node for this node.
273 * @param node the parent node
275 public void setParent(MutableTreeNode node
)
281 * Returns the child node at a given index.
283 * @param index the index
285 * @return the child node
287 public TreeNode
getChildAt(int index
)
289 return (TreeNode
) children
.elementAt(index
);
293 * Returns the number of children of this node.
295 * @return the number of children
297 public int getChildCount()
299 return children
.size();
303 * Returns the child index for a given node.
305 * @param node this node
309 public int getIndex(TreeNode node
)
311 return children
.indexOf(node
);
317 * @param allowsChildren TODO
319 public void setAllowsChildren(boolean allowsChildren
)
321 this.allowsChildren
= allowsChildren
;
329 public boolean getAllowsChildren()
331 return allowsChildren
;
335 * Sets the user object for this node
337 * @param userObject the user object
339 public void setUserObject(Object userObject
)
341 this.userObject
= userObject
;
345 * Returns the user object attached to this node. <code>null</code> is
346 * returned when no user object is set.
348 * @return the user object
350 public Object
getUserObject()
356 * Removes this node from its parent.
358 public void removeFromParent()
365 * Removes all child nodes from this node.
367 public void removeAllChildren()
369 children
.removeAllElements();
379 public boolean isNodeAncestor(TreeNode node
)
384 TreeNode current
= this;
386 while (current
!= null
388 current
= current
.getParent();
390 return current
== node
;
400 public boolean isNodeDescendant(DefaultMutableTreeNode node
)
405 TreeNode current
= node
;
407 while (current
!= null
409 current
= current
.getParent();
411 return current
== this;
421 public TreeNode
getSharedAncestor(DefaultMutableTreeNode node
)
423 TreeNode current
= this;
424 ArrayList list
= new ArrayList();
426 while (current
!= null)
429 current
= current
.getParent();
434 while (current
!= null)
436 if (list
.contains(current
))
439 current
= current
.getParent();
452 public boolean isNodeRelated(DefaultMutableTreeNode node
)
457 return node
.getRoot() == getRoot();
465 public int getDepth()
467 if ((! allowsChildren
)
468 || children
.size() == 0)
471 Stack stack
= new Stack();
472 stack
.push(new Integer(0));
473 TreeNode node
= getChildAt(0);
477 while (! stack
.empty())
479 if (node
.getChildCount() != 0)
481 node
= node
.getChildAt(0);
482 stack
.push(new Integer(0));
495 node
= node
.getParent();
496 size
= node
.getChildCount();
497 index
= ((Integer
) stack
.pop()).intValue() + 1;
505 node
= node
.getChildAt(index
);
506 stack
.push(new Integer(index
));
520 public int getLevel()
523 TreeNode current
= this;
527 current
= current
.getParent();
530 while (current
!= null);
543 protected TreeNode
[] getPathToRoot(TreeNode node
, int depth
)
550 return new TreeNode
[depth
];
553 TreeNode
[] path
= getPathToRoot(node
.getParent(), depth
+ 1);
554 path
[path
.length
- depth
- 1] = node
;
563 public Object
[] getUserObjectPath()
565 TreeNode
[] path
= getPathToRoot(this, 0);
566 Object
[] object
= new Object
[path
.length
];
568 for (int index
= 0; index
< path
.length
; ++index
)
569 object
[index
] = ((DefaultMutableTreeNode
) path
[index
]).getUserObject();
575 * Returns the root node by iterating the parents of this node.
577 * @return the root node
579 public TreeNode
getRoot()
581 TreeNode current
= this;
582 TreeNode check
= current
.getParent();
584 while (check
!= null)
587 check
= current
.getParent();
594 * Tells whether this node is the root node or not.
596 * @return <code>true</code> if this is the root node,
597 * <code>false</code>otherwise
599 public boolean isRoot()
601 return parent
== null;
607 * @return DefaultMutableTreeNode
609 public DefaultMutableTreeNode
getNextNode()
611 // Return first child.
612 if (getChildCount() != 0)
613 return (DefaultMutableTreeNode
) getChildAt(0);
615 // Return next sibling (if needed the sibling of some parent).
616 DefaultMutableTreeNode node
= this;
617 DefaultMutableTreeNode sibling
;
621 sibling
= node
.getNextSibling();
622 node
= (DefaultMutableTreeNode
) node
.getParent();
624 while (sibling
== null &&
634 * @return DefaultMutableTreeNode
636 public DefaultMutableTreeNode
getPreviousNode()
638 // Return null if no parent.
642 DefaultMutableTreeNode sibling
= getPreviousSibling();
644 // Return parent if no sibling.
646 return (DefaultMutableTreeNode
) parent
;
648 // Return last leaf of sibling.
649 if (sibling
.getChildCount() != 0)
650 return sibling
.getLastLeaf();
657 * preorderEnumeration
659 * @return Enumeration
661 public Enumeration
preorderEnumeration()
663 return new PreorderEnumeration(this);
667 * postorderEnumeration
669 * @return Enumeration
671 public Enumeration
postorderEnumeration()
673 return new PostorderEnumeration(this);
677 * breadthFirstEnumeration
679 * @return Enumeration
681 public Enumeration
breadthFirstEnumeration()
683 return new BreadthFirstEnumeration(this);
687 * depthFirstEnumeration
689 * @return Enumeration
691 public Enumeration
depthFirstEnumeration()
693 return postorderEnumeration();
697 * pathFromAncestorEnumeration
701 * @return Enumeration
703 public Enumeration
pathFromAncestorEnumeration(TreeNode node
)
706 throw new IllegalArgumentException();
708 TreeNode parent
= this;
709 Vector nodes
= new Vector();
712 while (parent
!= node
&& parent
!= null)
714 parent
= parent
.getParent();
715 nodes
.add(0, parent
);
719 throw new IllegalArgumentException();
721 return nodes
.elements();
731 public boolean isNodeChild(TreeNode node
)
736 return node
.getParent() == this;
744 public TreeNode
getFirstChild()
746 return (TreeNode
) children
.firstElement();
754 public TreeNode
getLastChild()
756 return (TreeNode
) children
.lastElement();
766 public TreeNode
getChildAfter(TreeNode node
)
769 || node
.getParent() != this)
770 throw new IllegalArgumentException();
772 int index
= getIndex(node
) + 1;
774 if (index
== getChildCount())
777 return getChildAt(index
);
787 public TreeNode
getChildBefore(TreeNode node
)
790 || node
.getParent() != this)
791 throw new IllegalArgumentException();
793 int index
= getIndex(node
) - 1;
798 return getChildAt(index
);
808 public boolean isNodeSibling(TreeNode node
)
813 return (node
.getParent() == getParent()
814 && getParent() != null);
822 public int getSiblingCount()
827 return parent
.getChildCount();
833 * @return DefaultMutableTreeNode
835 public DefaultMutableTreeNode
getNextSibling()
840 int index
= parent
.getIndex(this) + 1;
842 if (index
== parent
.getChildCount())
845 return (DefaultMutableTreeNode
) parent
.getChildAt(index
);
851 * @return DefaultMutableTreeNode
853 public DefaultMutableTreeNode
getPreviousSibling()
858 int index
= parent
.getIndex(this) - 1;
863 return (DefaultMutableTreeNode
) parent
.getChildAt(index
);
871 public boolean isLeaf()
873 return children
.size() == 0;
879 * @return DefaultMutableTreeNode
881 public DefaultMutableTreeNode
getFirstLeaf()
883 TreeNode current
= this;
885 while (current
.getChildCount() > 0)
886 current
= current
.getChildAt(0);
888 return (DefaultMutableTreeNode
) current
;
894 * @return DefaultMutableTreeNode
896 public DefaultMutableTreeNode
getLastLeaf()
898 TreeNode current
= this;
899 int size
= current
.getChildCount();
903 current
= current
.getChildAt(size
- 1);
904 size
= current
.getChildCount();
907 return (DefaultMutableTreeNode
) current
;
913 * @return DefaultMutableTreeNode
915 public DefaultMutableTreeNode
getNextLeaf()
920 // TODO: Fix implementation.
922 //return parent.getChildAfter(this);
928 * @return DefaultMutableTreeNode
930 public DefaultMutableTreeNode
getPreviousLeaf()
935 // TODO: Fix implementation.
937 //return parent.getChildBefore(this);
945 public int getLeafCount()
948 Enumeration e
= depthFirstEnumeration();
950 while (e
.hasMoreElements())
952 TreeNode current
= (TreeNode
) e
.nextElement();
954 if (current
.isLeaf())
961 /** Provides an enumeration of a tree in breadth-first traversal
964 static class BreadthFirstEnumeration
implements Enumeration
967 LinkedList queue
= new LinkedList();
969 BreadthFirstEnumeration(TreeNode node
)
974 public boolean hasMoreElements()
976 return !queue
.isEmpty();
979 public Object
nextElement()
982 throw new NoSuchElementException("No more elements left.");
984 TreeNode node
= (TreeNode
) queue
.removeFirst();
986 Enumeration children
= node
.children();
987 while (children
.hasMoreElements())
988 queue
.add(children
.nextElement());
994 /** Provides an enumeration of a tree traversing it
997 static class PreorderEnumeration
implements Enumeration
1001 Stack childrenEnums
= new Stack();
1003 PreorderEnumeration(TreeNode node
)
1006 childrenEnums
.push(node
.children());
1009 public boolean hasMoreElements()
1011 return next
!= null;
1014 public Object
nextElement()
1017 throw new NoSuchElementException("No more elements left.");
1019 Object current
= next
;
1021 Enumeration children
= (Enumeration
) childrenEnums
.peek();
1023 // Retrieves the next element.
1024 next
= traverse(children
);
1029 private TreeNode
traverse(Enumeration children
)
1031 // If more children are available step down.
1032 if( children
.hasMoreElements() )
1034 TreeNode child
= (TreeNode
) children
.nextElement();
1035 childrenEnums
.push(child
.children());
1040 // If no children are left, we return to a higher level.
1041 childrenEnums
.pop();
1043 // If there are no more levels left, there is no next
1044 // element to return.
1045 if ( childrenEnums
.isEmpty() )
1049 return traverse((Enumeration
) childrenEnums
.peek());
1054 /** Provides an enumeration of a tree traversing it
1055 * postordered (= depth-first).
1057 static class PostorderEnumeration
implements Enumeration
1060 Stack nodes
= new Stack();
1061 Stack childrenEnums
= new Stack();
1063 PostorderEnumeration(TreeNode node
)
1066 childrenEnums
.push(node
.children());
1069 public boolean hasMoreElements()
1071 return !nodes
.isEmpty();
1074 public Object
nextElement()
1076 if( nodes
.isEmpty() )
1077 throw new NoSuchElementException("No more elements left!");
1079 Enumeration children
= (Enumeration
) childrenEnums
.peek();
1081 return traverse(children
);
1084 private Object
traverse(Enumeration children
)
1086 if ( children
.hasMoreElements() )
1088 TreeNode node
= (TreeNode
) children
.nextElement();
1091 Enumeration newChildren
= node
.children();
1092 childrenEnums
.push(newChildren
);
1094 return traverse(newChildren
);
1098 childrenEnums
.pop();
1100 // Returns the node whose children
1101 // have all been visited. (= postorder)
1102 Object next
= nodes
.peek();