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


1 /*
2  * Primitive Collections for Java.
3  * Copyright (C) 2002, 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.IntCollection;
22 import bak.pcj.AbstractIntCollection;
23 import bak.pcj.FloatIterator;
24 import bak.pcj.IntIterator;
25 import bak.pcj.AbstractFloatCollection;
26 import bak.pcj.set.AbstractFloatSet;
27 import bak.pcj.set.FloatSet;
28 import bak.pcj.hash.FloatHashFunction;
29 import bak.pcj.hash.DefaultFloatHashFunction;
30 import bak.pcj.util.Exceptions;
31
32 import java.io.Serializable ;
33 import java.io.IOException ;
34 import java.io.ObjectInputStream ;
35 import java.io.ObjectOutputStream ;
36
37 /**
38  * This class represents open addressing hash table based maps from
39  * float values to int values.
40  *
41  * @see FloatKeyIntChainedHashMap
42  * @see java.util.Map
43  *
44  * @author Søren Bak
45  * @version 1.4 21-08-2003 18:40
46  * @since 1.0
47  */
48 public class FloatKeyIntOpenHashMap extends AbstractFloatKeyIntMap implements FloatKeyIntMap, Cloneable , Serializable {
49
50     /** Constant indicating relative growth policy. */
51     private static final int GROWTH_POLICY_RELATIVE = 0;
52
53     /** Constant indicating absolute growth policy. */
54     private static final int GROWTH_POLICY_ABSOLUTE = 1;
55
56     /**
57      * The default growth policy of this map.
58      * @see #GROWTH_POLICY_RELATIVE
59      * @see #GROWTH_POLICY_ABSOLUTE
60      */
61     private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
62
63     /** The default factor with which to increase the capacity of this map. */
64     public static final double DEFAULT_GROWTH_FACTOR = 1.0;
65
66     /** The default chunk size with which to increase the capacity of this map. */
67     public static final int DEFAULT_GROWTH_CHUNK = 10;
68
69     /** The default capacity of this map. */
70     public static final int DEFAULT_CAPACITY = 11;
71
72     /** The default load factor of this map. */
73     public static final double DEFAULT_LOAD_FACTOR = 0.75;
74
75     /**
76      * The hash function used to hash keys in this map.
77      * @serial
78      */
79     private FloatHashFunction keyhash;
80
81     /**
82      * The size of this map.
83      * @serial
84      */
85     private int size;
86
87     /**
88      * The keys of this map. Contains key values directly.
89      * Due to the use of a secondary hash function, the length of this
90      * array must be a prime.
91      */
92     private transient float[] keys;
93
94     /**
95      * The values of this map. Contains values directly.
96      * Due to the use of a secondary hash function, the length of this
97      * array must be a prime.
98      */
99     private transient int[] values;
100
101     /** The states of each cell in the keys[] and values[]. */
102     private transient byte[] states;
103
104     private static final byte EMPTY = 0;
105     private static final byte OCCUPIED = 1;
106     private static final byte REMOVED = 2;
107
108     /** The number of entries in use (removed or occupied). */
109     private transient int used;
110
111     /**
112      * The growth policy of this map (0 is relative growth, 1 is absolute growth).
113      * @serial
114      */
115     private int growthPolicy;
116
117     /**
118      * The growth factor of this map, if the growth policy is
119      * relative.
120      * @serial
121      */
122     private double growthFactor;
123
124     /**
125      * The growth chunk size of this map, if the growth policy is
126      * absolute.
127      * @serial
128      */
129     private int growthChunk;
130
131     /**
132      * The load factor of this map.
133      * @serial
134      */
135     private double loadFactor;
136
137     /**
138      * The next size at which to expand the data[].
139      * @serial
140      */
141     private int expandAt;
142
143     /** A set view of the keys of this map. */
144     private transient FloatSet ckeys;
145
146     /** A collection view of the values of this map. */
147     private transient IntCollection cvalues;
148
149     /** Indicates whether last call to containsKey() had a corresponding value. */
150     private transient boolean hasLastValue;
151     
152     /** Value corresponding to to the key of the last call of containsKey(). */
153     private transient int lastValue;
154
155     private FloatKeyIntOpenHashMap(FloatHashFunction keyhash, int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
156         if (keyhash == null)
157             Exceptions.nullArgument("hash function");
158         if (capacity < 0)
159             Exceptions.negativeArgument("capacity", String.valueOf(capacity));
160         if (growthFactor <= 0.0)
161             Exceptions.negativeOrZeroArgument("growthFactor", String.valueOf(growthFactor));
162         if (growthChunk <= 0)
163             Exceptions.negativeOrZeroArgument("growthChunk", String.valueOf(growthChunk));
164         if (loadFactor <= 0.0)
165             Exceptions.negativeOrZeroArgument("loadFactor", String.valueOf(loadFactor));
166         this.keyhash = keyhash;
167         capacity = bak.pcj.hash.Primes.nextPrime(capacity);
168         keys = new float[capacity];
169         values = new int[capacity];
170         this.states = new byte[capacity];
171         size = 0;
172         expandAt = (int)Math.round(loadFactor*capacity);
173         this.used = 0;
174         this.growthPolicy = growthPolicy;
175         this.growthFactor = growthFactor;
176         this.growthChunk = growthChunk;
177         this.loadFactor = loadFactor;
178         hasLastValue = false;
179     }
180
181     private FloatKeyIntOpenHashMap(int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
182         this(DefaultFloatHashFunction.INSTANCE, capacity, growthPolicy, growthFactor, growthChunk, loadFactor);
183     }
184
185     /**
186      * Creates a new hash map with capacity 11, a relative
187      * growth factor of 1.0, and a load factor of 75%.
188      */
189     public FloatKeyIntOpenHashMap() {
190         this(DEFAULT_CAPACITY);
191     }
192
193     /**
194      * Creates a new hash map with the same mappings as a specified map.
195      *
196      * @param map
197      * the map whose mappings to put into the new map.
198      *
199      * @throws NullPointerException
200      * if <tt>map</tt> is <tt>null</tt>.
201      */
202     public FloatKeyIntOpenHashMap(FloatKeyIntMap map) {
203         this();
204         putAll(map);
205     }
206
207     /**
208      * Creates a new hash map with a specified capacity, a relative
209      * growth factor of 1.0, and a load factor of 75%.
210      *
211      * @param capacity
212      * the initial capacity of the map.
213      *
214      * @throws IllegalArgumentException
215      * if <tt>capacity</tt> is negative.
216      */
217     public FloatKeyIntOpenHashMap(int capacity) {
218         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
219     }
220
221     /**
222      * Creates a new hash map with a capacity of 11, a relative
223      * growth factor of 1.0, and a specified load factor.
224      *
225      * @param loadFactor
226      * the load factor of the map.
227      *
228      * @throws IllegalArgumentException
229      * if <tt>capacity</tt> is negative;
230      * if <tt>loadFactor</tt> is not positive.
231      */
232     public FloatKeyIntOpenHashMap(double loadFactor) {
233         this(DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
234     }
235
236     /**
237      * Creates a new hash map with a specified capacity and
238      * load factor, and a relative growth factor of 1.0.
239      *
240      * @param capacity
241      * the initial capacity of the map.
242      *
243      * @param loadFactor
244      * the load factor of the map.
245      *
246      * @throws IllegalArgumentException
247      * if <tt>capacity</tt> is negative;
248      * if <tt>loadFactor</tt> is not positive.
249      */
250     public FloatKeyIntOpenHashMap(int capacity, double loadFactor) {
251         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
252     }
253
254     /**
255      * Creates a new hash map with a specified capacity,
256      * load factor, and relative growth factor.
257      *
258      * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
259      * This strategy is good for avoiding many capacity increases, but
260      * the amount of wasted memory is approximately the size of the map.
261      *
262      * @param capacity
263      * the initial capacity of the map.
264      *
265      * @param loadFactor
266      * the load factor of the map.
267      *
268      * @param growthFactor
269      * the relative amount with which to increase the
270      * the capacity when a capacity increase is needed.
271      *
272      * @throws IllegalArgumentException
273      * if <tt>capacity</tt> is negative;
274      * if <tt>loadFactor</tt> is not positive;
275      * if <tt>growthFactor</tt> is not positive.
276      */
277     public FloatKeyIntOpenHashMap(int capacity, double loadFactor, double growthFactor) {
278         this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
279     }
280
281     /**
282      * Creates a new hash map with a specified capacity,
283      * load factor, and absolute growth factor.
284      *
285      * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
286      * This strategy is good for avoiding wasting memory. However, an
287      * overhead is potentially introduced by frequent capacity increases.
288      *
289      * @param capacity
290      * the initial capacity of the map.
291      *
292      * @param loadFactor
293      * the load factor of the map.
294      *
295      * @param growthChunk
296      * the absolute amount with which to increase the
297      * the capacity when a capacity increase is needed.
298      *
299      * @throws IllegalArgumentException
300      * if <tt>capacity</tt> is negative;
301      * if <tt>loadFactor</tt> is not positive;
302      * if <tt>growthChunk</tt> is not positive.
303      */
304     public FloatKeyIntOpenHashMap(int capacity, double loadFactor, int growthChunk) {
305         this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
306     }
307
308     // ---------------------------------------------------------------
309 // Constructors with hash function argument
310 // ---------------------------------------------------------------
311
312     /**
313      * Creates a new hash map with capacity 11, a relative
314      * growth factor of 1.0, and a load factor of 75%.
315      *
316      * @param keyhash
317      * the hash function to use when hashing keys.
318      *
319      * @throws NullPointerException
320      * if <tt>keyhash</tt> is <tt>null</tt>.
321      */
322     public FloatKeyIntOpenHashMap(FloatHashFunction keyhash) {
323         this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
324     }
325
326     /**
327      * Creates a new hash map with a specified capacity, a relative
328      * growth factor of 1.0, and a load factor of 75%.
329      *
330      * @param keyhash
331      * the hash function to use when hashing keys.
332      *
333      * @param capacity
334      * the initial capacity of the map.
335      *
336      * @throws IllegalArgumentException
337      * if <tt>capacity</tt> is negative.
338      *
339      * @throws NullPointerException
340      * if <tt>keyhash</tt> is <tt>null</tt>.
341      */
342     public FloatKeyIntOpenHashMap(FloatHashFunction keyhash, int capacity) {
343         this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
344     }
345
346     /**
347      * Creates a new hash map with a capacity of 11, a relative
348      * growth factor of 1.0, and a specified load factor.
349      *
350      * @param keyhash
351      * the hash function to use when hashing keys.
352      *
353      * @param loadFactor
354      * the load factor of the map.
355      *
356      * @throws IllegalArgumentException
357      * if <tt>capacity</tt> is negative;
358      * if <tt>loadFactor</tt> is not positive.
359      *
360      * @throws NullPointerException
361      * if <tt>keyhash</tt> is <tt>null</tt>.
362      */
363     public FloatKeyIntOpenHashMap(FloatHashFunction keyhash, double loadFactor) {
364         this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
365     }
366
367     /**
368      * Creates a new hash map with a specified capacity and
369      * load factor, and a relative growth factor of 1.0.
370      *
371      * @param keyhash
372      * the hash function to use when hashing keys.
373      *
374      * @param capacity
375      * the initial capacity of the map.
376      *
377      * @param loadFactor
378      * the load factor of the map.
379      *
380      * @throws IllegalArgumentException
381      * if <tt>capacity</tt> is negative;
382      * if <tt>loadFactor</tt> is not positive.
383      *
384      * @throws NullPointerException
385      * if <tt>keyhash</tt> is <tt>null</tt>.
386      */
387     public FloatKeyIntOpenHashMap(FloatHashFunction keyhash, int capacity, double loadFactor) {
388         this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
389     }
390
391     /**
392      * Creates a new hash map with a specified capacity,
393      * load factor, and relative growth factor.
394      *
395      * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
396      * This strategy is good for avoiding many capacity increases, but
397      * the amount of wasted memory is approximately the size of the map.
398      *
399      * @param keyhash
400      * the hash function to use when hashing keys.
401      *
402      * @param capacity
403      * the initial capacity of the map.
404      *
405      * @param loadFactor
406      * the load factor of the map.
407      *
408      * @param growthFactor
409      * the relative amount with which to increase the
410      * the capacity when a capacity increase is needed.
411      *
412      * @throws IllegalArgumentException
413      * if <tt>capacity</tt> is negative;
414      * if <tt>loadFactor</tt> is not positive;
415      * if <tt>growthFactor</tt> is not positive.
416      *
417      * @throws NullPointerException
418      * if <tt>keyhash</tt> is <tt>null</tt>.
419      */
420     public FloatKeyIntOpenHashMap(FloatHashFunction keyhash, int capacity, double loadFactor, double growthFactor) {
421         this(keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
422     }
423
424     /**
425      * Creates a new hash map with a specified capacity,
426      * load factor, and absolute growth factor.
427      *
428      * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
429      * This strategy is good for avoiding wasting memory. However, an
430      * overhead is potentially introduced by frequent capacity increases.
431      *
432      * @param keyhash
433      * the hash function to use when hashing keys.
434      *
435      * @param capacity
436      * the initial capacity of the map.
437      *
438      * @param loadFactor
439      * the load factor of the map.
440      *
441      * @param growthChunk
442      * the absolute amount with which to increase the
443      * the capacity when a capacity increase is needed.
444      *
445      * @throws IllegalArgumentException
446      * if <tt>capacity</tt> is negative;
447      * if <tt>loadFactor</tt> is not positive;
448      * if <tt>growthChunk</tt> is not positive.
449      *
450      * @throws NullPointerException
451      * if <tt>keyhash</tt> is <tt>null</tt>.
452      */
453     public FloatKeyIntOpenHashMap(FloatHashFunction keyhash, int capacity, double loadFactor, int growthChunk) {
454         this(keyhash, capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
455     }
456
457     // ---------------------------------------------------------------
458 // Hash table management
459 // ---------------------------------------------------------------
460
461     private void ensureCapacity(int elements) {
462         if (elements >= expandAt) {
463             int newcapacity;
464             if (growthPolicy == GROWTH_POLICY_RELATIVE)
465                 newcapacity = (int)(keys.length * (1.0 + growthFactor));
466             else
467                 newcapacity = keys.length + growthChunk;
468             if (newcapacity*loadFactor < elements)
469                 newcapacity = (int)Math.round(((double)elements/loadFactor));
470             newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
471             expandAt = (int)Math.round(loadFactor*newcapacity);
472
473             float[] newkeys = new float[newcapacity];
474             int[] newvalues = new int[newcapacity];
475             byte[] newstates = new byte[newcapacity];
476
477             used = 0;
478             // re-hash
479 for (int i = 0; i < keys.length; i++) {
480                 if (states[i] == OCCUPIED) {
481                     used++;
482                     float k = keys[i];
483                     int v = values[i];
484                     // first hash
485 int h = Math.abs(keyhash.hash(k));
486                     int n = h % newcapacity;
487                     if (newstates[n] == OCCUPIED) {
488                         // second hash
489 int c = 1 + (h % (newcapacity - 2));
490                         for (;;) {
491                             n -= c;
492                             if (n < 0)
493                                 n += newcapacity;
494                             if (newstates[n] == EMPTY)
495                                 break;
496                         }
497                     }
498                     newstates[n] = OCCUPIED;
499                     newvalues[n] = v;
500                     newkeys[n] = k;
501                 }
502             }
503
504             keys = newkeys;
505             values = newvalues;
506             states = newstates;
507         }
508     }
509
510     // ---------------------------------------------------------------
511 // Operations not supported by abstract implementation
512 // ---------------------------------------------------------------
513
514     public FloatSet keySet() {
515         if (ckeys == null)
516             ckeys = new KeySet();
517         return ckeys;
518     }
519
520     public int lget() {
521         if (!hasLastValue)
522             Exceptions.noLastElement();
523         return lastValue;
524     }
525
526     public int put(float key, int value) {
527         int result;
528
529         // first hash
530 int h = Math.abs(keyhash.hash(key));
531         int i = h % keys.length;
532         if (states[i] == OCCUPIED) {
533             if (keys[i] == key) {
534                 int oldValue = values[i];
535                 values[i] = value;
536                 return oldValue;
537             }
538             // second hash
539 int c = 1 + (h % (keys.length - 2));
540             for (;;) {
541                 i -= c;
542                 if (i < 0)
543                     i += keys.length;
544                 // Empty entries are not re-used
545 if (states[i] == EMPTY || states[i] == REMOVED)
546                     break;
547                 if (states[i] == OCCUPIED && keys[i] == key) {
548                     int oldValue = values[i];
549                     values[i] = value;
550                     return oldValue;
551                 }
552             }
553         }
554         if (states[i] == EMPTY)
555             used++;
556         states[i] = OCCUPIED;
557         keys[i] = key;
558         values[i] = value;
559         size++;
560         ensureCapacity(used);
561         return MapDefaults.defaultInt();
562     }
563
564     public IntCollection values() {
565         if (cvalues == null)
566             cvalues = new ValueCollection();
567         return cvalues;
568     }
569
570     /**
571      * Returns a clone of this hash map.
572      *
573      * @return a clone of this hash map.
574      *
575      * @since 1.1
576      */
577     public Object clone() {
578         try {
579             FloatKeyIntOpenHashMap c = (FloatKeyIntOpenHashMap)super.clone();
580             c.keys = new float[keys.length];
581             System.arraycopy(keys, 0, c.keys, 0, keys.length);
582             c.values = new int[values.length];
583             System.arraycopy(values, 0, c.values, 0, values.length);
584             c.states = new byte[states.length];
585             System.arraycopy(states, 0, c.states, 0, states.length);
586             // The views should not refer to this map's views
587 c.cvalues = null;
588             c.ckeys = null;
589             return c;
590         } catch (CloneNotSupportedException e) {
591             Exceptions.cloning(); return null;
592         }
593     }
594
595     public FloatKeyIntMapIterator entries() {
596         return new FloatKeyIntMapIterator() {
597             int nextEntry = nextEntry(0);
598             int lastEntry = -1;
599
600             int nextEntry(int index) {
601                 while (index < keys.length && states[index] != OCCUPIED)
602                     index++;
603                 return index;
604             }
605
606             public boolean hasNext() {
607                 return nextEntry < keys.length;
608             }
609
610             public void next() {
611                 if (!hasNext())
612                     Exceptions.endOfIterator();
613                 lastEntry = nextEntry;
614                 nextEntry = nextEntry(nextEntry+1);
615             }
616
617             public void remove() {
618                 if (lastEntry == -1)
619                     Exceptions.noElementToRemove();
620                 states[lastEntry] = REMOVED;
621                 size--;
622                 lastEntry = -1;
623             }
624
625             public float getKey() {
626                 if (lastEntry == -1)
627                     Exceptions.noElementToGet();
628                 return keys[lastEntry];
629             }
630
631             public int getValue() {
632                 if (lastEntry == -1)
633                     Exceptions.noElementToGet();
634                 return values[lastEntry];
635             }
636         };
637     }
638
639     private class KeySet extends AbstractFloatSet {
640
641         public void clear()
642         { FloatKeyIntOpenHashMap.this.clear(); }
643
644         public boolean contains(float v) {
645             return containsKey(v);
646         }
647
648         public FloatIterator iterator() {
649             return new FloatIterator() {
650                 int nextEntry = nextEntry(0);
651                 int lastEntry = -1;
652
653                 int nextEntry(int index) {
654                     while (index < keys.length && states[index] != OCCUPIED)
655                         index++;
656                     return index;
657                 }
658
659                 public boolean hasNext() {
660                     return nextEntry < keys.length;
661                 }
662
663                 public float next() {
664                     if (!hasNext())
665                         Exceptions.endOfIterator();
666                     lastEntry = nextEntry;
667                     nextEntry = nextEntry(nextEntry+1);
668                     return keys[lastEntry];
669                 }
670
671                 public void remove() {
672                     if (lastEntry == -1)
673                         Exceptions.noElementToRemove();
674                     states[lastEntry] = REMOVED;
675                     size--;
676                     lastEntry = -1;
677                 }
678             };
679         }
680
681         public boolean remove(float v) {
682             boolean result = containsKey(v);
683             if (result)
684                 FloatKeyIntOpenHashMap.this.remove(v);
685             return result;
686         }
687
688         public int size()
689         { return size; }
690
691     }
692
693
694     private class ValueCollection extends AbstractIntCollection {
695
696         public void clear()
697         { FloatKeyIntOpenHashMap.this.clear(); }
698
699         public boolean contains(int v) {
700             return containsValue(v);
701         }
702
703         public IntIterator iterator() {
704             return new IntIterator() {
705                 int nextEntry = nextEntry(0);
706                 int lastEntry = -1;
707
708                 int nextEntry(int index) {
709                     while (index < keys.length && states[index] != OCCUPIED)
710                         index++;
711                     return index;
712                 }
713
714                 public boolean hasNext() {
715                     return nextEntry < keys.length;
716                 }
717
718                 public int next() {
719                     if (!hasNext())
720                         Exceptions.endOfIterator();
721                     lastEntry = nextEntry;
722                     nextEntry = nextEntry(nextEntry+1);
723                     return values[lastEntry];
724                 }
725
726                 public void remove() {
727                     if (lastEntry == -1)
728                         Exceptions.noElementToRemove();
729                     states[lastEntry] = REMOVED;
730                     size--;
731                     lastEntry = -1;
732                 }
733             };
734         }
735
736         public int size()
737         { return size; }
738
739     }
740
741     // ---------------------------------------------------------------
742 // Operations overwritten for efficiency
743 // ---------------------------------------------------------------
744
745     public void clear() {
746         java.util.Arrays.fill(states, EMPTY);
747         size = 0;
748         used = 0;
749     }
750
751     public boolean containsKey(float key) {
752         int h = Math.abs(keyhash.hash(key));
753         int i = h % keys.length;
754         if (states[i] != EMPTY) {
755             if (states[i] == OCCUPIED && keys[i] == key) {
756                 hasLastValue = true;
757                 lastValue = values[i];
758                 return true;
759             }
760             // second hash
761
762             int c = 1 + (h % (keys.length - 2));
763             for (;;) {
764                 i -= c;
765                 if (i < 0)
766                     i += keys.length;
767                 if (states[i] == EMPTY) {
768                     hasLastValue = false;
769                     return false;
770                 }
771                 if (states[i] == OCCUPIED && keys[i] == key) {
772                     hasLastValue = true;
773                     lastValue = values[i];
774                     return true;
775                 }
776             }
777         }
778         hasLastValue = false;
779         return false;
780     }
781
782     public boolean containsValue(int value) {
783         for (int i = 0; i < states.length; i++)
784             if (states[i] == OCCUPIED && values[i] == value)
785                 return true;
786         return false;
787     }
788
789     public int get(float key) {
790         int h = Math.abs(keyhash.hash(key));
791         int i = h % keys.length;
792         if (states[i] != EMPTY) {
793             if (states[i] == OCCUPIED && keys[i] == key)
794                 return values[i];
795             // second hash
796
797             int c = 1 + (h % (keys.length - 2));
798             for (;;) {
799                 i -= c;
800                 if (i < 0)
801                     i += keys.length;
802                 if (states[i] == EMPTY)
803                     return MapDefaults.defaultInt();
804                 if (states[i] == OCCUPIED && keys[i] == key)
805                     return values[i];
806             }
807         }
808         return MapDefaults.defaultInt();
809     }
810
811     public boolean isEmpty()
812     { return size == 0; }
813
814     public int remove(float key) {
815         int h = Math.abs(keyhash.hash(key));
816         int i = h % keys.length;
817         if (states[i] != EMPTY) {
818             if (states[i] == OCCUPIED && keys[i] == key) {
819                 int oldValue = values[i];
820                 states[i] = REMOVED;
821                 size--;
822                 return oldValue;
823             }
824             // second hash
825 int c = 1 + (h % (keys.length - 2));
826             for (;;) {
827                 i -= c;
828                 if (i < 0)
829                     i += keys.length;
830                 if (states[i] == EMPTY) {
831                     return MapDefaults.defaultInt();
832                 }
833                 if (states[i] == OCCUPIED && keys[i] == key) {
834                     int oldValue = values[i];
835                     states[i] = REMOVED;
836                     size--;
837                     return oldValue;
838                 }
839             }
840         }
841         return MapDefaults.defaultInt();
842     }
843
844     public int size()
845     { return size; }
846
847     public int tget(float key) {
848         int h = Math.abs(keyhash.hash(key));
849         int i = h % keys.length;
850         if (states[i] != EMPTY) {
851             if (states[i] == OCCUPIED && keys[i] == key)
852                 return values[i];
853             // second hash
854
855             int c = 1 + (h % (keys.length - 2));
856             for (;;) {
857                 i -= c;
858                 if (i < 0)
859                     i += keys.length;
860                 if (states[i] == EMPTY)
861                     Exceptions.noSuchMapping(String.valueOf(key));
862                 if (states[i] == OCCUPIED && keys[i] == key)
863                     return values[i];
864             }
865         }
866         Exceptions.noSuchMapping(String.valueOf(key)); throw new RuntimeException ();
867     }
868
869     // ---------------------------------------------------------------
870 // Serialization
871 // ---------------------------------------------------------------
872
873     /**
874      * @serialData Default fields; the capacity of the
875      * map (<tt>int</tt>); the maps's entries
876      * (<tt>float</tt>, <tt>int</tt>).
877      *
878      * @since 1.1
879      */
880     private void writeObject(ObjectOutputStream s) throws IOException {
881         s.defaultWriteObject();
882         s.writeInt(keys.length);
883         FloatKeyIntMapIterator i = entries();
884         while (i.hasNext()) {
885             i.next();
886             s.writeFloat(i.getKey());
887             s.writeInt(i.getValue());
888         }
889     }
890
891     /**
892      * @since 1.1
893      */
894     private void readObject(ObjectInputStream s) throws IOException , ClassNotFoundException {
895         s.defaultReadObject();
896         keys = new float[s.readInt()];
897         states = new byte[keys.length];
898         values = new int[keys.length];
899         used = size;
900         
901         for (int n = 0; n < size; n++) {
902             float key = s.readFloat();
903             int value = s.readInt();
904
905             // first hash
906 int h = Math.abs(keyhash.hash(key));
907             int i = h % keys.length;
908             if (states[i] != EMPTY) {
909                 // second hash
910 int c = 1 + (h % (keys.length - 2));
911                 for (;;) {
912                     i -= c;
913                     if (i < 0)
914                         i += keys.length;
915                     if (states[i] == EMPTY)
916                         break;
917                 }
918             }
919             states[i] = OCCUPIED;
920             keys[i] = key;
921             values[i] = value;
922         }
923     }
924
925 }

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags