001 /* Copyright 2000, 2001, Compaq Computer Corporation */
002
003 package javafe.filespace;
004
005
006 import java.util.*;
007 import java.io.File;
008
009
010 /**
011 * This class provides a way to enumerate all the nodes of a
012 * given Tree in depth-first pre-order using lexical ordering on
013 * siblings. I.e., X preceeds X.A, which in turn preceeds X.B.
014 * The first node in the list will be the root note of the Tree.
015 * It also allows enumerating a Tree's direct children in sorted order
016 * (based on their labels).<p>
017 *
018 * Guarantee: Returned elements are always non-null Trees.<p>
019 */
020
021 public final class TreeWalker extends LookAheadEnum {
022
023 /***************************************************
024 * *
025 * Instance variables: *
026 * *
027 **************************************************/
028
029 //@ invariant elementType == \type(Tree);
030 //@ invariant !returnsNull;
031
032
033 /**
034 * The remaining children we have yet to start processing:
035 */
036 //@ invariant remainingChildren != null;
037 //@ invariant !remainingChildren.returnsNull;
038 //@ invariant remainingChildren.elementType == \type(Tree);
039 protected Enumeration remainingChildren;
040
041 /**
042 * The remaining nodes from the child we are currently
043 * processing:
044 */
045 //@ invariant remainingNodes != null;
046 //@ invariant !remainingNodes.returnsNull;
047 //@ invariant remainingNodes.elementType == \type(Tree);
048 protected Enumeration remainingNodes;
049
050
051 /***************************************************
052 * *
053 * Creation: *
054 * *
055 **************************************************/
056
057 /**
058 * From a Tree create an enumeration that enumerates
059 * all of the Tree's nodes (including the root node first).
060 * The nodes are produced in depth-first lexical pre-order.
061 */
062 //@ requires T != null;
063 public TreeWalker(Tree T) {
064 // First element is the tree itself:
065 super(T);
066
067 remainingChildren = sortedChildren(T);
068 remainingNodes = new EmptyEnum();
069 //@ set remainingNodes.elementType = \type(Tree);
070
071 //@ set elementType = \type(Tree);
072 //@ set returnsNull = false;
073 }
074
075
076 /***************************************************
077 * *
078 * Calculating the next element: *
079 * *
080 **************************************************/
081
082 /*
083 * This returns the next element in the enumeration or null if there
084 * are no more nodes left.
085 */
086 //@ also
087 //@ assignable remainingNodes;
088 protected Object calcNextElement() {
089 for (;;) {
090 // First exhaust the nodes from the current child:
091 if (remainingNodes.hasMoreElements())
092 return remainingNodes.nextElement();
093
094 // Advance to next child:
095 if (!remainingChildren.hasMoreElements())
096 return null; // no nodes left...
097 Tree nextChild = (Tree)remainingChildren.nextElement();
098
099 // Process all of its nodes:
100 remainingNodes = new TreeWalker(nextChild);
101 }
102 }
103
104
105 /***************************************************
106 * *
107 * Enumerating children in order: *
108 * *
109 **************************************************/
110
111 /**
112 * Enumerate a Tree's direct children in sorted order (of labels).<p>
113 *
114 * Guarantee: The resulting enumeration never yields null as an
115 * element.<p>
116 */
117 //@ requires T != null;
118 //@ ensures \result != null;
119 //@ ensures !\result.returnsNull;
120 //@ ensures \result.elementType == \type(Tree);
121 //@ ensures ((Object)\result).owner == null;
122 public static Enumeration sortedChildren(Tree T) {
123 return new TreeWalker_ArrayEnum(getSortedChildren(T));
124 }
125
126
127 /** Return a sorted list of a Tree's direct children: */
128 //@ requires T != null;
129 //@ ensures \result != null;
130 //@ ensures \elemtype(\typeof(\result)) == \type(Tree);
131 private static Tree[] getSortedChildren(Tree T) {
132 Tree[] directChildren = new Tree[T.getChildrenCount()];
133
134 // Copy list of T's direct children into an array:
135 int c = 0;
136 for (Enumeration C=T.children(); C.hasMoreElements(); ) {
137 directChildren[c++] = (Tree)C.nextElement(); //@nowarn IndexTooBig;
138 }
139 //@ assume \nonnullelements(directChildren);
140
141 // Sort the array then return it:
142 sort(directChildren);
143 return directChildren;
144 }
145
146 /*
147 * A simple, stupid (aka slow) sorting routine.
148 *
149 * precondition: a[i] is not a root node.
150 */
151 //@ requires \nonnullelements(a);
152 private static void sort(Tree[] a) {
153 // Only arrays of length>2 need to be sorted:
154 if (a.length<2)
155 return;
156
157 // Bubble sort...
158 for (;;) {
159 boolean sorted = true;
160 for (int i=0; i<a.length-1; i++) {
161 if (a[i].getLabel().compareTo //@ nowarn Null;
162 (a[i+1].getLabel())>0) { //@ nowarn NonNull;
163 Tree tmp = a[i];
164 a[i] = a[i+1];
165 a[i+1] = tmp;
166 sorted = false;
167 }
168 }
169 if (sorted)
170 return;
171 }
172 }
173
174
175 /***************************************************
176 * *
177 * Debugging: *
178 * *
179 **************************************************/
180
181 /** A simple test driver. */
182 //@ requires \nonnullelements(args);
183 public static void main(String[] args) {
184 if (args.length != 1) {
185 System.out.println("usage: TreeWalker <pathname>");
186 return;
187 }
188 String treeName = args[0];
189
190 // Find the tree in question:
191 Tree top = new FileTree(new File(treeName));
192
193 // Enumerate its subtrees:
194 for (Enumeration E = new TreeWalker(top); E.hasMoreElements();) {
195 Tree subtree = (Tree)E.nextElement();
196 System.out.println(subtree.getQualifiedName(".") + ":");
197 }
198 }
199 }
200
201
202 /**
203 * A Enumeration for enumerating the members of an array of Objects.
204 *
205 * This filter is for the use of the TreeWalker class only; if inner
206 * classes were available, it would be expressed as an anonymous class.
207 */
208 class TreeWalker_ArrayEnum extends LookAheadEnum {
209
210 //@ private invariant list != null;
211 //@ private invariant \elemtype(\typeof(list)) == elementType;
212 private Object[] list;
213
214 //@ private invariant index+1>=0;
215 private int index = -1;
216
217
218 //@ private normal_behavior
219 //@ requires list != null;
220 //@ assignable \not_specified;
221 //@ ensures elementType == \elemtype(\typeof(list));
222 TreeWalker_ArrayEnum(Object[] list) {
223 this.list = list;
224
225 //@ set elementType = \elemtype(\typeof(list));
226 }
227
228 //@ also private normal_behavior
229 //@ assignable index;
230 public Object calcNextElement() {
231 if (++index>=list.length)
232 return null;
233 else
234 return list[index];
235 }
236 }