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