001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 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.BooleanCollection;
022: import bak.pcj.AbstractBooleanCollection;
023: import bak.pcj.BooleanIterator;
024: import bak.pcj.hash.DefaultBooleanHashFunction;
025: import bak.pcj.util.Exceptions;
026: import java.util.Set;
027: import java.util.AbstractSet;
028: import java.util.Iterator;
029:
030: import java.io.Serializable;
031: import java.io.IOException;
032: import java.io.ObjectInputStream;
033: import java.io.ObjectOutputStream;
034:
035: /**
036: * This class represents chained hash table based maps from
037: * object values to boolean values.
038: *
039: * @see ObjectKeyBooleanOpenHashMap
040: * @see java.util.Map
041: *
042: * @author Søren Bak
043: * @version 1.1 2003/8/3
044: * @since 1.1
045: */
046: public class ObjectKeyBooleanChainedHashMap extends
047: AbstractObjectKeyBooleanMap implements ObjectKeyBooleanMap,
048: Cloneable, Serializable {
049:
050: /** Constant indicating relative growth policy. */
051: private static final int GROWTH_POLICY_RELATIVE = 0;
052:
053: /** Constant indicating absolute growth policy. */
054: private static final int GROWTH_POLICY_ABSOLUTE = 1;
055:
056: /**
057: * The default growth policy of this map.
058: * @see #GROWTH_POLICY_RELATIVE
059: * @see #GROWTH_POLICY_ABSOLUTE
060: */
061: private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
062:
063: /** The default factor with which to increase the capacity of this map. */
064: public static final double DEFAULT_GROWTH_FACTOR = 1.0;
065:
066: /** The default chunk size with which to increase the capacity of this map. */
067: public static final int DEFAULT_GROWTH_CHUNK = 10;
068:
069: /** The default capacity of this map. */
070: public static final int DEFAULT_CAPACITY = 11;
071:
072: /** The default load factor of this map. */
073: public static final double DEFAULT_LOAD_FACTOR = 0.75;
074:
075: /**
076: * The size of this map.
077: * @serial
078: */
079: private int size;
080:
081: /** The hash table backing up this map. Contains linked entry values. */
082: private transient Entry[] data;
083:
084: /**
085: * The growth policy of this map. (0 is relative growth, 1 is absolute growth).
086: * @serial
087: */
088: private int growthPolicy;
089:
090: /**
091: * The growth factor of this map, if the growth policy is
092: * relative.
093: * @serial
094: */
095: private double growthFactor;
096:
097: /**
098: * The growth chunk size of this map, if the growth policy is
099: * absolute.
100: * @serial
101: */
102: private int growthChunk;
103:
104: /**
105: * The load factor of this map.
106: * @serial
107: */
108: private double loadFactor;
109:
110: /**
111: * The next size at which to expand the data[].
112: * @serial
113: */
114: private int expandAt;
115:
116: /** A set view of the keys of this map. */
117: private transient Set keys;
118:
119: /** A collection view of the values of this map. */
120: private transient BooleanCollection values;
121:
122: /** Indicates whether last call to containsKey() had a corresponding value. */
123: private transient boolean hasLastValue;
124:
125: /** Value corresponding to to the key of the last call of containsKey(). */
126: private transient boolean lastValue;
127:
128: private ObjectKeyBooleanChainedHashMap(int capacity,
129: int growthPolicy, double growthFactor, int growthChunk,
130: double loadFactor) {
131: if (capacity < 0)
132: Exceptions.negativeArgument("capacity", String
133: .valueOf(capacity));
134: if (growthFactor < 0.0)
135: Exceptions.negativeArgument("growthFactor", String
136: .valueOf(growthFactor));
137: if (growthChunk < 0)
138: Exceptions.negativeArgument("growthChunk", String
139: .valueOf(growthChunk));
140: if (loadFactor <= 0.0)
141: Exceptions.negativeOrZeroArgument("loadFactor", String
142: .valueOf(loadFactor));
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: hasLastValue = false;
151: }
152:
153: /**
154: * Creates a new hash map with capacity 11, a relative
155: * growth factor of 1.0, and a load factor of 75%.
156: */
157: public ObjectKeyBooleanChainedHashMap() {
158: this (DEFAULT_CAPACITY);
159: }
160:
161: /**
162: * Creates a new hash map with the same mappings as a specified map.
163: *
164: * @param map
165: * the map whose mappings to put into the new map.
166: *
167: * @throws NullPointerException
168: * if <tt>map</tt> is <tt>null</tt>.
169: */
170: public ObjectKeyBooleanChainedHashMap(ObjectKeyBooleanMap map) {
171: this ();
172: putAll(map);
173: }
174:
175: /**
176: * Creates a new hash map with a specified capacity, a relative
177: * growth factor of 1.0, and a load factor of 75%.
178: *
179: * @param capacity
180: * the initial capacity of the map.
181: *
182: * @throws IllegalArgumentException
183: * if <tt>capacity</tt> is negative.
184: */
185: public ObjectKeyBooleanChainedHashMap(int capacity) {
186: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
187: DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
188: }
189:
190: /**
191: * Creates a new hash map with a capacity of 11, a relative
192: * growth factor of 1.0, and a specified load factor.
193: *
194: * @param loadFactor
195: * the load factor of the map.
196: *
197: * @throws IllegalArgumentException
198: * if <tt>capacity</tt> is negative.
199: */
200: public ObjectKeyBooleanChainedHashMap(double loadFactor) {
201: this (DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
202: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
203: }
204:
205: /**
206: * Creates a new hash map with a specified capacity and
207: * load factor, and a relative growth factor of 1.0.
208: *
209: * @param capacity
210: * the initial capacity of the map.
211: *
212: * @param loadFactor
213: * the load factor of the map.
214: *
215: * @throws IllegalArgumentException
216: * if <tt>capacity</tt> is negative;
217: * if <tt>loadFactor</tt> is not positive.
218: */
219: public ObjectKeyBooleanChainedHashMap(int capacity,
220: double loadFactor) {
221: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
222: DEFAULT_GROWTH_CHUNK, loadFactor);
223: }
224:
225: /**
226: * Creates a new hash map with a specified capacity,
227: * load factor, and relative growth factor.
228: *
229: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
230: * This strategy is good for avoiding many capacity increases, but
231: * the amount of wasted memory is approximately the size of the map.
232: *
233: * @param capacity
234: * the initial capacity of the map.
235: *
236: * @param loadFactor
237: * the load factor of the map.
238: *
239: * @param growthFactor
240: * the relative amount with which to increase the
241: * the capacity when a capacity increase is needed.
242: *
243: * @throws IllegalArgumentException
244: * if <tt>capacity</tt> is negative;
245: * if <tt>loadFactor</tt> is not positive;
246: * if <tt>growthFactor</tt> is not positive.
247: */
248: public ObjectKeyBooleanChainedHashMap(int capacity,
249: double loadFactor, double growthFactor) {
250: this (capacity, GROWTH_POLICY_RELATIVE, growthFactor,
251: DEFAULT_GROWTH_CHUNK, loadFactor);
252: }
253:
254: /**
255: * Creates a new hash map with a specified capacity,
256: * load factor, and absolute growth factor.
257: *
258: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
259: * This strategy is good for avoiding wasting memory. However, an
260: * overhead is potentially introduced by frequent capacity increases.
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 growthChunk
269: * the absolute 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>growthChunk</tt> is not positive;
276: */
277: public ObjectKeyBooleanChainedHashMap(int capacity,
278: double loadFactor, int growthChunk) {
279: this (capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR,
280: growthChunk, loadFactor);
281: }
282:
283: // ---------------------------------------------------------------
284: // Hash table management
285: // ---------------------------------------------------------------
286:
287: private static int hash(Object key) {
288: return key == null ? 0 : key.hashCode();
289: }
290:
291: private static boolean keyeq(Object k1, Object k2) {
292: return k1 == null ? k2 == null : k1.equals(k2);
293: }
294:
295: private void ensureCapacity(int elements) {
296: if (elements >= expandAt) {
297: int newcapacity;
298: if (growthPolicy == GROWTH_POLICY_RELATIVE)
299: newcapacity = (int) (data.length * (1.0 + growthFactor));
300: else
301: newcapacity = data.length + growthChunk;
302: if (newcapacity * loadFactor < elements)
303: newcapacity = (int) Math
304: .round(((double) elements / loadFactor));
305: newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
306: expandAt = (int) Math.round(loadFactor * newcapacity);
307:
308: Entry[] newdata = new Entry[newcapacity];
309:
310: // re-hash
311: for (int i = 0; i < data.length; i++) {
312: Entry e = data[i];
313: while (e != null) {
314: int index = Math.abs(hash(e.key)) % newdata.length;
315: Entry next = e.next;
316: e.next = newdata[index];
317: newdata[index] = e;
318: e = next;
319: }
320: }
321:
322: data = newdata;
323: }
324: }
325:
326: private Entry addList(Entry list, Entry v) {
327: v.next = list;
328: return v;
329: }
330:
331: private Entry removeList(Entry list, Entry e) {
332: if (list == e) {
333: list = e.next;
334: e.next = null;
335: return list;
336: }
337: Entry listStart = list;
338: while (list.next != e)
339: list = list.next;
340: list.next = e.next;
341: e.next = null;
342: return listStart;
343: }
344:
345: private Entry searchList(Entry list, Object key) {
346: while (list != null) {
347: if (keyeq(list.key, key))
348: return list;
349: list = list.next;
350: }
351: return null;
352: }
353:
354: private Entry getEntry(Object key) {
355: int index = Math.abs(hash(key)) % data.length;
356: return searchList(data[index], key);
357: }
358:
359: // ---------------------------------------------------------------
360: // Operations not supported by abstract implementation
361: // ---------------------------------------------------------------
362:
363: public Set keySet() {
364: if (keys == null)
365: keys = new KeySet();
366: return keys;
367: }
368:
369: public boolean lget() {
370: if (!hasLastValue)
371: Exceptions.noLastElement();
372: return lastValue;
373: }
374:
375: public boolean put(Object key, boolean value) {
376: boolean result;
377: int index = Math.abs(hash(key)) % data.length;
378: Entry e = searchList(data[index], key);
379: if (e == null) {
380: result = MapDefaults.defaultBoolean();
381: e = new Entry(key, value);
382: e.next = data[index];
383: data[index] = e;
384: // Capacity is increased after insertion in order to
385: // avoid recalculation of index
386: ensureCapacity(size + 1);
387: size++;
388: } else {
389: result = e.value;
390: e.value = value;
391: }
392: return result;
393: }
394:
395: public BooleanCollection values() {
396: if (values == null)
397: values = new ValueCollection();
398: return values;
399: }
400:
401: /**
402: * Returns a clone of this hash map.
403: *
404: * @return a clone of this hash map.
405: *
406: * @since 1.1
407: */
408: public Object clone() {
409: try {
410: ObjectKeyBooleanChainedHashMap c = (ObjectKeyBooleanChainedHashMap) super
411: .clone();
412: c.data = new Entry[data.length];
413: for (int i = 0; i < data.length; i++)
414: c.data[i] = cloneList(data[i]);
415: // The views should not refer to this map's views
416: c.values = null;
417: c.keys = null;
418: return c;
419: } catch (CloneNotSupportedException e) {
420: Exceptions.cloning();
421: return null;
422: }
423: }
424:
425: private Entry cloneList(Entry e) {
426: if (e == null)
427: return null;
428: Entry ne = new Entry(e.getKey(), e.getValue());
429: ne.next = cloneList(e.next);
430: return ne;
431: }
432:
433: private static class Entry {
434: Object key;
435: boolean value;
436: Entry next;
437:
438: Entry(Object key, boolean value) {
439: this .key = key;
440: this .value = value;
441: }
442:
443: public Object getKey() {
444: return key;
445: }
446:
447: public boolean getValue() {
448: return value;
449: }
450:
451: public boolean equals(Object obj) {
452: if (!(obj instanceof Entry))
453: return false;
454: Entry e = (Entry) obj;
455: return keyeq(e.getKey(), key) && e.getValue() == value;
456: }
457: }
458:
459: public ObjectKeyBooleanMapIterator entries() {
460: return new ObjectKeyBooleanMapIterator() {
461: Entry currEntry = null;
462: int nextList = nextList(0);
463: Entry nextEntry = nextList == -1 ? null : data[nextList];
464:
465: int nextList(int index) {
466: while (index < data.length && data[index] == null)
467: index++;
468: return index < data.length ? index : -1;
469: }
470:
471: public boolean hasNext() {
472: return nextEntry != null;
473: }
474:
475: public void next() {
476: if (nextEntry == null)
477: Exceptions.endOfIterator();
478: currEntry = nextEntry;
479:
480: // Find next
481: nextEntry = nextEntry.next;
482: if (nextEntry == null) {
483: nextList = nextList(nextList + 1);
484: if (nextList != -1)
485: nextEntry = data[nextList];
486: }
487: }
488:
489: public Object getKey() {
490: if (currEntry == null)
491: Exceptions.noElementToGet();
492: return currEntry.getKey();
493: }
494:
495: public boolean getValue() {
496: if (currEntry == null)
497: Exceptions.noElementToGet();
498: return currEntry.getValue();
499: }
500:
501: public void remove() {
502: if (currEntry == null)
503: Exceptions.noElementToRemove();
504: ObjectKeyBooleanChainedHashMap.this .remove(currEntry
505: .getKey());
506: currEntry = null;
507: }
508:
509: };
510: }
511:
512: private class KeySet extends AbstractSet {
513:
514: public void clear() {
515: ObjectKeyBooleanChainedHashMap.this .clear();
516: }
517:
518: public boolean contains(Object v) {
519: return getEntry(v) != null;
520: }
521:
522: public Iterator iterator() {
523: return new Iterator() {
524: Entry currEntry = null;
525: int nextList = nextList(0);
526: Entry nextEntry = nextList == -1 ? null
527: : data[nextList];
528:
529: int nextList(int index) {
530: while (index < data.length && data[index] == null)
531: index++;
532: return index < data.length ? index : -1;
533: }
534:
535: public boolean hasNext() {
536: return nextEntry != null;
537: }
538:
539: public Object next() {
540: if (nextEntry == null)
541: Exceptions.endOfIterator();
542: currEntry = nextEntry;
543:
544: // Find next
545: nextEntry = nextEntry.next;
546: if (nextEntry == null) {
547: nextList = nextList(nextList + 1);
548: if (nextList != -1)
549: nextEntry = data[nextList];
550: }
551: return currEntry.key;
552: }
553:
554: public void remove() {
555: if (currEntry == null)
556: Exceptions.noElementToRemove();
557: ObjectKeyBooleanChainedHashMap.this
558: .remove(currEntry.getKey());
559: currEntry = null;
560: }
561: };
562: }
563:
564: public boolean remove(Object v) {
565: boolean result = containsKey(v);
566: if (result)
567: ObjectKeyBooleanChainedHashMap.this .remove(v);
568: return result;
569: }
570:
571: public int size() {
572: return size;
573: }
574:
575: }
576:
577: private class ValueCollection extends AbstractBooleanCollection {
578:
579: public void clear() {
580: ObjectKeyBooleanChainedHashMap.this .clear();
581: }
582:
583: public boolean contains(boolean v) {
584: return containsValue(v);
585: }
586:
587: public BooleanIterator iterator() {
588: return new BooleanIterator() {
589: Entry currEntry = null;
590: int nextList = nextList(0);
591: Entry nextEntry = nextList == -1 ? null
592: : data[nextList];
593:
594: int nextList(int index) {
595: while (index < data.length && data[index] == null)
596: index++;
597: return index < data.length ? index : -1;
598: }
599:
600: public boolean hasNext() {
601: return nextEntry != null;
602: }
603:
604: public boolean next() {
605: if (nextEntry == null)
606: Exceptions.endOfIterator();
607: currEntry = nextEntry;
608:
609: // Find next
610: nextEntry = nextEntry.next;
611: if (nextEntry == null) {
612: nextList = nextList(nextList + 1);
613: if (nextList != -1)
614: nextEntry = data[nextList];
615: }
616: return currEntry.value;
617: }
618:
619: public void remove() {
620: if (currEntry == null)
621: Exceptions.noElementToRemove();
622: ObjectKeyBooleanChainedHashMap.this
623: .remove(currEntry.getKey());
624: currEntry = null;
625: }
626: };
627: }
628:
629: public int size() {
630: return size;
631: }
632:
633: }
634:
635: // ---------------------------------------------------------------
636: // Operations overwritten for efficiency
637: // ---------------------------------------------------------------
638:
639: public void clear() {
640: java.util.Arrays.fill(data, null);
641: size = 0;
642: }
643:
644: public boolean containsKey(Object key) {
645: Entry e = getEntry(key);
646: if (e == null)
647: hasLastValue = false;
648: else {
649: hasLastValue = true;
650: lastValue = e.value;
651: }
652: return hasLastValue;
653: }
654:
655: public boolean containsValue(boolean value) {
656: for (int i = 0; i < data.length; i++) {
657: Entry e = data[i];
658: while (e != null) {
659: if (e.value == value)
660: return true;
661: e = e.next;
662: }
663: }
664: return false;
665: }
666:
667: public boolean get(Object key) {
668: int index = Math.abs(hash(key)) % data.length;
669: Entry e = searchList(data[index], key);
670: return e != null ? e.value : MapDefaults.defaultBoolean();
671: }
672:
673: public boolean isEmpty() {
674: return size == 0;
675: }
676:
677: public boolean remove(Object key) {
678: int index = Math.abs(hash(key)) % data.length;
679: Entry e = searchList(data[index], key);
680: boolean value;
681: if (e != null) {
682: // This can be improved to one iteration
683: data[index] = removeList(data[index], e);
684: value = e.value;
685: size--;
686: } else
687: value = MapDefaults.defaultBoolean();
688: return value;
689: }
690:
691: public int size() {
692: return size;
693: }
694:
695: public boolean tget(Object key) {
696: int index = Math.abs(hash(key)) % data.length;
697: Entry e = searchList(data[index], key);
698: if (e == null)
699: Exceptions.noSuchMapping(key);
700: return e.value;
701: }
702:
703: // ---------------------------------------------------------------
704: // Serialization
705: // ---------------------------------------------------------------
706:
707: /**
708: * @serialData Default fields; the capacity of the
709: * map (<tt>int</tt>); the maps's entries
710: * (<tt>Object</tt>, <tt>boolean</tt>).
711: */
712: private void writeObject(ObjectOutputStream s) throws IOException {
713: s.defaultWriteObject();
714: s.writeInt(data.length);
715: ObjectKeyBooleanMapIterator i = entries();
716: while (i.hasNext()) {
717: i.next();
718: s.writeObject(i.getKey());
719: s.writeBoolean(i.getValue());
720: }
721: }
722:
723: private void readObject(ObjectInputStream s) throws IOException,
724: ClassNotFoundException {
725: s.defaultReadObject();
726: data = new Entry[s.readInt()];
727: for (int i = 0; i < size; i++) {
728: Object key = s.readObject();
729: boolean value = s.readBoolean();
730: int index = Math.abs(hash(key)) % data.length;
731: Entry e = new Entry(key, value);
732: e.next = data[index];
733: data[index] = e;
734: }
735: }
736:
737: }
|