Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
TreeNode |
|
| 1.8333333333333333;1.833 |
1 | /* | |
2 | * $Source$ | |
3 | * $Revision$ | |
4 | * | |
5 | * Copyright (C) 2001 Myles Chippendale | |
6 | * | |
7 | * Part of Melati (http://melati.org), a framework for the rapid | |
8 | * development of clean, maintainable web applications. | |
9 | * | |
10 | * Melati is free software; Permission is granted to copy, distribute | |
11 | * and/or modify this software under the terms either: | |
12 | * | |
13 | * a) the GNU General Public License as published by the Free Software | |
14 | * Foundation; either version 2 of the License, or (at your option) | |
15 | * any later version, | |
16 | * | |
17 | * or | |
18 | * | |
19 | * b) any version of the Melati Software License, as published | |
20 | * at http://melati.org | |
21 | * | |
22 | * You should have received a copy of the GNU General Public License and | |
23 | * the Melati Software License along with this program; | |
24 | * if not, write to the Free Software Foundation, Inc., | |
25 | * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA to obtain the | |
26 | * GNU General Public License and visit http://melati.org to obtain the | |
27 | * Melati Software License. | |
28 | * | |
29 | * Feel free to contact the Developers of Melati (http://melati.org), | |
30 | * if you would like to work out a different arrangement than the options | |
31 | * outlined here. It is our intention to allow Melati to be used by as | |
32 | * wide an audience as possible. | |
33 | * | |
34 | * This program is distributed in the hope that it will be useful, | |
35 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
36 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
37 | * GNU General Public License for more details. | |
38 | * | |
39 | * Contact details for copyright holder: | |
40 | * | |
41 | * Myles Chippendale <MylesC At paneris.org> | |
42 | */ | |
43 | ||
44 | package org.melati.util; | |
45 | ||
46 | import java.util.Vector; | |
47 | import org.melati.poem.Treeable; | |
48 | ||
49 | /** | |
50 | * A {@link Tree} node. | |
51 | * | |
52 | * @author MylesC At paneris.org | |
53 | * | |
54 | */ | |
55 | public class TreeNode { | |
56 | private Treeable data; | |
57 | int depth; | |
58 | 21 | protected TreeNode parent = null; |
59 | 21 | private TreeNode[] children = null; |
60 | 21 | private boolean checkedForChildren = false; |
61 | ||
62 | /** | |
63 | * Constructor. | |
64 | * @param n the Treeable object | |
65 | * @param d the depth of this node | |
66 | */ | |
67 | 21 | public TreeNode(Treeable n, int d) { |
68 | 21 | data = n; |
69 | 21 | depth = d; |
70 | 21 | } |
71 | ||
72 | /** | |
73 | * @return whether this is a root node | |
74 | */ | |
75 | public boolean isRoot() { | |
76 | 0 | return (parent == null); |
77 | } | |
78 | ||
79 | /** | |
80 | * @return whether this is a terminal node | |
81 | */ | |
82 | public boolean isLeaf() { | |
83 | 11 | return (getChildren() == null); |
84 | } | |
85 | ||
86 | /** | |
87 | * @return the depth in the tree | |
88 | */ | |
89 | public int getDepth() { | |
90 | 11 | return depth; |
91 | } | |
92 | ||
93 | /** | |
94 | * @return the Treeable data object this wraps | |
95 | */ | |
96 | public Treeable getData() { | |
97 | 77 | return data; |
98 | } | |
99 | ||
100 | /** | |
101 | * @return theis nodes parent, null if this is a root node | |
102 | */ | |
103 | public TreeNode getParent() { | |
104 | 16 | return parent; |
105 | } | |
106 | ||
107 | /** | |
108 | * @return the name unique within the Tree | |
109 | */ | |
110 | public String getUniqueName() { | |
111 | 38 | int code = hashCode(); |
112 | 38 | String name = ""; |
113 | 38 | if (code < 0) { |
114 | 0 | code = -code; |
115 | 0 | name = "Z"; |
116 | } | |
117 | 38 | return name + Integer.toString(code, java.lang.Character.MAX_RADIX); |
118 | } | |
119 | ||
120 | /** | |
121 | * @return the descendants of this node, maybe an empty Array | |
122 | */ | |
123 | public synchronized TreeNode[] getChildren() { | |
124 | 27 | if (checkedForChildren) |
125 | 16 | return children; |
126 | ||
127 | 11 | Treeable[] kids = data.getChildren(); |
128 | 11 | if (kids == null || kids.length == 0) |
129 | 8 | children = null; |
130 | else { | |
131 | 3 | children = augment(kids, depth + 1); |
132 | 8 | for (int i = 0; i<children.length; i++) |
133 | 5 | children[i].parent = this; |
134 | } | |
135 | 11 | checkedForChildren = true; |
136 | ||
137 | 11 | return children; |
138 | } | |
139 | ||
140 | /** | |
141 | * Retrieve an Array of TreeNodes which is the shortest path from | |
142 | * this node to its root. | |
143 | * | |
144 | * @param includeNode whether to include this node in the path | |
145 | * @param reverse if true returns a path from root to this | |
146 | * @return an Array of TreeNodes | |
147 | */ | |
148 | public TreeNode[] getNodeToRootPath(boolean includeNode, boolean reverse) { | |
149 | 0 | Vector<TreeNode> path = new Vector<TreeNode>(); |
150 | 0 | if (includeNode) |
151 | 0 | path.addElement(this); |
152 | ||
153 | 0 | TreeNode current = this; |
154 | ||
155 | 0 | while (!current.isRoot()) { |
156 | 0 | current = current.parent; |
157 | 0 | if (reverse) |
158 | 0 | path.insertElementAt(current, 0); |
159 | else | |
160 | 0 | path.addElement(current); |
161 | } | |
162 | ||
163 | 0 | TreeNode[] result = new TreeNode[path.size()]; |
164 | 0 | return (TreeNode[])path.toArray(result); |
165 | } | |
166 | ||
167 | /** | |
168 | * @return the path to this node's root excluding this node | |
169 | */ | |
170 | public TreeNode[] getPathToRoot() { | |
171 | 0 | return getNodeToRootPath(false, false); |
172 | } | |
173 | ||
174 | /** | |
175 | * @return the path from this node's root excluding this node | |
176 | */ | |
177 | public TreeNode[] getPathFromRoot() { | |
178 | 0 | return getNodeToRootPath(false, true); |
179 | } | |
180 | ||
181 | /** | |
182 | * Create a new Array of TreeNodes specifying a new depth. | |
183 | * @param nodes the nodes to copy | |
184 | * @param depth the new depth | |
185 | * @return a new Array of TreeNodes with the new depth | |
186 | */ | |
187 | public static TreeNode[] augment(Treeable[] nodes, int depth) { | |
188 | 11 | TreeNode[] t = new TreeNode[nodes.length]; |
189 | 25 | for (int i=0; i<nodes.length; i++) { |
190 | 14 | t[i] = new TreeNode(nodes[i], depth); |
191 | } | |
192 | 11 | return t; |
193 | } | |
194 | } | |
195 | ||
196 | ||
197 | ||
198 | ||
199 | ||
200 |