View Javadoc

1   // SetRepository.java, created Wed Mar  5  0:26:27 2003 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
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              //if (TRACE) out.println("Looking for union set: "+check);
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 }