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    }