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    }