001 package echopointng.tree;
002
003 /*
004 * This file is part of the Echo Point Project. This project is a collection
005 * of Components that have extended the Echo Web Application Framework.
006 *
007 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
008 *
009 * The contents of this file are subject to the Mozilla Public License Version
010 * 1.1 (the "License"); you may not use this file except in compliance with
011 * the License. You may obtain a copy of the License at
012 * http://www.mozilla.org/MPL/
013 *
014 * Software distributed under the License is distributed on an "AS IS" basis,
015 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
016 * for the specific language governing rights and limitations under the
017 * License.
018 *
019 * Alternatively, the contents of this file may be used under the terms of
020 * either the GNU General Public License Version 2 or later (the "GPL"), or
021 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
022 * in which case the provisions of the GPL or the LGPL are applicable instead
023 * of those above. If you wish to allow use of your version of this file only
024 * under the terms of either the GPL or the LGPL, and not to allow others to
025 * use your version of this file under the terms of the MPL, indicate your
026 * decision by deleting the provisions above and replace them with the notice
027 * and other provisions required by the GPL or the LGPL. If you do not delete
028 * the provisions above, a recipient may use your version of this file under
029 * the terms of any one of the MPL, the GPL or the LGPL.
030 */
031
032 /*
033 * The design paradigm and class name used within have been taken directly from
034 * the java.swing package has been retro-fitted to work with the NextApp Echo web framework.
035 *
036 * This file was made part of the EchoPoint project on the 25/07/2002.
037 *
038 */
039
040 import java.io.Serializable;
041 import java.util.Vector;
042 import java.util.Stack;
043 import java.util.Enumeration;
044 import java.util.NoSuchElementException;
045 import java.util.EmptyStackException;
046
047 /**
048 * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
049 * structure. A tree node may have at most one parent and 0 or more children.
050 * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a
051 * node's parent and children and also operations for examining the tree that
052 * the node is a part of. A node's tree is the set of all nodes that can be
053 * reached by starting at the node and following all the possible links to
054 * parents and children. A node with no parent is the root of its tree; a
055 * node with no children is a leaf. A tree may consist of many subtrees,
056 * each node acting as the root for its own subtree.
057 * <p>
058 * This class provides enumerations for efficiently traversing a tree or
059 * subtree in various orders or for following the path between two nodes.
060 * <p>
061 * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
062 * use of which is left to the user. Asking a <code>DefaultMutableTreeNode</code> for its
063 * string representation with <code>toString()</code> returns the string
064 * representation of its user object.
065 * <p>
066 * <b>This is not a thread safe class.</b>If you intend to use
067 * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
068 * need to do your own synchronizing. A good convention to adopt is
069 * synchronizing on the root node of a tree.
070 * <p>
071 * While DefaultMutableTreeNode implements the MutableTreeNode interface and
072 * will allow you to add in any implementation of MutableTreeNode not all
073 * of the methods in DefaultMutableTreeNode will be applicable to all
074 * MutableTreeNodes implementations. Especially with some of the enumerations
075 * that are provided, using some of these methods assumes the
076 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All
077 * of the TreeNode/MutableTreeNode methods will behave as defined no
078 * matter what implementations are added.
079 * <p>
080 *
081 */
082 public class DefaultMutableTreeNode implements MutableTreeNode, Serializable {
083
084 /** this node's action command */
085 protected String actionCommand;
086
087 /** this node's parent, or null if this node has no parent */
088 protected MutableTreeNode parent;
089
090 /** array of children, may be null if this node has no children */
091 protected Vector children;
092
093 /** optional user object */
094 transient protected Object userObject;
095
096 /** true if the node is able to have children */
097 protected boolean allowsChildren;
098
099 /**
100 * An enumeration that is always empty. This is used when an enumeration
101 * of a leaf node's children is requested.
102 */
103 public static final Enumeration EMPTY_ENUMERATION = new Enumeration() {
104 public boolean hasMoreElements() {
105 return false;
106 }
107 public Object nextElement() {
108 throw new NoSuchElementException("No more elements");
109 }
110 };
111
112 public final class PreorderEnumeration implements Enumeration, Serializable {
113 protected Stack stack;
114
115 public PreorderEnumeration(TreeNode rootNode) {
116 super();
117 Vector v = new Vector(1);
118 v.addElement(rootNode);
119 stack = new Stack();
120 stack.push(v.elements());
121 }
122
123 public boolean hasMoreElements() {
124 return (!stack.empty() && ((Enumeration) stack.peek()).hasMoreElements());
125 }
126
127 public Object nextElement() {
128 Enumeration enumer = (Enumeration) stack.peek();
129 TreeNode node = (TreeNode) enumer.nextElement();
130 Enumeration children = node.children();
131
132 if (!enumer.hasMoreElements()) {
133 stack.pop();
134 }
135 if (children.hasMoreElements()) {
136 stack.push(children);
137 }
138 return node;
139 }
140
141 }
142
143 public final class PostorderEnumeration implements Enumeration, Serializable {
144 protected TreeNode root;
145 protected Enumeration children;
146 protected Enumeration subtree;
147
148 public PostorderEnumeration(TreeNode rootNode) {
149 super();
150 root = rootNode;
151 children = root.children();
152 subtree = EMPTY_ENUMERATION;
153 }
154
155 public boolean hasMoreElements() {
156 return root != null;
157 }
158
159 public Object nextElement() {
160 Object retval;
161
162 if (subtree.hasMoreElements()) {
163 retval = subtree.nextElement();
164 } else if (children.hasMoreElements()) {
165 subtree = new PostorderEnumeration((TreeNode) children.nextElement());
166 retval = subtree.nextElement();
167 } else {
168 retval = root;
169 root = null;
170 }
171
172 return retval;
173 }
174
175 }
176
177 public final class BreadthFirstEnumeration implements Enumeration, Serializable {
178 protected Queue queue;
179
180 public BreadthFirstEnumeration(TreeNode rootNode) {
181 super();
182 Vector v = new Vector(1);
183 v.addElement(rootNode);
184 queue = new Queue();
185 queue.enqueue(v.elements());
186 }
187
188 public boolean hasMoreElements() {
189 return (!queue.isEmpty() && ((Enumeration) queue.firstObject()).hasMoreElements());
190 }
191
192 public Object nextElement() {
193 Enumeration enumer = (Enumeration) queue.firstObject();
194 TreeNode node = (TreeNode) enumer.nextElement();
195 Enumeration children = node.children();
196
197 if (!enumer.hasMoreElements()) {
198 queue.dequeue();
199 }
200 if (children.hasMoreElements()) {
201 queue.enqueue(children);
202 }
203 return node;
204 }
205
206 // A simple queue with a linked list data structure.
207 final class Queue {
208 QNode head; // null if empty
209 QNode tail;
210
211 final class QNode {
212 public Object object;
213 public QNode next; // null if end
214 public QNode(Object object, QNode next) {
215 this.object = object;
216 this.next = next;
217 }
218 }
219
220 public void enqueue(Object anObject) {
221 if (head == null) {
222 head = tail = new QNode(anObject, null);
223 } else {
224 tail.next = new QNode(anObject, null);
225 tail = tail.next;
226 }
227 }
228
229 public Object dequeue() {
230 if (head == null) {
231 throw new NoSuchElementException("No more elements");
232 }
233
234 Object retval = head.object;
235 QNode oldHead = head;
236 head = head.next;
237 if (head == null) {
238 tail = null;
239 } else {
240 oldHead.next = null;
241 }
242 return retval;
243 }
244
245 public Object firstObject() {
246 if (head == null) {
247 throw new NoSuchElementException("No more elements");
248 }
249
250 return head.object;
251 }
252
253 public boolean isEmpty() {
254 return head == null;
255 }
256
257 } // End of class Queue
258
259 }
260
261 public final class PathBetweenNodesEnumeration implements Enumeration, Serializable {
262 protected Stack stack;
263
264 public PathBetweenNodesEnumeration(TreeNode ancestor, TreeNode descendant) {
265 super();
266
267 if (ancestor == null || descendant == null) {
268 throw new IllegalArgumentException("argument is null");
269 }
270
271 TreeNode current;
272
273 stack = new Stack();
274 stack.push(descendant);
275
276 current = descendant;
277 while (current != ancestor) {
278 current = current.getParent();
279 if (current == null && descendant != ancestor) {
280 throw new IllegalArgumentException("node " + ancestor + " is not an ancestor of " + descendant);
281 }
282 stack.push(current);
283 }
284 }
285
286 public boolean hasMoreElements() {
287 return stack.size() > 0;
288 }
289
290 public Object nextElement() {
291 try {
292 return stack.pop();
293 } catch (EmptyStackException e) {
294 throw new NoSuchElementException("No more elements");
295 }
296 }
297
298 }
299
300 /**
301 * Creates a tree node that has no parent and no children, but which
302 * allows children.
303 */
304 public DefaultMutableTreeNode() {
305 super();
306 }
307 /**
308 * Creates a tree node with no parent, no children, but which allows
309 * children, and initializes it with the specified user object.
310 *
311 * @param userObject an Object provided by the user that constitutes
312 * the node's data
313 */
314 public DefaultMutableTreeNode(Object userObject) {
315 this(userObject, true);
316 }
317 /**
318 * Creates a tree node with no parent, no children, initialized with
319 * the specified user object, and that allows children only if
320 * specified.
321 *
322 * @param userObject an Object provided by the user that constitutes
323 * the node's data
324 * @param allowsChildren if true, the node is allowed to have child
325 * nodes -- otherwise, it is always a leaf node
326 */
327 public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) {
328 super();
329 parent = null;
330 this.allowsChildren = allowsChildren;
331 this.userObject = userObject;
332 }
333 /**
334 * Removes <code>newChild</code> from its parent and makes it a child of
335 * this node by adding it to the end of this node's child array.
336 *
337 * @exception IllegalArgumentException if <code>newChild</code>
338 * is null
339 * @exception IllegalStateException if this node does not allow
340 * children
341 */
342 public void add(MutableTreeNode newChild) {
343 if (newChild != null && newChild.getParent() == this)
344 insert(newChild, getChildCount() - 1);
345 else
346 insert(newChild, getChildCount());
347 }
348 /**
349 * Creates and returns an enumeration that traverses the subtree rooted at
350 * this node in breadth-first order. The first node returned by the
351 * enumeration's <code>nextElement()</code> method is this node.<P>
352 *
353 * Modifying the tree by inserting, removing, or moving a node invalidates
354 * any enumerations created before the modification.
355 *
356 * @return an enumeration for traversing the tree in breadth-first order
357 */
358 public Enumeration breadthFirstEnumeration() {
359 return new BreadthFirstEnumeration(this);
360 }
361 /**
362 * Creates and returns a forward-order enumeration of this node's
363 * children. Modifying this node's child array invalidates any child
364 * enumerations created before the modification.
365 *
366 * @return an Enumeration of this node's children
367 */
368 public Enumeration children() {
369 if (children == null) {
370 return EMPTY_ENUMERATION;
371 } else {
372 return children.elements();
373 }
374 }
375 /**
376 * Creates and returns an enumeration that traverses the subtree rooted at
377 * this node in depth-first order. The first node returned by the
378 * enumeration's <code>nextElement()</code> method is the leftmost leaf.
379 * This is the same as a postorder traversal.<P>
380 *
381 * Modifying the tree by inserting, removing, or moving a node invalidates
382 * any enumerations created before the modification.
383 *
384 * @return an enumeration for traversing the tree in depth-first order
385 */
386 public Enumeration depthFirstEnumeration() {
387 return postorderEnumeration();
388 }
389 /**
390 * Returns the Action command string associated with this node
391 */
392 public String getActionCommand() {
393 return actionCommand;
394 }
395 /**
396 * Returns true if this node is allowed to have children.
397 *
398 * @return true if this node allows children, else false
399 */
400 public boolean getAllowsChildren() {
401 return allowsChildren;
402 }
403 /**
404 * Returns the child in this node's child array that immediately
405 * follows <code>aChild</code>, which must be a child of this node. If
406 * <code>aChild</code> is the last child, returns null. This method
407 * performs a linear search of this node's children for
408 * <code>aChild</code> and is O(n) where n is the number of children; to
409 * traverse the entire array of children, use an enumeration instead.
410 *
411 * @exception IllegalArgumentException if <code>aChild</code> is
412 * null or is not a child of this node
413 * @return the child of this node that immediately follows
414 * <code>aChild</code>
415 */
416 public TreeNode getChildAfter(TreeNode aChild) {
417 if (aChild == null) {
418 throw new IllegalArgumentException("argument is null");
419 }
420
421 int index = getIndex(aChild); // linear search
422
423 if (index == -1) {
424 throw new IllegalArgumentException("node is not a child");
425 }
426
427 if (index < getChildCount() - 1) {
428 return getChildAt(index + 1);
429 } else {
430 return null;
431 }
432 }
433 /**
434 * Returns the child at the specified index in this node's child array.
435 *
436 * @param index an index into this node's child array
437 * @exception ArrayIndexOutOfBoundsException if <code>index</code>
438 * is out of bounds
439 * @return the TreeNode in this node's child array at the specified index
440 */
441 public TreeNode getChildAt(int index) {
442 if (children == null) {
443 throw new ArrayIndexOutOfBoundsException("node has no children");
444 }
445 return (TreeNode) children.elementAt(index);
446 }
447 /**
448 * Returns the child in this node's child array that immediately
449 * precedes <code>aChild</code>, which must be a child of this node. If
450 * <code>aChild</code> is the first child, returns null. This method
451 * performs a linear search of this node's children for <code>aChild</code>
452 * and is O(n) where n is the number of children.
453 *
454 * @exception IllegalArgumentException if <code>aChild</code> is null
455 * or is not a child of this node
456 * @return the child of this node that immediately precedes
457 * <code>aChild</code>
458 */
459 public TreeNode getChildBefore(TreeNode aChild) {
460 if (aChild == null) {
461 throw new IllegalArgumentException("argument is null");
462 }
463
464 int index = getIndex(aChild); // linear search
465
466 if (index == -1) {
467 throw new IllegalArgumentException("argument is not a child");
468 }
469
470 if (index > 0) {
471 return getChildAt(index - 1);
472 } else {
473 return null;
474 }
475 }
476 /**
477 * Returns the number of children of this node.
478 *
479 * @return an int giving the number of children of this node
480 */
481 public int getChildCount() {
482 if (children == null) {
483 return 0;
484 } else {
485 return children.size();
486 }
487 }
488 /**
489 * Returns the depth of the tree rooted at this node -- the longest
490 * distance from this node to a leaf. If this node has no children,
491 * returns 0. This operation is much more expensive than
492 * <code>getLevel()</code> because it must effectively traverse the entire
493 * tree rooted at this node.
494 *
495 * @return the depth of the tree whose root is this node
496 */
497 public int getDepth() {
498 Object last = null;
499 Enumeration enumeration = breadthFirstEnumeration();
500
501 while (enumeration.hasMoreElements()) {
502 last = enumeration.nextElement();
503 }
504
505 if (last == null) {
506 throw new InternalError("nodes should be null");
507 }
508
509 return ((DefaultMutableTreeNode) last).getLevel() - getLevel();
510 }
511 /**
512 * Returns this node's first child. If this node has no children,
513 * throws NoSuchElementException.
514 *
515 * @return the first child of this node
516 * @exception NoSuchElementException if this node has no children
517 */
518 public TreeNode getFirstChild() {
519 if (getChildCount() == 0) {
520 throw new NoSuchElementException("node has no children");
521 }
522 return getChildAt(0);
523 }
524 /**
525 * Finds and returns the first leaf that is a descendant of this node --
526 * either this node or its first child's first leaf.
527 * Returns this node if it is a leaf.
528 *
529 * @return the first leaf in the subtree rooted at this node
530 */
531 public DefaultMutableTreeNode getFirstLeaf() {
532 DefaultMutableTreeNode node = this;
533
534 while (!node.isLeaf()) {
535 node = (DefaultMutableTreeNode) node.getFirstChild();
536 }
537
538 return node;
539 }
540 /**
541 * Returns the index of the specified child in this node's child array.
542 * If the specified node is not a child of this node, returns
543 * <code>-1</code>. This method performs a linear search and is O(n)
544 * where n is the number of children.
545 *
546 * @param aChild the TreeNode to search for among this node's children
547 * @exception IllegalArgumentException if <code>aChild</code>
548 * is null
549 * @return an int giving the index of the node in this node's child
550 * array, or <code>-1</code> if the specified node is a not
551 * a child of this node
552 */
553 public int getIndex(TreeNode aChild) {
554 if (aChild == null) {
555 throw new IllegalArgumentException("argument is null");
556 }
557
558 if (!isNodeChild(aChild)) {
559 return -1;
560 }
561 return children.indexOf(aChild); // linear search
562 }
563 /**
564 * Returns this node's last child. If this node has no children,
565 * throws NoSuchElementException.
566 *
567 * @return the last child of this node
568 * @exception NoSuchElementException if this node has no children
569 */
570 public TreeNode getLastChild() {
571 if (getChildCount() == 0) {
572 throw new NoSuchElementException("node has no children");
573 }
574 return getChildAt(getChildCount() - 1);
575 }
576 /**
577 * Finds and returns the last leaf that is a descendant of this node --
578 * either this node or its last child's last leaf.
579 * Returns this node if it is a leaf.
580 *
581 * @return the last leaf in the subtree rooted at this node
582 */
583 public DefaultMutableTreeNode getLastLeaf() {
584 DefaultMutableTreeNode node = this;
585
586 while (!node.isLeaf()) {
587 node = (DefaultMutableTreeNode) node.getLastChild();
588 }
589
590 return node;
591 }
592 /**
593 * Returns the total number of leaves that are descendants of this node.
594 * If this node is a leaf, returns <code>1</code>. This method is O(n)
595 * where n is the number of descendants of this node.
596 *
597 * @return the number of leaves beneath this node
598 */
599 public int getLeafCount() {
600 int count = 0;
601
602 TreeNode node;
603 Enumeration enumeration = breadthFirstEnumeration(); // order matters not
604
605 while (enumeration.hasMoreElements()) {
606 node = (TreeNode) enumeration.nextElement();
607 if (node.isLeaf()) {
608 count++;
609 }
610 }
611
612 if (count < 1) {
613 throw new InternalError("tree has zero leaves");
614 }
615
616 return count;
617 }
618 /**
619 * Returns the number of levels above this node -- the distance from
620 * the root to this node. If this node is the root, returns 0.
621 *
622 * @return the number of levels above this node
623 */
624 public int getLevel() {
625 TreeNode ancestor;
626 int levels = 0;
627
628 ancestor = this;
629 while ((ancestor = ancestor.getParent()) != null) {
630 levels++;
631 }
632
633 return levels;
634 }
635 /**
636 * Returns the leaf after this node or null if this node is the
637 * last leaf in the tree.
638 * <p>
639 * In this implementation of the <code>MutableNode</code> interface,
640 * this operation is very inefficient. In order to determine the
641 * next node, this method first performs a linear search in the
642 * parent's child-list in order to find the current node.
643 * <p>
644 * That implementation makes the operation suitable for short
645 * traversals from a known position. But to traverse all of the
646 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
647 * to enumerate the nodes in the tree and use <code>isLeaf</code>
648 * on each node to determine which are leaves.
649 *
650 */
651 public DefaultMutableTreeNode getNextLeaf() {
652 DefaultMutableTreeNode nextSibling;
653 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
654
655 if (myParent == null)
656 return null;
657
658 nextSibling = getNextSibling(); // linear search
659
660 if (nextSibling != null)
661 return nextSibling.getFirstLeaf();
662
663 return myParent.getNextLeaf(); // tail recursion
664 }
665 /**
666 * Returns the node that follows this node in a preorder traversal of this
667 * node's tree. Returns null if this node is the last node of the
668 * traversal. This is an inefficient way to traverse the entire tree; use
669 * an enumeration, instead.
670 *
671 */
672 public DefaultMutableTreeNode getNextNode() {
673 if (getChildCount() == 0) {
674 // No children, so look for nextSibling
675 DefaultMutableTreeNode nextSibling = getNextSibling();
676
677 if (nextSibling == null) {
678 DefaultMutableTreeNode aNode = (DefaultMutableTreeNode) getParent();
679
680 do {
681 if (aNode == null) {
682 return null;
683 }
684
685 nextSibling = aNode.getNextSibling();
686 if (nextSibling != null) {
687 return nextSibling;
688 }
689
690 aNode = (DefaultMutableTreeNode) aNode.getParent();
691 } while (true);
692 } else {
693 return nextSibling;
694 }
695 } else {
696 return (DefaultMutableTreeNode) getChildAt(0);
697 }
698 }
699 /**
700 * Returns the next sibling of this node in the parent's children array.
701 * Returns null if this node has no parent or is the parent's last child.
702 * This method performs a linear search that is O(n) where n is the number
703 * of children; to traverse the entire array, use the parent's child
704 * enumeration instead.
705 *
706 */
707 public DefaultMutableTreeNode getNextSibling() {
708 DefaultMutableTreeNode retval;
709
710 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
711
712 if (myParent == null) {
713 retval = null;
714 } else {
715 retval = (DefaultMutableTreeNode) myParent.getChildAfter(this);
716 // linear search
717 }
718
719 if (retval != null && !isNodeSibling(retval)) {
720 throw new InternalError("child of parent is not a sibling");
721 }
722
723 return retval;
724 }
725 /**
726 * Returns this node's parent or null if this node has no parent.
727 *
728 * @return this node's parent TreeNode, or null if this node has no parent
729 */
730 public TreeNode getParent() {
731 return parent;
732 }
733 /**
734 * Returns the path from the root, to get to this node. The last
735 * element in the path is this node.
736 *
737 * @return an array of TreeNode objects giving the path, where the
738 * first element in the path is the root and the last
739 * element is this node.
740 */
741 public TreeNode[] getPath() {
742 return getPathToRoot(this, 0);
743 }
744 /**
745 * Builds the parents of node up to and including the root node,
746 * where the original node is the last element in the returned array.
747 * The length of the returned array gives the node's depth in the
748 * tree.
749 *
750 * @param aNode the TreeNode to get the path for
751 * @param depth an int giving the number of steps already taken towards
752 * the root (on recursive calls), used to size the returned array
753 * @return an array of TreeNodes giving the path from the root to the
754 * specified node
755 */
756 protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) {
757 TreeNode[] retNodes;
758
759 /* Check for null, in case someone passed in a null node, or
760 they passed in an element that isn't rooted at root. */
761 if (aNode == null) {
762 if (depth == 0)
763 return null;
764 else
765 retNodes = new TreeNode[depth];
766 } else {
767 depth++;
768 retNodes = getPathToRoot(aNode.getParent(), depth);
769 retNodes[retNodes.length - depth] = aNode;
770 }
771 return retNodes;
772 }
773 /**
774 * Returns the leaf before this node or null if this node is the
775 * first leaf in the tree.
776 * <p>
777 * In this implementation of the <code>MutableNode</code> interface,
778 * this operation is very inefficient. In order to determine the
779 * previous node, this method first performs a linear search in the
780 * parent's child-list in order to find the current node.
781 * <p>
782 * That implementation makes the operation suitable for short
783 * traversals from a known position. But to traverse all of the
784 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
785 * to enumerate the nodes in the tree and use <code>isLeaf</code>
786 * on each node to determine which are leaves.
787 *
788 */
789 public DefaultMutableTreeNode getPreviousLeaf() {
790 DefaultMutableTreeNode previousSibling;
791 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
792
793 if (myParent == null)
794 return null;
795
796 previousSibling = getPreviousSibling(); // linear search
797
798 if (previousSibling != null)
799 return previousSibling.getLastLeaf();
800
801 return myParent.getPreviousLeaf(); // tail recursion
802 }
803 /**
804 * Returns the node that precedes this node in a preorder traversal of
805 * this node's tree. Returns null if this node is the first node of the
806 * traveral -- the root of the tree. This is an inefficient way to
807 * traverse the entire tree; use an enumeration, instead.
808 *
809 */
810 public DefaultMutableTreeNode getPreviousNode() {
811 DefaultMutableTreeNode previousSibling;
812 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
813
814 if (myParent == null) {
815 return null;
816 }
817
818 previousSibling = getPreviousSibling();
819
820 if (previousSibling != null) {
821 if (previousSibling.getChildCount() == 0)
822 return previousSibling;
823 else
824 return previousSibling.getLastLeaf();
825 } else {
826 return myParent;
827 }
828 }
829 /**
830 * Returns the previous sibling of this node in the parent's children
831 * array. Returns null if this node has no parent or is the parent's
832 * first child. This method performs a linear search that is O(n) where n
833 * is the number of children.
834 *
835 * @return the sibling of this node that immediately precedes this node
836 */
837 public DefaultMutableTreeNode getPreviousSibling() {
838 DefaultMutableTreeNode retval;
839
840 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
841
842 if (myParent == null) {
843 retval = null;
844 } else {
845 retval = (DefaultMutableTreeNode) myParent.getChildBefore(this);
846 // linear search
847 }
848
849 if (retval != null && !isNodeSibling(retval)) {
850 throw new InternalError("child of parent is not a sibling");
851 }
852
853 return retval;
854 }
855 /**
856 * Returns the root of the tree that contains this node. The root is
857 * the ancestor with a null parent.
858 *
859 */
860 public TreeNode getRoot() {
861 TreeNode ancestor = this;
862 TreeNode previous;
863
864 do {
865 previous = ancestor;
866 ancestor = ancestor.getParent();
867 } while (ancestor != null);
868
869 return previous;
870 }
871 /**
872 * Returns the nearest common ancestor to this node and <code>aNode</code>.
873 * Returns null, if no such ancestor exists -- if this node and
874 * <code>aNode</code> are in different trees or if <code>aNode</code> is
875 * null. A node is considered an ancestor of itself.
876 *
877 */
878 public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {
879 if (aNode == this) {
880 return this;
881 } else if (aNode == null) {
882 return null;
883 }
884
885 int level1, level2, diff;
886 TreeNode node1, node2;
887
888 level1 = getLevel();
889 level2 = aNode.getLevel();
890
891 if (level2 > level1) {
892 diff = level2 - level1;
893 node1 = aNode;
894 node2 = this;
895 } else {
896 diff = level1 - level2;
897 node1 = this;
898 node2 = aNode;
899 }
900
901 // Go up the tree until the nodes are at the same level
902 while (diff > 0) {
903 node1 = node1.getParent();
904 diff--;
905 }
906
907 // Move up the tree until we find a common ancestor. Since we know
908 // that both nodes are at the same level, we won't cross paths
909 // unknowingly (if there is a common ancestor, both nodes hit it in
910 // the same iteration).
911
912 do {
913 if (node1 == node2) {
914 return node1;
915 }
916 node1 = node1.getParent();
917 node2 = node2.getParent();
918 } while (node1 != null); // only need to check one -- they're at the
919 // same level so if one is null, the other is
920
921 if (node1 != null || node2 != null) {
922 throw new InternalError("nodes should be null");
923 }
924
925 return null;
926 }
927 /**
928 * Returns the number of siblings of this node. A node is its own sibling
929 * (if it has no parent or no siblings, this method returns
930 * <code>1</code>).
931 *
932 * @return the number of siblings of this node
933 */
934 public int getSiblingCount() {
935 TreeNode myParent = getParent();
936
937 if (myParent == null) {
938 return 1;
939 } else {
940 return myParent.getChildCount();
941 }
942 }
943 /**
944 * Returns this node's user object.
945 *
946 */
947 public Object getUserObject() {
948 return userObject;
949 }
950 /**
951 * Returns the user object path, from the root, to get to this node.
952 * If some of the TreeNodes in the path have null user objects, the
953 * returned path will contain nulls.
954 */
955 public Object[] getUserObjectPath() {
956 TreeNode[] realPath = getPath();
957 Object[] retPath = new Object[realPath.length];
958
959 for (int counter = 0; counter < realPath.length; counter++)
960 retPath[counter] = ((DefaultMutableTreeNode) realPath[counter]).getUserObject();
961 return retPath;
962 }
963 /**
964 * Removes <code>newChild</code> from its present parent (if it has a
965 * parent), sets the child's parent to this node, and then adds the child
966 * to this node's child array at index <code>childIndex</code>.
967 * <code>newChild</code> must not be null and must not be an ancestor of
968 * this node.
969 *
970 */
971 public void insert(MutableTreeNode newChild, int childIndex) {
972 if (!getAllowsChildren()) {
973 throw new IllegalStateException("node does not allow children");
974 } else if (newChild == null) {
975 throw new IllegalArgumentException("new child is null");
976 } else if (isNodeAncestor(newChild)) {
977 throw new IllegalArgumentException("new child is an ancestor");
978 }
979
980 MutableTreeNode oldParent = (MutableTreeNode) newChild.getParent();
981
982 if (oldParent != null) {
983 oldParent.remove(newChild);
984 }
985 newChild.setParent(this);
986 if (children == null) {
987 children = new Vector();
988 }
989 children.insertElementAt(newChild, childIndex);
990 }
991 /**
992 * Returns true if this node has no children. To distinguish between
993 * nodes that have no children and nodes that <i>cannot</i> have
994 * children (e.g. to distinguish files from empty directories), use this
995 * method in conjunction with <code>getAllowsChildren</code>
996 *
997 */
998 public boolean isLeaf() {
999 return (getChildCount() == 0);
1000 }
1001 /**
1002 * Returns true if <code>anotherNode</code> is an ancestor of this node
1003 * -- if it is this node, this node's parent, or an ancestor of this
1004 * node's parent. (Note that a node is considered an ancestor of itself.)
1005 * If <code>anotherNode</code> is null, this method returns false. This
1006 * operation is at worst O(h) where h is the distance from the root to
1007 * this node.
1008 *
1009 */
1010 public boolean isNodeAncestor(TreeNode anotherNode) {
1011 if (anotherNode == null) {
1012 return false;
1013 }
1014
1015 TreeNode ancestor = this;
1016
1017 do {
1018 if (ancestor == anotherNode) {
1019 return true;
1020 }
1021 } while ((ancestor = ancestor.getParent()) != null);
1022
1023 return false;
1024 }
1025 /**
1026 * Returns true if <code>aNode</code> is a child of this node. If
1027 * <code>aNode</code> is null, this method returns false.
1028 *
1029 * @return true if <code>aNode</code> is a child of this node; false if
1030 * <code>aNode</code> is null
1031 */
1032 public boolean isNodeChild(TreeNode aNode) {
1033 boolean retval;
1034
1035 if (aNode == null) {
1036 retval = false;
1037 } else {
1038 if (getChildCount() == 0) {
1039 retval = false;
1040 } else {
1041 retval = (aNode.getParent() == this);
1042 }
1043 }
1044
1045 return retval;
1046 }
1047 /**
1048 * Returns true if <code>anotherNode</code> is a descendant of this node
1049 * -- if it is this node, one of this node's children, or a descendant of
1050 * one of this node's children. Note that a node is considered a
1051 * descendant of itself. If <code>anotherNode</code> is null, returns
1052 * false. This operation is at worst O(h) where h is the distance from the
1053 * root to <code>anotherNode</code>.
1054 *
1055 */
1056 public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {
1057 if (anotherNode == null)
1058 return false;
1059
1060 return anotherNode.isNodeAncestor(this);
1061 }
1062 /**
1063 * Returns true if and only if <code>aNode</code> is in the same tree
1064 * as this node. Returns false if <code>aNode</code> is null.
1065 *
1066 */
1067 public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
1068 return (aNode != null) && (getRoot() == aNode.getRoot());
1069 }
1070 /**
1071 * Returns true if <code>anotherNode</code> is a sibling of (has the
1072 * same parent as) this node. A node is its own sibling. If
1073 * <code>anotherNode</code> is null, returns false.
1074 *
1075 * @param anotherNode node to test as sibling of this node
1076 * @return true if <code>anotherNode</code> is a sibling of this node
1077 */
1078 public boolean isNodeSibling(TreeNode anotherNode) {
1079 boolean retval;
1080
1081 if (anotherNode == null) {
1082 retval = false;
1083 } else if (anotherNode == this) {
1084 retval = true;
1085 } else {
1086 TreeNode myParent = getParent();
1087 retval = (myParent != null && myParent == anotherNode.getParent());
1088
1089 if (retval && !((DefaultMutableTreeNode) getParent()).isNodeChild(anotherNode)) {
1090 throw new InternalError("sibling has different parent");
1091 }
1092 }
1093
1094 return retval;
1095 }
1096 /**
1097 * Returns true if this node is the root of the tree. The root is
1098 * the only node in the tree with a null parent; every tree has exactly
1099 * one root.
1100 *
1101 * @return true if this node is the root of its tree
1102 */
1103 public boolean isRoot() {
1104 return getParent() == null;
1105 }
1106 /**
1107 * Creates and returns an enumeration that follows the path from
1108 * <code>ancestor</code> to this node. The enumeration's
1109 * <code>nextElement()</code> method first returns <code>ancestor</code>,
1110 * then the child of <code>ancestor</code> that is an ancestor of this
1111 * node, and so on, and finally returns this node. Creation of the
1112 * enumeration is O(m) where m is the number of nodes between this node
1113 * and <code>ancestor</code>, inclusive. Each <code>nextElement()</code>
1114 * message is O(1).<P>
1115 *
1116 * Modifying the tree by inserting, removing, or moving a node invalidates
1117 * any enumerations created before the modification.
1118 *
1119 */
1120 public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) {
1121 return new PathBetweenNodesEnumeration(ancestor, this);
1122 }
1123 /**
1124 * Creates and returns an enumeration that traverses the subtree rooted at
1125 * this node in postorder. The first node returned by the enumeration's
1126 * <code>nextElement()</code> method is the leftmost leaf. This is the
1127 * same as a depth-first traversal.<P>
1128 *
1129 * Modifying the tree by inserting, removing, or moving a node invalidates
1130 * any enumerations created before the modification.
1131 *
1132 */
1133 public Enumeration postorderEnumeration() {
1134 return new PostorderEnumeration(this);
1135 }
1136 /**
1137 * Creates and returns an enumeration that traverses the subtree rooted at
1138 * this node in preorder. The first node returned by the enumeration's
1139 * <code>nextElement()</code> method is this node.<P>
1140 *
1141 * Modifying the tree by inserting, removing, or moving a node invalidates
1142 * any enumerations created before the modification.
1143 *
1144 */
1145 public Enumeration preorderEnumeration() {
1146 return new PreorderEnumeration(this);
1147 }
1148 /**
1149 * Removes the child at the specified index from this node's children
1150 * and sets that node's parent to null. The child node to remove
1151 * must be a <code>MutableTreeNode</code>.
1152 *
1153 * @param childIndex the index in this node's child array
1154 * of the child to remove
1155 * @exception ArrayIndexOutOfBoundsException if
1156 * <code>childIndex</code> is out of bounds
1157 */
1158 public void remove(int childIndex) {
1159 MutableTreeNode child = (MutableTreeNode) getChildAt(childIndex);
1160 children.removeElementAt(childIndex);
1161 child.setParent(null);
1162 }
1163 /**
1164 * Removes <code>aChild</code> from this node's child array, giving it a
1165 * null parent.
1166 *
1167 * @param aChild a child of this node to remove
1168 * @exception IllegalArgumentException if <code>aChild</code>
1169 * is null or is not a child of this node
1170 */
1171 public void remove(MutableTreeNode aChild) {
1172 if (aChild == null) {
1173 throw new IllegalArgumentException("argument is null");
1174 }
1175
1176 if (!isNodeChild(aChild)) {
1177 throw new IllegalArgumentException("argument is not a child");
1178 }
1179 remove(getIndex(aChild)); // linear search
1180 }
1181 /**
1182 * Removes all of this node's children, setting their parents to null.
1183 * If this node has no children, this method does nothing.
1184 */
1185 public void removeAllChildren() {
1186 for (int i = getChildCount() - 1; i >= 0; i--) {
1187 remove(i);
1188 }
1189 }
1190 /**
1191 * Removes the subtree rooted at this node from the tree, giving this
1192 * node a null parent. Does nothing if this node is the root of its
1193 * tree.
1194 */
1195 public void removeFromParent() {
1196 MutableTreeNode parent = (MutableTreeNode) getParent();
1197 if (parent != null) {
1198 parent.remove(this);
1199 }
1200 }
1201 /**
1202 * Sets this node's action command to <code>newActionCommand</code>
1203 *
1204 * @param newActionCommand this node's new action command
1205 */
1206 public void setActionCommand(String newActionCommand) {
1207 actionCommand = newActionCommand;
1208 }
1209 /**
1210 * Determines whether or not this node is allowed to have children.
1211 * If <code>allows</code> is false, all of this node's children are
1212 * removed.
1213 * <p>
1214 * Note: By default, a node allows children.
1215 *
1216 * @param allows true if this node is allowed to have children
1217 */
1218 public void setAllowsChildren(boolean allows) {
1219 if (allows != allowsChildren) {
1220 allowsChildren = allows;
1221 if (!allowsChildren) {
1222 removeAllChildren();
1223 }
1224 }
1225 }
1226 /**
1227 * Sets this node's parent to <code>newParent</code> but does not
1228 * change the parent's child array. This method is called from
1229 * <code>insert()</code> and <code>remove()</code> to
1230 * reassign a child's parent, it should not be messaged from anywhere
1231 * else.
1232 *
1233 * @param newParent this node's new parent
1234 */
1235 public void setParent(MutableTreeNode newParent) {
1236 parent = newParent;
1237 }
1238 /**
1239 * Sets the user object for this node to <code>userObject</code>.
1240 *
1241 */
1242 public void setUserObject(Object userObject) {
1243 this.userObject = userObject;
1244 }
1245 /**
1246 * Returns the result of sending <code>toString()</code> to this node's
1247 * user object, or null if this node has no user object.
1248 *
1249 */
1250 public String toString() {
1251 if (userObject == null) {
1252 return null;
1253 } else {
1254 return userObject.toString();
1255 }
1256 }
1257 }