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 package org.melati.util;
44
45 import javax.swing.tree.DefaultMutableTreeNode;
46 import java.util.Vector;
47 import java.util.Enumeration;
48 import org.melati.poem.Treeable;
49
50 /**
51 * A tree of <code>DefaultMutableTreeNode</code>s,
52 * the <code>userObject</code>s of which
53 * are {@link Treeable} objects which supply their own
54 * <code>getChildren()</code> functions.
55 * This is used to build the tree of
56 * <code>DefaultMutableTreeNode</code>s.
57 * <p>
58 * It also allows you to search the subtree for a particular
59 * {@link Treeable} object and returns the corresponding
60 * <code>DefaultMutableTreeNode</code> object if one exists.
61 *
62 * @see DefaultMutableTreeNode
63 *
64 * @since 04/10/2000
65 * @author Myles Chippendale
66 **/
67
68
69 public class ChildrenDrivenMutableTree {
70
71 /**
72 * An enumeration that is always empty. This is used when an enumeration
73 * of a leaf node's children is requested.
74 */
75 // FIXME we need our own empty enumeration
76 @SuppressWarnings("rawtypes")
77 public static final Enumeration EMPTY_ENUMERATION =
78 DefaultMutableTreeNode.EMPTY_ENUMERATION;
79
80 /** root node */
81 protected DefaultMutableTreeNode root;
82
83 /**
84 * Constructor.
85 */
86 public ChildrenDrivenMutableTree() {
87 this(null);
88 }
89
90 /**
91 * Constructor.
92 * @param userObject the root
93 */
94 public ChildrenDrivenMutableTree(Treeable userObject) {
95 root = new DefaultMutableTreeNode(userObject);
96 buildTree();
97 }
98
99 /**
100 * Compute the children.
101 */
102 public void buildTree() {
103 buildTree(computeChildren(root));
104 }
105
106 /**
107 * Compute the children given the nodes.
108 * @param nodes an Enumeration of nodes
109 */
110 public void buildTree(Enumeration<DefaultMutableTreeNode> nodes) {
111 while (nodes.hasMoreElements())
112 buildTree(computeChildren(nodes.nextElement()));
113 }
114
115 @SuppressWarnings("unchecked")
116 private static Enumeration<DefaultMutableTreeNode> computeChildren(DefaultMutableTreeNode node) {
117 if (node == null)
118 return EMPTY_ENUMERATION;
119 Treeable[] kids = ((Treeable)node.getUserObject()).getChildren();
120 for(int i = 0; i<kids.length; i++) {
121 node.add(new DefaultMutableTreeNode(kids[i]));
122 }
123 return node.children();
124 }
125
126
127 /**
128 * Find a node in a tree.
129 * @param search the node object
130 * @return a tree node
131 */
132 @SuppressWarnings("unchecked")
133 public DefaultMutableTreeNode getTreeNodeFor(Treeable search) {
134
135 Vector<DefaultMutableTreeNode> agenda = new Vector<DefaultMutableTreeNode>();
136 agenda.addElement(root);
137
138 while (!agenda.isEmpty()) {
139 DefaultMutableTreeNode current =
140 agenda.firstElement();
141 if (current == null)
142 return null;
143 if (current.getUserObject() == search)
144 return current;
145
146 agenda.removeElementAt(0);
147 Enumeration<DefaultMutableTreeNode> kids = current.children();
148 while(kids.hasMoreElements()) {
149 agenda.addElement(kids.nextElement());
150 }
151 }
152 return null;
153 }
154
155 /**
156 * @return the root
157 */
158 public DefaultMutableTreeNode getRoot() {
159 return root;
160 }
161
162 /**
163 * Return an enumeration of nodes in preorder, whatever
164 * that means.
165 * <p>
166 * Root is first node. What is the difference
167 * from breadth first?
168 * @return the nodes
169 */
170 @SuppressWarnings("unchecked")
171 public Enumeration<TreeNode> preorderEnumeration() {
172 return root.preorderEnumeration();
173 }
174
175 /**
176 * Return an enumeration of nodes in postorder, whatever
177 * that means.
178 * <p>
179 * Leftmost leaf is first. What is the difference
180 * from depth first?
181 * @return the nodes
182 */
183 @SuppressWarnings("unchecked")
184 public Enumeration<TreeNode> postorderEnumeration() {
185 return root.postorderEnumeration();
186 }
187
188 /**
189 * @return an enumeration of nodes in breadth first order.
190 */
191 @SuppressWarnings("unchecked")
192 public Enumeration<TreeNode> breadthFirstEnumeration() {
193 return root.breadthFirstEnumeration();
194 }
195
196 /**
197 * @return an enumeration of nodes in depth first order.
198 */
199 @SuppressWarnings("unchecked")
200 public Enumeration<TreeNode> depthFirstEnumeration() {
201 return root.depthFirstEnumeration();
202 }
203 }