1:
37:
38:
39: package ;
40:
41: import ;
42:
43: import ;
44: import ;
45: import ;
46: import ;
47: import ;
48: import ;
49: import ;
50: import ;
51: import ;
52: import ;
53:
54:
55:
61: public class DefaultMutableTreeNode
62: implements Cloneable, MutableTreeNode, Serializable
63: {
64: private static final long serialVersionUID = -4298474751201349152L;
65:
66:
69: public static final Enumeration EMPTY_ENUMERATION =
70: EmptyEnumeration.getInstance();
71:
72:
75: protected MutableTreeNode parent;
76:
77:
80: protected Vector children = new Vector();
81:
82:
85: protected transient Object userObject;
86:
87:
90: protected boolean allowsChildren;
91:
92:
96: public DefaultMutableTreeNode()
97: {
98: this(null, true);
99: }
100:
101:
107: public DefaultMutableTreeNode(Object userObject)
108: {
109: this(userObject, true);
110: }
111:
112:
120: public DefaultMutableTreeNode(Object userObject, boolean allowsChildren)
121: {
122: this.userObject = userObject;
123: this.allowsChildren = allowsChildren;
124: }
125:
126:
131: public Object clone()
132: {
133: try
134: {
135: return super.clone();
136:
137: }
138: catch (CloneNotSupportedException e)
139: {
140:
141: return null;
142: }
143: }
144:
145:
150: public String toString()
151: {
152: if (userObject == null)
153: return null;
154:
155: return userObject.toString();
156: }
157:
158:
166: public void add(MutableTreeNode child)
167: {
168: if (child == null)
169: throw new IllegalArgumentException();
170:
171: if (! allowsChildren)
172: throw new IllegalStateException();
173:
174: children.add(child);
175: child.setParent(this);
176: }
177:
178:
183: public TreeNode getParent()
184: {
185: return parent;
186: }
187:
188:
193: public void remove(int index)
194: {
195: children.remove(index);
196: }
197:
198:
203: public void remove(MutableTreeNode node)
204: {
205: children.remove(node);
206: }
207:
208:
215: private void writeObject(ObjectOutputStream stream)
216: throws IOException
217: {
218:
219: }
220:
221:
229: private void readObject(ObjectInputStream stream)
230: throws IOException, ClassNotFoundException
231: {
232:
233: }
234:
235:
241: public void insert(MutableTreeNode node, int index)
242: {
243: children.insertElementAt(node, index);
244: }
245:
246:
251: public TreeNode[] getPath()
252: {
253: return getPathToRoot(this, 0);
254: }
255:
256:
262: public Enumeration children()
263: {
264: if (children.size() == 0)
265: return EMPTY_ENUMERATION;
266:
267: return children.elements();
268: }
269:
270:
275: public void setParent(MutableTreeNode node)
276: {
277: parent = node;
278: }
279:
280:
287: public TreeNode getChildAt(int index)
288: {
289: return (TreeNode) children.elementAt(index);
290: }
291:
292:
297: public int getChildCount()
298: {
299: return children.size();
300: }
301:
302:
309: public int getIndex(TreeNode node)
310: {
311: return children.indexOf(node);
312: }
313:
314:
319: public void setAllowsChildren(boolean allowsChildren)
320: {
321: this.allowsChildren = allowsChildren;
322: }
323:
324:
329: public boolean getAllowsChildren()
330: {
331: return allowsChildren;
332: }
333:
334:
339: public void setUserObject(Object userObject)
340: {
341: this.userObject = userObject;
342: }
343:
344:
350: public Object getUserObject()
351: {
352: return userObject;
353: }
354:
355:
358: public void removeFromParent()
359: {
360: parent.remove(this);
361: parent = null;
362: }
363:
364:
367: public void removeAllChildren()
368: {
369: children.removeAllElements();
370: }
371:
372:
379: public boolean isNodeAncestor(TreeNode node)
380: {
381: if (node == null)
382: return false;
383:
384: TreeNode current = this;
385:
386: while (current != null
387: && current != node)
388: current = current.getParent();
389:
390: return current == node;
391: }
392:
393:
400: public boolean isNodeDescendant(DefaultMutableTreeNode node)
401: {
402: if (node == null)
403: return false;
404:
405: TreeNode current = node;
406:
407: while (current != null
408: && current != this)
409: current = current.getParent();
410:
411: return current == this;
412: }
413:
414:
421: public TreeNode getSharedAncestor(DefaultMutableTreeNode node)
422: {
423: TreeNode current = this;
424: ArrayList list = new ArrayList();
425:
426: while (current != null)
427: {
428: list.add(current);
429: current = current.getParent();
430: }
431:
432: current = node;
433:
434: while (current != null)
435: {
436: if (list.contains(current))
437: return current;
438:
439: current = current.getParent();
440: }
441:
442: return null;
443: }
444:
445:
452: public boolean isNodeRelated(DefaultMutableTreeNode node)
453: {
454: if (node == null)
455: return false;
456:
457: return node.getRoot() == getRoot();
458: }
459:
460:
465: public int getDepth()
466: {
467: if ((! allowsChildren)
468: || children.size() == 0)
469: return 0;
470:
471: Stack stack = new Stack();
472: stack.push(new Integer(0));
473: TreeNode node = getChildAt(0);
474: int depth = 0;
475: int current = 1;
476:
477: while (! stack.empty())
478: {
479: if (node.getChildCount() != 0)
480: {
481: node = node.getChildAt(0);
482: stack.push(new Integer(0));
483: current++;
484: }
485: else
486: {
487: if (current > depth)
488: depth = current;
489:
490: int size;
491: int index;
492:
493: do
494: {
495: node = node.getParent();
496: size = node.getChildCount();
497: index = ((Integer) stack.pop()).intValue() + 1;
498: current--;
499: }
500: while (index >= size
501: && node != this);
502:
503: if (index < size)
504: {
505: node = node.getChildAt(index);
506: stack.push(new Integer(index));
507: current++;
508: }
509: }
510: }
511:
512: return depth;
513: }
514:
515:
520: public int getLevel()
521: {
522: int count = -1;
523: TreeNode current = this;
524:
525: do
526: {
527: current = current.getParent();
528: count++;
529: }
530: while (current != null);
531:
532: return count;
533: }
534:
535:
543: protected TreeNode[] getPathToRoot(TreeNode node, int depth)
544: {
545: if (node == null)
546: {
547: if (depth == 0)
548: return null;
549:
550: return new TreeNode[depth];
551: }
552:
553: TreeNode[] path = getPathToRoot(node.getParent(), depth + 1);
554: path[path.length - depth - 1] = node;
555: return path;
556: }
557:
558:
563: public Object[] getUserObjectPath()
564: {
565: TreeNode[] path = getPathToRoot(this, 0);
566: Object[] object = new Object[path.length];
567:
568: for (int index = 0; index < path.length; ++index)
569: object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject();
570:
571: return object;
572: }
573:
574:
579: public TreeNode getRoot()
580: {
581: TreeNode current = this;
582: TreeNode check = current.getParent();
583:
584: while (check != null)
585: {
586: current = check;
587: check = current.getParent();
588: }
589:
590: return current;
591: }
592:
593:
599: public boolean isRoot()
600: {
601: return parent == null;
602: }
603:
604:
609: public DefaultMutableTreeNode getNextNode()
610: {
611:
612: if (getChildCount() != 0)
613: return (DefaultMutableTreeNode) getChildAt(0);
614:
615:
616: DefaultMutableTreeNode node = this;
617: DefaultMutableTreeNode sibling;
618:
619: do
620: {
621: sibling = node.getNextSibling();
622: node = (DefaultMutableTreeNode) node.getParent();
623: }
624: while (sibling == null &&
625: node != null);
626:
627:
628: return sibling;
629: }
630:
631:
636: public DefaultMutableTreeNode getPreviousNode()
637: {
638:
639: if (parent == null)
640: return null;
641:
642: DefaultMutableTreeNode sibling = getPreviousSibling();
643:
644:
645: if (sibling == null)
646: return (DefaultMutableTreeNode) parent;
647:
648:
649: if (sibling.getChildCount() != 0)
650: return sibling.getLastLeaf();
651:
652:
653: return sibling;
654: }
655:
656:
661: public Enumeration preorderEnumeration()
662: {
663: return new PreorderEnumeration(this);
664: }
665:
666:
671: public Enumeration postorderEnumeration()
672: {
673: return new PostorderEnumeration(this);
674: }
675:
676:
681: public Enumeration breadthFirstEnumeration()
682: {
683: return new BreadthFirstEnumeration(this);
684: }
685:
686:
691: public Enumeration depthFirstEnumeration()
692: {
693: return postorderEnumeration();
694: }
695:
696:
703: public Enumeration pathFromAncestorEnumeration(TreeNode node)
704: {
705: if (node == null)
706: throw new IllegalArgumentException();
707:
708: TreeNode parent = this;
709: Vector nodes = new Vector();
710: nodes.add(this);
711:
712: while (parent != node && parent != null)
713: {
714: parent = parent.getParent();
715: nodes.add(0, parent);
716: }
717:
718: if (parent != node)
719: throw new IllegalArgumentException();
720:
721: return nodes.elements();
722: }
723:
724:
731: public boolean isNodeChild(TreeNode node)
732: {
733: if (node == null)
734: return false;
735:
736: return node.getParent() == this;
737: }
738:
739:
744: public TreeNode getFirstChild()
745: {
746: return (TreeNode) children.firstElement();
747: }
748:
749:
754: public TreeNode getLastChild()
755: {
756: return (TreeNode) children.lastElement();
757: }
758:
759:
766: public TreeNode getChildAfter(TreeNode node)
767: {
768: if (node == null
769: || node.getParent() != this)
770: throw new IllegalArgumentException();
771:
772: int index = getIndex(node) + 1;
773:
774: if (index == getChildCount())
775: return null;
776:
777: return getChildAt(index);
778: }
779:
780:
787: public TreeNode getChildBefore(TreeNode node)
788: {
789: if (node == null
790: || node.getParent() != this)
791: throw new IllegalArgumentException();
792:
793: int index = getIndex(node) - 1;
794:
795: if (index < 0)
796: return null;
797:
798: return getChildAt(index);
799: }
800:
801:
808: public boolean isNodeSibling(TreeNode node)
809: {
810: if (node == null)
811: return false;
812:
813: return (node.getParent() == getParent()
814: && getParent() != null);
815: }
816:
817:
822: public int getSiblingCount()
823: {
824: if (parent == null)
825: return 1;
826:
827: return parent.getChildCount();
828: }
829:
830:
835: public DefaultMutableTreeNode getNextSibling()
836: {
837: if (parent == null)
838: return null;
839:
840: int index = parent.getIndex(this) + 1;
841:
842: if (index == parent.getChildCount())
843: return null;
844:
845: return (DefaultMutableTreeNode) parent.getChildAt(index);
846: }
847:
848:
853: public DefaultMutableTreeNode getPreviousSibling()
854: {
855: if (parent == null)
856: return null;
857:
858: int index = parent.getIndex(this) - 1;
859:
860: if (index < 0)
861: return null;
862:
863: return (DefaultMutableTreeNode) parent.getChildAt(index);
864: }
865:
866:
871: public boolean isLeaf()
872: {
873: return children.size() == 0;
874: }
875:
876:
881: public DefaultMutableTreeNode getFirstLeaf()
882: {
883: TreeNode current = this;
884:
885: while (current.getChildCount() > 0)
886: current = current.getChildAt(0);
887:
888: return (DefaultMutableTreeNode) current;
889: }
890:
891:
896: public DefaultMutableTreeNode getLastLeaf()
897: {
898: TreeNode current = this;
899: int size = current.getChildCount();
900:
901: while (size > 0)
902: {
903: current = current.getChildAt(size - 1);
904: size = current.getChildCount();
905: }
906:
907: return (DefaultMutableTreeNode) current;
908: }
909:
910:
915: public DefaultMutableTreeNode getNextLeaf()
916: {
917: if (parent == null)
918: return null;
919:
920:
921: return null;
922:
923: }
924:
925:
930: public DefaultMutableTreeNode getPreviousLeaf()
931: {
932: if (parent == null)
933: return null;
934:
935:
936: return null;
937:
938: }
939:
940:
945: public int getLeafCount()
946: {
947: int count = 0;
948: Enumeration e = depthFirstEnumeration();
949:
950: while (e.hasMoreElements())
951: {
952: TreeNode current = (TreeNode) e.nextElement();
953:
954: if (current.isLeaf())
955: count++;
956: }
957:
958: return count;
959: }
960:
961:
964: static class BreadthFirstEnumeration implements Enumeration
965: {
966:
967: LinkedList queue = new LinkedList();
968:
969: BreadthFirstEnumeration(TreeNode node)
970: {
971: queue.add(node);
972: }
973:
974: public boolean hasMoreElements()
975: {
976: return !queue.isEmpty();
977: }
978:
979: public Object nextElement()
980: {
981: if(queue.isEmpty())
982: throw new NoSuchElementException("No more elements left.");
983:
984: TreeNode node = (TreeNode) queue.removeFirst();
985:
986: Enumeration children = node.children();
987: while (children.hasMoreElements())
988: queue.add(children.nextElement());
989:
990: return node;
991: }
992: }
993:
994:
997: static class PreorderEnumeration implements Enumeration
998: {
999: TreeNode next;
1000:
1001: Stack childrenEnums = new Stack();
1002:
1003: PreorderEnumeration(TreeNode node)
1004: {
1005: next = node;
1006: childrenEnums.push(node.children());
1007: }
1008:
1009: public boolean hasMoreElements()
1010: {
1011: return next != null;
1012: }
1013:
1014: public Object nextElement()
1015: {
1016: if( next == null )
1017: throw new NoSuchElementException("No more elements left.");
1018:
1019: Object current = next;
1020:
1021: Enumeration children = (Enumeration) childrenEnums.peek();
1022:
1023:
1024: next = traverse(children);
1025:
1026: return current;
1027: }
1028:
1029: private TreeNode traverse(Enumeration children)
1030: {
1031:
1032: if( children.hasMoreElements() )
1033: {
1034: TreeNode child = (TreeNode) children.nextElement();
1035: childrenEnums.push(child.children());
1036:
1037: return child;
1038: }
1039:
1040:
1041: childrenEnums.pop();
1042:
1043:
1044:
1045: if ( childrenEnums.isEmpty() )
1046: return null;
1047: else
1048: {
1049: return traverse((Enumeration) childrenEnums.peek());
1050: }
1051: }
1052: }
1053:
1054:
1057: static class PostorderEnumeration implements Enumeration
1058: {
1059:
1060: Stack nodes = new Stack();
1061: Stack childrenEnums = new Stack();
1062:
1063: PostorderEnumeration(TreeNode node)
1064: {
1065: nodes.push(node);
1066: childrenEnums.push(node.children());
1067: }
1068:
1069: public boolean hasMoreElements()
1070: {
1071: return !nodes.isEmpty();
1072: }
1073:
1074: public Object nextElement()
1075: {
1076: if( nodes.isEmpty() )
1077: throw new NoSuchElementException("No more elements left!");
1078:
1079: Enumeration children = (Enumeration) childrenEnums.peek();
1080:
1081: return traverse(children);
1082: }
1083:
1084: private Object traverse(Enumeration children)
1085: {
1086: if ( children.hasMoreElements() )
1087: {
1088: TreeNode node = (TreeNode) children.nextElement();
1089: nodes.push(node);
1090:
1091: Enumeration newChildren = node.children();
1092: childrenEnums.push(newChildren);
1093:
1094: return traverse(newChildren);
1095: }
1096: else
1097: {
1098: childrenEnums.pop();
1099:
1100:
1101:
1102: Object next = nodes.peek();
1103: nodes.pop();
1104:
1105: return next;
1106: }
1107: }
1108:
1109: }
1110:
1111: }