    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    }