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


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags