KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > jofti > util > FastSet


1 package com.jofti.util;
2
3 import java.util.AbstractSet JavaDoc;
4 import java.util.Collection JavaDoc;
5 import java.util.ConcurrentModificationException JavaDoc;
6 import java.util.HashMap JavaDoc;
7 import java.util.Iterator JavaDoc;
8 import java.util.LinkedHashMap JavaDoc;
9 import java.util.LinkedHashSet JavaDoc;
10 import java.util.Map JavaDoc;
11 import java.util.NoSuchElementException JavaDoc;
12
13
14
15
16
17 import java.io.Serializable JavaDoc;
18 import java.lang.ref.SoftReference JavaDoc;
19
20
21
22
23 /**
24  *
25  * This is a specific implementation of a Set (heavily based on the HashMap code) that provides for quicker and cached
26  * return of entries in the toArray method. </p>
27  * Once a call to the toArray has been made, the resulting Object[] is cached for future calls. </p>
28  *
29  * Any mutator method called on the set will clear the cached array. In addition, the cached array is held as a SoftReference so the
30  * Garbage Collector can clear the value if it needs to. </p>
31  * The degenerate behaviour without the cache is around 50% of the Hashset implementation.
32  *
33  * @author swoodcock
34  *
35  */

36 public class FastSet extends AbstractSet JavaDoc
37  implements Cloneable JavaDoc, Serializable JavaDoc
38 {
39     transient SoftReference JavaDoc lookupArray = null;
40   
41       /**
42      * The default initial capacity - MUST be a power of two.
43      */

44     static final int DEFAULT_INITIAL_CAPACITY = 2;
45
46     /**
47      * The maximum capacity, used if a higher value is implicitly specified
48      * by either of the constructors with arguments.
49      * MUST be a power of two <= 1<<30.
50      */

51     static final int MAXIMUM_CAPACITY = 1 << 30;
52
53     /**
54      * The load factor used when none specified in constructor.
55      **/

56     static final float DEFAULT_LOAD_FACTOR = 0.75f;
57
58     /**
59      * The table, resized as necessary. Length MUST Always be a power of two.
60      */

61      transient Entry[] table;
62
63     /**
64      * The number of key-value mappings contained in this identity hash map.
65      */

66      transient int size;
67   
68     /**
69      * The next size value at which to resize (capacity * load factor).
70      * @serial
71      */

72     int threshold;
73   
74     /**
75      * The load factor for the hash table.
76      *
77      * @serial
78      */

79     float loadFactor;
80
81     /**
82      * The number of times this HashMap has been structurally modified
83      * Structural modifications are those that change the number of mappings in
84      * the HashMap or otherwise modify its internal structure (e.g.,
85      * rehash). This field is used to make iterators on Collection-views of
86      * the HashMap fail-fast. (See ConcurrentModificationException).
87      */

88     transient volatile int modCount;
89  
90
91   
92     /**
93      * Constructs an empty <tt>HashMap</tt> with the default initial
94      * capacity and the default load factor (0.75).
95      *
96      * @throws IllegalArgumentException if the initial capacity is negative.
97      */

98     public FastSet() {
99         this.loadFactor = DEFAULT_LOAD_FACTOR;
100         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
101         table = new Entry[DEFAULT_INITIAL_CAPACITY];
102     }
103     
104     /**
105      * Value representing null keys inside tables.
106      */

107     static final Object JavaDoc NULL_KEY = new Object JavaDoc();
108     
109     static Object JavaDoc maskNull(Object JavaDoc key) {
110         return (key == null ? NULL_KEY : key);
111     }
112
113     /**
114      * Returns key represented by specified internal representation.
115      */

116     static Object JavaDoc unmaskNull(Object JavaDoc key) {
117         return (key == NULL_KEY ? null : key);
118     }
119     
120     static class Entry {
121         Object JavaDoc value;
122         final int hash;
123         Entry next;
124
125         /**
126          * Create new entry.
127          */

128         Entry(int h, Object JavaDoc k, Entry n) {
129             next = n;
130             value = k;
131             hash = h;
132         }
133
134         public Object JavaDoc getValue() {
135             return unmaskNull(value);
136         }
137     
138     
139         public Object JavaDoc setValue(Object JavaDoc newValue) {
140             Object JavaDoc oldValue = value;
141             value = newValue;
142             return oldValue;
143         }
144     
145         public boolean equals(Object JavaDoc o) {
146             if (!(o instanceof Map.Entry JavaDoc))
147                 return false;
148             Entry e = (Entry)o;
149             Object JavaDoc k1 = value;
150             Object JavaDoc k2 = e.value;
151             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
152                     return true;
153             }
154             return false;
155         }
156     
157         public int hashCode() {
158             return (value==NULL_KEY ? 0 : value.hashCode());
159         }
160     
161         public String JavaDoc toString() {
162             return getValue().toString();
163         }
164
165         /**
166          * This method is invoked whenever the value in an entry is
167          * overwritten by an invocation of put(k,v) for a key k that's already
168          * in the HashMap.
169          */

170         void recordAccess(HashMap JavaDoc m) {
171         }
172
173         /**
174          * This method is invoked whenever the entry is
175          * removed from the table.
176          */

177         void recordRemoval(HashMap JavaDoc m) {
178         }
179     }
180
181     public Iterator JavaDoc iterator() {
182         return new KeyIterator();
183         }
184     
185     public int size() {
186         return size;
187         }
188     public boolean isEmpty() {
189         return size == 0;
190     }
191     
192     
193     static int hash(Object JavaDoc x) {
194         int h = x.hashCode();
195
196         h += ~(h << 9);
197         h ^= (h >>> 14);
198         h += (h << 4);
199         h ^= (h >>> 10);
200         return h;
201     }
202
203     /**
204      * Check for equality of non-null reference x and possibly-null y.
205      */

206     static boolean eq(Object JavaDoc x, Object JavaDoc y) {
207         return x == y || x.equals(y);
208     }
209
210     /**
211      * Returns index for hash code h.
212      */

213     static int indexFor(int h, int length) {
214         return h & (length-1);
215     }
216     
217     public boolean contains(Object JavaDoc o) {
218         
219
220                 Object JavaDoc k = maskNull(o);
221                 int hash = hash(k);
222                 int i = indexFor(hash, table.length);
223                 Entry e = table[i];
224                 while (e != null) {
225                     if (e.hash == hash && eq(k, e.value))
226                         return true;
227                     e = e.next;
228                 }
229                 return false;
230             }
231
232     private void clearCache(){
233         lookupArray = new SoftReference JavaDoc(null);
234
235         
236     }
237     public boolean add(Object JavaDoc o) {
238             // set toArray cache to be null
239
clearCache();
240             
241                 Object JavaDoc k = maskNull(o);
242                 int hash = hash(k);
243                 int i = indexFor(hash, table.length);
244
245                 for (Entry e = table[i]; e != null; e = e.next) {
246                     if (e.hash == hash && eq(k, e.value)) {
247                         Object JavaDoc oldValue = e.value;
248                         e.value = k;
249                        
250                         return oldValue ==null;
251                     }
252                 }
253
254                 modCount++;
255                 addEntry(hash, k, i);
256                 return false;
257             
258
259         }
260     
261     public boolean remove(Object JavaDoc o) {
262         
263           Entry e = removeEntryForKey(o);
264           return (e == null ? false : true);
265         }
266     
267    
268     /**
269      * Removes and returns the entry associated with the specified key
270      * in the HashMap. Returns null if the HashMap contains no mapping
271      * for this key.
272      */

273     Entry removeEntryForKey(Object JavaDoc value) {
274         Object JavaDoc k = maskNull(value);
275         int hash = hash(k);
276         int i = indexFor(hash, table.length);
277         Entry prev = table[i];
278         Entry e = prev;
279
280         while (e != null) {
281             Entry next = e.next;
282             if (e.hash == hash && eq(k, e.value)) {
283                 modCount++;
284                 size--;
285                 if (prev == e)
286                     table[i] = next;
287                 else
288                     prev.next = next;
289                 return e;
290             }
291             prev = e;
292             e = next;
293         }
294        if (e != null){
295            clearCache();
296        }
297         return e;
298     }
299
300     public void clear() {
301         // set toArray cache to be null
302
clearCache();
303         modCount++;
304         Entry tab[] = table;
305         for (int i = 0; i < tab.length; i++)
306             tab[i] = null;
307         size = 0;
308     }
309     public boolean removeAll(Collection JavaDoc c) {
310         boolean modified =false;
311     clearCache();
312     if (size() > c.size()) {
313         for (Iterator JavaDoc i = c.iterator(); i.hasNext(); )
314             modified |= remove(i.next());
315     } else {
316         for (Iterator JavaDoc i = iterator(); i.hasNext(); ) {
317             if(c.contains(i.next())) {
318                 i.remove();
319                 modified = true;
320             }
321         }
322     }
323     return modified;
324     
325     }
326     /**
327      * Add a new entry with the specified key, value and hash code to
328      * the specified bucket. It is the responsibility of this
329      * method to resize the table if appropriate.
330      *
331      * Subclass overrides this to alter the behavior of put method.
332      */

333     void addEntry(int hash, Object JavaDoc value, int bucketIndex) {
334         table[bucketIndex] = new Entry(hash, value, table[bucketIndex]);
335         if (size++ >= threshold)
336             resize(2 * table.length);
337     }
338     
339     void resize(int newCapacity) {
340         Entry[] oldTable = table;
341         int oldCapacity = oldTable.length;
342         if (oldCapacity == MAXIMUM_CAPACITY) {
343             threshold = Integer.MAX_VALUE;
344             return;
345         }
346
347         Entry[] newTable = new Entry[newCapacity];
348         transfer(newTable);
349         table = newTable;
350         threshold = (int)(newCapacity * loadFactor);
351     }
352     
353     /**
354      * Transfer all entries from current table to newTable.
355      */

356     void transfer(Entry[] newTable) {
357         Entry[] src = table;
358         int newCapacity = newTable.length;
359         for (int j = 0; j < src.length; j++) {
360             Entry e = src[j];
361             if (e != null) {
362                 src[j] = null;
363                 do {
364                     Entry next = e.next;
365                     int i = indexFor(e.hash, newCapacity);
366                     e.next = newTable[i];
367                     newTable[i] = e;
368                     e = next;
369                 } while (e != null);
370             }
371         }
372     }
373     
374     
375     
376     
377     public Object JavaDoc[] toArray() {
378         Object JavaDoc[] result = null;
379         if (lookupArray != null){
380             result =(Object JavaDoc[])lookupArray.get();
381         }
382         
383             if (result ==null){
384                 result= new Object JavaDoc[size];
385                 int resultCounter =0;
386                 Entry n = null;
387                 int length = table.length-1;
388                 for (int i = length; i >= 0 ; i--){
389                     n = table[i];
390                     while (n != null){
391                         result[resultCounter++]= n.value;
392                         n = n.next;
393                     }
394                   
395                 }
396                 lookupArray = new SoftReference JavaDoc(result);
397             }
398         return result;
399         }
400     
401    
402     
403     
404     public boolean containsAll(Collection JavaDoc c) {
405         Iterator JavaDoc e = c.iterator();
406         while (e.hasNext())
407             if(!contains(e.next()))
408             return false;
409
410         return true;
411         }
412
413     private class KeyIterator extends HashIterator {
414         public Object JavaDoc next() {
415             return nextEntry().getValue();
416         }
417     }
418     
419     private abstract class HashIterator implements Iterator JavaDoc {
420         Entry next; // next entry to return
421
int expectedModCount; // For fast-fail
422
int index; // current slot
423
Entry current; // current entry
424

425         HashIterator() {
426             expectedModCount = modCount;
427             Entry[] t = table;
428             if (t ==null){
429     
430             }
431             int i = t.length;
432             Entry n = null;
433             if (size != 0) { // advance to first entry
434
while (i > 0 && (n = t[--i]) == null)
435                     ;
436             }
437             next = n;
438             index = i;
439         }
440
441         public boolean hasNext() {
442             return next != null;
443         }
444
445         Entry nextEntry() {
446             if (modCount != expectedModCount)
447                 throw new ConcurrentModificationException JavaDoc();
448             Entry e = next;
449             if (e == null)
450                 throw new NoSuchElementException JavaDoc();
451                 
452             Entry n = e.next;
453             Entry[] t = table;
454             int i = index;
455             while (n == null && i > 0)
456                 n = t[--i];
457             index = i;
458             next = n;
459             return current = e;
460         }
461
462         public void remove() {
463             
464             if (current == null)
465                 throw new IllegalStateException JavaDoc();
466             if (modCount != expectedModCount)
467                 throw new ConcurrentModificationException JavaDoc();
468             // set toArray cache to be null
469
clearCache();
470             Object JavaDoc k = current.value;
471             current = null;
472             removeEntryForKey(k);
473             expectedModCount = modCount;
474         }
475
476     }
477     
478     private void writeObject(java.io.ObjectOutputStream JavaDoc s)
479     throws java.io.IOException JavaDoc {
480 // Write out any hidden serialization magic
481
s.defaultWriteObject();
482
483     // Write out HashMap capacity and load factor
484
s.writeFloat(loadFactor);
485
486     // Write out size
487
s.writeInt(size);
488
489 // Write out all elements in the proper order.
490
for (Iterator JavaDoc i=new KeyIterator(); i.hasNext(); )
491         s.writeObject(i.next());
492 }
493
494 /**
495  * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
496  * deserialize it).
497  */

498 private void readObject(java.io.ObjectInputStream JavaDoc s)
499     throws java.io.IOException JavaDoc, ClassNotFoundException JavaDoc {
500 // Read in any hidden serialization magic
501
s.defaultReadObject();
502
503     // Read in HashMap capacity and load factor and create backing HashMap
504
float loadFactor = s.readFloat();
505     
506     this.loadFactor = DEFAULT_LOAD_FACTOR;
507     threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
508     table = new Entry[DEFAULT_INITIAL_CAPACITY];
509     
510   
511     // Read in size
512
int size = s.readInt();
513
514 // Read in all elements in the proper order.
515
for (int i=0; i<size; i++) {
516         Object JavaDoc e = s.readObject();
517         add(e);
518     }
519 }
520     
521 }
522
523
524
Popular Tags