001 /* Copyright 2000, 2001, Compaq Computer Corporation */
002
003 package javafe.filespace;
004
005
006 import java.util.Enumeration;
007
008
009 /**
010 * A Tree is a n-ary tree with data at each node; the direct children of a
011 * node are unordered but distinguished via String labels on the edges
012 * to them.<p>
013 *
014 * All labels must be non-null.<p>
015 */
016
017 public abstract class Tree {
018
019 /***************************************************
020 * *
021 * Instance variables: *
022 * *
023 **************************************************/
024
025 /** Our parent or null if we have no parent (aka, we are a root) */
026 //@ spec_public
027 private Tree parent = null;
028
029 /**
030 * The label on the edge leading to us from our parent, or null if
031 * we have no parent.
032 */
033 //@ invariant (label == null) == (parent == null);
034 //@ spec_public
035 private String label = null;
036
037 /*
038 * Note: the existence of these two fields implies that any given
039 * Tree has at most 1 parent and can be reached via at most 1 edge.
040 */
041
042 /** The data, if any, associated with this node: */
043 public Object data;
044
045
046 /***************************************************
047 * *
048 * Creation: *
049 * *
050 **************************************************/
051
052 /** Create a root node: */
053 protected Tree(Object data) {
054 this.data = data;
055 }
056
057 /** Create a non-root node: */
058 //@ requires parent != null && label != null;
059 protected Tree(Tree parent, String label, Object data) {
060 this.parent = parent;
061 this.label = label;
062 this.data = data;
063 }
064
065
066 /***************************************************
067 * *
068 * Simple public accessors: *
069 * *
070 **************************************************/
071
072 /** Return our parent node or null if we have no parent */
073 public final Tree getParent() {
074 return parent;
075 }
076
077 /**
078 * Return the label on the edge to us from our parent or null if we
079 * have no parent.
080 */
081 public final String getLabel() {
082 return label;
083 }
084
085
086 /***************************************************
087 * *
088 * Fetching and counting children: *
089 * *
090 **************************************************/
091
092 /**
093 * An enumeration of this node's direct children. Each child
094 * occurs exactly once in the enumeration. The order is
095 * unspecified and may differ from call to call.<p>
096 *
097 * Note: The Objects returned by the resulting enumeration's
098 * nextElement method are guaranteed to be of type Tree,
099 * non-null, and have non-null labels.<p>
100 */
101 //@ ensures \result != null;
102 //@ ensures !\result.returnsNull;
103 //@ ensures \result.elementType == \type(Tree);
104 public abstract Enumeration children();
105
106
107 /**
108 * Fetch our direct child along the edge labelled label. Iff there
109 * is no such child, return null.
110 */
111 //@ requires label != null;
112 public Tree getChild(String label) {
113 /*
114 * Stupid & slow default implementation using children()
115 * enumeration:
116 */
117 Enumeration C = children();
118
119 while (C.hasMoreElements()) {
120 Tree next = (Tree)C.nextElement();
121
122 if (label.equals(next.label))
123 return next;
124 }
125
126 return null;
127 }
128
129
130 /** Return true iff we have no direct children */
131 public boolean isLeaf() {
132 return (!children().hasMoreElements());
133 }
134
135
136 /** Return a count of how many direct children we have: */
137 //@ ensures \result >= 0;
138 public int getChildrenCount() {
139 /*
140 * Stupid & slow default implementation using children()
141 * enumeration:
142 */
143 int count = 0;
144 for (Enumeration C = children(); C.hasMoreElements(); C.nextElement())
145 count++;
146
147 return count;
148
149 }
150
151
152 /***************************************************
153 * *
154 * Utility functions: *
155 * *
156 **************************************************/
157
158 /**
159 * The same as getLabel, except that it returns "" instead of null
160 * for the top node.
161 */
162 //@ ensures \result != null;
163 public final String getSimpleName() {
164 if (label == null)
165 return "";
166 else
167 return label;
168 }
169
170 /**
171 * Return a fully qualified name for this node using a specified
172 * separator String.<p>
173 *
174 * If the sequences of labels on the edges from the root of the
175 * tree this node belongs to til this node is X, Y, ... Z, then
176 * this routine returns the string X!Y! ... !Z, where ! is the
177 * separator. Normal usage is to use "." as the separator.<p>
178 *
179 * Root nodes are thus named "" and their direct children have
180 * names of the form X, where X is their label.<p>
181 *
182 * For the resulting name to be useful, labels should never contain
183 * the separator or be the empty string.<p>
184 */
185 //@ ensures \result != null;
186 public final String getQualifiedName(String separator) {
187 if (parent == null)
188 return "";
189
190 if (parent.parent == null)
191 return label;
192
193 return parent.getQualifiedName(separator) + separator + label;
194 }
195
196 /** Return the root node for the tree we belong to. */
197 public final Tree getRootNode() {
198 if (parent == null)
199 return this;
200
201 return parent.getRootNode();
202 }
203
204 /**
205 * Return the child with a given partially qualified name or null
206 * if no such node exists; if this node is X.Y and name is Z!W,
207 * where ! is the specified separator, then this routine attempts
208 * to find the child with fully qualified name X.Y.Z.W.<p>
209 *
210 * See getQualifiedName for more information on qualified names.
211 * Name must be non-null.<p>
212 */
213 //@ requires name != null;
214 public final Tree getQualifiedChild(String name, char separator) {
215 String[] path = StringUtil.parseList(name, separator);
216
217 Tree currentNode = this;
218 for (int i=0; i<path.length; i++) {
219 currentNode = currentNode.getChild(path[i]);
220 if (currentNode == null)
221 return null;
222 }
223
224 return currentNode;
225 }
226
227
228 /***************************************************
229 * *
230 * Debugging functions: *
231 * *
232 **************************************************/
233
234 /**
235 * Print out on System.out a human-readable representation of this
236 * tree.<p>
237 *
238 * Included is our fully qualified name, our data, and information
239 * about each of our children.<p>
240 */
241 public void print(String prefix) {
242 System.out.print(prefix + "Node '" + getQualifiedName(".") + "'");
243 printDetails(prefix + " ");
244 if (isLeaf())
245 System.out.println();
246 else {
247 System.out.println(":");
248 for (Enumeration E = children(); E.hasMoreElements(); )
249 ((Tree)E.nextElement()).print(prefix + " ");
250 }
251 }
252
253 public void printDetails(String prefix) {
254 System.out.print(", data=" + data);
255 }
256 }