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 }