    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    }