1
2
3
4 package jwutil.collections;
5
6 import java.util.Collection;
7 import java.util.HashMap;
8 import java.util.Iterator;
9 import java.util.LinkedHashSet;
10 import java.util.Map;
11 import java.util.Set;
12 import java.io.PrintStream;
13 import jwutil.util.Assert;
14
15 /***
16 * @author John Whaley <jwhaley@alum.mit.edu>
17 * @version $Id: SetRepository.java 2249 2005-04-29 02:32:27Z joewhaley $
18 */
19 public class SetRepository extends SetFactory {
20
21 /***
22 * Version ID for serialization.
23 */
24 private static final long serialVersionUID = 4050480114695222065L;
25
26 public static final boolean USE_HASHCODES = true;
27 public static final boolean USE_SIZES = false;
28
29 public static final boolean VerifyAssertions = false;
30 public static final boolean TRACE = false;
31 public static final PrintStream out = System.out;
32
33 public static class LinkedHashSetFactory extends SetFactory {
34 /***
35 * Version ID for serialization.
36 */
37 private static final long serialVersionUID = 3257854264024840501L;
38
39 private LinkedHashSetFactory() { }
40 public static final LinkedHashSetFactory INSTANCE = new LinkedHashSetFactory();
41
42 /*** Generates a new mutable <code>Set</code>, using the elements
43 of <code>c</code> as a template for its initial contents.
44 */
45 public final Set makeSet(Collection c) {
46 return new LinkedHashSet(c);
47 }
48 }
49 public static class SimpleHashSetFactory extends MapFactory {
50 private SimpleHashSetFactory() { }
51 public static final SimpleHashSetFactory INSTANCE = new SimpleHashSetFactory();
52
53 /*** Generates a new <code>Map</code>, using the entries of
54 <code>map</code> as a template for its initial mappings.
55 */
56 public final Map makeMap(Map map) {
57 SimpleHashSet set = new SimpleHashSet();
58 set.putAll(map);
59 return set;
60 }
61 }
62
63 Map cache;
64 SetFactory setFactory;
65 MapFactory entryFactory;
66
67 public SetRepository() {
68 if (USE_HASHCODES) {
69 cache = new HashMap();
70 setFactory = LinkedHashSetFactory.INSTANCE;
71 entryFactory = LightMap.Factory.INSTANCE;
72 } else if (USE_SIZES) {
73 cache = new LightMap();
74 setFactory = LinkedHashSetFactory.INSTANCE;
75 entryFactory = SimpleHashSetFactory.INSTANCE;
76 } else {
77 Assert.UNREACHABLE();
78 }
79 }
80
81 public final Set makeSet(Collection c) {
82 Set s = SharedSet.make(this, c);
83 if (VerifyAssertions) {
84 if (!s.equals(c))
85 Assert.UNREACHABLE(c+" != "+s);
86 }
87 return s;
88 }
89
90 public SharedSet getUnion(Collection sets, boolean disjoint) {
91 Set check;
92 if (VerifyAssertions) {
93 check = new LinkedHashSet();
94 for (Iterator i=sets.iterator(); i.hasNext(); )
95 check.addAll((Collection)i.next());
96
97 }
98 if (USE_HASHCODES) {
99 SharedSet resultSet = SharedSet.makeUnion(this, sets);
100 Object setIdentifier = new Integer(resultSet.hashCode());
101 Map entry = (Map) cache.get(setIdentifier);
102 if (entry == null) {
103 if (TRACE) out.println("Adding new cache entry for "+setIdentifier);
104 cache.put(setIdentifier, entry = entryFactory.makeMap());
105 } else {
106 if (TRACE) out.println("Cache entry for "+setIdentifier+" exists");
107 }
108 SharedSet resultSet2 = (SharedSet) entry.get(resultSet);
109 if (resultSet2 != null) {
110 if (TRACE) out.println("Set already exists in cache: "+System.identityHashCode(resultSet2));
111 if (VerifyAssertions) {
112 if (!check.equals(resultSet2)) {
113 Assert.UNREACHABLE(check+" != "+resultSet2);
114 }
115 }
116 return resultSet2;
117 }
118 entry.put(resultSet, resultSet);
119 if (TRACE) out.println("Set doesn't exist in cache, adding: "+System.identityHashCode(resultSet));
120 if (VerifyAssertions) {
121 if (!check.equals(resultSet)) {
122 Assert.UNREACHABLE(check+" != "+resultSet);
123 }
124 }
125 return resultSet;
126 } else if (USE_SIZES) {
127 Object setIdentifier;
128 if (disjoint)
129 setIdentifier = calculateSetIdentifier_disjoint(sets);
130 else
131 setIdentifier = calculateSetIdentifier(sets);
132 Map entry = (Map) cache.get(setIdentifier);
133 if (entry == null) {
134 if (TRACE) out.println("Adding new cache entry for "+setIdentifier);
135 cache.put(setIdentifier, entry = entryFactory.makeMap());
136 } else {
137 if (TRACE) out.println("Cache entry for "+setIdentifier+" exists");
138 }
139 int newHashCode;
140 if (disjoint)
141 newHashCode = calculateHashcode_disjoint(sets);
142 else
143 newHashCode = calculateHashcode(sets);
144 SimpleHashSet s = (SimpleHashSet) entry;
145 Iterator i = s.getMatchingHashcode(newHashCode).iterator();
146 uphere:
147 while (i.hasNext()) {
148 SharedSet hs = (SharedSet) i.next();
149 if (TRACE) out.println("Checking matching hashcode ("+newHashCode+") set: "+System.identityHashCode(hs));
150 Iterator j = sets.iterator();
151 while (j.hasNext()) {
152 Set s1 = (Set) j.next();
153 if (!hs.containsAll(s1)) {
154 if (TRACE) out.println("Missing something from set "+System.identityHashCode(s1));
155 continue uphere;
156 }
157 }
158 if (TRACE) out.println("Set already exists in cache: "+System.identityHashCode(hs));
159 if (VerifyAssertions) {
160 if (!check.equals(hs)) {
161 Assert.UNREACHABLE(check+" != "+hs);
162 }
163 }
164 return hs;
165 }
166 SharedSet resultSet = SharedSet.makeUnion(this, sets);
167 s.put(resultSet, resultSet);
168 if (TRACE) out.println("Set doesn't exist in cache, adding: "+System.identityHashCode(resultSet));
169 if (VerifyAssertions) {
170 if (!check.equals(resultSet)) {
171 Assert.UNREACHABLE(check+" != "+resultSet);
172 }
173 }
174 return resultSet;
175 } else {
176 Assert.UNREACHABLE(); return null;
177 }
178 }
179
180 static boolean checkDisjoint(Collection sets) {
181 Iterator i = sets.iterator();
182 if (!i.hasNext()) return true;
183 Set s1 = (Set) i.next();
184 while (i.hasNext()) {
185 s1 = (Set) i.next();
186 for (Iterator j = s1.iterator(); j.hasNext(); ) {
187 Object o = j.next();
188 for (Iterator k = sets.iterator(); ; ) {
189 Set s2 = (Set) k.next();
190 if (s2 == s1) break;
191 if (s2.contains(o)) return false;
192 }
193 }
194 }
195 return true;
196 }
197
198 static int calculateHashcode_disjoint(Collection sets) {
199 int newHashCode = 0;
200 for (Iterator i = sets.iterator(); i.hasNext(); ) {
201 Set s = (Set) i.next();
202 newHashCode += s.hashCode();
203 }
204 if (VerifyAssertions) Assert._assert(checkDisjoint(sets) == true);
205 return newHashCode;
206 }
207
208 static int calculateSize_disjoint(Collection sets) {
209 int newSize = 0;
210 for (Iterator i = sets.iterator(); i.hasNext(); ) {
211 Set s = (Set) i.next();
212 newSize += s.size();
213 }
214 if (VerifyAssertions) Assert._assert(checkDisjoint(sets) == true);
215 return newSize;
216 }
217
218 static int calculateHashcode(Collection sets) {
219 int newHashCode = 0;
220 Iterator i = sets.iterator();
221 if (!i.hasNext()) return newHashCode;
222 Set s1 = (Set) i.next();
223 newHashCode = s1.hashCode();
224 while (i.hasNext()) {
225 s1 = (Set) i.next();
226 uphere:
227 for (Iterator j = s1.iterator(); j.hasNext(); ) {
228 Object o = j.next();
229 for (Iterator k = sets.iterator(); ; ) {
230 Set s2 = (Set) k.next();
231 if (s2 == s1) break;
232 if (s2.contains(o)) break uphere;
233 }
234 newHashCode += o.hashCode();
235 }
236 }
237 return newHashCode;
238 }
239
240 static int calculateSize(Collection sets) {
241 int newSize = 0;
242 Iterator i = sets.iterator();
243 if (!i.hasNext()) return newSize;
244 Set s1 = (Set) i.next();
245 newSize = s1.size();
246 while (i.hasNext()) {
247 s1 = (Set) i.next();
248 uphere:
249 for (Iterator j = s1.iterator(); j.hasNext(); ) {
250 Object o = j.next();
251 for (Iterator k = sets.iterator(); ; ) {
252 Set s2 = (Set) k.next();
253 if (s2 == s1) break;
254 if (s2.contains(o)) break uphere;
255 }
256 ++newSize;
257 }
258 }
259 return newSize;
260 }
261
262 public static Object calculateSetIdentifier_disjoint(Collection sets) {
263 if (USE_HASHCODES) {
264 int newHashCode = calculateHashcode_disjoint(sets);
265 return new Integer(newHashCode);
266 } else if (USE_SIZES) {
267 int newSize = calculateSize_disjoint(sets);
268 return new Integer(newSize);
269 } else {
270 Assert.UNREACHABLE();
271 return null;
272 }
273 }
274
275 public static Object calculateSetIdentifier(Collection sets) {
276 if (USE_HASHCODES) {
277 int newHashCode = calculateHashcode(sets);
278 return new Integer(newHashCode);
279 } else if (USE_SIZES) {
280 int newSize = calculateSize(sets);
281 return new Integer(newSize);
282 } else {
283 Assert.UNREACHABLE();
284 return null;
285 }
286 }
287
288 public static class SharedSet implements Set {
289 private final Set set;
290 private final SetRepository repository;
291
292 public static SharedSet make(SetRepository repository, Collection s) {
293 return new SharedSet(repository, s);
294 }
295 public static SharedSet makeUnion(SetRepository repository, Collection sets) {
296 Iterator i = sets.iterator();
297 Set s = (Set) i.next();
298 SharedSet that = new SharedSet(repository, s);
299 while (i.hasNext()) {
300 s = (Set) i.next();
301 that.set.addAll(s);
302 }
303 return that;
304 }
305 private SharedSet(SetRepository repository, Collection s) {
306 this.repository = repository;
307 this.set = repository.setFactory.makeSet(s);
308 }
309
310 public SharedSet copyAndAddAll(Set s, boolean disjoint) {
311 return repository.getUnion(new Pair(this.set, s), disjoint);
312 }
313
314 public SharedSet copyAndAddAllSets(Collection sets, boolean disjoint) {
315 return repository.getUnion(sets, disjoint);
316 }
317
318 public String toString() {
319 StringBuffer sb = new StringBuffer();
320 sb.append("[shared: ");
321 for (Iterator i=iterator(); i.hasNext(); ) {
322 sb.append(i.next());
323 if (i.hasNext()) sb.append(", ");
324 }
325 sb.append("]");
326 return sb.toString();
327 }
328
329 public int hashCode() {
330 return this.set.hashCode();
331 }
332
333 public boolean equals(Collection c) {
334 return this.containsAll(c) && c.containsAll(this);
335 }
336
337 public boolean equals(Object o) {
338 if (o instanceof Collection) return equals((Collection)o);
339 return false;
340 }
341
342 /***
343 * @see java.util.Collection#add(Object)
344 */
345 public boolean add(Object arg0) {
346 throw new UnsupportedOperationException();
347 }
348
349 /***
350 * @see java.util.Collection#addAll(Collection)
351 */
352 public boolean addAll(Collection arg0) {
353 throw new UnsupportedOperationException();
354 }
355
356 /***
357 * @see java.util.Collection#clear()
358 */
359 public void clear() {
360 throw new UnsupportedOperationException();
361 }
362
363 /***
364 * @see java.util.Collection#contains(Object)
365 */
366 public boolean contains(Object arg0) {
367 return set.contains(arg0);
368 }
369
370 /***
371 * @see java.util.Collection#containsAll(Collection)
372 */
373 public boolean containsAll(Collection arg0) {
374 return set.containsAll(arg0);
375 }
376
377 /***
378 * @see java.util.Collection#isEmpty()
379 */
380 public boolean isEmpty() {
381 return set.isEmpty();
382 }
383
384 /***
385 * @see java.util.Collection#iterator()
386 */
387 public Iterator iterator() {
388 return set.iterator();
389 }
390
391 /***
392 * @see java.util.Collection#remove(Object)
393 */
394 public boolean remove(Object arg0) {
395 throw new UnsupportedOperationException();
396 }
397
398 /***
399 * @see java.util.Collection#removeAll(Collection)
400 */
401 public boolean removeAll(Collection arg0) {
402 throw new UnsupportedOperationException();
403 }
404
405 /***
406 * @see java.util.Collection#retainAll(Collection)
407 */
408 public boolean retainAll(Collection arg0) {
409 throw new UnsupportedOperationException();
410 }
411
412 /***
413 * @see java.util.Collection#size()
414 */
415 public int size() {
416 return set.size();
417 }
418
419 /***
420 * @see java.util.Collection#toArray()
421 */
422 public Object[] toArray() {
423 return set.toArray();
424 }
425
426 /***
427 * @see java.util.Collection#toArray(Object[])
428 */
429 public Object[] toArray(Object[] arg0) {
430 return set.toArray(arg0);
431 }
432
433 }
434
435 }