1 /*
2 * $Source: /usr/cvsroot/melati/melati/src/main/java/org/melati/util/ChildrenDrivenMutableTree.java,v $
3 * $Revision: 1.8 $
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 @SuppressWarnings("unchecked") // FIXME we need our own empty enumeration
76 public static final Enumeration EMPTY_ENUMERATION =
77 DefaultMutableTreeNode.EMPTY_ENUMERATION;
78
79 /** root node */
80 protected DefaultMutableTreeNode root;
81
82 /**
83 * Constructor.
84 */
85 public ChildrenDrivenMutableTree() {
86 this(null);
87 }
88
89 /**
90 * Constructor.
91 * @param userObject the root
92 */
93 public ChildrenDrivenMutableTree(Treeable userObject) {
94 root = new DefaultMutableTreeNode(userObject);
95 buildTree();
96 }
97
98 /**
99 * Compute the children.
100 */
101 public void buildTree() {
102 buildTree(computeChildren(root));
103 }
104
105 /**
106 * Compute the children given the nodes.
107 * @param nodes an Enumeration of nodes
108 */
109 public void buildTree(Enumeration<DefaultMutableTreeNode> nodes) {
110 while (nodes.hasMoreElements())
111 buildTree(computeChildren(nodes.nextElement()));
112 }
113
114 @SuppressWarnings("unchecked")
115 private static Enumeration<DefaultMutableTreeNode> computeChildren(DefaultMutableTreeNode node) {
116 if (node == null)
117 return EMPTY_ENUMERATION;
118 Treeable[] kids = ((Treeable)node.getUserObject()).getChildren();
119 for(int i = 0; i<kids.length; i++) {
120 node.add(new DefaultMutableTreeNode(kids[i]));
121 }
122 return node.children();
123 }
124
125
126 /**
127 * Find a node in a tree.
128 * @param search the node object
129 * @return a tree node
130 */
131 @SuppressWarnings("unchecked")
132 public DefaultMutableTreeNode getTreeNodeFor(Treeable search) {
133
134 Vector<DefaultMutableTreeNode> agenda = new Vector<DefaultMutableTreeNode>();
135 agenda.addElement(root);
136
137 while (!agenda.isEmpty()) {
138 DefaultMutableTreeNode current =
139 agenda.firstElement();
140 if (current == null)
141 return null;
142 if (current.getUserObject() == search)
143 return current;
144
145 agenda.removeElementAt(0);
146 Enumeration<DefaultMutableTreeNode> kids = current.children();
147 while(kids.hasMoreElements()) {
148 agenda.addElement(kids.nextElement());
149 }
150 }
151 return null;
152 }
153
154 /**
155 * @return the root
156 */
157 public DefaultMutableTreeNode getRoot() {
158 return root;
159 }
160
161 /**
162 * Return an enumeration of nodes in preorder, whatever
163 * that means.
164 * <p>
165 * Root is first node. What is the difference
166 * from breadth first?
167 * @return the nodes
168 */
169 @SuppressWarnings("unchecked")
170 public Enumeration preorderEnumeration() {
171 return root.preorderEnumeration();
172 }
173
174 /**
175 * Return an enumeration of nodes in postorder, whatever
176 * that means.
177 * <p>
178 * Leftmost leaf is first. What is the difference
179 * from depth first?
180 * @return the nodes
181 */
182 @SuppressWarnings("unchecked")
183 public Enumeration postorderEnumeration() {
184 return root.postorderEnumeration();
185 }
186
187 /**
188 * @return an enumeration of nodes in breadth first order.
189 */
190 @SuppressWarnings("unchecked")
191 public Enumeration breadthFirstEnumeration() {
192 return root.breadthFirstEnumeration();
193 }
194
195 /**
196 * @return an enumeration of nodes in depth first order.
197 */
198 @SuppressWarnings("unchecked")
199 public Enumeration depthFirstEnumeration() {
200 return root.depthFirstEnumeration();
201 }
202 }