001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: /**
018: * @author Anton Avtamonov
019: * @version $Revision$
020: */package javax.swing.tree;
021:
022: import java.io.Serializable;
023: import java.util.Enumeration;
024: import java.util.Iterator;
025: import java.util.LinkedList;
026: import java.util.List;
027: import java.util.NoSuchElementException;
028: import java.util.Vector;
029:
030: import org.apache.harmony.x.swing.internal.nls.Messages;
031:
032: public class DefaultMutableTreeNode implements Cloneable,
033: MutableTreeNode, Serializable {
034: public static final Enumeration<TreeNode> EMPTY_ENUMERATION = new Vector<TreeNode>()
035: .elements();
036:
037: protected MutableTreeNode parent;
038: protected Vector children;
039: protected transient Object userObject;
040: protected boolean allowsChildren;
041:
042: public DefaultMutableTreeNode() {
043: this (null);
044: }
045:
046: public DefaultMutableTreeNode(final Object userObject) {
047: this (userObject, true);
048: }
049:
050: public DefaultMutableTreeNode(final Object userObject,
051: final boolean allowsChildren) {
052: setUserObject(userObject);
053: setAllowsChildren(allowsChildren);
054: }
055:
056: public void insert(final MutableTreeNode child, final int childIndex) {
057: if (!getAllowsChildren()) {
058: throw new IllegalStateException(Messages
059: .getString("swing.A6")); //$NON-NLS-1$
060: }
061: if (child == null || isNodeAncestor(child)) {
062: throw new IllegalArgumentException(Messages
063: .getString("swing.A7")); //$NON-NLS-1$
064: }
065:
066: if (child.getParent() instanceof MutableTreeNode) {
067: ((MutableTreeNode) child.getParent()).remove(child);
068: }
069: child.setParent(this );
070: getChildren().insertElementAt(child, childIndex);
071: }
072:
073: public void remove(final int childIndex) {
074: MutableTreeNode child = (MutableTreeNode) getChildren().remove(
075: childIndex);
076: child.setParent(null);
077: }
078:
079: public void setParent(final MutableTreeNode parent) {
080: this .parent = parent;
081: }
082:
083: public TreeNode getParent() {
084: return parent;
085: }
086:
087: public TreeNode getChildAt(final int index) {
088: return (TreeNode) getChildren().get(index);
089: }
090:
091: public int getChildCount() {
092: return children != null ? children.size() : 0;
093: }
094:
095: public int getIndex(final TreeNode child) {
096: if (child == null) {
097: throw new IllegalArgumentException(Messages
098: .getString("swing.A8")); //$NON-NLS-1$
099: }
100:
101: return children != null ? children.indexOf(child) : -1;
102: }
103:
104: public Enumeration children() {
105: return children != null ? children.elements()
106: : EMPTY_ENUMERATION;
107: }
108:
109: public void setAllowsChildren(final boolean allows) {
110: allowsChildren = allows;
111: if (!allowsChildren && children != null) {
112: children.clear();
113: }
114: }
115:
116: public boolean getAllowsChildren() {
117: return allowsChildren;
118: }
119:
120: public void setUserObject(final Object userObject) {
121: this .userObject = userObject;
122: }
123:
124: public Object getUserObject() {
125: return userObject;
126: }
127:
128: public void removeFromParent() {
129: if (parent != null) {
130: parent.remove(this );
131: }
132: }
133:
134: public void remove(final MutableTreeNode child) {
135: int index = -1;
136: if (child == null || children == null
137: || (index = children.indexOf(child)) == -1) {
138: throw new IllegalArgumentException(Messages
139: .getString("swing.A9")); //$NON-NLS-1$
140: }
141: remove(index);
142: }
143:
144: public void removeAllChildren() {
145: if (children == null) {
146: return;
147: }
148: for (Iterator it = children.iterator(); it.hasNext();) {
149: MutableTreeNode child = (MutableTreeNode) it.next();
150: child.setParent(null);
151: it.remove();
152: }
153: }
154:
155: public void add(final MutableTreeNode child) {
156: insert(child, getChildCount() - (isNodeChild(child) ? 1 : 0));
157: }
158:
159: public boolean isNodeAncestor(final TreeNode anotherNode) {
160: if (anotherNode == null) {
161: return false;
162: }
163: TreeNode currentParent = this ;
164: while (currentParent != null) {
165: if (currentParent == anotherNode) {
166: return true;
167: }
168: currentParent = currentParent.getParent();
169: }
170:
171: return false;
172: }
173:
174: public boolean isNodeDescendant(
175: final DefaultMutableTreeNode anotherNode) {
176: return anotherNode != null ? anotherNode.isNodeAncestor(this )
177: : false;
178: }
179:
180: public TreeNode getSharedAncestor(
181: final DefaultMutableTreeNode anotherNode) {
182: TreeNode currentParent = anotherNode;
183: while (currentParent != null) {
184: if (isNodeAncestor(currentParent)) {
185: return currentParent;
186: }
187:
188: currentParent = currentParent.getParent();
189: }
190:
191: return null;
192: }
193:
194: public boolean isNodeRelated(final DefaultMutableTreeNode node) {
195: return getSharedAncestor(node) != null;
196: }
197:
198: public int getDepth() {
199: if (children == null || children.size() == 0) {
200: return 0;
201: }
202: int childrenDepth = 0;
203: for (Iterator it = children.iterator(); it.hasNext();) {
204: DefaultMutableTreeNode child = (DefaultMutableTreeNode) it
205: .next();
206: int childDepth = child.getDepth();
207: if (childDepth > childrenDepth) {
208: childrenDepth = childDepth;
209: }
210: }
211: return childrenDepth + 1;
212: }
213:
214: public int getLevel() {
215: int result = 0;
216: TreeNode currentParent = getParent();
217: while (currentParent != null) {
218: currentParent = currentParent.getParent();
219: result++;
220: }
221:
222: return result;
223: }
224:
225: public TreeNode[] getPath() {
226: return getPathToRoot(this , 0);
227: }
228:
229: public Object[] getUserObjectPath() {
230: TreeNode[] path = getPath();
231: Object[] result = new Object[path.length];
232: for (int i = 0; i < path.length; i++) {
233: result[i] = ((DefaultMutableTreeNode) path[i])
234: .getUserObject();
235: }
236:
237: return result;
238: }
239:
240: public TreeNode getRoot() {
241: TreeNode currentNode = this ;
242: while (currentNode.getParent() != null) {
243: currentNode = currentNode.getParent();
244: }
245:
246: return currentNode;
247: }
248:
249: public boolean isRoot() {
250: return getParent() == null;
251: }
252:
253: public DefaultMutableTreeNode getNextNode() {
254: if (getRoot() == null) {
255: return null;
256: }
257: Enumeration preorderEnum = preorderEnumeration(getRoot());
258: while (preorderEnum.hasMoreElements()) {
259: TreeNode curNode = (TreeNode) preorderEnum.nextElement();
260: if (curNode == this ) {
261: return preorderEnum.hasMoreElements() ? (DefaultMutableTreeNode) preorderEnum
262: .nextElement()
263: : null;
264: }
265: }
266:
267: return null;
268: }
269:
270: public DefaultMutableTreeNode getPreviousNode() {
271: if (getParent() == null) {
272: return null;
273: }
274: Enumeration preorderEnum = ((DefaultMutableTreeNode) getParent())
275: .preorderEnumeration();
276: DefaultMutableTreeNode previousNode = null;
277: while (preorderEnum.hasMoreElements()) {
278: DefaultMutableTreeNode currentNode = (DefaultMutableTreeNode) preorderEnum
279: .nextElement();
280: if (currentNode == this ) {
281: break;
282: }
283: previousNode = currentNode;
284: }
285:
286: return previousNode;
287: }
288:
289: public Enumeration preorderEnumeration() {
290: return preorderEnumeration(this );
291: }
292:
293: public Enumeration postorderEnumeration() {
294: return depthFirstEnumeration(this );
295: }
296:
297: public Enumeration breadthFirstEnumeration() {
298: return new Enumeration() {
299: private Enumeration children;
300: private List nextLevelChildren;
301:
302: public Object nextElement() {
303: if (nextLevelChildren == null) {
304: nextLevelChildren = new LinkedList();
305: nextLevelChildren.add(children());
306: return DefaultMutableTreeNode.this ;
307: }
308:
309: if (children == null || !children.hasMoreElements()) {
310: if (nextLevelChildren.isEmpty()) {
311: throw new NoSuchElementException(Messages
312: .getString("swing.AA")); //$NON-NLS-1$
313: } else {
314: children = (Enumeration) nextLevelChildren
315: .remove(0);
316: }
317: }
318:
319: TreeNode result = (TreeNode) children.nextElement();
320: if (result.getChildCount() > 0) {
321: nextLevelChildren.add(result.children());
322: }
323:
324: return result;
325: }
326:
327: public boolean hasMoreElements() {
328: return nextLevelChildren == null || children != null
329: && children.hasMoreElements();
330: }
331: };
332: }
333:
334: public Enumeration depthFirstEnumeration() {
335: return postorderEnumeration();
336: }
337:
338: public Enumeration pathFromAncestorEnumeration(
339: final TreeNode ancestor) {
340: if (!isNodeAncestor(ancestor)) {
341: throw new IllegalArgumentException(Messages
342: .getString("swing.AB")); //$NON-NLS-1$
343: }
344:
345: return new Enumeration() {
346: private TreeNode previousAncestor;
347:
348: public Object nextElement() {
349: if (previousAncestor == null) {
350: previousAncestor = ancestor;
351: return ancestor;
352: }
353:
354: if (previousAncestor == DefaultMutableTreeNode.this ) {
355: throw new NoSuchElementException(Messages
356: .getString("swing.AA")); //$NON-NLS-1$
357: }
358: TreeNode nextNode = DefaultMutableTreeNode.this ;
359: while (nextNode.getParent() != previousAncestor) {
360: nextNode = nextNode.getParent();
361: }
362: previousAncestor = nextNode;
363:
364: return previousAncestor;
365: }
366:
367: public boolean hasMoreElements() {
368: return previousAncestor != DefaultMutableTreeNode.this ;
369: }
370: };
371: }
372:
373: public boolean isNodeChild(final TreeNode child) {
374: return child != null && children != null ? children
375: .contains(child) : false;
376: }
377:
378: public TreeNode getFirstChild() {
379: if (children == null || children.isEmpty()) {
380: throw new NoSuchElementException(Messages
381: .getString("swing.AC")); //$NON-NLS-1$
382: }
383:
384: return (TreeNode) children.get(0);
385: }
386:
387: public TreeNode getLastChild() {
388: if (children == null || children.isEmpty()) {
389: throw new NoSuchElementException(Messages
390: .getString("swing.AC")); //$NON-NLS-1$
391: }
392:
393: return (TreeNode) children.get(children.size() - 1);
394: }
395:
396: public TreeNode getChildAfter(final TreeNode child) {
397: int index = -1;
398: if (child == null || (index = getIndex(child)) == -1) {
399: throw new IllegalArgumentException(Messages
400: .getString("swing.AD")); //$NON-NLS-1$
401: }
402:
403: return index + 1 < getChildCount() ? getChildAt(index + 1)
404: : null;
405: }
406:
407: public TreeNode getChildBefore(final TreeNode child) {
408: int index = -1;
409: if (child == null || (index = getIndex(child)) == -1) {
410: throw new IllegalArgumentException(Messages
411: .getString("swing.AD")); //$NON-NLS-1$
412: }
413:
414: return index > 0 ? getChildAt(index - 1) : null;
415: }
416:
417: public boolean isNodeSibling(final TreeNode sibling) {
418: if (sibling == null) {
419: return false;
420: }
421:
422: if (sibling == this ) {
423: return true;
424: }
425:
426: return getParent() != null
427: && getParent() == sibling.getParent();
428: }
429:
430: public int getSiblingCount() {
431: if (getParent() == null) {
432: return 1;
433: }
434:
435: Enumeration children = getParent().children();
436: int result = 0;
437: while (children.hasMoreElements()) {
438: children.nextElement();
439: result++;
440: }
441:
442: return result;
443: }
444:
445: public DefaultMutableTreeNode getNextSibling() {
446: if (getParent() == null) {
447: return null;
448: }
449:
450: return (DefaultMutableTreeNode) ((DefaultMutableTreeNode) getParent())
451: .getChildAfter(this );
452: }
453:
454: public DefaultMutableTreeNode getPreviousSibling() {
455: if (getParent() == null) {
456: return null;
457: }
458:
459: return (DefaultMutableTreeNode) ((DefaultMutableTreeNode) getParent())
460: .getChildBefore(this );
461: }
462:
463: public boolean isLeaf() {
464: return children == null || children.isEmpty();
465: }
466:
467: public DefaultMutableTreeNode getFirstLeaf() {
468: TreeNode curNode = this ;
469: while (!curNode.isLeaf() && curNode.getChildCount() > 0) {
470: curNode = curNode.getChildAt(0);
471: }
472:
473: return (DefaultMutableTreeNode) curNode;
474: }
475:
476: public DefaultMutableTreeNode getLastLeaf() {
477: TreeNode curNode = this ;
478: while (!curNode.isLeaf() && curNode.getChildCount() > 0) {
479: curNode = curNode.getChildAt(curNode.getChildCount() - 1);
480: }
481:
482: return (DefaultMutableTreeNode) curNode;
483: }
484:
485: public DefaultMutableTreeNode getNextLeaf() {
486: if (getRoot() == null) {
487: return null;
488: }
489:
490: boolean nodeFound = false;
491: Enumeration depthEnum = depthFirstEnumeration(getRoot());
492: while (depthEnum.hasMoreElements()) {
493: TreeNode nextNode = (TreeNode) depthEnum.nextElement();
494: if (nodeFound && nextNode.isLeaf()) {
495: return (DefaultMutableTreeNode) nextNode;
496: }
497: if (nextNode == this ) {
498: nodeFound = true;
499: }
500: }
501:
502: return null;
503: }
504:
505: public DefaultMutableTreeNode getPreviousLeaf() {
506: if (getRoot() == null) {
507: return null;
508: }
509:
510: TreeNode previousLeaf = null;
511: Enumeration preEnum = preorderEnumeration(getRoot());
512: while (preEnum.hasMoreElements()) {
513: TreeNode nextNode = (TreeNode) preEnum.nextElement();
514: if (nextNode == this ) {
515: return (DefaultMutableTreeNode) previousLeaf;
516: }
517: if (nextNode.isLeaf()) {
518: previousLeaf = nextNode;
519: }
520: }
521:
522: return null;
523: }
524:
525: public int getLeafCount() {
526: int result = 0;
527: Enumeration preEnum = preorderEnumeration();
528: while (preEnum.hasMoreElements()) {
529: DefaultMutableTreeNode nextNode = (DefaultMutableTreeNode) preEnum
530: .nextElement();
531: if (nextNode.isLeaf()) {
532: result++;
533: }
534: }
535:
536: return result;
537: }
538:
539: public String toString() {
540: return getUserObject() != null ? getUserObject().toString()
541: : null;
542: }
543:
544: public Object clone() {
545: return new DefaultMutableTreeNode(getUserObject());
546: }
547:
548: protected TreeNode[] getPathToRoot(final TreeNode node,
549: final int depth) {
550: if (node == null) {
551: return new TreeNode[depth];
552: }
553: TreeNode[] result = getPathToRoot(node.getParent(), depth + 1);
554: result[result.length - 1 - depth] = node;
555:
556: return result;
557: }
558:
559: private Vector getChildren() {
560: if (children == null) {
561: children = new Vector();
562: }
563:
564: return children;
565: }
566:
567: private static Enumeration preorderEnumeration(final TreeNode root) {
568: return new Enumeration() {
569: private Enumeration children;
570: private Enumeration subChildren;
571:
572: public Object nextElement() {
573: if (children == null) {
574: children = root.children();
575: return root;
576: }
577:
578: if (subChildren != null
579: && subChildren.hasMoreElements()) {
580: return subChildren.nextElement();
581: }
582: if (children.hasMoreElements()) {
583: subChildren = preorderEnumeration((TreeNode) children
584: .nextElement());
585: return subChildren.nextElement();
586: }
587:
588: throw new NoSuchElementException(Messages
589: .getString("swing.AA")); //$NON-NLS-1$
590: }
591:
592: public boolean hasMoreElements() {
593: return children == null || children.hasMoreElements()
594: || subChildren != null
595: && subChildren.hasMoreElements();
596: }
597: };
598: }
599:
600: private static Enumeration depthFirstEnumeration(final TreeNode root) {
601: return new Enumeration() {
602: private Enumeration children = root.children();
603: private Enumeration subChildren;
604:
605: public Object nextElement() {
606: if (subChildren != null
607: && subChildren.hasMoreElements()) {
608: return subChildren.nextElement();
609: }
610:
611: if (children != null && children.hasMoreElements()) {
612: subChildren = depthFirstEnumeration((TreeNode) children
613: .nextElement());
614: return subChildren.nextElement();
615: } else if (children != null) {
616: children = null;
617: return root;
618: } else {
619: throw new NoSuchElementException(Messages
620: .getString("swing.AA")); //$NON-NLS-1$
621: }
622: }
623:
624: public boolean hasMoreElements() {
625: return children != null;
626: }
627: };
628: }
629: }
|