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:
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:
109: public DefaultMutableTreeNode(Object userObject)
110: {
111: this(userObject, true);
112: }
113:
114:
122: public DefaultMutableTreeNode(Object userObject, boolean allowsChildren)
123: {
124: this.userObject = userObject;
125: this.allowsChildren = allowsChildren;
126: }
127:
128:
134: public Object clone()
135: {
136: return new DefaultMutableTreeNode(this.userObject, this.allowsChildren);
137: }
138:
139:
146: public String toString()
147: {
148: if (userObject == null)
149: return null;
150:
151: return userObject.toString();
152: }
153:
154:
169: public void add(MutableTreeNode child)
170: {
171: if (! allowsChildren)
172: throw new IllegalStateException();
173:
174: if (child == null)
175: throw new IllegalArgumentException();
176:
177: if (isNodeAncestor(child))
178: throw new IllegalArgumentException("Cannot add ancestor node.");
179:
180: children.add(child);
181: child.setParent(this);
182: }
183:
184:
189: public TreeNode getParent()
190: {
191: return parent;
192: }
193:
194:
203: public void remove(int index)
204: {
205: MutableTreeNode child = (MutableTreeNode) children.remove(index);
206: child.setParent(null);
207: }
208:
209:
219: public void remove(MutableTreeNode node)
220: {
221: if (node == null)
222: throw new IllegalArgumentException("Null 'node' argument.");
223: if (node.getParent() != this)
224: throw new IllegalArgumentException(
225: "The given 'node' is not a child of this node.");
226: children.remove(node);
227: node.setParent(null);
228: }
229:
230:
237: private void writeObject(ObjectOutputStream stream)
238: throws IOException
239: {
240:
241: }
242:
243:
251: private void readObject(ObjectInputStream stream)
252: throws IOException, ClassNotFoundException
253: {
254:
255: }
256:
257:
266: public void insert(MutableTreeNode node, int index)
267: {
268: if (! allowsChildren)
269: throw new IllegalStateException();
270:
271: if (node == null)
272: throw new IllegalArgumentException("Null 'node' argument.");
273:
274: if (isNodeAncestor(node))
275: throw new IllegalArgumentException("Cannot insert ancestor node.");
276:
277: children.insertElementAt(node, index);
278: }
279:
280:
285: public TreeNode[] getPath()
286: {
287: return getPathToRoot(this, 0);
288: }
289:
290:
296: public Enumeration children()
297: {
298: if (children.size() == 0)
299: return EMPTY_ENUMERATION;
300:
301: return children.elements();
302: }
303:
304:
309: public void setParent(MutableTreeNode node)
310: {
311: parent = node;
312: }
313:
314:
321: public TreeNode getChildAt(int index)
322: {
323: return (TreeNode) children.elementAt(index);
324: }
325:
326:
331: public int getChildCount()
332: {
333: return children.size();
334: }
335:
336:
346: public int getIndex(TreeNode node)
347: {
348: if (node == null)
349: throw new IllegalArgumentException("Null 'node' argument.");
350: return children.indexOf(node);
351: }
352:
353:
360: public void setAllowsChildren(boolean allowsChildren)
361: {
362: if (!allowsChildren)
363: removeAllChildren();
364: this.allowsChildren = allowsChildren;
365: }
366:
367:
372: public boolean getAllowsChildren()
373: {
374: return allowsChildren;
375: }
376:
377:
382: public void setUserObject(Object userObject)
383: {
384: this.userObject = userObject;
385: }
386:
387:
393: public Object getUserObject()
394: {
395: return userObject;
396: }
397:
398:
401: public void removeFromParent()
402: {
403: parent.remove(this);
404: parent = null;
405: }
406:
407:
410: public void removeAllChildren()
411: {
412: for (int i = getChildCount() - 1; i >= 0; i--)
413: remove(i);
414: }
415:
416:
431: public boolean isNodeAncestor(TreeNode node)
432: {
433: if (node == null)
434: return false;
435:
436: TreeNode current = this;
437:
438: while (current != null && current != node)
439: current = current.getParent();
440:
441: return current == node;
442: }
443:
444:
459: public boolean isNodeDescendant(DefaultMutableTreeNode node)
460: {
461: if (node == null)
462: return false;
463:
464: TreeNode current = node;
465:
466: while (current != null
467: && current != this)
468: current = current.getParent();
469:
470: return current == this;
471: }
472:
473:
480: public TreeNode getSharedAncestor(DefaultMutableTreeNode node)
481: {
482: TreeNode current = this;
483: ArrayList list = new ArrayList();
484:
485: while (current != null)
486: {
487: list.add(current);
488: current = current.getParent();
489: }
490:
491: current = node;
492:
493: while (current != null)
494: {
495: if (list.contains(current))
496: return current;
497:
498: current = current.getParent();
499: }
500:
501: return null;
502: }
503:
504:
511: public boolean isNodeRelated(DefaultMutableTreeNode node)
512: {
513: if (node == null)
514: return false;
515:
516: return node.getRoot() == getRoot();
517: }
518:
519:
524: public int getDepth()
525: {
526: if ((! allowsChildren)
527: || children.size() == 0)
528: return 0;
529:
530: Stack stack = new Stack();
531: stack.push(new Integer(0));
532: TreeNode node = getChildAt(0);
533: int depth = 0;
534: int current = 1;
535:
536: while (! stack.empty())
537: {
538: if (node.getChildCount() != 0)
539: {
540: node = node.getChildAt(0);
541: stack.push(new Integer(0));
542: current++;
543: }
544: else
545: {
546: if (current > depth)
547: depth = current;
548:
549: int size;
550: int index;
551:
552: do
553: {
554: node = node.getParent();
555: size = node.getChildCount();
556: index = ((Integer) stack.pop()).intValue() + 1;
557: current--;
558: }
559: while (index >= size
560: && node != this);
561:
562: if (index < size)
563: {
564: node = node.getChildAt(index);
565: stack.push(new Integer(index));
566: current++;
567: }
568: }
569: }
570:
571: return depth;
572: }
573:
574:
579: public int getLevel()
580: {
581: int count = -1;
582: TreeNode current = this;
583:
584: do
585: {
586: current = current.getParent();
587: count++;
588: }
589: while (current != null);
590:
591: return count;
592: }
593:
594:
602: protected TreeNode[] getPathToRoot(TreeNode node, int depth)
603: {
604: if (node == null)
605: {
606: if (depth == 0)
607: return null;
608:
609: return new TreeNode[depth];
610: }
611:
612: TreeNode[] path = getPathToRoot(node.getParent(), depth + 1);
613: path[path.length - depth - 1] = node;
614: return path;
615: }
616:
617:
622: public Object[] getUserObjectPath()
623: {
624: TreeNode[] path = getPathToRoot(this, 0);
625: Object[] object = new Object[path.length];
626:
627: for (int index = 0; index < path.length; ++index)
628: object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject();
629:
630: return object;
631: }
632:
633:
638: public TreeNode getRoot()
639: {
640: TreeNode current = this;
641: TreeNode check = current.getParent();
642:
643: while (check != null)
644: {
645: current = check;
646: check = current.getParent();
647: }
648:
649: return current;
650: }
651:
652:
658: public boolean isRoot()
659: {
660: return parent == null;
661: }
662:
663:
668: public DefaultMutableTreeNode getNextNode()
669: {
670:
671: if (getChildCount() != 0)
672: return (DefaultMutableTreeNode) getChildAt(0);
673:
674:
675: DefaultMutableTreeNode node = this;
676: DefaultMutableTreeNode sibling;
677:
678: do
679: {
680: sibling = node.getNextSibling();
681: node = (DefaultMutableTreeNode) node.getParent();
682: }
683: while (sibling == null &&
684: node != null);
685:
686:
687: return sibling;
688: }
689:
690:
695: public DefaultMutableTreeNode getPreviousNode()
696: {
697:
698: if (parent == null)
699: return null;
700:
701: DefaultMutableTreeNode sibling = getPreviousSibling();
702:
703:
704: if (sibling == null)
705: return (DefaultMutableTreeNode) parent;
706:
707:
708: if (sibling.getChildCount() != 0)
709: return sibling.getLastLeaf();
710:
711:
712: return sibling;
713: }
714:
715:
720: public Enumeration preorderEnumeration()
721: {
722: return new PreorderEnumeration(this);
723: }
724:
725:
730: public Enumeration postorderEnumeration()
731: {
732: return new PostorderEnumeration(this);
733: }
734:
735:
740: public Enumeration breadthFirstEnumeration()
741: {
742: return new BreadthFirstEnumeration(this);
743: }
744:
745:
750: public Enumeration depthFirstEnumeration()
751: {
752: return postorderEnumeration();
753: }
754:
755:
762: public Enumeration pathFromAncestorEnumeration(TreeNode node)
763: {
764: if (node == null)
765: throw new IllegalArgumentException();
766:
767: TreeNode parent = this;
768: Vector nodes = new Vector();
769: nodes.add(this);
770:
771: while (parent != node && parent != null)
772: {
773: parent = parent.getParent();
774: nodes.add(0, parent);
775: }
776:
777: if (parent != node)
778: throw new IllegalArgumentException();
779:
780: return nodes.elements();
781: }
782:
783:
792: public boolean isNodeChild(TreeNode node)
793: {
794: if (node == null)
795: return false;
796:
797: return node.getParent() == this;
798: }
799:
800:
807: public TreeNode getFirstChild()
808: {
809: return (TreeNode) children.firstElement();
810: }
811:
812:
819: public TreeNode getLastChild()
820: {
821: return (TreeNode) children.lastElement();
822: }
823:
824:
836: public TreeNode getChildAfter(TreeNode node)
837: {
838: if (node == null || node.getParent() != this)
839: throw new IllegalArgumentException();
840:
841: int index = getIndex(node) + 1;
842:
843: if (index == getChildCount())
844: return null;
845:
846: return getChildAt(index);
847: }
848:
849:
861: public TreeNode getChildBefore(TreeNode node)
862: {
863: if (node == null || node.getParent() != this)
864: throw new IllegalArgumentException();
865:
866: int index = getIndex(node) - 1;
867:
868: if (index < 0)
869: return null;
870:
871: return getChildAt(index);
872: }
873:
874:
884: public boolean isNodeSibling(TreeNode node)
885: {
886: if (node == null)
887: return false;
888: if (node == this)
889: return true;
890: return (node.getParent() == getParent()
891: && getParent() != null);
892: }
893:
894:
901: public int getSiblingCount()
902: {
903: if (parent == null)
904: return 1;
905:
906: return parent.getChildCount();
907: }
908:
909:
916: public DefaultMutableTreeNode getNextSibling()
917: {
918: if (parent == null)
919: return null;
920:
921: int index = parent.getIndex(this) + 1;
922:
923: if (index == parent.getChildCount())
924: return null;
925:
926: return (DefaultMutableTreeNode) parent.getChildAt(index);
927: }
928:
929:
936: public DefaultMutableTreeNode getPreviousSibling()
937: {
938: if (parent == null)
939: return null;
940:
941: int index = parent.getIndex(this) - 1;
942:
943: if (index < 0)
944: return null;
945:
946: return (DefaultMutableTreeNode) parent.getChildAt(index);
947: }
948:
949:
955: public boolean isLeaf()
956: {
957: return children.size() == 0;
958: }
959:
960:
967: public DefaultMutableTreeNode getFirstLeaf()
968: {
969: TreeNode current = this;
970:
971: while (current.getChildCount() > 0)
972: current = current.getChildAt(0);
973:
974: return (DefaultMutableTreeNode) current;
975: }
976:
977:
984: public DefaultMutableTreeNode getLastLeaf()
985: {
986: TreeNode current = this;
987: int size = current.getChildCount();
988:
989: while (size > 0)
990: {
991: current = current.getChildAt(size - 1);
992: size = current.getChildCount();
993: }
994:
995: return (DefaultMutableTreeNode) current;
996: }
997:
998:
1003: public DefaultMutableTreeNode getNextLeaf()
1004: {
1005:
1006: DefaultMutableTreeNode sibling = getNextSibling();
1007: if (sibling != null)
1008: return sibling.getFirstLeaf();
1009:
1010: if (parent != null)
1011: return ((DefaultMutableTreeNode) parent).getNextLeaf();
1012: return null;
1013: }
1014:
1015:
1020: public DefaultMutableTreeNode getPreviousLeaf()
1021: {
1022:
1023: DefaultMutableTreeNode sibling = getPreviousSibling();
1024: if (sibling != null)
1025: return sibling.getLastLeaf();
1026:
1027: if (parent != null)
1028: return ((DefaultMutableTreeNode) parent).getPreviousLeaf();
1029: return null;
1030: }
1031:
1032:
1037: public int getLeafCount()
1038: {
1039: int count = 0;
1040: Enumeration e = depthFirstEnumeration();
1041:
1042: while (e.hasMoreElements())
1043: {
1044: TreeNode current = (TreeNode) e.nextElement();
1045:
1046: if (current.isLeaf())
1047: count++;
1048: }
1049:
1050: return count;
1051: }
1052:
1053:
1056: static class BreadthFirstEnumeration implements Enumeration
1057: {
1058:
1059: LinkedList queue = new LinkedList();
1060:
1061: BreadthFirstEnumeration(TreeNode node)
1062: {
1063: queue.add(node);
1064: }
1065:
1066: public boolean hasMoreElements()
1067: {
1068: return !queue.isEmpty();
1069: }
1070:
1071: public Object nextElement()
1072: {
1073: if(queue.isEmpty())
1074: throw new NoSuchElementException("No more elements left.");
1075:
1076: TreeNode node = (TreeNode) queue.removeFirst();
1077:
1078: Enumeration children = node.children();
1079: while (children.hasMoreElements())
1080: queue.add(children.nextElement());
1081:
1082: return node;
1083: }
1084: }
1085:
1086:
1089: static class PreorderEnumeration implements Enumeration
1090: {
1091: TreeNode next;
1092:
1093: Stack childrenEnums = new Stack();
1094:
1095: PreorderEnumeration(TreeNode node)
1096: {
1097: next = node;
1098: childrenEnums.push(node.children());
1099: }
1100:
1101: public boolean hasMoreElements()
1102: {
1103: return next != null;
1104: }
1105:
1106: public Object nextElement()
1107: {
1108: if( next == null )
1109: throw new NoSuchElementException("No more elements left.");
1110:
1111: Object current = next;
1112:
1113: Enumeration children = (Enumeration) childrenEnums.peek();
1114:
1115:
1116: next = traverse(children);
1117:
1118: return current;
1119: }
1120:
1121: private TreeNode traverse(Enumeration children)
1122: {
1123:
1124: if( children.hasMoreElements() )
1125: {
1126: TreeNode child = (TreeNode) children.nextElement();
1127: childrenEnums.push(child.children());
1128:
1129: return child;
1130: }
1131:
1132:
1133: childrenEnums.pop();
1134:
1135:
1136:
1137: if ( childrenEnums.isEmpty() )
1138: return null;
1139: else
1140: {
1141: return traverse((Enumeration) childrenEnums.peek());
1142: }
1143: }
1144: }
1145:
1146:
1149: static class PostorderEnumeration implements Enumeration
1150: {
1151:
1152: Stack nodes = new Stack();
1153: Stack childrenEnums = new Stack();
1154:
1155: PostorderEnumeration(TreeNode node)
1156: {
1157: nodes.push(node);
1158: childrenEnums.push(node.children());
1159: }
1160:
1161: public boolean hasMoreElements()
1162: {
1163: return !nodes.isEmpty();
1164: }
1165:
1166: public Object nextElement()
1167: {
1168: if( nodes.isEmpty() )
1169: throw new NoSuchElementException("No more elements left!");
1170:
1171: Enumeration children = (Enumeration) childrenEnums.peek();
1172:
1173: return traverse(children);
1174: }
1175:
1176: private Object traverse(Enumeration children)
1177: {
1178: if ( children.hasMoreElements() )
1179: {
1180: TreeNode node = (TreeNode) children.nextElement();
1181: nodes.push(node);
1182:
1183: Enumeration newChildren = node.children();
1184: childrenEnums.push(newChildren);
1185:
1186: return traverse(newChildren);
1187: }
1188: else
1189: {
1190: childrenEnums.pop();
1191:
1192:
1193:
1194: Object next = nodes.peek();
1195: nodes.pop();
1196:
1197: return next;
1198: }
1199: }
1200:
1201: }
1202:
1203: }