DoubleKeyDoubleChainedHashMap


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