001    /* Copyright 2000, 2001, Compaq Computer Corporation */
002    
003    package javafe.filespace;
004    
005    
006    import java.util.Enumeration;
007    import java.io.File;
008    
009    
010    /**
011     * A UnionTree is a Tree which represents the union of a series of
012     * Tree's.<p>
013     *
014     * A node exists in a UnionTree iff a corresponding node (i.e., same
015     * fully qualified name) exists in any of the underlying Trees.  Its
016     * data field is copied at creation time from the first such
017     * corresponding node (i.e., the one whose Tree is first in the list
018     * of underlying Trees).<p>
019     *
020     * Exception: if the underlying list contains 0 Trees, then the
021     * UnionTree contains exactly 1 node, the root node, which will have
022     * data equal to null.<p>
023     *
024     * The other corresponding nodes of a node X can be accessed by calling
025     * X.duplicates(), which returns a list of all the corresponding nodes
026     * (including the first one) in the same order as the original input
027     * list of Trees.<p>
028     * 
029     * The behavior of a UnionTree is undefined if the underlying Trees it
030     * depends on are altered after it has been created.<p>
031     */
032    
033    public class UnionTree extends PreloadedTree {
034    
035        /***************************************************
036         *                                                 *
037         * Creation:                                       *
038         *                                                 *
039         **************************************************/
040    
041        /**
042         * The list of Trees we represent the union of:<p>
043         *
044         * Invariant: contains no nulls and is non-null.<p>
045         */
046        //@ invariant \nonnullelements(roots);
047        protected Tree[] roots;
048    
049        /**
050         * Create a new Tree that represents the union of the Trees in
051         * roots.<p>
052         *
053         * roots must be non-null and contain no nulls.<p>
054         */
055        //@ requires \nonnullelements(roots);
056        public UnionTree(Tree[] roots) {
057            super(null);
058    
059            this.roots = roots;
060            if (roots.length>0)
061                data = roots[0].data;
062        }
063    
064        /**
065         * Create a non-root node:<p>
066         *
067         * roots must be non-null and contain no nulls.<p>
068         */
069        //@ requires \nonnullelements(roots);
070        //@ requires parent != null && label != null;
071        protected UnionTree(Tree parent, String label, Tree[] roots) {
072            super(parent, label, null);
073    
074            this.roots = roots;
075            if (roots.length>0)
076                data = roots[0].data;
077        }
078    
079        /***************************************************
080         *                                                 *
081         * Accessors:                                      *
082         *                                                 *
083         **************************************************/
084    
085        /**
086         * Return a list of all the nodes that correspond to this one in
087         * the underlying Trees in the same order as the original list of
088         * Trees.  This ist is never null and never contains any nulls.
089         */
090        //@ ensures \nonnullelements(\result);
091        public Tree[] duplicates() {
092            return roots;
093        }
094    
095        /**
096         * Return the number of nodes corresponding to this one there are
097         * in the underlying Trees.
098         */
099        public int countDuplicates() {
100            return roots.length;
101        }
102    
103    
104        /***************************************************
105         *                                                 *
106         * Loading the edges map:                          *
107         *                                                 *
108         **************************************************/
109    
110        /** Load the edges map for use.  */
111        protected void loadEdges() {
112            /*
113             * Make sure all our direct children are loaded by trying to
114             * load all the direct edges of each of our roots:
115             */
116            for (int i=0; i<roots.length; i++)
117                for (Enumeration C=roots[i].children(); C.hasMoreElements(); ) {
118                    Tree next = (Tree)C.nextElement();
119                    loadEdge(next.getLabel());              //@ nowarn Pre;
120                }
121        }
122    
123        /* Load the direct edge labeled label if it is not already loaded */
124        //@ requires label != null;
125        protected void loadEdge(String label) {
126            if (edges.containsKey(label))
127                return;                     // Edge already loaded...
128    
129            // Get a list and count of the corresponding nodes:
130            int count = 0;
131            Tree[] directChildren = new Tree[roots.length];
132            for (int i=0; i<roots.length; i++) {
133                Tree directChild = roots[i].getChild(label);
134                if (directChild != null)
135                    directChildren[count++] = directChild;
136            }
137    
138            // If there are no corresponding nodes, then do nothing;
139            // this case should not occur.
140            if (count == 0)
141                return;
142    
143            // Shrink the resulting array to remove the extra space then use
144            // the list of nodes to create a subUnionTree to be installed as
145            // the child for this edge.
146            Tree[] childRoots = new Tree[count];
147            for (int i=0; i<count; i++)
148                childRoots[i] = directChildren[i];
149    
150            edges.put(label, new UnionTree(this, label, childRoots));
151        }
152    
153    
154        /***************************************************
155         *                                                 *
156         * Debugging functions:                            *
157         *                                                 *
158         **************************************************/
159    
160        public void printDetails(String prefix) {
161            System.out.print(" [" + countDuplicates() + "]");
162    
163    //      System.out.println();
164    //      for (int i=0; i<roots.length; i++)
165    //          roots[i].print(prefix + "  >> ");
166        }
167    
168        /** A simple test driver */
169        //@ requires args != null;
170        /*@ requires (\forall int i; (0<=i && i<args.length)
171                    ==> args[i] != null); */
172        public static void main(String[] args) {
173            /*
174             * Create a list of FileTree's using the paths we're passed in:
175             */
176            Tree[] roots = new Tree[args.length];
177            for (int i=0; i<args.length; i++)
178                roots[i] = new FileTree(new File(args[i]));
179    
180            /*
181             * Create a new UnionTree that is a union of those trees then
182             * print it out.
183             */
184            Tree T = new UnionTree(roots);
185            T.print("");
186        }
187    }