Java > Open Source Codes > bak > pcj > map > ObjectKeyFloatChainedHashMap


1 /*
2  * Primitive Collections for Java.
3  * Copyright (C) 2003 Søren Bak
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */
19 package bak.pcj.map;
20
21 import bak.pcj.FloatCollection;
22 import bak.pcj.AbstractFloatCollection;
23 import bak.pcj.FloatIterator;
24 import bak.pcj.hash.DefaultFloatHashFunction;
25 import bak.pcj.util.Exceptions;
26 import java.util.Set ;
27 import java.util.AbstractSet ;
28 import java.util.Iterator ;
29
30 import java.io.Serializable ;
31 import java.io.IOException ;
32 import java.io.ObjectInputStream ;
33 import java.io.ObjectOutputStream ;
34
35 /**
36  * This class represents chained hash table based maps from
37  * object values to float values.
38  *
39  * @see ObjectKeyFloatOpenHashMap
40  * @see java.util.Map
41  *
42  * @author Søren Bak
43  * @version 1.1 2003/8/3
44  * @since 1.1
45  */
46 public class ObjectKeyFloatChainedHashMap extends AbstractObjectKeyFloatMap implements ObjectKeyFloatMap, Cloneable , Serializable {
47
48     /** Constant indicating relative growth policy. */
49     private static final int GROWTH_POLICY_RELATIVE = 0;
50
51     /** Constant indicating absolute growth policy. */
52     private static final int GROWTH_POLICY_ABSOLUTE = 1;
53
54     /**
55      * The default growth policy of this map.
56      * @see #GROWTH_POLICY_RELATIVE
57      * @see #GROWTH_POLICY_ABSOLUTE
58      */
59     private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
60
61     /** The default factor with which to increase the capacity of this map. */
62     public static final double DEFAULT_GROWTH_FACTOR = 1.0;
63
64     /** The default chunk size with which to increase the capacity of this map. */
65     public static final int DEFAULT_GROWTH_CHUNK = 10;
66
67     /** The default capacity of this map. */
68     public static final int DEFAULT_CAPACITY = 11;
69
70     /** The default load factor of this map. */
71     public static final double DEFAULT_LOAD_FACTOR = 0.75;
72
73     /**
74      * The size of this map.
75      * @serial
76      */
77     private int size;
78
79     /** The hash table backing up this map. Contains linked entry values. */
80     private transient Entry[] data;
81
82     /**
83      * The growth policy of this map. (0 is relative growth, 1 is absolute growth).
84      * @serial
85      */
86     private int growthPolicy;
87
88     /**
89      * The growth factor of this map, if the growth policy is
90      * relative.
91      * @serial
92      */
93     private double growthFactor;
94
95     /**
96      * The growth chunk size of this map, if the growth policy is
97      * absolute.
98      * @serial
99      */
100     private int growthChunk;
101
102     /**
103      * The load factor of this map.
104      * @serial
105      */
106     private double loadFactor;
107
108     /**
109      * The next size at which to expand the data[].
110      * @serial
111      */
112     private int expandAt;
113
114     /** A set view of the keys of this map. */
115     private transient Set keys;
116
117     /** A collection view of the values of this map. */
118     private transient FloatCollection values;
119
120     /** Indicates whether last call to containsKey() had a corresponding value. */
121     private transient boolean hasLastValue;
122     
123     /** Value corresponding to to the key of the last call of containsKey(). */
124     private transient float lastValue;
125
126     private ObjectKeyFloatChainedHashMap(int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
127         if (capacity < 0)
128             Exceptions.negativeArgument("capacity", String.valueOf(capacity));
129         if (growthFactor < 0.0)
130             Exceptions.negativeArgument("growthFactor", String.valueOf(growthFactor));
131         if (growthChunk < 0)
132             Exceptions.negativeArgument("growthChunk", String.valueOf(growthChunk));
133         if (loadFactor <= 0.0)
134             Exceptions.negativeOrZeroArgument("loadFactor", String.valueOf(loadFactor));
135         data = new Entry[capacity];
136         size = 0;
137         expandAt = (int)Math.round(loadFactor*capacity);
138         this.growthPolicy = growthPolicy;
139         this.growthFactor = growthFactor;
140         this.growthChunk = growthChunk;
141         this.loadFactor = loadFactor;
142         hasLastValue = false;
143     }
144
145     /**
146      * Creates a new hash map with capacity 11, a relative
147      * growth factor of 1.0, and a load factor of 75%.
148      */
149     public ObjectKeyFloatChainedHashMap() {
150         this(DEFAULT_CAPACITY);
151     }
152
153     /**
154      * Creates a new hash map with the same mappings as a specified map.
155      *
156      * @param map
157      * the map whose mappings to put into the new map.
158      *
159      * @throws NullPointerException
160      * if <tt>map</tt> is <tt>null</tt>.
161      */
162     public ObjectKeyFloatChainedHashMap(ObjectKeyFloatMap map) {
163         this();
164         putAll(map);
165     }
166
167     /**
168      * Creates a new hash map with a specified capacity, a relative
169      * growth factor of 1.0, and a load factor of 75%.
170      *
171      * @param capacity
172      * the initial capacity of the map.
173      *
174      * @throws IllegalArgumentException
175      * if <tt>capacity</tt> is negative.
176      */
177     public ObjectKeyFloatChainedHashMap(int capacity) {
178         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
179     }
180
181     /**
182      * Creates a new hash map with a capacity of 11, a relative
183      * growth factor of 1.0, and a specified load factor.
184      *
185      * @param loadFactor
186      * the load factor of the map.
187      *
188      * @throws IllegalArgumentException
189      * if <tt>capacity</tt> is negative.
190      */
191     public ObjectKeyFloatChainedHashMap(double loadFactor) {
192         this(DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
193     }
194
195     /**
196      * Creates a new hash map with a specified capacity and
197      * load factor, and a relative growth factor of 1.0.
198      *
199      * @param capacity
200      * the initial capacity of the map.
201      *
202      * @param loadFactor
203      * the load factor of the map.
204      *
205      * @throws IllegalArgumentException
206      * if <tt>capacity</tt> is negative;
207      * if <tt>loadFactor</tt> is not positive.
208      */
209     public ObjectKeyFloatChainedHashMap(int capacity, double loadFactor) {
210         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
211     }
212
213     /**
214      * Creates a new hash map with a specified capacity,
215      * load factor, and relative growth factor.
216      *
217      * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
218      * This strategy is good for avoiding many capacity increases, but
219      * the amount of wasted memory is approximately the size of the map.
220      *
221      * @param capacity
222      * the initial capacity of the map.
223      *
224      * @param loadFactor
225      * the load factor of the map.
226      *
227      * @param growthFactor
228      * the relative amount with which to increase the
229      * the capacity when a capacity increase is needed.
230      *
231      * @throws IllegalArgumentException
232      * if <tt>capacity</tt> is negative;
233      * if <tt>loadFactor</tt> is not positive;
234      * if <tt>growthFactor</tt> is not positive.
235      */
236     public ObjectKeyFloatChainedHashMap(int capacity, double loadFactor, double growthFactor) {
237         this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
238     }
239
240     /**
241      * Creates a new hash map with a specified capacity,
242      * load factor, and absolute growth factor.
243      *
244      * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
245      * This strategy is good for avoiding wasting memory. However, an
246      * overhead is potentially introduced by frequent capacity increases.
247      *
248      * @param capacity
249      * the initial capacity of the map.
250      *
251      * @param loadFactor
252      * the load factor of the map.
253      *
254      * @param growthChunk
255      * the absolute amount with which to increase the
256      * the capacity when a capacity increase is needed.
257      *
258      * @throws IllegalArgumentException
259      * if <tt>capacity</tt> is negative;
260      * if <tt>loadFactor</tt> is not positive;
261      * if <tt>growthChunk</tt> is not positive;
262      */
263     public ObjectKeyFloatChainedHashMap(int capacity, double loadFactor, int growthChunk) {
264         this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
265     }
266
267     // ---------------------------------------------------------------
268 // Hash table management
269 // ---------------------------------------------------------------
270
271     private static int hash(Object key)
272     { return key == null ? 0 : key.hashCode(); }
273
274     private static boolean keyeq(Object k1, Object k2)
275     { return k1 == null ? k2 == null : k1.equals(k2); }
276
277     private void ensureCapacity(int elements) {
278         if (elements >= expandAt) {
279             int newcapacity;
280             if (growthPolicy == GROWTH_POLICY_RELATIVE)
281                 newcapacity = (int)(data.length * (1.0 + growthFactor));
282             else
283                 newcapacity = data.length + growthChunk;
284             if (newcapacity*loadFactor < elements)
285                 newcapacity = (int)Math.round(((double)elements/loadFactor));
286             newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
287             expandAt = (int)Math.round(loadFactor*newcapacity);
288
289             Entry[] newdata = new Entry[newcapacity];
290
291             // re-hash
292 for (int i = 0; i < data.length; i++) {
293                 Entry e = data[i];
294                 while (e != null) {
295                     int index = Math.abs(hash(e.key)) % newdata.length;
296                     Entry next = e.next;
297                     e.next = newdata[index];
298                     newdata[index] = e;
299                     e = next;
300                 }
301             }
302
303             data = newdata;
304         }
305     }
306
307     private Entry addList(Entry list, Entry v) {
308         v.next = list;
309         return v;
310     }
311
312     private Entry removeList(Entry list, Entry e) {
313         if (list == e) {
314             list = e.next;
315             e.next = null;
316             return list;
317         }
318         Entry listStart = list;
319         while (list.next != e)
320             list = list.next;
321         list.next = e.next;
322         e.next = null;
323         return listStart;
324     }
325
326     private Entry searchList(Entry list, Object key) {
327         while (list != null) {
328             if (keyeq(list.key, key))
329                 return list;
330             list = list.next;
331         }
332         return null;
333     }
334
335     private Entry getEntry(Object key) {
336         int index = Math.abs(hash(key)) % data.length;
337         return searchList(data[index], key);
338     }
339
340     // ---------------------------------------------------------------
341 // Operations not supported by abstract implementation
342 // ---------------------------------------------------------------
343
344     public Set keySet() {
345         if (keys == null)
346             keys = new KeySet();
347         return keys;
348     }
349
350     public float lget() {
351         if (!hasLastValue)
352             Exceptions.noLastElement();
353         return lastValue;
354     }
355
356     public float put(Object key, float value) {
357         float result;
358         int index = Math.abs(hash(key)) % data.length;
359         Entry e = searchList(data[index], key);
360         if (e == null) {
361             result = MapDefaults.defaultFloat();
362             e = new Entry(key, value);
363             e.next = data[index];
364             data[index] = e;
365             // Capacity is increased after insertion in order to
366 // avoid recalculation of index
367 ensureCapacity(size+1);
368             size++;
369         } else {
370             result = e.value;
371             e.value = value;
372         }
373         return result;
374     }
375
376     public FloatCollection values() {
377         if (values == null)
378             values = new ValueCollection();
379         return values;
380     }
381
382     /**
383      * Returns a clone of this hash map.
384      *
385      * @return a clone of this hash map.
386      *
387      * @since 1.1
388      */
389     public Object clone() {
390         try {
391             ObjectKeyFloatChainedHashMap c = (ObjectKeyFloatChainedHashMap)super.clone();
392             c.data = new Entry[data.length];
393             for (int i = 0; i < data.length; i++)
394                 c.data[i] = cloneList(data[i]);
395             // The views should not refer to this map's views
396 c.values = null;
397             c.keys = null;
398             return c;
399         } catch (CloneNotSupportedException e) {
400             Exceptions.cloning(); return null;
401         }
402     }
403
404     private Entry cloneList(Entry e) {
405         if (e == null)
406             return null;
407         Entry ne = new Entry(e.getKey(), e.getValue());
408         ne.next = cloneList(e.next);
409         return ne;
410     }
411
412     private static class Entry {
413         Object key;
414         float value;
415         Entry next;
416
417         Entry(Object key, float value) {
418             this.key = key;
419             this.value = value;
420         }
421
422         public Object getKey()
423         { return key; }
424
425         public float getValue()
426         { return value; }
427
428         public boolean equals(Object obj) {
429             if (!(obj instanceof Entry))
430                 return false;
431             Entry e = (Entry)obj;
432             return keyeq(e.getKey(), key) && e.getValue() == value;
433         }
434     }
435
436
437     public ObjectKeyFloatMapIterator entries() {
438         return new ObjectKeyFloatMapIterator() {
439             Entry currEntry = null;
440             int nextList = nextList(0);
441             Entry nextEntry = nextList == -1 ? null : data[nextList];
442
443             int nextList(int index) {
444                 while (index < data.length && data[index] == null)
445                     index++;
446                 return index < data.length ? index : -1;
447             }
448
449             public boolean hasNext() {
450                 return nextEntry != null;
451             }
452
453             public void next() {
454                 if (nextEntry == null)
455                     Exceptions.endOfIterator();
456                 currEntry = nextEntry;
457
458                 // Find next
459 nextEntry = nextEntry.next;
460                 if (nextEntry == null) {
461                     nextList = nextList(nextList+1);
462                     if (nextList != -1)
463                         nextEntry = data[nextList];
464                 }
465             }
466
467             public Object getKey() {
468                 if (currEntry == null)
469                     Exceptions.noElementToGet();
470                 return currEntry.getKey();
471             }
472
473             public float getValue() {
474                 if (currEntry == null)
475                     Exceptions.noElementToGet();
476                 return currEntry.getValue();
477             }
478
479             public void remove() {
480                 if (currEntry == null)
481                     Exceptions.noElementToRemove();
482                  ObjectKeyFloatChainedHashMap.this.remove(currEntry.getKey());
483                  currEntry = null;
484             }
485
486         };
487     }
488
489     private class KeySet extends AbstractSet {
490
491         public void clear()
492         { ObjectKeyFloatChainedHashMap.this.clear(); }
493
494         public boolean contains(Object v) {
495             return getEntry(v) != null;
496         }
497
498         public Iterator iterator() {
499             return new Iterator() {
500                 Entry currEntry = null;
501                 int nextList = nextList(0);
502                 Entry nextEntry = nextList == -1 ? null : data[nextList];
503
504                 int nextList(int index) {
505                     while (index < data.length && data[index] == null)
506                         index++;
507                     return index < data.length ? index : -1;
508                 }
509
510                 public boolean hasNext() {
511                     return nextEntry != null;
512                 }
513
514                 public Object next() {
515                     if (nextEntry == null)
516                         Exceptions.endOfIterator();
517                     currEntry = nextEntry;
518
519                     // Find next
520 nextEntry = nextEntry.next;
521                     if (nextEntry == null) {
522                         nextList = nextList(nextList+1);
523                         if (nextList != -1)
524                             nextEntry = data[nextList];
525                     }
526                     return currEntry.key;
527                 }
528
529                 public void remove() {
530                     if (currEntry == null)
531                         Exceptions.noElementToRemove();
532                      ObjectKeyFloatChainedHashMap.this.remove(currEntry.getKey());
533                      currEntry = null;
534                 }
535             };
536         }
537
538         public boolean remove(Object v) {
539             boolean result = containsKey(v);
540             if (result)
541                 ObjectKeyFloatChainedHashMap.this.remove(v);
542             return result;
543         }
544
545         public int size()
546         { return size; }
547
548     }
549
550
551     private class ValueCollection extends AbstractFloatCollection {
552
553         public void clear()
554         { ObjectKeyFloatChainedHashMap.this.clear(); }
555
556         public boolean contains(float v) {
557             return containsValue(v);
558         }
559
560         public FloatIterator iterator() {
561             return new FloatIterator() {
562                 Entry currEntry = null;
563                 int nextList = nextList(0);
564                 Entry nextEntry = nextList == -1 ? null : data[nextList];
565
566                 int nextList(int index) {
567                     while (index < data.length && data[index] == null)
568                         index++;
569                     return index < data.length ? index : -1;
570                 }
571
572                 public boolean hasNext() {
573                     return nextEntry != null;
574                 }
575
576                 public float next() {
577                     if (nextEntry == null)
578                         Exceptions.endOfIterator();
579                     currEntry = nextEntry;
580
581                     // Find next
582 nextEntry = nextEntry.next;
583                     if (nextEntry == null) {
584                         nextList = nextList(nextList+1);
585                         if (nextList != -1)
586                             nextEntry = data[nextList];
587                     }
588                     return currEntry.value;
589                 }
590
591                 public void remove() {
592                     if (currEntry == null)
593                         Exceptions.noElementToRemove();
594                      ObjectKeyFloatChainedHashMap.this.remove(currEntry.getKey());
595                      currEntry = null;
596                 }
597             };
598         }
599
600         public int size()
601         { return size; }
602
603     }
604
605     // ---------------------------------------------------------------
606 // Operations overwritten for efficiency
607 // ---------------------------------------------------------------
608
609     public void clear() {
610         java.util.Arrays.fill(data, null);
611         size = 0;
612     }
613
614     public boolean containsKey(Object key) {
615         Entry e = getEntry(key);
616         if (e == null)
617             hasLastValue = false;
618         else {
619             hasLastValue = true;
620             lastValue = e.value;
621         }
622         return hasLastValue;
623     }
624
625     public boolean containsValue(float value) {
626         for (int i = 0; i < data.length; i++) {
627             Entry e = data[i];
628             while (e != null) {
629                 if (e.value == value)
630                     return true;
631                 e = e.next;
632             }
633         }
634         return false;
635     }
636
637     public float get(Object key) {
638         int index = Math.abs(hash(key)) % data.length;
639         Entry e = searchList(data[index], key);
640         return e != null ? e.value : MapDefaults.defaultFloat();
641     }
642
643     public boolean isEmpty()
644     { return size == 0; }
645
646     public float remove(Object key) {
647         int index = Math.abs(hash(key)) % data.length;
648         Entry e = searchList(data[index], key);
649         float value;
650         if (e != null) {
651             // This can be improved to one iteration
652 data[index] = removeList(data[index], e);
653             value = e.value;
654             size--;
655         } else
656             value = MapDefaults.defaultFloat();
657         return value;
658     }
659
660     public int size()
661     { return size; }
662
663     public float tget(Object key) {
664         int index = Math.abs(hash(key)) % data.length;
665         Entry e = searchList(data[index], key);
666         if (e == null)
667             Exceptions.noSuchMapping(key);
668         return e.value;
669     }
670
671     // ---------------------------------------------------------------
672 // Serialization
673 // ---------------------------------------------------------------
674
675     /**
676      * @serialData Default fields; the capacity of the
677      * map (<tt>int</tt>); the maps's entries
678      * (<tt>Object</tt>, <tt>float</tt>).
679      */
680     private void writeObject(ObjectOutputStream s) throws IOException {
681         s.defaultWriteObject();
682         s.writeInt(data.length);
683         ObjectKeyFloatMapIterator i = entries();
684         while (i.hasNext()) {
685             i.next();
686             s.writeObject(i.getKey());
687             s.writeFloat(i.getValue());
688         }
689     }
690
691     private void readObject(ObjectInputStream s) throws IOException , ClassNotFoundException {
692         s.defaultReadObject();
693         data = new Entry[s.readInt()];
694         for (int i = 0; i < size; i++) {
695             Object key = s.readObject();
696             float value = s.readFloat();
697             int index = Math.abs(hash(key)) % data.length;
698             Entry e = new Entry(key, value);
699             e.next = data[index];
700             data[index] = e;
701         }
702     }
703
704 }

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags