author | prr |
Sat, 19 Sep 2015 15:45:59 -0700 | |
changeset 32865 | f9cb6e427f9e |
parent 26353 | b5e3b7fbf56d |
permissions | -rw-r--r-- |
2 | 1 |
/* |
22574
7f8ce0c8c20a
8032627: Add @SuppressWarnings("serial") to appropriate javax.swing classes
darcy
parents:
21593
diff
changeset
|
2 |
* Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved. |
2 | 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
* |
|
5 |
* This code is free software; you can redistribute it and/or modify it |
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
|
5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
2 | 10 |
* |
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
|
15 |
* accompanied this code). |
|
16 |
* |
|
17 |
* You should have received a copy of the GNU General Public License version |
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 |
* |
|
5506 | 21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
22 |
* or visit www.oracle.com if you need additional information or have any |
|
23 |
* questions. |
|
2 | 24 |
*/ |
25 |
||
26 |
package javax.swing.tree; |
|
27 |
// ISSUE: this class depends on nothing in AWT -- move to java.util? |
|
28 |
||
21593
4284575a978e
8027648: Type of overridden property is resolved incorrectly
malenkov
parents:
20458
diff
changeset
|
29 |
import java.beans.Transient; |
2 | 30 |
import java.io.*; |
31 |
import java.util.*; |
|
32 |
||
33 |
||
34 |
/** |
|
35 |
* A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data |
|
36 |
* structure. |
|
37 |
* For examples of using default mutable tree nodes, see |
|
38 |
* <a |
|
20455
f6f9a0c2796b
8020688: Broken links in documentation at http://docs.oracle.com/javase/6/docs/api/index.
mcherkas
parents:
5506
diff
changeset
|
39 |
href="http://docs.oracle.com/javase/tutorial/uiswing/components/tree.html">How to Use Trees</a> |
2 | 40 |
* in <em>The Java Tutorial.</em> |
41 |
* |
|
42 |
* <p> |
|
43 |
* |
|
44 |
* A tree node may have at most one parent and 0 or more children. |
|
45 |
* <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a |
|
46 |
* node's parent and children and also operations for examining the tree that |
|
47 |
* the node is a part of. A node's tree is the set of all nodes that can be |
|
48 |
* reached by starting at the node and following all the possible links to |
|
49 |
* parents and children. A node with no parent is the root of its tree; a |
|
50 |
* node with no children is a leaf. A tree may consist of many subtrees, |
|
51 |
* each node acting as the root for its own subtree. |
|
52 |
* <p> |
|
53 |
* This class provides enumerations for efficiently traversing a tree or |
|
54 |
* subtree in various orders or for following the path between two nodes. |
|
55 |
* A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the |
|
56 |
* use of which is left to the user. Asking a <code>DefaultMutableTreeNode</code> for its |
|
57 |
* string representation with <code>toString()</code> returns the string |
|
58 |
* representation of its user object. |
|
59 |
* <p> |
|
60 |
* <b>This is not a thread safe class.</b>If you intend to use |
|
61 |
* a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you |
|
62 |
* need to do your own synchronizing. A good convention to adopt is |
|
63 |
* synchronizing on the root node of a tree. |
|
64 |
* <p> |
|
65 |
* While DefaultMutableTreeNode implements the MutableTreeNode interface and |
|
66 |
* will allow you to add in any implementation of MutableTreeNode not all |
|
67 |
* of the methods in DefaultMutableTreeNode will be applicable to all |
|
68 |
* MutableTreeNodes implementations. Especially with some of the enumerations |
|
69 |
* that are provided, using some of these methods assumes the |
|
70 |
* DefaultMutableTreeNode contains only DefaultMutableNode instances. All |
|
71 |
* of the TreeNode/MutableTreeNode methods will behave as defined no |
|
72 |
* matter what implementations are added. |
|
73 |
* |
|
74 |
* <p> |
|
75 |
* <strong>Warning:</strong> |
|
76 |
* Serialized objects of this class will not be compatible with |
|
77 |
* future Swing releases. The current serialization support is |
|
78 |
* appropriate for short term storage or RMI between applications running |
|
79 |
* the same version of Swing. As of 1.4, support for long term storage |
|
20458 | 80 |
* of all JavaBeans™ |
2 | 81 |
* has been added to the <code>java.beans</code> package. |
82 |
* Please see {@link java.beans.XMLEncoder}. |
|
83 |
* |
|
84 |
* @see MutableTreeNode |
|
85 |
* |
|
86 |
* @author Rob Davis |
|
87 |
*/ |
|
22574
7f8ce0c8c20a
8032627: Add @SuppressWarnings("serial") to appropriate javax.swing classes
darcy
parents:
21593
diff
changeset
|
88 |
@SuppressWarnings("serial") // Same-version serialization only |
1843
267cc4de4221
6776095: Code improvement and warnings removing from swing packages
rupashka
parents:
2
diff
changeset
|
89 |
public class DefaultMutableTreeNode implements Cloneable, |
2 | 90 |
MutableTreeNode, Serializable |
91 |
{ |
|
92 |
private static final long serialVersionUID = -4298474751201349152L; |
|
93 |
||
94 |
/** |
|
95 |
* An enumeration that is always empty. This is used when an enumeration |
|
96 |
* of a leaf node's children is requested. |
|
97 |
*/ |
|
32865
f9cb6e427f9e
8136783: Run blessed-modifier-order script on java.desktop
prr
parents:
26353
diff
changeset
|
98 |
public static final Enumeration<TreeNode> EMPTY_ENUMERATION |
2 | 99 |
= Collections.emptyEnumeration(); |
100 |
||
101 |
/** this node's parent, or null if this node has no parent */ |
|
102 |
protected MutableTreeNode parent; |
|
103 |
||
104 |
/** array of children, may be null if this node has no children */ |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
105 |
protected Vector<TreeNode> children; |
2 | 106 |
|
107 |
/** optional user object */ |
|
32865
f9cb6e427f9e
8136783: Run blessed-modifier-order script on java.desktop
prr
parents:
26353
diff
changeset
|
108 |
protected transient Object userObject; |
2 | 109 |
|
110 |
/** true if the node is able to have children */ |
|
111 |
protected boolean allowsChildren; |
|
112 |
||
113 |
||
114 |
/** |
|
115 |
* Creates a tree node that has no parent and no children, but which |
|
116 |
* allows children. |
|
117 |
*/ |
|
118 |
public DefaultMutableTreeNode() { |
|
119 |
this(null); |
|
120 |
} |
|
121 |
||
122 |
/** |
|
123 |
* Creates a tree node with no parent, no children, but which allows |
|
124 |
* children, and initializes it with the specified user object. |
|
125 |
* |
|
126 |
* @param userObject an Object provided by the user that constitutes |
|
127 |
* the node's data |
|
128 |
*/ |
|
129 |
public DefaultMutableTreeNode(Object userObject) { |
|
130 |
this(userObject, true); |
|
131 |
} |
|
132 |
||
133 |
/** |
|
134 |
* Creates a tree node with no parent, no children, initialized with |
|
135 |
* the specified user object, and that allows children only if |
|
136 |
* specified. |
|
137 |
* |
|
138 |
* @param userObject an Object provided by the user that constitutes |
|
139 |
* the node's data |
|
140 |
* @param allowsChildren if true, the node is allowed to have child |
|
141 |
* nodes -- otherwise, it is always a leaf node |
|
142 |
*/ |
|
143 |
public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) { |
|
144 |
super(); |
|
145 |
parent = null; |
|
146 |
this.allowsChildren = allowsChildren; |
|
147 |
this.userObject = userObject; |
|
148 |
} |
|
149 |
||
150 |
||
151 |
// |
|
152 |
// Primitives |
|
153 |
// |
|
154 |
||
155 |
/** |
|
156 |
* Removes <code>newChild</code> from its present parent (if it has a |
|
157 |
* parent), sets the child's parent to this node, and then adds the child |
|
158 |
* to this node's child array at index <code>childIndex</code>. |
|
159 |
* <code>newChild</code> must not be null and must not be an ancestor of |
|
160 |
* this node. |
|
161 |
* |
|
162 |
* @param newChild the MutableTreeNode to insert under this node |
|
163 |
* @param childIndex the index in this node's child array |
|
164 |
* where this node is to be inserted |
|
165 |
* @exception ArrayIndexOutOfBoundsException if |
|
166 |
* <code>childIndex</code> is out of bounds |
|
167 |
* @exception IllegalArgumentException if |
|
168 |
* <code>newChild</code> is null or is an |
|
169 |
* ancestor of this node |
|
170 |
* @exception IllegalStateException if this node does not allow |
|
171 |
* children |
|
172 |
* @see #isNodeDescendant |
|
173 |
*/ |
|
174 |
public void insert(MutableTreeNode newChild, int childIndex) { |
|
175 |
if (!allowsChildren) { |
|
176 |
throw new IllegalStateException("node does not allow children"); |
|
177 |
} else if (newChild == null) { |
|
178 |
throw new IllegalArgumentException("new child is null"); |
|
179 |
} else if (isNodeAncestor(newChild)) { |
|
180 |
throw new IllegalArgumentException("new child is an ancestor"); |
|
181 |
} |
|
182 |
||
183 |
MutableTreeNode oldParent = (MutableTreeNode)newChild.getParent(); |
|
184 |
||
185 |
if (oldParent != null) { |
|
186 |
oldParent.remove(newChild); |
|
187 |
} |
|
188 |
newChild.setParent(this); |
|
189 |
if (children == null) { |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
190 |
children = new Vector<>(); |
2 | 191 |
} |
192 |
children.insertElementAt(newChild, childIndex); |
|
193 |
} |
|
194 |
||
195 |
/** |
|
196 |
* Removes the child at the specified index from this node's children |
|
197 |
* and sets that node's parent to null. The child node to remove |
|
198 |
* must be a <code>MutableTreeNode</code>. |
|
199 |
* |
|
200 |
* @param childIndex the index in this node's child array |
|
201 |
* of the child to remove |
|
202 |
* @exception ArrayIndexOutOfBoundsException if |
|
203 |
* <code>childIndex</code> is out of bounds |
|
204 |
*/ |
|
205 |
public void remove(int childIndex) { |
|
206 |
MutableTreeNode child = (MutableTreeNode)getChildAt(childIndex); |
|
207 |
children.removeElementAt(childIndex); |
|
208 |
child.setParent(null); |
|
209 |
} |
|
210 |
||
211 |
/** |
|
212 |
* Sets this node's parent to <code>newParent</code> but does not |
|
213 |
* change the parent's child array. This method is called from |
|
214 |
* <code>insert()</code> and <code>remove()</code> to |
|
215 |
* reassign a child's parent, it should not be messaged from anywhere |
|
216 |
* else. |
|
217 |
* |
|
218 |
* @param newParent this node's new parent |
|
219 |
*/ |
|
21593
4284575a978e
8027648: Type of overridden property is resolved incorrectly
malenkov
parents:
20458
diff
changeset
|
220 |
@Transient |
2 | 221 |
public void setParent(MutableTreeNode newParent) { |
222 |
parent = newParent; |
|
223 |
} |
|
224 |
||
225 |
/** |
|
226 |
* Returns this node's parent or null if this node has no parent. |
|
227 |
* |
|
228 |
* @return this node's parent TreeNode, or null if this node has no parent |
|
229 |
*/ |
|
230 |
public TreeNode getParent() { |
|
231 |
return parent; |
|
232 |
} |
|
233 |
||
234 |
/** |
|
235 |
* Returns the child at the specified index in this node's child array. |
|
236 |
* |
|
237 |
* @param index an index into this node's child array |
|
238 |
* @exception ArrayIndexOutOfBoundsException if <code>index</code> |
|
239 |
* is out of bounds |
|
240 |
* @return the TreeNode in this node's child array at the specified index |
|
241 |
*/ |
|
242 |
public TreeNode getChildAt(int index) { |
|
243 |
if (children == null) { |
|
244 |
throw new ArrayIndexOutOfBoundsException("node has no children"); |
|
245 |
} |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
246 |
return children.elementAt(index); |
2 | 247 |
} |
248 |
||
249 |
/** |
|
250 |
* Returns the number of children of this node. |
|
251 |
* |
|
252 |
* @return an int giving the number of children of this node |
|
253 |
*/ |
|
254 |
public int getChildCount() { |
|
255 |
if (children == null) { |
|
256 |
return 0; |
|
257 |
} else { |
|
258 |
return children.size(); |
|
259 |
} |
|
260 |
} |
|
261 |
||
262 |
/** |
|
263 |
* Returns the index of the specified child in this node's child array. |
|
264 |
* If the specified node is not a child of this node, returns |
|
265 |
* <code>-1</code>. This method performs a linear search and is O(n) |
|
266 |
* where n is the number of children. |
|
267 |
* |
|
268 |
* @param aChild the TreeNode to search for among this node's children |
|
269 |
* @exception IllegalArgumentException if <code>aChild</code> |
|
270 |
* is null |
|
271 |
* @return an int giving the index of the node in this node's child |
|
272 |
* array, or <code>-1</code> if the specified node is a not |
|
273 |
* a child of this node |
|
274 |
*/ |
|
275 |
public int getIndex(TreeNode aChild) { |
|
276 |
if (aChild == null) { |
|
277 |
throw new IllegalArgumentException("argument is null"); |
|
278 |
} |
|
279 |
||
280 |
if (!isNodeChild(aChild)) { |
|
281 |
return -1; |
|
282 |
} |
|
283 |
return children.indexOf(aChild); // linear search |
|
284 |
} |
|
285 |
||
286 |
/** |
|
287 |
* Creates and returns a forward-order enumeration of this node's |
|
288 |
* children. Modifying this node's child array invalidates any child |
|
289 |
* enumerations created before the modification. |
|
290 |
* |
|
291 |
* @return an Enumeration of this node's children |
|
292 |
*/ |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
293 |
public Enumeration<TreeNode> children() { |
2 | 294 |
if (children == null) { |
295 |
return EMPTY_ENUMERATION; |
|
296 |
} else { |
|
297 |
return children.elements(); |
|
298 |
} |
|
299 |
} |
|
300 |
||
301 |
/** |
|
302 |
* Determines whether or not this node is allowed to have children. |
|
303 |
* If <code>allows</code> is false, all of this node's children are |
|
304 |
* removed. |
|
305 |
* <p> |
|
306 |
* Note: By default, a node allows children. |
|
307 |
* |
|
308 |
* @param allows true if this node is allowed to have children |
|
309 |
*/ |
|
310 |
public void setAllowsChildren(boolean allows) { |
|
311 |
if (allows != allowsChildren) { |
|
312 |
allowsChildren = allows; |
|
313 |
if (!allowsChildren) { |
|
314 |
removeAllChildren(); |
|
315 |
} |
|
316 |
} |
|
317 |
} |
|
318 |
||
319 |
/** |
|
320 |
* Returns true if this node is allowed to have children. |
|
321 |
* |
|
322 |
* @return true if this node allows children, else false |
|
323 |
*/ |
|
324 |
public boolean getAllowsChildren() { |
|
325 |
return allowsChildren; |
|
326 |
} |
|
327 |
||
328 |
/** |
|
329 |
* Sets the user object for this node to <code>userObject</code>. |
|
330 |
* |
|
331 |
* @param userObject the Object that constitutes this node's |
|
332 |
* user-specified data |
|
333 |
* @see #getUserObject |
|
334 |
* @see #toString |
|
335 |
*/ |
|
336 |
public void setUserObject(Object userObject) { |
|
337 |
this.userObject = userObject; |
|
338 |
} |
|
339 |
||
340 |
/** |
|
341 |
* Returns this node's user object. |
|
342 |
* |
|
343 |
* @return the Object stored at this node by the user |
|
344 |
* @see #setUserObject |
|
345 |
* @see #toString |
|
346 |
*/ |
|
347 |
public Object getUserObject() { |
|
348 |
return userObject; |
|
349 |
} |
|
350 |
||
351 |
||
352 |
// |
|
353 |
// Derived methods |
|
354 |
// |
|
355 |
||
356 |
/** |
|
357 |
* Removes the subtree rooted at this node from the tree, giving this |
|
358 |
* node a null parent. Does nothing if this node is the root of its |
|
359 |
* tree. |
|
360 |
*/ |
|
361 |
public void removeFromParent() { |
|
362 |
MutableTreeNode parent = (MutableTreeNode)getParent(); |
|
363 |
if (parent != null) { |
|
364 |
parent.remove(this); |
|
365 |
} |
|
366 |
} |
|
367 |
||
368 |
/** |
|
369 |
* Removes <code>aChild</code> from this node's child array, giving it a |
|
370 |
* null parent. |
|
371 |
* |
|
372 |
* @param aChild a child of this node to remove |
|
373 |
* @exception IllegalArgumentException if <code>aChild</code> |
|
374 |
* is null or is not a child of this node |
|
375 |
*/ |
|
376 |
public void remove(MutableTreeNode aChild) { |
|
377 |
if (aChild == null) { |
|
378 |
throw new IllegalArgumentException("argument is null"); |
|
379 |
} |
|
380 |
||
381 |
if (!isNodeChild(aChild)) { |
|
382 |
throw new IllegalArgumentException("argument is not a child"); |
|
383 |
} |
|
384 |
remove(getIndex(aChild)); // linear search |
|
385 |
} |
|
386 |
||
387 |
/** |
|
388 |
* Removes all of this node's children, setting their parents to null. |
|
389 |
* If this node has no children, this method does nothing. |
|
390 |
*/ |
|
391 |
public void removeAllChildren() { |
|
392 |
for (int i = getChildCount()-1; i >= 0; i--) { |
|
393 |
remove(i); |
|
394 |
} |
|
395 |
} |
|
396 |
||
397 |
/** |
|
398 |
* Removes <code>newChild</code> from its parent and makes it a child of |
|
399 |
* this node by adding it to the end of this node's child array. |
|
400 |
* |
|
401 |
* @see #insert |
|
402 |
* @param newChild node to add as a child of this node |
|
403 |
* @exception IllegalArgumentException if <code>newChild</code> |
|
404 |
* is null |
|
405 |
* @exception IllegalStateException if this node does not allow |
|
406 |
* children |
|
407 |
*/ |
|
408 |
public void add(MutableTreeNode newChild) { |
|
409 |
if(newChild != null && newChild.getParent() == this) |
|
410 |
insert(newChild, getChildCount() - 1); |
|
411 |
else |
|
412 |
insert(newChild, getChildCount()); |
|
413 |
} |
|
414 |
||
415 |
||
416 |
||
417 |
// |
|
418 |
// Tree Queries |
|
419 |
// |
|
420 |
||
421 |
/** |
|
422 |
* Returns true if <code>anotherNode</code> is an ancestor of this node |
|
423 |
* -- if it is this node, this node's parent, or an ancestor of this |
|
424 |
* node's parent. (Note that a node is considered an ancestor of itself.) |
|
425 |
* If <code>anotherNode</code> is null, this method returns false. This |
|
426 |
* operation is at worst O(h) where h is the distance from the root to |
|
427 |
* this node. |
|
428 |
* |
|
429 |
* @see #isNodeDescendant |
|
430 |
* @see #getSharedAncestor |
|
431 |
* @param anotherNode node to test as an ancestor of this node |
|
432 |
* @return true if this node is a descendant of <code>anotherNode</code> |
|
433 |
*/ |
|
434 |
public boolean isNodeAncestor(TreeNode anotherNode) { |
|
435 |
if (anotherNode == null) { |
|
436 |
return false; |
|
437 |
} |
|
438 |
||
439 |
TreeNode ancestor = this; |
|
440 |
||
441 |
do { |
|
442 |
if (ancestor == anotherNode) { |
|
443 |
return true; |
|
444 |
} |
|
445 |
} while((ancestor = ancestor.getParent()) != null); |
|
446 |
||
447 |
return false; |
|
448 |
} |
|
449 |
||
450 |
/** |
|
451 |
* Returns true if <code>anotherNode</code> is a descendant of this node |
|
452 |
* -- if it is this node, one of this node's children, or a descendant of |
|
453 |
* one of this node's children. Note that a node is considered a |
|
454 |
* descendant of itself. If <code>anotherNode</code> is null, returns |
|
455 |
* false. This operation is at worst O(h) where h is the distance from the |
|
456 |
* root to <code>anotherNode</code>. |
|
457 |
* |
|
458 |
* @see #isNodeAncestor |
|
459 |
* @see #getSharedAncestor |
|
460 |
* @param anotherNode node to test as descendant of this node |
|
461 |
* @return true if this node is an ancestor of <code>anotherNode</code> |
|
462 |
*/ |
|
463 |
public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) { |
|
464 |
if (anotherNode == null) |
|
465 |
return false; |
|
466 |
||
467 |
return anotherNode.isNodeAncestor(this); |
|
468 |
} |
|
469 |
||
470 |
/** |
|
471 |
* Returns the nearest common ancestor to this node and <code>aNode</code>. |
|
472 |
* Returns null, if no such ancestor exists -- if this node and |
|
473 |
* <code>aNode</code> are in different trees or if <code>aNode</code> is |
|
474 |
* null. A node is considered an ancestor of itself. |
|
475 |
* |
|
476 |
* @see #isNodeAncestor |
|
477 |
* @see #isNodeDescendant |
|
478 |
* @param aNode node to find common ancestor with |
|
479 |
* @return nearest ancestor common to this node and <code>aNode</code>, |
|
480 |
* or null if none |
|
481 |
*/ |
|
482 |
public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) { |
|
483 |
if (aNode == this) { |
|
484 |
return this; |
|
485 |
} else if (aNode == null) { |
|
486 |
return null; |
|
487 |
} |
|
488 |
||
489 |
int level1, level2, diff; |
|
490 |
TreeNode node1, node2; |
|
491 |
||
492 |
level1 = getLevel(); |
|
493 |
level2 = aNode.getLevel(); |
|
494 |
||
495 |
if (level2 > level1) { |
|
496 |
diff = level2 - level1; |
|
497 |
node1 = aNode; |
|
498 |
node2 = this; |
|
499 |
} else { |
|
500 |
diff = level1 - level2; |
|
501 |
node1 = this; |
|
502 |
node2 = aNode; |
|
503 |
} |
|
504 |
||
505 |
// Go up the tree until the nodes are at the same level |
|
506 |
while (diff > 0) { |
|
507 |
node1 = node1.getParent(); |
|
508 |
diff--; |
|
509 |
} |
|
510 |
||
511 |
// Move up the tree until we find a common ancestor. Since we know |
|
512 |
// that both nodes are at the same level, we won't cross paths |
|
513 |
// unknowingly (if there is a common ancestor, both nodes hit it in |
|
514 |
// the same iteration). |
|
515 |
||
516 |
do { |
|
517 |
if (node1 == node2) { |
|
518 |
return node1; |
|
519 |
} |
|
520 |
node1 = node1.getParent(); |
|
521 |
node2 = node2.getParent(); |
|
522 |
} while (node1 != null);// only need to check one -- they're at the |
|
523 |
// same level so if one is null, the other is |
|
524 |
||
525 |
if (node1 != null || node2 != null) { |
|
526 |
throw new Error ("nodes should be null"); |
|
527 |
} |
|
528 |
||
529 |
return null; |
|
530 |
} |
|
531 |
||
532 |
||
533 |
/** |
|
534 |
* Returns true if and only if <code>aNode</code> is in the same tree |
|
535 |
* as this node. Returns false if <code>aNode</code> is null. |
|
536 |
* |
|
24495
a5c854a00679
8042089: Fix doclint warnings from javax.swing.tree and javax.swing.undo packages
yan
parents:
22574
diff
changeset
|
537 |
* @param aNode node to find common ancestor with |
2 | 538 |
* @see #getSharedAncestor |
539 |
* @see #getRoot |
|
540 |
* @return true if <code>aNode</code> is in the same tree as this node; |
|
541 |
* false if <code>aNode</code> is null |
|
542 |
*/ |
|
543 |
public boolean isNodeRelated(DefaultMutableTreeNode aNode) { |
|
544 |
return (aNode != null) && (getRoot() == aNode.getRoot()); |
|
545 |
} |
|
546 |
||
547 |
||
548 |
/** |
|
549 |
* Returns the depth of the tree rooted at this node -- the longest |
|
550 |
* distance from this node to a leaf. If this node has no children, |
|
551 |
* returns 0. This operation is much more expensive than |
|
552 |
* <code>getLevel()</code> because it must effectively traverse the entire |
|
553 |
* tree rooted at this node. |
|
554 |
* |
|
555 |
* @see #getLevel |
|
556 |
* @return the depth of the tree whose root is this node |
|
557 |
*/ |
|
558 |
public int getDepth() { |
|
559 |
Object last = null; |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
560 |
Enumeration<TreeNode> enum_ = breadthFirstEnumeration(); |
2 | 561 |
|
562 |
while (enum_.hasMoreElements()) { |
|
563 |
last = enum_.nextElement(); |
|
564 |
} |
|
565 |
||
566 |
if (last == null) { |
|
567 |
throw new Error ("nodes should be null"); |
|
568 |
} |
|
569 |
||
570 |
return ((DefaultMutableTreeNode)last).getLevel() - getLevel(); |
|
571 |
} |
|
572 |
||
573 |
||
574 |
||
575 |
/** |
|
576 |
* Returns the number of levels above this node -- the distance from |
|
577 |
* the root to this node. If this node is the root, returns 0. |
|
578 |
* |
|
579 |
* @see #getDepth |
|
580 |
* @return the number of levels above this node |
|
581 |
*/ |
|
582 |
public int getLevel() { |
|
583 |
TreeNode ancestor; |
|
584 |
int levels = 0; |
|
585 |
||
586 |
ancestor = this; |
|
587 |
while((ancestor = ancestor.getParent()) != null){ |
|
588 |
levels++; |
|
589 |
} |
|
590 |
||
591 |
return levels; |
|
592 |
} |
|
593 |
||
594 |
||
595 |
/** |
|
596 |
* Returns the path from the root, to get to this node. The last |
|
597 |
* element in the path is this node. |
|
598 |
* |
|
599 |
* @return an array of TreeNode objects giving the path, where the |
|
600 |
* first element in the path is the root and the last |
|
601 |
* element is this node. |
|
602 |
*/ |
|
603 |
public TreeNode[] getPath() { |
|
604 |
return getPathToRoot(this, 0); |
|
605 |
} |
|
606 |
||
607 |
/** |
|
608 |
* Builds the parents of node up to and including the root node, |
|
609 |
* where the original node is the last element in the returned array. |
|
610 |
* The length of the returned array gives the node's depth in the |
|
611 |
* tree. |
|
612 |
* |
|
613 |
* @param aNode the TreeNode to get the path for |
|
614 |
* @param depth an int giving the number of steps already taken towards |
|
615 |
* the root (on recursive calls), used to size the returned array |
|
616 |
* @return an array of TreeNodes giving the path from the root to the |
|
617 |
* specified node |
|
618 |
*/ |
|
619 |
protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) { |
|
620 |
TreeNode[] retNodes; |
|
621 |
||
622 |
/* Check for null, in case someone passed in a null node, or |
|
623 |
they passed in an element that isn't rooted at root. */ |
|
624 |
if(aNode == null) { |
|
625 |
if(depth == 0) |
|
626 |
return null; |
|
627 |
else |
|
628 |
retNodes = new TreeNode[depth]; |
|
629 |
} |
|
630 |
else { |
|
631 |
depth++; |
|
632 |
retNodes = getPathToRoot(aNode.getParent(), depth); |
|
633 |
retNodes[retNodes.length - depth] = aNode; |
|
634 |
} |
|
635 |
return retNodes; |
|
636 |
} |
|
637 |
||
638 |
/** |
|
639 |
* Returns the user object path, from the root, to get to this node. |
|
640 |
* If some of the TreeNodes in the path have null user objects, the |
|
641 |
* returned path will contain nulls. |
|
24495
a5c854a00679
8042089: Fix doclint warnings from javax.swing.tree and javax.swing.undo packages
yan
parents:
22574
diff
changeset
|
642 |
* |
a5c854a00679
8042089: Fix doclint warnings from javax.swing.tree and javax.swing.undo packages
yan
parents:
22574
diff
changeset
|
643 |
* @return the user object path, from the root, to get to this node |
2 | 644 |
*/ |
645 |
public Object[] getUserObjectPath() { |
|
646 |
TreeNode[] realPath = getPath(); |
|
647 |
Object[] retPath = new Object[realPath.length]; |
|
648 |
||
649 |
for(int counter = 0; counter < realPath.length; counter++) |
|
650 |
retPath[counter] = ((DefaultMutableTreeNode)realPath[counter]) |
|
651 |
.getUserObject(); |
|
652 |
return retPath; |
|
653 |
} |
|
654 |
||
655 |
/** |
|
656 |
* Returns the root of the tree that contains this node. The root is |
|
657 |
* the ancestor with a null parent. |
|
658 |
* |
|
659 |
* @see #isNodeAncestor |
|
660 |
* @return the root of the tree that contains this node |
|
661 |
*/ |
|
662 |
public TreeNode getRoot() { |
|
663 |
TreeNode ancestor = this; |
|
664 |
TreeNode previous; |
|
665 |
||
666 |
do { |
|
667 |
previous = ancestor; |
|
668 |
ancestor = ancestor.getParent(); |
|
669 |
} while (ancestor != null); |
|
670 |
||
671 |
return previous; |
|
672 |
} |
|
673 |
||
674 |
||
675 |
/** |
|
676 |
* Returns true if this node is the root of the tree. The root is |
|
677 |
* the only node in the tree with a null parent; every tree has exactly |
|
678 |
* one root. |
|
679 |
* |
|
680 |
* @return true if this node is the root of its tree |
|
681 |
*/ |
|
682 |
public boolean isRoot() { |
|
683 |
return getParent() == null; |
|
684 |
} |
|
685 |
||
686 |
||
687 |
/** |
|
688 |
* Returns the node that follows this node in a preorder traversal of this |
|
689 |
* node's tree. Returns null if this node is the last node of the |
|
690 |
* traversal. This is an inefficient way to traverse the entire tree; use |
|
691 |
* an enumeration, instead. |
|
692 |
* |
|
693 |
* @see #preorderEnumeration |
|
694 |
* @return the node that follows this node in a preorder traversal, or |
|
695 |
* null if this node is last |
|
696 |
*/ |
|
697 |
public DefaultMutableTreeNode getNextNode() { |
|
698 |
if (getChildCount() == 0) { |
|
699 |
// No children, so look for nextSibling |
|
700 |
DefaultMutableTreeNode nextSibling = getNextSibling(); |
|
701 |
||
702 |
if (nextSibling == null) { |
|
703 |
DefaultMutableTreeNode aNode = (DefaultMutableTreeNode)getParent(); |
|
704 |
||
705 |
do { |
|
706 |
if (aNode == null) { |
|
707 |
return null; |
|
708 |
} |
|
709 |
||
710 |
nextSibling = aNode.getNextSibling(); |
|
711 |
if (nextSibling != null) { |
|
712 |
return nextSibling; |
|
713 |
} |
|
714 |
||
715 |
aNode = (DefaultMutableTreeNode)aNode.getParent(); |
|
716 |
} while(true); |
|
717 |
} else { |
|
718 |
return nextSibling; |
|
719 |
} |
|
720 |
} else { |
|
721 |
return (DefaultMutableTreeNode)getChildAt(0); |
|
722 |
} |
|
723 |
} |
|
724 |
||
725 |
||
726 |
/** |
|
727 |
* Returns the node that precedes this node in a preorder traversal of |
|
728 |
* this node's tree. Returns <code>null</code> if this node is the |
|
729 |
* first node of the traversal -- the root of the tree. |
|
730 |
* This is an inefficient way to |
|
731 |
* traverse the entire tree; use an enumeration, instead. |
|
732 |
* |
|
733 |
* @see #preorderEnumeration |
|
734 |
* @return the node that precedes this node in a preorder traversal, or |
|
735 |
* null if this node is the first |
|
736 |
*/ |
|
737 |
public DefaultMutableTreeNode getPreviousNode() { |
|
738 |
DefaultMutableTreeNode previousSibling; |
|
739 |
DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent(); |
|
740 |
||
741 |
if (myParent == null) { |
|
742 |
return null; |
|
743 |
} |
|
744 |
||
745 |
previousSibling = getPreviousSibling(); |
|
746 |
||
747 |
if (previousSibling != null) { |
|
748 |
if (previousSibling.getChildCount() == 0) |
|
749 |
return previousSibling; |
|
750 |
else |
|
751 |
return previousSibling.getLastLeaf(); |
|
752 |
} else { |
|
753 |
return myParent; |
|
754 |
} |
|
755 |
} |
|
756 |
||
757 |
/** |
|
758 |
* Creates and returns an enumeration that traverses the subtree rooted at |
|
759 |
* this node in preorder. The first node returned by the enumeration's |
|
760 |
* <code>nextElement()</code> method is this node.<P> |
|
761 |
* |
|
762 |
* Modifying the tree by inserting, removing, or moving a node invalidates |
|
763 |
* any enumerations created before the modification. |
|
764 |
* |
|
765 |
* @see #postorderEnumeration |
|
766 |
* @return an enumeration for traversing the tree in preorder |
|
767 |
*/ |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
768 |
public Enumeration<TreeNode> preorderEnumeration() { |
2 | 769 |
return new PreorderEnumeration(this); |
770 |
} |
|
771 |
||
772 |
/** |
|
773 |
* Creates and returns an enumeration that traverses the subtree rooted at |
|
774 |
* this node in postorder. The first node returned by the enumeration's |
|
775 |
* <code>nextElement()</code> method is the leftmost leaf. This is the |
|
776 |
* same as a depth-first traversal.<P> |
|
777 |
* |
|
778 |
* Modifying the tree by inserting, removing, or moving a node invalidates |
|
779 |
* any enumerations created before the modification. |
|
780 |
* |
|
781 |
* @see #depthFirstEnumeration |
|
782 |
* @see #preorderEnumeration |
|
783 |
* @return an enumeration for traversing the tree in postorder |
|
784 |
*/ |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
785 |
public Enumeration<TreeNode> postorderEnumeration() { |
2 | 786 |
return new PostorderEnumeration(this); |
787 |
} |
|
788 |
||
789 |
/** |
|
790 |
* Creates and returns an enumeration that traverses the subtree rooted at |
|
791 |
* this node in breadth-first order. The first node returned by the |
|
792 |
* enumeration's <code>nextElement()</code> method is this node.<P> |
|
793 |
* |
|
794 |
* Modifying the tree by inserting, removing, or moving a node invalidates |
|
795 |
* any enumerations created before the modification. |
|
796 |
* |
|
797 |
* @see #depthFirstEnumeration |
|
798 |
* @return an enumeration for traversing the tree in breadth-first order |
|
799 |
*/ |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
800 |
public Enumeration<TreeNode> breadthFirstEnumeration() { |
2 | 801 |
return new BreadthFirstEnumeration(this); |
802 |
} |
|
803 |
||
804 |
/** |
|
805 |
* Creates and returns an enumeration that traverses the subtree rooted at |
|
806 |
* this node in depth-first order. The first node returned by the |
|
807 |
* enumeration's <code>nextElement()</code> method is the leftmost leaf. |
|
808 |
* This is the same as a postorder traversal.<P> |
|
809 |
* |
|
810 |
* Modifying the tree by inserting, removing, or moving a node invalidates |
|
811 |
* any enumerations created before the modification. |
|
812 |
* |
|
813 |
* @see #breadthFirstEnumeration |
|
814 |
* @see #postorderEnumeration |
|
815 |
* @return an enumeration for traversing the tree in depth-first order |
|
816 |
*/ |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
817 |
public Enumeration<TreeNode> depthFirstEnumeration() { |
2 | 818 |
return postorderEnumeration(); |
819 |
} |
|
820 |
||
821 |
/** |
|
822 |
* Creates and returns an enumeration that follows the path from |
|
823 |
* <code>ancestor</code> to this node. The enumeration's |
|
824 |
* <code>nextElement()</code> method first returns <code>ancestor</code>, |
|
825 |
* then the child of <code>ancestor</code> that is an ancestor of this |
|
826 |
* node, and so on, and finally returns this node. Creation of the |
|
827 |
* enumeration is O(m) where m is the number of nodes between this node |
|
828 |
* and <code>ancestor</code>, inclusive. Each <code>nextElement()</code> |
|
829 |
* message is O(1).<P> |
|
830 |
* |
|
831 |
* Modifying the tree by inserting, removing, or moving a node invalidates |
|
832 |
* any enumerations created before the modification. |
|
833 |
* |
|
24495
a5c854a00679
8042089: Fix doclint warnings from javax.swing.tree and javax.swing.undo packages
yan
parents:
22574
diff
changeset
|
834 |
* @param ancestor the node to start enumeration from |
2 | 835 |
* @see #isNodeAncestor |
836 |
* @see #isNodeDescendant |
|
837 |
* @exception IllegalArgumentException if <code>ancestor</code> is |
|
838 |
* not an ancestor of this node |
|
839 |
* @return an enumeration for following the path from an ancestor of |
|
840 |
* this node to this one |
|
841 |
*/ |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
842 |
public Enumeration<TreeNode> pathFromAncestorEnumeration(TreeNode ancestor) { |
2 | 843 |
return new PathBetweenNodesEnumeration(ancestor, this); |
844 |
} |
|
845 |
||
846 |
||
847 |
// |
|
848 |
// Child Queries |
|
849 |
// |
|
850 |
||
851 |
/** |
|
852 |
* Returns true if <code>aNode</code> is a child of this node. If |
|
853 |
* <code>aNode</code> is null, this method returns false. |
|
854 |
* |
|
24495
a5c854a00679
8042089: Fix doclint warnings from javax.swing.tree and javax.swing.undo packages
yan
parents:
22574
diff
changeset
|
855 |
* @param aNode the node to determinate whether it is a child |
2 | 856 |
* @return true if <code>aNode</code> is a child of this node; false if |
857 |
* <code>aNode</code> is null |
|
858 |
*/ |
|
859 |
public boolean isNodeChild(TreeNode aNode) { |
|
860 |
boolean retval; |
|
861 |
||
862 |
if (aNode == null) { |
|
863 |
retval = false; |
|
864 |
} else { |
|
865 |
if (getChildCount() == 0) { |
|
866 |
retval = false; |
|
867 |
} else { |
|
868 |
retval = (aNode.getParent() == this); |
|
869 |
} |
|
870 |
} |
|
871 |
||
872 |
return retval; |
|
873 |
} |
|
874 |
||
875 |
||
876 |
/** |
|
877 |
* Returns this node's first child. If this node has no children, |
|
878 |
* throws NoSuchElementException. |
|
879 |
* |
|
880 |
* @return the first child of this node |
|
881 |
* @exception NoSuchElementException if this node has no children |
|
882 |
*/ |
|
883 |
public TreeNode getFirstChild() { |
|
884 |
if (getChildCount() == 0) { |
|
885 |
throw new NoSuchElementException("node has no children"); |
|
886 |
} |
|
887 |
return getChildAt(0); |
|
888 |
} |
|
889 |
||
890 |
||
891 |
/** |
|
892 |
* Returns this node's last child. If this node has no children, |
|
893 |
* throws NoSuchElementException. |
|
894 |
* |
|
895 |
* @return the last child of this node |
|
896 |
* @exception NoSuchElementException if this node has no children |
|
897 |
*/ |
|
898 |
public TreeNode getLastChild() { |
|
899 |
if (getChildCount() == 0) { |
|
900 |
throw new NoSuchElementException("node has no children"); |
|
901 |
} |
|
902 |
return getChildAt(getChildCount()-1); |
|
903 |
} |
|
904 |
||
905 |
||
906 |
/** |
|
907 |
* Returns the child in this node's child array that immediately |
|
908 |
* follows <code>aChild</code>, which must be a child of this node. If |
|
909 |
* <code>aChild</code> is the last child, returns null. This method |
|
910 |
* performs a linear search of this node's children for |
|
911 |
* <code>aChild</code> and is O(n) where n is the number of children; to |
|
912 |
* traverse the entire array of children, use an enumeration instead. |
|
913 |
* |
|
24495
a5c854a00679
8042089: Fix doclint warnings from javax.swing.tree and javax.swing.undo packages
yan
parents:
22574
diff
changeset
|
914 |
* @param aChild the child node to look for next child after it |
2 | 915 |
* @see #children |
916 |
* @exception IllegalArgumentException if <code>aChild</code> is |
|
917 |
* null or is not a child of this node |
|
918 |
* @return the child of this node that immediately follows |
|
919 |
* <code>aChild</code> |
|
920 |
*/ |
|
921 |
public TreeNode getChildAfter(TreeNode aChild) { |
|
922 |
if (aChild == null) { |
|
923 |
throw new IllegalArgumentException("argument is null"); |
|
924 |
} |
|
925 |
||
926 |
int index = getIndex(aChild); // linear search |
|
927 |
||
928 |
if (index == -1) { |
|
929 |
throw new IllegalArgumentException("node is not a child"); |
|
930 |
} |
|
931 |
||
932 |
if (index < getChildCount() - 1) { |
|
933 |
return getChildAt(index + 1); |
|
934 |
} else { |
|
935 |
return null; |
|
936 |
} |
|
937 |
} |
|
938 |
||
939 |
||
940 |
/** |
|
941 |
* Returns the child in this node's child array that immediately |
|
942 |
* precedes <code>aChild</code>, which must be a child of this node. If |
|
943 |
* <code>aChild</code> is the first child, returns null. This method |
|
944 |
* performs a linear search of this node's children for <code>aChild</code> |
|
945 |
* and is O(n) where n is the number of children. |
|
946 |
* |
|
24495
a5c854a00679
8042089: Fix doclint warnings from javax.swing.tree and javax.swing.undo packages
yan
parents:
22574
diff
changeset
|
947 |
* @param aChild the child node to look for previous child before it |
2 | 948 |
* @exception IllegalArgumentException if <code>aChild</code> is null |
949 |
* or is not a child of this node |
|
950 |
* @return the child of this node that immediately precedes |
|
951 |
* <code>aChild</code> |
|
952 |
*/ |
|
953 |
public TreeNode getChildBefore(TreeNode aChild) { |
|
954 |
if (aChild == null) { |
|
955 |
throw new IllegalArgumentException("argument is null"); |
|
956 |
} |
|
957 |
||
958 |
int index = getIndex(aChild); // linear search |
|
959 |
||
960 |
if (index == -1) { |
|
961 |
throw new IllegalArgumentException("argument is not a child"); |
|
962 |
} |
|
963 |
||
964 |
if (index > 0) { |
|
965 |
return getChildAt(index - 1); |
|
966 |
} else { |
|
967 |
return null; |
|
968 |
} |
|
969 |
} |
|
970 |
||
971 |
||
972 |
// |
|
973 |
// Sibling Queries |
|
974 |
// |
|
975 |
||
976 |
||
977 |
/** |
|
978 |
* Returns true if <code>anotherNode</code> is a sibling of (has the |
|
979 |
* same parent as) this node. A node is its own sibling. If |
|
980 |
* <code>anotherNode</code> is null, returns false. |
|
981 |
* |
|
982 |
* @param anotherNode node to test as sibling of this node |
|
983 |
* @return true if <code>anotherNode</code> is a sibling of this node |
|
984 |
*/ |
|
985 |
public boolean isNodeSibling(TreeNode anotherNode) { |
|
986 |
boolean retval; |
|
987 |
||
988 |
if (anotherNode == null) { |
|
989 |
retval = false; |
|
990 |
} else if (anotherNode == this) { |
|
991 |
retval = true; |
|
992 |
} else { |
|
993 |
TreeNode myParent = getParent(); |
|
994 |
retval = (myParent != null && myParent == anotherNode.getParent()); |
|
995 |
||
996 |
if (retval && !((DefaultMutableTreeNode)getParent()) |
|
997 |
.isNodeChild(anotherNode)) { |
|
998 |
throw new Error("sibling has different parent"); |
|
999 |
} |
|
1000 |
} |
|
1001 |
||
1002 |
return retval; |
|
1003 |
} |
|
1004 |
||
1005 |
||
1006 |
/** |
|
1007 |
* Returns the number of siblings of this node. A node is its own sibling |
|
1008 |
* (if it has no parent or no siblings, this method returns |
|
1009 |
* <code>1</code>). |
|
1010 |
* |
|
1011 |
* @return the number of siblings of this node |
|
1012 |
*/ |
|
1013 |
public int getSiblingCount() { |
|
1014 |
TreeNode myParent = getParent(); |
|
1015 |
||
1016 |
if (myParent == null) { |
|
1017 |
return 1; |
|
1018 |
} else { |
|
1019 |
return myParent.getChildCount(); |
|
1020 |
} |
|
1021 |
} |
|
1022 |
||
1023 |
||
1024 |
/** |
|
1025 |
* Returns the next sibling of this node in the parent's children array. |
|
1026 |
* Returns null if this node has no parent or is the parent's last child. |
|
1027 |
* This method performs a linear search that is O(n) where n is the number |
|
1028 |
* of children; to traverse the entire array, use the parent's child |
|
1029 |
* enumeration instead. |
|
1030 |
* |
|
1031 |
* @see #children |
|
1032 |
* @return the sibling of this node that immediately follows this node |
|
1033 |
*/ |
|
1034 |
public DefaultMutableTreeNode getNextSibling() { |
|
1035 |
DefaultMutableTreeNode retval; |
|
1036 |
||
1037 |
DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent(); |
|
1038 |
||
1039 |
if (myParent == null) { |
|
1040 |
retval = null; |
|
1041 |
} else { |
|
1042 |
retval = (DefaultMutableTreeNode)myParent.getChildAfter(this); // linear search |
|
1043 |
} |
|
1044 |
||
1045 |
if (retval != null && !isNodeSibling(retval)) { |
|
1046 |
throw new Error("child of parent is not a sibling"); |
|
1047 |
} |
|
1048 |
||
1049 |
return retval; |
|
1050 |
} |
|
1051 |
||
1052 |
||
1053 |
/** |
|
1054 |
* Returns the previous sibling of this node in the parent's children |
|
1055 |
* array. Returns null if this node has no parent or is the parent's |
|
1056 |
* first child. This method performs a linear search that is O(n) where n |
|
1057 |
* is the number of children. |
|
1058 |
* |
|
1059 |
* @return the sibling of this node that immediately precedes this node |
|
1060 |
*/ |
|
1061 |
public DefaultMutableTreeNode getPreviousSibling() { |
|
1062 |
DefaultMutableTreeNode retval; |
|
1063 |
||
1064 |
DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent(); |
|
1065 |
||
1066 |
if (myParent == null) { |
|
1067 |
retval = null; |
|
1068 |
} else { |
|
1069 |
retval = (DefaultMutableTreeNode)myParent.getChildBefore(this); // linear search |
|
1070 |
} |
|
1071 |
||
1072 |
if (retval != null && !isNodeSibling(retval)) { |
|
1073 |
throw new Error("child of parent is not a sibling"); |
|
1074 |
} |
|
1075 |
||
1076 |
return retval; |
|
1077 |
} |
|
1078 |
||
1079 |
||
1080 |
||
1081 |
// |
|
1082 |
// Leaf Queries |
|
1083 |
// |
|
1084 |
||
1085 |
/** |
|
1086 |
* Returns true if this node has no children. To distinguish between |
|
1087 |
* nodes that have no children and nodes that <i>cannot</i> have |
|
1088 |
* children (e.g. to distinguish files from empty directories), use this |
|
1089 |
* method in conjunction with <code>getAllowsChildren</code> |
|
1090 |
* |
|
1091 |
* @see #getAllowsChildren |
|
1092 |
* @return true if this node has no children |
|
1093 |
*/ |
|
1094 |
public boolean isLeaf() { |
|
1095 |
return (getChildCount() == 0); |
|
1096 |
} |
|
1097 |
||
1098 |
||
1099 |
/** |
|
1100 |
* Finds and returns the first leaf that is a descendant of this node -- |
|
1101 |
* either this node or its first child's first leaf. |
|
1102 |
* Returns this node if it is a leaf. |
|
1103 |
* |
|
1104 |
* @see #isLeaf |
|
1105 |
* @see #isNodeDescendant |
|
1106 |
* @return the first leaf in the subtree rooted at this node |
|
1107 |
*/ |
|
1108 |
public DefaultMutableTreeNode getFirstLeaf() { |
|
1109 |
DefaultMutableTreeNode node = this; |
|
1110 |
||
1111 |
while (!node.isLeaf()) { |
|
1112 |
node = (DefaultMutableTreeNode)node.getFirstChild(); |
|
1113 |
} |
|
1114 |
||
1115 |
return node; |
|
1116 |
} |
|
1117 |
||
1118 |
||
1119 |
/** |
|
1120 |
* Finds and returns the last leaf that is a descendant of this node -- |
|
1121 |
* either this node or its last child's last leaf. |
|
1122 |
* Returns this node if it is a leaf. |
|
1123 |
* |
|
1124 |
* @see #isLeaf |
|
1125 |
* @see #isNodeDescendant |
|
1126 |
* @return the last leaf in the subtree rooted at this node |
|
1127 |
*/ |
|
1128 |
public DefaultMutableTreeNode getLastLeaf() { |
|
1129 |
DefaultMutableTreeNode node = this; |
|
1130 |
||
1131 |
while (!node.isLeaf()) { |
|
1132 |
node = (DefaultMutableTreeNode)node.getLastChild(); |
|
1133 |
} |
|
1134 |
||
1135 |
return node; |
|
1136 |
} |
|
1137 |
||
1138 |
||
1139 |
/** |
|
1140 |
* Returns the leaf after this node or null if this node is the |
|
1141 |
* last leaf in the tree. |
|
1142 |
* <p> |
|
1143 |
* In this implementation of the <code>MutableNode</code> interface, |
|
1144 |
* this operation is very inefficient. In order to determine the |
|
1145 |
* next node, this method first performs a linear search in the |
|
1146 |
* parent's child-list in order to find the current node. |
|
1147 |
* <p> |
|
1148 |
* That implementation makes the operation suitable for short |
|
1149 |
* traversals from a known position. But to traverse all of the |
|
1150 |
* leaves in the tree, you should use <code>depthFirstEnumeration</code> |
|
1151 |
* to enumerate the nodes in the tree and use <code>isLeaf</code> |
|
1152 |
* on each node to determine which are leaves. |
|
1153 |
* |
|
1154 |
* @see #depthFirstEnumeration |
|
1155 |
* @see #isLeaf |
|
1156 |
* @return returns the next leaf past this node |
|
1157 |
*/ |
|
1158 |
public DefaultMutableTreeNode getNextLeaf() { |
|
1159 |
DefaultMutableTreeNode nextSibling; |
|
1160 |
DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent(); |
|
1161 |
||
1162 |
if (myParent == null) |
|
1163 |
return null; |
|
1164 |
||
1165 |
nextSibling = getNextSibling(); // linear search |
|
1166 |
||
1167 |
if (nextSibling != null) |
|
1168 |
return nextSibling.getFirstLeaf(); |
|
1169 |
||
1170 |
return myParent.getNextLeaf(); // tail recursion |
|
1171 |
} |
|
1172 |
||
1173 |
||
1174 |
/** |
|
1175 |
* Returns the leaf before this node or null if this node is the |
|
1176 |
* first leaf in the tree. |
|
1177 |
* <p> |
|
1178 |
* In this implementation of the <code>MutableNode</code> interface, |
|
1179 |
* this operation is very inefficient. In order to determine the |
|
1180 |
* previous node, this method first performs a linear search in the |
|
1181 |
* parent's child-list in order to find the current node. |
|
1182 |
* <p> |
|
1183 |
* That implementation makes the operation suitable for short |
|
1184 |
* traversals from a known position. But to traverse all of the |
|
1185 |
* leaves in the tree, you should use <code>depthFirstEnumeration</code> |
|
1186 |
* to enumerate the nodes in the tree and use <code>isLeaf</code> |
|
1187 |
* on each node to determine which are leaves. |
|
1188 |
* |
|
1189 |
* @see #depthFirstEnumeration |
|
1190 |
* @see #isLeaf |
|
1191 |
* @return returns the leaf before this node |
|
1192 |
*/ |
|
1193 |
public DefaultMutableTreeNode getPreviousLeaf() { |
|
1194 |
DefaultMutableTreeNode previousSibling; |
|
1195 |
DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent(); |
|
1196 |
||
1197 |
if (myParent == null) |
|
1198 |
return null; |
|
1199 |
||
1200 |
previousSibling = getPreviousSibling(); // linear search |
|
1201 |
||
1202 |
if (previousSibling != null) |
|
1203 |
return previousSibling.getLastLeaf(); |
|
1204 |
||
1205 |
return myParent.getPreviousLeaf(); // tail recursion |
|
1206 |
} |
|
1207 |
||
1208 |
||
1209 |
/** |
|
1210 |
* Returns the total number of leaves that are descendants of this node. |
|
1211 |
* If this node is a leaf, returns <code>1</code>. This method is O(n) |
|
1212 |
* where n is the number of descendants of this node. |
|
1213 |
* |
|
1214 |
* @see #isNodeAncestor |
|
1215 |
* @return the number of leaves beneath this node |
|
1216 |
*/ |
|
1217 |
public int getLeafCount() { |
|
1218 |
int count = 0; |
|
1219 |
||
1220 |
TreeNode node; |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
1221 |
Enumeration<TreeNode> enum_ = breadthFirstEnumeration(); // order matters not |
2 | 1222 |
|
1223 |
while (enum_.hasMoreElements()) { |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
1224 |
node = enum_.nextElement(); |
2 | 1225 |
if (node.isLeaf()) { |
1226 |
count++; |
|
1227 |
} |
|
1228 |
} |
|
1229 |
||
1230 |
if (count < 1) { |
|
1231 |
throw new Error("tree has zero leaves"); |
|
1232 |
} |
|
1233 |
||
1234 |
return count; |
|
1235 |
} |
|
1236 |
||
1237 |
||
1238 |
// |
|
1239 |
// Overrides |
|
1240 |
// |
|
1241 |
||
1242 |
/** |
|
1243 |
* Returns the result of sending <code>toString()</code> to this node's |
|
1244 |
* user object, or the empty string if the node has no user object. |
|
1245 |
* |
|
1246 |
* @see #getUserObject |
|
1247 |
*/ |
|
1248 |
public String toString() { |
|
1249 |
if (userObject == null) { |
|
1250 |
return ""; |
|
1251 |
} else { |
|
1252 |
return userObject.toString(); |
|
1253 |
} |
|
1254 |
} |
|
1255 |
||
1256 |
/** |
|
1257 |
* Overridden to make clone public. Returns a shallow copy of this node; |
|
1258 |
* the new node has no parent or children and has a reference to the same |
|
1259 |
* user object, if any. |
|
1260 |
* |
|
1261 |
* @return a copy of this node |
|
1262 |
*/ |
|
1263 |
public Object clone() { |
|
1843
267cc4de4221
6776095: Code improvement and warnings removing from swing packages
rupashka
parents:
2
diff
changeset
|
1264 |
DefaultMutableTreeNode newNode; |
2 | 1265 |
|
1266 |
try { |
|
1267 |
newNode = (DefaultMutableTreeNode)super.clone(); |
|
1268 |
||
1269 |
// shallow copy -- the new node has no parent or children |
|
1270 |
newNode.children = null; |
|
1271 |
newNode.parent = null; |
|
1272 |
||
1273 |
} catch (CloneNotSupportedException e) { |
|
1274 |
// Won't happen because we implement Cloneable |
|
1275 |
throw new Error(e.toString()); |
|
1276 |
} |
|
1277 |
||
1278 |
return newNode; |
|
1279 |
} |
|
1280 |
||
1281 |
||
1282 |
// Serialization support. |
|
1283 |
private void writeObject(ObjectOutputStream s) throws IOException { |
|
1284 |
Object[] tValues; |
|
1285 |
||
1286 |
s.defaultWriteObject(); |
|
1287 |
// Save the userObject, if its Serializable. |
|
1288 |
if(userObject != null && userObject instanceof Serializable) { |
|
1289 |
tValues = new Object[2]; |
|
1290 |
tValues[0] = "userObject"; |
|
1291 |
tValues[1] = userObject; |
|
1292 |
} |
|
1293 |
else |
|
1294 |
tValues = new Object[0]; |
|
1295 |
s.writeObject(tValues); |
|
1296 |
} |
|
1297 |
||
1298 |
private void readObject(ObjectInputStream s) |
|
1299 |
throws IOException, ClassNotFoundException { |
|
1300 |
||
26001
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1301 |
ObjectInputStream.GetField f = s.readFields(); |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1302 |
parent = (MutableTreeNode) f.get("parent", null); |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1303 |
@SuppressWarnings("unchecked") |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1304 |
Vector<TreeNode> newChildren = (Vector<TreeNode>) f.get("children", null); |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1305 |
boolean newAllowsChildren = f.get("allowsChildren", false); |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1306 |
if (!newAllowsChildren && newChildren != null && newChildren.size() > 0) { |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1307 |
throw new IllegalStateException("node does not allow children"); |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1308 |
} |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1309 |
children = newChildren; |
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1310 |
allowsChildren = newAllowsChildren; |
2 | 1311 |
|
26001
991e1be0b235
8038937: Validate fields on Swing classes deserialization
alexsch
parents:
25568
diff
changeset
|
1312 |
Object[] tValues; |
2 | 1313 |
tValues = (Object[])s.readObject(); |
1314 |
||
1315 |
if(tValues.length > 0 && tValues[0].equals("userObject")) |
|
1316 |
userObject = tValues[1]; |
|
1317 |
} |
|
1318 |
||
1843
267cc4de4221
6776095: Code improvement and warnings removing from swing packages
rupashka
parents:
2
diff
changeset
|
1319 |
private final class PreorderEnumeration implements Enumeration<TreeNode> { |
26351 | 1320 |
private final Stack<Enumeration<? extends TreeNode>> stack = new Stack<>(); |
2 | 1321 |
|
1322 |
public PreorderEnumeration(TreeNode rootNode) { |
|
1323 |
super(); |
|
1843
267cc4de4221
6776095: Code improvement and warnings removing from swing packages
rupashka
parents:
2
diff
changeset
|
1324 |
Vector<TreeNode> v = new Vector<TreeNode>(1); |
2 | 1325 |
v.addElement(rootNode); // PENDING: don't really need a vector |
1326 |
stack.push(v.elements()); |
|
1327 |
} |
|
1328 |
||
1329 |
public boolean hasMoreElements() { |
|
1843
267cc4de4221
6776095: Code improvement and warnings removing from swing packages
rupashka
parents:
2
diff
changeset
|
1330 |
return (!stack.empty() && stack.peek().hasMoreElements()); |
2 | 1331 |
} |
1332 |
||
1333 |
public TreeNode nextElement() { |
|
26351 | 1334 |
Enumeration<? extends TreeNode> enumer = stack.peek(); |
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
1335 |
TreeNode node = enumer.nextElement(); |
26351 | 1336 |
Enumeration<? extends TreeNode> children = node.children(); |
2 | 1337 |
|
1338 |
if (!enumer.hasMoreElements()) { |
|
1339 |
stack.pop(); |
|
1340 |
} |
|
1341 |
if (children.hasMoreElements()) { |
|
1342 |
stack.push(children); |
|
1343 |
} |
|
1344 |
return node; |
|
1345 |
} |
|
1346 |
||
1347 |
} // End of class PreorderEnumeration |
|
1348 |
||
1349 |
||
1350 |
||
1351 |
final class PostorderEnumeration implements Enumeration<TreeNode> { |
|
1352 |
protected TreeNode root; |
|
26351 | 1353 |
protected Enumeration<? extends TreeNode> children; |
2 | 1354 |
protected Enumeration<TreeNode> subtree; |
1355 |
||
1356 |
public PostorderEnumeration(TreeNode rootNode) { |
|
1357 |
super(); |
|
1358 |
root = rootNode; |
|
1359 |
children = root.children(); |
|
1360 |
subtree = EMPTY_ENUMERATION; |
|
1361 |
} |
|
1362 |
||
1363 |
public boolean hasMoreElements() { |
|
1364 |
return root != null; |
|
1365 |
} |
|
1366 |
||
1367 |
public TreeNode nextElement() { |
|
1368 |
TreeNode retval; |
|
1369 |
||
1370 |
if (subtree.hasMoreElements()) { |
|
1371 |
retval = subtree.nextElement(); |
|
1372 |
} else if (children.hasMoreElements()) { |
|
1843
267cc4de4221
6776095: Code improvement and warnings removing from swing packages
rupashka
parents:
2
diff
changeset
|
1373 |
subtree = new PostorderEnumeration(children.nextElement()); |
2 | 1374 |
retval = subtree.nextElement(); |
1375 |
} else { |
|
1376 |
retval = root; |
|
1377 |
root = null; |
|
1378 |
} |
|
1379 |
||
1380 |
return retval; |
|
1381 |
} |
|
1382 |
||
1383 |
} // End of class PostorderEnumeration |
|
1384 |
||
1385 |
||
1386 |
||
1387 |
final class BreadthFirstEnumeration implements Enumeration<TreeNode> { |
|
1388 |
protected Queue queue; |
|
1389 |
||
1390 |
public BreadthFirstEnumeration(TreeNode rootNode) { |
|
1391 |
super(); |
|
1843
267cc4de4221
6776095: Code improvement and warnings removing from swing packages
rupashka
parents:
2
diff
changeset
|
1392 |
Vector<TreeNode> v = new Vector<TreeNode>(1); |
2 | 1393 |
v.addElement(rootNode); // PENDING: don't really need a vector |
1394 |
queue = new Queue(); |
|
1395 |
queue.enqueue(v.elements()); |
|
1396 |
} |
|
1397 |
||
1398 |
public boolean hasMoreElements() { |
|
1399 |
return (!queue.isEmpty() && |
|
1400 |
((Enumeration)queue.firstObject()).hasMoreElements()); |
|
1401 |
} |
|
1402 |
||
1403 |
public TreeNode nextElement() { |
|
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
1404 |
Enumeration<?> enumer = (Enumeration)queue.firstObject(); |
2 | 1405 |
TreeNode node = (TreeNode)enumer.nextElement(); |
25568
b906a74c6882
8043550: Fix raw and unchecked lint warnings in javax.swing.*
darcy
parents:
24495
diff
changeset
|
1406 |
Enumeration<?> children = node.children(); |
2 | 1407 |
|
1408 |
if (!enumer.hasMoreElements()) { |
|
1409 |
queue.dequeue(); |
|
1410 |
} |
|
1411 |
if (children.hasMoreElements()) { |
|
1412 |
queue.enqueue(children); |
|
1413 |
} |
|
1414 |
return node; |
|
1415 |
} |
|
1416 |
||
1417 |
||
1418 |
// A simple queue with a linked list data structure. |
|
1419 |
final class Queue { |
|
1420 |
QNode head; // null if empty |
|
1421 |
QNode tail; |
|
1422 |
||
1423 |
final class QNode { |
|
1424 |
public Object object; |
|
1425 |
public QNode next; // null if end |
|
1426 |
public QNode(Object object, QNode next) { |
|
1427 |
this.object = object; |
|
1428 |
this.next = next; |
|
1429 |
} |
|
1430 |
} |
|
1431 |
||
1432 |
public void enqueue(Object anObject) { |
|
1433 |
if (head == null) { |
|
1434 |
head = tail = new QNode(anObject, null); |
|
1435 |
} else { |
|
1436 |
tail.next = new QNode(anObject, null); |
|
1437 |
tail = tail.next; |
|
1438 |
} |
|
1439 |
} |
|
1440 |
||
1441 |
public Object dequeue() { |
|
1442 |
if (head == null) { |
|
1443 |
throw new NoSuchElementException("No more elements"); |
|
1444 |
} |
|
1445 |
||
1446 |
Object retval = head.object; |
|
1447 |
QNode oldHead = head; |
|
1448 |
head = head.next; |
|
1449 |
if (head == null) { |
|
1450 |
tail = null; |
|
1451 |
} else { |
|
1452 |
oldHead.next = null; |
|
1453 |
} |
|
1454 |
return retval; |
|
1455 |
} |
|
1456 |
||
1457 |
public Object firstObject() { |
|
1458 |
if (head == null) { |
|
1459 |
throw new NoSuchElementException("No more elements"); |
|
1460 |
} |
|
1461 |
||
1462 |
return head.object; |
|
1463 |
} |
|
1464 |
||
1465 |
public boolean isEmpty() { |
|
1466 |
return head == null; |
|
1467 |
} |
|
1468 |
||
1469 |
} // End of class Queue |
|
1470 |
||
1471 |
} // End of class BreadthFirstEnumeration |
|
1472 |
||
1473 |
||
1474 |
||
1475 |
final class PathBetweenNodesEnumeration implements Enumeration<TreeNode> { |
|
1476 |
protected Stack<TreeNode> stack; |
|
1477 |
||
1478 |
public PathBetweenNodesEnumeration(TreeNode ancestor, |
|
1479 |
TreeNode descendant) |
|
1480 |
{ |
|
1481 |
super(); |
|
1482 |
||
1483 |
if (ancestor == null || descendant == null) { |
|
1484 |
throw new IllegalArgumentException("argument is null"); |
|
1485 |
} |
|
1486 |
||
1487 |
TreeNode current; |
|
1488 |
||
1489 |
stack = new Stack<TreeNode>(); |
|
1490 |
stack.push(descendant); |
|
1491 |
||
1492 |
current = descendant; |
|
1493 |
while (current != ancestor) { |
|
1494 |
current = current.getParent(); |
|
1495 |
if (current == null && descendant != ancestor) { |
|
1496 |
throw new IllegalArgumentException("node " + ancestor + |
|
1497 |
" is not an ancestor of " + descendant); |
|
1498 |
} |
|
1499 |
stack.push(current); |
|
1500 |
} |
|
1501 |
} |
|
1502 |
||
1503 |
public boolean hasMoreElements() { |
|
1504 |
return stack.size() > 0; |
|
1505 |
} |
|
1506 |
||
1507 |
public TreeNode nextElement() { |
|
1508 |
try { |
|
1509 |
return stack.pop(); |
|
1510 |
} catch (EmptyStackException e) { |
|
1511 |
throw new NoSuchElementException("No more elements"); |
|
1512 |
} |
|
1513 |
} |
|
1514 |
||
1515 |
} // End of class PathBetweenNodesEnumeration |
|
1516 |
||
1517 |
||
1518 |
||
1519 |
} // End of class DefaultMutableTreeNode |