001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 2002, 2003 Søren Bak
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019: package bak.pcj.map;
020:
021: import bak.pcj.LongCollection;
022: import bak.pcj.AbstractLongCollection;
023: import bak.pcj.DoubleIterator;
024: import bak.pcj.LongIterator;
025: import bak.pcj.AbstractDoubleCollection;
026: import bak.pcj.set.AbstractDoubleSet;
027: import bak.pcj.set.DoubleSet;
028: import bak.pcj.hash.DoubleHashFunction;
029: import bak.pcj.hash.DefaultDoubleHashFunction;
030: import bak.pcj.util.Exceptions;
031:
032: import java.io.Serializable;
033: import java.io.IOException;
034: import java.io.ObjectInputStream;
035: import java.io.ObjectOutputStream;
036:
037: /**
038: * This class represents open addressing hash table based maps from
039: * double values to long values.
040: *
041: * @see DoubleKeyLongChainedHashMap
042: * @see java.util.Map
043: *
044: * @author Søren Bak
045: * @version 1.4 21-08-2003 18:40
046: * @since 1.0
047: */
048: public class DoubleKeyLongOpenHashMap extends AbstractDoubleKeyLongMap
049: implements DoubleKeyLongMap, Cloneable, Serializable {
050:
051: /** Constant indicating relative growth policy. */
052: private static final int GROWTH_POLICY_RELATIVE = 0;
053:
054: /** Constant indicating absolute growth policy. */
055: private static final int GROWTH_POLICY_ABSOLUTE = 1;
056:
057: /**
058: * The default growth policy of this map.
059: * @see #GROWTH_POLICY_RELATIVE
060: * @see #GROWTH_POLICY_ABSOLUTE
061: */
062: private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
063:
064: /** The default factor with which to increase the capacity of this map. */
065: public static final double DEFAULT_GROWTH_FACTOR = 1.0;
066:
067: /** The default chunk size with which to increase the capacity of this map. */
068: public static final int DEFAULT_GROWTH_CHUNK = 10;
069:
070: /** The default capacity of this map. */
071: public static final int DEFAULT_CAPACITY = 11;
072:
073: /** The default load factor of this map. */
074: public static final double DEFAULT_LOAD_FACTOR = 0.75;
075:
076: /**
077: * The hash function used to hash keys in this map.
078: * @serial
079: */
080: private DoubleHashFunction keyhash;
081:
082: /**
083: * The size of this map.
084: * @serial
085: */
086: private int size;
087:
088: /**
089: * The keys of this map. Contains key values directly.
090: * Due to the use of a secondary hash function, the length of this
091: * array must be a prime.
092: */
093: private transient double[] keys;
094:
095: /**
096: * The values of this map. Contains values directly.
097: * Due to the use of a secondary hash function, the length of this
098: * array must be a prime.
099: */
100: private transient long[] values;
101:
102: /** The states of each cell in the keys[] and values[]. */
103: private transient byte[] states;
104:
105: private static final byte EMPTY = 0;
106: private static final byte OCCUPIED = 1;
107: private static final byte REMOVED = 2;
108:
109: /** The number of entries in use (removed or occupied). */
110: private transient int used;
111:
112: /**
113: * The growth policy of this map (0 is relative growth, 1 is absolute growth).
114: * @serial
115: */
116: private int growthPolicy;
117:
118: /**
119: * The growth factor of this map, if the growth policy is
120: * relative.
121: * @serial
122: */
123: private double growthFactor;
124:
125: /**
126: * The growth chunk size of this map, if the growth policy is
127: * absolute.
128: * @serial
129: */
130: private int growthChunk;
131:
132: /**
133: * The load factor of this map.
134: * @serial
135: */
136: private double loadFactor;
137:
138: /**
139: * The next size at which to expand the data[].
140: * @serial
141: */
142: private int expandAt;
143:
144: /** A set view of the keys of this map. */
145: private transient DoubleSet ckeys;
146:
147: /** A collection view of the values of this map. */
148: private transient LongCollection cvalues;
149:
150: /** Indicates whether last call to containsKey() had a corresponding value. */
151: private transient boolean hasLastValue;
152:
153: /** Value corresponding to to the key of the last call of containsKey(). */
154: private transient long lastValue;
155:
156: private DoubleKeyLongOpenHashMap(DoubleHashFunction keyhash,
157: int capacity, int growthPolicy, double growthFactor,
158: int growthChunk, double loadFactor) {
159: if (keyhash == null)
160: Exceptions.nullArgument("hash function");
161: if (capacity < 0)
162: Exceptions.negativeArgument("capacity", String
163: .valueOf(capacity));
164: if (growthFactor <= 0.0)
165: Exceptions.negativeOrZeroArgument("growthFactor", String
166: .valueOf(growthFactor));
167: if (growthChunk <= 0)
168: Exceptions.negativeOrZeroArgument("growthChunk", String
169: .valueOf(growthChunk));
170: if (loadFactor <= 0.0)
171: Exceptions.negativeOrZeroArgument("loadFactor", String
172: .valueOf(loadFactor));
173: this .keyhash = keyhash;
174: capacity = bak.pcj.hash.Primes.nextPrime(capacity);
175: keys = new double[capacity];
176: values = new long[capacity];
177: this .states = new byte[capacity];
178: size = 0;
179: expandAt = (int) Math.round(loadFactor * capacity);
180: this .used = 0;
181: this .growthPolicy = growthPolicy;
182: this .growthFactor = growthFactor;
183: this .growthChunk = growthChunk;
184: this .loadFactor = loadFactor;
185: hasLastValue = false;
186: }
187:
188: private DoubleKeyLongOpenHashMap(int capacity, int growthPolicy,
189: double growthFactor, int growthChunk, double loadFactor) {
190: this (DefaultDoubleHashFunction.INSTANCE, capacity,
191: growthPolicy, growthFactor, growthChunk, loadFactor);
192: }
193:
194: /**
195: * Creates a new hash map with capacity 11, a relative
196: * growth factor of 1.0, and a load factor of 75%.
197: */
198: public DoubleKeyLongOpenHashMap() {
199: this (DEFAULT_CAPACITY);
200: }
201:
202: /**
203: * Creates a new hash map with the same mappings as a specified map.
204: *
205: * @param map
206: * the map whose mappings to put into the new map.
207: *
208: * @throws NullPointerException
209: * if <tt>map</tt> is <tt>null</tt>.
210: */
211: public DoubleKeyLongOpenHashMap(DoubleKeyLongMap map) {
212: this ();
213: putAll(map);
214: }
215:
216: /**
217: * Creates a new hash map with a specified capacity, a relative
218: * growth factor of 1.0, and a load factor of 75%.
219: *
220: * @param capacity
221: * the initial capacity of the map.
222: *
223: * @throws IllegalArgumentException
224: * if <tt>capacity</tt> is negative.
225: */
226: public DoubleKeyLongOpenHashMap(int capacity) {
227: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
228: DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
229: }
230:
231: /**
232: * Creates a new hash map with a capacity of 11, a relative
233: * growth factor of 1.0, and a specified load factor.
234: *
235: * @param loadFactor
236: * the load factor of the map.
237: *
238: * @throws IllegalArgumentException
239: * if <tt>capacity</tt> is negative;
240: * if <tt>loadFactor</tt> is not positive.
241: */
242: public DoubleKeyLongOpenHashMap(double loadFactor) {
243: this (DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
244: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
245: }
246:
247: /**
248: * Creates a new hash map with a specified capacity and
249: * load factor, and a relative growth factor of 1.0.
250: *
251: * @param capacity
252: * the initial capacity of the map.
253: *
254: * @param loadFactor
255: * the load factor of the map.
256: *
257: * @throws IllegalArgumentException
258: * if <tt>capacity</tt> is negative;
259: * if <tt>loadFactor</tt> is not positive.
260: */
261: public DoubleKeyLongOpenHashMap(int capacity, double loadFactor) {
262: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
263: DEFAULT_GROWTH_CHUNK, loadFactor);
264: }
265:
266: /**
267: * Creates a new hash map with a specified capacity,
268: * load factor, and relative growth factor.
269: *
270: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
271: * This strategy is good for avoiding many capacity increases, but
272: * the amount of wasted memory is approximately the size of the map.
273: *
274: * @param capacity
275: * the initial capacity of the map.
276: *
277: * @param loadFactor
278: * the load factor of the map.
279: *
280: * @param growthFactor
281: * the relative amount with which to increase the
282: * the capacity when a capacity increase is needed.
283: *
284: * @throws IllegalArgumentException
285: * if <tt>capacity</tt> is negative;
286: * if <tt>loadFactor</tt> is not positive;
287: * if <tt>growthFactor</tt> is not positive.
288: */
289: public DoubleKeyLongOpenHashMap(int capacity, double loadFactor,
290: double growthFactor) {
291: this (capacity, GROWTH_POLICY_RELATIVE, growthFactor,
292: DEFAULT_GROWTH_CHUNK, loadFactor);
293: }
294:
295: /**
296: * Creates a new hash map with a specified capacity,
297: * load factor, and absolute growth factor.
298: *
299: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
300: * This strategy is good for avoiding wasting memory. However, an
301: * overhead is potentially introduced by frequent capacity increases.
302: *
303: * @param capacity
304: * the initial capacity of the map.
305: *
306: * @param loadFactor
307: * the load factor of the map.
308: *
309: * @param growthChunk
310: * the absolute amount with which to increase the
311: * the capacity when a capacity increase is needed.
312: *
313: * @throws IllegalArgumentException
314: * if <tt>capacity</tt> is negative;
315: * if <tt>loadFactor</tt> is not positive;
316: * if <tt>growthChunk</tt> is not positive.
317: */
318: public DoubleKeyLongOpenHashMap(int capacity, double loadFactor,
319: int growthChunk) {
320: this (capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR,
321: growthChunk, loadFactor);
322: }
323:
324: // ---------------------------------------------------------------
325: // Constructors with hash function argument
326: // ---------------------------------------------------------------
327:
328: /**
329: * Creates a new hash map with capacity 11, a relative
330: * growth factor of 1.0, and a load factor of 75%.
331: *
332: * @param keyhash
333: * the hash function to use when hashing keys.
334: *
335: * @throws NullPointerException
336: * if <tt>keyhash</tt> is <tt>null</tt>.
337: */
338: public DoubleKeyLongOpenHashMap(DoubleHashFunction keyhash) {
339: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
340: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK,
341: DEFAULT_LOAD_FACTOR);
342: }
343:
344: /**
345: * Creates a new hash map with a specified capacity, a relative
346: * growth factor of 1.0, and a load factor of 75%.
347: *
348: * @param keyhash
349: * the hash function to use when hashing keys.
350: *
351: * @param capacity
352: * the initial capacity of the map.
353: *
354: * @throws IllegalArgumentException
355: * if <tt>capacity</tt> is negative.
356: *
357: * @throws NullPointerException
358: * if <tt>keyhash</tt> is <tt>null</tt>.
359: */
360: public DoubleKeyLongOpenHashMap(DoubleHashFunction keyhash,
361: int capacity) {
362: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
363: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK,
364: DEFAULT_LOAD_FACTOR);
365: }
366:
367: /**
368: * Creates a new hash map with a capacity of 11, a relative
369: * growth factor of 1.0, and a specified load factor.
370: *
371: * @param keyhash
372: * the hash function to use when hashing keys.
373: *
374: * @param loadFactor
375: * the load factor of the map.
376: *
377: * @throws IllegalArgumentException
378: * if <tt>capacity</tt> is negative;
379: * if <tt>loadFactor</tt> is not positive.
380: *
381: * @throws NullPointerException
382: * if <tt>keyhash</tt> is <tt>null</tt>.
383: */
384: public DoubleKeyLongOpenHashMap(DoubleHashFunction keyhash,
385: double loadFactor) {
386: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
387: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
388: }
389:
390: /**
391: * Creates a new hash map with a specified capacity and
392: * load factor, and a relative growth factor of 1.0.
393: *
394: * @param keyhash
395: * the hash function to use when hashing keys.
396: *
397: * @param capacity
398: * the initial capacity of the map.
399: *
400: * @param loadFactor
401: * the load factor of the map.
402: *
403: * @throws IllegalArgumentException
404: * if <tt>capacity</tt> is negative;
405: * if <tt>loadFactor</tt> is not positive.
406: *
407: * @throws NullPointerException
408: * if <tt>keyhash</tt> is <tt>null</tt>.
409: */
410: public DoubleKeyLongOpenHashMap(DoubleHashFunction keyhash,
411: int capacity, double loadFactor) {
412: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
413: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
414: }
415:
416: /**
417: * Creates a new hash map with a specified capacity,
418: * load factor, and relative growth factor.
419: *
420: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
421: * This strategy is good for avoiding many capacity increases, but
422: * the amount of wasted memory is approximately the size of the map.
423: *
424: * @param keyhash
425: * the hash function to use when hashing keys.
426: *
427: * @param capacity
428: * the initial capacity of the map.
429: *
430: * @param loadFactor
431: * the load factor of the map.
432: *
433: * @param growthFactor
434: * the relative amount with which to increase the
435: * the capacity when a capacity increase is needed.
436: *
437: * @throws IllegalArgumentException
438: * if <tt>capacity</tt> is negative;
439: * if <tt>loadFactor</tt> is not positive;
440: * if <tt>growthFactor</tt> is not positive.
441: *
442: * @throws NullPointerException
443: * if <tt>keyhash</tt> is <tt>null</tt>.
444: */
445: public DoubleKeyLongOpenHashMap(DoubleHashFunction keyhash,
446: int capacity, double loadFactor, double growthFactor) {
447: this (keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor,
448: DEFAULT_GROWTH_CHUNK, loadFactor);
449: }
450:
451: /**
452: * Creates a new hash map with a specified capacity,
453: * load factor, and absolute growth factor.
454: *
455: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
456: * This strategy is good for avoiding wasting memory. However, an
457: * overhead is potentially introduced by frequent capacity increases.
458: *
459: * @param keyhash
460: * the hash function to use when hashing keys.
461: *
462: * @param capacity
463: * the initial capacity of the map.
464: *
465: * @param loadFactor
466: * the load factor of the map.
467: *
468: * @param growthChunk
469: * the absolute amount with which to increase the
470: * the capacity when a capacity increase is needed.
471: *
472: * @throws IllegalArgumentException
473: * if <tt>capacity</tt> is negative;
474: * if <tt>loadFactor</tt> is not positive;
475: * if <tt>growthChunk</tt> is not positive.
476: *
477: * @throws NullPointerException
478: * if <tt>keyhash</tt> is <tt>null</tt>.
479: */
480: public DoubleKeyLongOpenHashMap(DoubleHashFunction keyhash,
481: int capacity, double loadFactor, int growthChunk) {
482: this (keyhash, capacity, GROWTH_POLICY_ABSOLUTE,
483: DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
484: }
485:
486: // ---------------------------------------------------------------
487: // Hash table management
488: // ---------------------------------------------------------------
489:
490: private void ensureCapacity(int elements) {
491: if (elements >= expandAt) {
492: int newcapacity;
493: if (growthPolicy == GROWTH_POLICY_RELATIVE)
494: newcapacity = (int) (keys.length * (1.0 + growthFactor));
495: else
496: newcapacity = keys.length + growthChunk;
497: if (newcapacity * loadFactor < elements)
498: newcapacity = (int) Math
499: .round(((double) elements / loadFactor));
500: newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
501: expandAt = (int) Math.round(loadFactor * newcapacity);
502:
503: double[] newkeys = new double[newcapacity];
504: long[] newvalues = new long[newcapacity];
505: byte[] newstates = new byte[newcapacity];
506:
507: used = 0;
508: // re-hash
509: for (int i = 0; i < keys.length; i++) {
510: if (states[i] == OCCUPIED) {
511: used++;
512: double k = keys[i];
513: long v = values[i];
514: // first hash
515: int h = Math.abs(keyhash.hash(k));
516: int n = h % newcapacity;
517: if (newstates[n] == OCCUPIED) {
518: // second hash
519: int c = 1 + (h % (newcapacity - 2));
520: for (;;) {
521: n -= c;
522: if (n < 0)
523: n += newcapacity;
524: if (newstates[n] == EMPTY)
525: break;
526: }
527: }
528: newstates[n] = OCCUPIED;
529: newvalues[n] = v;
530: newkeys[n] = k;
531: }
532: }
533:
534: keys = newkeys;
535: values = newvalues;
536: states = newstates;
537: }
538: }
539:
540: // ---------------------------------------------------------------
541: // Operations not supported by abstract implementation
542: // ---------------------------------------------------------------
543:
544: public DoubleSet keySet() {
545: if (ckeys == null)
546: ckeys = new KeySet();
547: return ckeys;
548: }
549:
550: public long lget() {
551: if (!hasLastValue)
552: Exceptions.noLastElement();
553: return lastValue;
554: }
555:
556: public long put(double key, long value) {
557: long result;
558:
559: // first hash
560: int h = Math.abs(keyhash.hash(key));
561: int i = h % keys.length;
562: if (states[i] == OCCUPIED) {
563: if (keys[i] == key) {
564: long oldValue = values[i];
565: values[i] = value;
566: return oldValue;
567: }
568: // second hash
569: int c = 1 + (h % (keys.length - 2));
570: for (;;) {
571: i -= c;
572: if (i < 0)
573: i += keys.length;
574: // Empty entries are not re-used
575: if (states[i] == EMPTY || states[i] == REMOVED)
576: break;
577: if (states[i] == OCCUPIED && keys[i] == key) {
578: long oldValue = values[i];
579: values[i] = value;
580: return oldValue;
581: }
582: }
583: }
584: if (states[i] == EMPTY)
585: used++;
586: states[i] = OCCUPIED;
587: keys[i] = key;
588: values[i] = value;
589: size++;
590: ensureCapacity(used);
591: return MapDefaults.defaultLong();
592: }
593:
594: public LongCollection values() {
595: if (cvalues == null)
596: cvalues = new ValueCollection();
597: return cvalues;
598: }
599:
600: /**
601: * Returns a clone of this hash map.
602: *
603: * @return a clone of this hash map.
604: *
605: * @since 1.1
606: */
607: public Object clone() {
608: try {
609: DoubleKeyLongOpenHashMap c = (DoubleKeyLongOpenHashMap) super
610: .clone();
611: c.keys = new double[keys.length];
612: System.arraycopy(keys, 0, c.keys, 0, keys.length);
613: c.values = new long[values.length];
614: System.arraycopy(values, 0, c.values, 0, values.length);
615: c.states = new byte[states.length];
616: System.arraycopy(states, 0, c.states, 0, states.length);
617: // The views should not refer to this map's views
618: c.cvalues = null;
619: c.ckeys = null;
620: return c;
621: } catch (CloneNotSupportedException e) {
622: Exceptions.cloning();
623: return null;
624: }
625: }
626:
627: public DoubleKeyLongMapIterator entries() {
628: return new DoubleKeyLongMapIterator() {
629: int nextEntry = nextEntry(0);
630: int lastEntry = -1;
631:
632: int nextEntry(int index) {
633: while (index < keys.length && states[index] != OCCUPIED)
634: index++;
635: return index;
636: }
637:
638: public boolean hasNext() {
639: return nextEntry < keys.length;
640: }
641:
642: public void next() {
643: if (!hasNext())
644: Exceptions.endOfIterator();
645: lastEntry = nextEntry;
646: nextEntry = nextEntry(nextEntry + 1);
647: }
648:
649: public void remove() {
650: if (lastEntry == -1)
651: Exceptions.noElementToRemove();
652: states[lastEntry] = REMOVED;
653: size--;
654: lastEntry = -1;
655: }
656:
657: public double getKey() {
658: if (lastEntry == -1)
659: Exceptions.noElementToGet();
660: return keys[lastEntry];
661: }
662:
663: public long getValue() {
664: if (lastEntry == -1)
665: Exceptions.noElementToGet();
666: return values[lastEntry];
667: }
668: };
669: }
670:
671: private class KeySet extends AbstractDoubleSet {
672:
673: public void clear() {
674: DoubleKeyLongOpenHashMap.this .clear();
675: }
676:
677: public boolean contains(double v) {
678: return containsKey(v);
679: }
680:
681: public DoubleIterator iterator() {
682: return new DoubleIterator() {
683: int nextEntry = nextEntry(0);
684: int lastEntry = -1;
685:
686: int nextEntry(int index) {
687: while (index < keys.length
688: && states[index] != OCCUPIED)
689: index++;
690: return index;
691: }
692:
693: public boolean hasNext() {
694: return nextEntry < keys.length;
695: }
696:
697: public double next() {
698: if (!hasNext())
699: Exceptions.endOfIterator();
700: lastEntry = nextEntry;
701: nextEntry = nextEntry(nextEntry + 1);
702: return keys[lastEntry];
703: }
704:
705: public void remove() {
706: if (lastEntry == -1)
707: Exceptions.noElementToRemove();
708: states[lastEntry] = REMOVED;
709: size--;
710: lastEntry = -1;
711: }
712: };
713: }
714:
715: public boolean remove(double v) {
716: boolean result = containsKey(v);
717: if (result)
718: DoubleKeyLongOpenHashMap.this .remove(v);
719: return result;
720: }
721:
722: public int size() {
723: return size;
724: }
725:
726: }
727:
728: private class ValueCollection extends AbstractLongCollection {
729:
730: public void clear() {
731: DoubleKeyLongOpenHashMap.this .clear();
732: }
733:
734: public boolean contains(long v) {
735: return containsValue(v);
736: }
737:
738: public LongIterator iterator() {
739: return new LongIterator() {
740: int nextEntry = nextEntry(0);
741: int lastEntry = -1;
742:
743: int nextEntry(int index) {
744: while (index < keys.length
745: && states[index] != OCCUPIED)
746: index++;
747: return index;
748: }
749:
750: public boolean hasNext() {
751: return nextEntry < keys.length;
752: }
753:
754: public long next() {
755: if (!hasNext())
756: Exceptions.endOfIterator();
757: lastEntry = nextEntry;
758: nextEntry = nextEntry(nextEntry + 1);
759: return values[lastEntry];
760: }
761:
762: public void remove() {
763: if (lastEntry == -1)
764: Exceptions.noElementToRemove();
765: states[lastEntry] = REMOVED;
766: size--;
767: lastEntry = -1;
768: }
769: };
770: }
771:
772: public int size() {
773: return size;
774: }
775:
776: }
777:
778: // ---------------------------------------------------------------
779: // Operations overwritten for efficiency
780: // ---------------------------------------------------------------
781:
782: public void clear() {
783: java.util.Arrays.fill(states, EMPTY);
784: size = 0;
785: used = 0;
786: }
787:
788: public boolean containsKey(double key) {
789: int h = Math.abs(keyhash.hash(key));
790: int i = h % keys.length;
791: if (states[i] != EMPTY) {
792: if (states[i] == OCCUPIED && keys[i] == key) {
793: hasLastValue = true;
794: lastValue = values[i];
795: return true;
796: }
797: // second hash
798:
799: int c = 1 + (h % (keys.length - 2));
800: for (;;) {
801: i -= c;
802: if (i < 0)
803: i += keys.length;
804: if (states[i] == EMPTY) {
805: hasLastValue = false;
806: return false;
807: }
808: if (states[i] == OCCUPIED && keys[i] == key) {
809: hasLastValue = true;
810: lastValue = values[i];
811: return true;
812: }
813: }
814: }
815: hasLastValue = false;
816: return false;
817: }
818:
819: public boolean containsValue(long value) {
820: for (int i = 0; i < states.length; i++)
821: if (states[i] == OCCUPIED && values[i] == value)
822: return true;
823: return false;
824: }
825:
826: public long get(double key) {
827: int h = Math.abs(keyhash.hash(key));
828: int i = h % keys.length;
829: if (states[i] != EMPTY) {
830: if (states[i] == OCCUPIED && keys[i] == key)
831: return values[i];
832: // second hash
833:
834: int c = 1 + (h % (keys.length - 2));
835: for (;;) {
836: i -= c;
837: if (i < 0)
838: i += keys.length;
839: if (states[i] == EMPTY)
840: return MapDefaults.defaultLong();
841: if (states[i] == OCCUPIED && keys[i] == key)
842: return values[i];
843: }
844: }
845: return MapDefaults.defaultLong();
846: }
847:
848: public boolean isEmpty() {
849: return size == 0;
850: }
851:
852: public long remove(double key) {
853: int h = Math.abs(keyhash.hash(key));
854: int i = h % keys.length;
855: if (states[i] != EMPTY) {
856: if (states[i] == OCCUPIED && keys[i] == key) {
857: long oldValue = values[i];
858: states[i] = REMOVED;
859: size--;
860: return oldValue;
861: }
862: // second hash
863: int c = 1 + (h % (keys.length - 2));
864: for (;;) {
865: i -= c;
866: if (i < 0)
867: i += keys.length;
868: if (states[i] == EMPTY) {
869: return MapDefaults.defaultLong();
870: }
871: if (states[i] == OCCUPIED && keys[i] == key) {
872: long oldValue = values[i];
873: states[i] = REMOVED;
874: size--;
875: return oldValue;
876: }
877: }
878: }
879: return MapDefaults.defaultLong();
880: }
881:
882: public int size() {
883: return size;
884: }
885:
886: public long tget(double key) {
887: int h = Math.abs(keyhash.hash(key));
888: int i = h % keys.length;
889: if (states[i] != EMPTY) {
890: if (states[i] == OCCUPIED && keys[i] == key)
891: return values[i];
892: // second hash
893:
894: int c = 1 + (h % (keys.length - 2));
895: for (;;) {
896: i -= c;
897: if (i < 0)
898: i += keys.length;
899: if (states[i] == EMPTY)
900: Exceptions.noSuchMapping(String.valueOf(key));
901: if (states[i] == OCCUPIED && keys[i] == key)
902: return values[i];
903: }
904: }
905: Exceptions.noSuchMapping(String.valueOf(key));
906: throw new RuntimeException();
907: }
908:
909: // ---------------------------------------------------------------
910: // Serialization
911: // ---------------------------------------------------------------
912:
913: /**
914: * @serialData Default fields; the capacity of the
915: * map (<tt>int</tt>); the maps's entries
916: * (<tt>double</tt>, <tt>long</tt>).
917: *
918: * @since 1.1
919: */
920: private void writeObject(ObjectOutputStream s) throws IOException {
921: s.defaultWriteObject();
922: s.writeInt(keys.length);
923: DoubleKeyLongMapIterator i = entries();
924: while (i.hasNext()) {
925: i.next();
926: s.writeDouble(i.getKey());
927: s.writeLong(i.getValue());
928: }
929: }
930:
931: /**
932: * @since 1.1
933: */
934: private void readObject(ObjectInputStream s) throws IOException,
935: ClassNotFoundException {
936: s.defaultReadObject();
937: keys = new double[s.readInt()];
938: states = new byte[keys.length];
939: values = new long[keys.length];
940: used = size;
941:
942: for (int n = 0; n < size; n++) {
943: double key = s.readDouble();
944: long value = s.readLong();
945:
946: // first hash
947: int h = Math.abs(keyhash.hash(key));
948: int i = h % keys.length;
949: if (states[i] != EMPTY) {
950: // second hash
951: int c = 1 + (h % (keys.length - 2));
952: for (;;) {
953: i -= c;
954: if (i < 0)
955: i += keys.length;
956: if (states[i] == EMPTY)
957: break;
958: }
959: }
960: states[i] = OCCUPIED;
961: keys[i] = key;
962: values[i] = value;
963: }
964: }
965:
966: }
|