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 }