    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    }