##### Coverage Report - org.melati.util.Tree

Classes in this File | Line Coverage | Branch Coverage | Complexity
Tree |
65% | 36/55
75% | 12/16
| 1.5333333333333334;1.533

1 |  |
     /*
2 |  |
      * $Source: /usr/cvsroot/melati/melati/src/site/resources/withWebmacro/org.melati.util.Tree.html,v $
3 |  |
      * $Revision: 1.1 $
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 | 14 |
       public Tree(Treeable node) {
65 | 14 |
         orig_roots = new Treeable[1];
66 | 14 |
         orig_roots[0] = node;
67 | 14 |
         this.depth = 0;
68 | 14 |
         roots = new TreeNode[] { new TreeNode(node, 0) };
69 | 14 |
       }
70 |  |
71 |  |
       /**
72 |  |
        * Constructor from root node with anticipated depth.
73 |  |
        * @param node root node
74 |  |
        * @param depth the anticipated depth
75 |  |
        */
76 | 0 |
       public Tree(Treeable node, int depth) {
77 | 0 |
         orig_roots = new Treeable[1];
78 | 0 |
         orig_roots[0] = node;
79 | 0 |
         this.depth = depth;
80 | 0 |
         roots = new TreeNode[] { new TreeNode(node, depth) };
81 | 0 |
       }
82 |  |
83 |  |
       /**
84 |  |
        * Constructor for a multi-rooted tree.
85 |  |
        * @param nodes the root nodes
86 |  |
        */
87 | 2 |
       public Tree(Treeable[] nodes) {
88 | 2 |
         orig_roots = nodes;
89 | 2 |
         this.depth = 0;
90 | 2 |
         roots = TreeNode.augment(nodes, 0);
91 | 2 |
       }
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 | 14 |
       public Tree(Treeable[] nodes, int depth) {
99 | 14 |
         orig_roots = nodes;
100 | 14 |
         this.depth = depth;
101 | 14 |
         roots = TreeNode.augment(nodes, depth);
102 | 14 |
       }
103 |  |
104 |  |
       /**
105 |  |
        * @return the roots
106 |  |
        */
107 |  |
       public Treeable[] getTreeableRoots() {
108 | 14 |
         return orig_roots;
109 |  |
       }
110 |  |
111 |  |
       /**
112 |  |
        * @return the depth, possibly anticipated
113 |  |
        */
114 |  |
       public int getDepth() {
115 | 14 |
         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 | 26 |
         Vector<TreeNode> results = new Vector<TreeNode>();
131 | 26 |
         Vector<TreeNode> agenda = new Vector<TreeNode>();
132 | 58 |
         for (int i = 0; i < roots.length; i++) {
133 | 32 |
           agenda.addElement(roots[i]);
134 |  |
         }
135 |  |
136 | 70 |
         while (!agenda.isEmpty()) {
137 | 44 |
           TreeNode current = (TreeNode)agenda.firstElement();
138 | 44 |
           agenda.removeElementAt(0);
139 | 44 |
           results.addElement(current);
140 |  |
141 | 44 |
           if (depthP < 0 || current.depth < depthP) {
142 | 32 |
             TreeNode[] kids = current.getChildren();
143 |  |
144 | 32 |
             if (kids != null) {
145 | 20 |
               for (int i = 0; i < kids.length; i++) {
146 | 12 |
                 if (depthFirst)
147 |  |
                   // Maybe not the most efficient ...?
148 | 12 |
                   agenda.insertElementAt(kids[i], i);
149 |  |
                 else
150 | 0 |
                   agenda.addElement(kids[i]);
151 |  |
               }
152 |  |
             }
153 |  |
           }
154 | 44 |
         }
155 | 26 |
         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 | 26 |
         return flattened(depthP, true);
167 |  |
       }
168 |  |
169 |  |
       /**
170 |  |
        * @return all the nodes, depth-first
171 |  |
        */
172 |  |
       public Vector<TreeNode> flattened() {
173 | 6 |
         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 | 0 |
         Vector<TreeNode> flattened = flattened(depthP, depthFirst);
190 | 0 |
         for (int i = 0; i < flattened.size(); i++) {
191 | 0 |
           flattened.setElementAt((TreeNode)func.apply(flattened.elementAt(i)), i);
192 |  |
         }
193 | 0 |
         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 | 0 |
         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 | 0 |
         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 | 0 |
         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 | 0 |
         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 | 0 |
         Vector<TreeNode> flattened = flattened(depthP);
248 | 0 |
         Object[] sorted = SortUtils.sorted(cmp, flattened);
249 | 0 |
         System.arraycopy(sorted, 0, flattened, 0, sorted.length);
250 | 0 |
         return flattened;
251 |  |
       }
252 |  |
253 |  |
     }