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
48 import org.melati.poem.util.Order;
49 import org.melati.poem.util.SortUtils;
50 import org.melati.poem.Treeable;
51
52 /**
53 * A whole tree.
54 */
55 public class Tree {
56 private Treeable[] orig_roots;
57 private TreeNode[] roots;
58 private int depth;
59
60 /**
61 * Constructor from root node.
62 * @param node root node
63 */
64 public Tree(Treeable node) {
65 orig_roots = new Treeable[1];
66 orig_roots[0] = node;
67 this.depth = 0;
68 roots = new TreeNode[] { new TreeNode(node, 0) };
69 }
70
71 /**
72 * Constructor from root node with anticipated depth.
73 * @param node root node
74 * @param depth the anticipated depth
75 */
76 public Tree(Treeable node, int depth) {
77 orig_roots = new Treeable[1];
78 orig_roots[0] = node;
79 this.depth = depth;
80 roots = new TreeNode[] { new TreeNode(node, depth) };
81 }
82
83 /**
84 * Constructor for a multi-rooted tree.
85 * @param nodes the root nodes
86 */
87 public Tree(Treeable[] nodes) {
88 orig_roots = nodes;
89 this.depth = 0;
90 roots = TreeNode.augment(nodes, 0);
91 }
92
93 /**
94 * Constructor for a multi-rooted tree with anticipated depth.
95 * @param nodes the root nodes
96 * @param depth anticipated depth
97 */
98 public Tree(Treeable[] nodes, int depth) {
99 orig_roots = nodes;
100 this.depth = depth;
101 roots = TreeNode.augment(nodes, depth);
102 }
103
104 /**
105 * @return the roots
106 */
107 public Treeable[] getTreeableRoots() {
108 return orig_roots;
109 }
110
111 /**
112 * @return the depth, possibly anticipated
113 */
114 public int getDepth() {
115 return depth;
116 }
117
118 /**
119 * Retrieve all the nodes down to a given depth.
120 * @param depthP
121 * Only apply the function to nodes at or above this depth. A negative
122 * depth means apply this to all nodes in the tree
123 * @param depthFirst
124 * If true, traverse the tree depth-first, otherwise traverse it
125 * breadth-first
126 * @return all the nodes down to the given depth
127 */
128 public Vector<TreeNode> flattened(int depthP, boolean depthFirst) {
129
130 Vector<TreeNode> results = new Vector<TreeNode>();
131 Vector<TreeNode> agenda = new Vector<TreeNode>();
132 for (int i = 0; i < roots.length; i++) {
133 agenda.addElement(roots[i]);
134 }
135
136 while (!agenda.isEmpty()) {
137 TreeNode current = (TreeNode)agenda.firstElement();
138 agenda.removeElementAt(0);
139 results.addElement(current);
140
141 if (depthP < 0 || current.depth < depthP) {
142 TreeNode[] kids = current.getChildren();
143
144 if (kids != null) {
145 for (int i = 0; i < kids.length; i++) {
146 if (depthFirst)
147 // Maybe not the most efficient ...?
148 agenda.insertElementAt(kids[i], i);
149 else
150 agenda.addElement(kids[i]);
151 }
152 }
153 }
154 }
155 return results;
156 }
157
158 /**
159 * Retrieve all the nodes down to a given depth, depth-first.
160 * @param depthP
161 * Only apply the function to nodes at or above this depth. A negative
162 * depth means apply this to all nodes in the tree
163 * @return all the nodes down to the given depth
164 */
165 public Vector<TreeNode> flattened(int depthP) {
166 return flattened(depthP, true);
167 }
168
169 /**
170 * @return all the nodes, depth-first
171 */
172 public Vector<TreeNode> flattened() {
173 return flattened(-1);
174 }
175
176 /**
177 * Apply the Function to each node in the tree.
178 *
179 * @param func the Function to apply
180 * @param depthP
181 * Only apply the function to nodes at or above this depth. A negative
182 * depth means apply this to all nodes in the tree
183 * @param depthFirst
184 * If true, traverse the tree depth-first, otherwise traverse it
185 * breadth-first
186 * @return a Vector nodes that have had func applied to them
187 */
188 public Vector<TreeNode> apply(Function func, int depthP, boolean depthFirst) {
189 Vector<TreeNode> flattened = flattened(depthP, depthFirst);
190 for (int i = 0; i < flattened.size(); i++) {
191 flattened.setElementAt((TreeNode)func.apply(flattened.elementAt(i)), i);
192 }
193 return flattened;
194 }
195
196 /**
197 * Apply a function to all nodes, depth first.
198 * @param func the function to apply
199 * @return a vector of nodes to which the function has been applied
200 */
201 public Vector<TreeNode> applyDepthFirst(Function func) {
202 return apply(func, -1, true);
203 }
204
205 /**
206 * Apply a function to all nodes to a given depth, depth first.
207 * @param func the function to apply
208 * @param depthP
209 * Only apply the function to nodes at or above this depth. A negative
210 * depth means apply this to all nodes in the tree
211 * @return a vector of nodes to which the function has been applied
212 */
213 public Vector<TreeNode> applyDepthFirst(Function func, int depthP) {
214 return apply(func, depthP, true);
215 }
216
217 /**
218 * Apply a function to all nodes, breadth first.
219 * @param func the function to apply
220 * @return a vector of nodes to which the function has been applied
221 */
222 public Vector<TreeNode> applyBreadthFirst(Function func) {
223 return apply(func, -1, false);
224 }
225
226 /**
227 * Apply a function to all nodes to a given depth, breadth first.
228 * @param func the function to apply
229 * @param depthP
230 * Only apply the function to nodes at or above this depth. A negative
231 * depth means apply this to all nodes in the tree
232 * @return a vector of nodes to which the function has been applied
233 */
234 public Vector<TreeNode> applyBreadthFirst(Function func, int depthP) {
235 return apply(func, depthP, false);
236 }
237
238 /**
239 * Retrieve a sorted Vector of the tree's contents, down to the given depth.
240 * @param cmp an Ordering
241 * @param depthP
242 * Only return nodes at or above this depth. A negative
243 * depth means return all nodes in the tree
244 * @return a sorted Vector of the tree's contents, down to the given depth
245 */
246 public Vector<TreeNode> sorted(Order cmp, int depthP) {
247 Vector<TreeNode> flattened = flattened(depthP);
248 TreeNode[] sorted = SortUtils.sorted(cmp, flattened);
249 System.arraycopy(sorted, 0, flattened, 0, sorted.length);
250 return flattened;
251 }
252
253 }