001: ///////////////////////////////////////////////////////////////////////////////
002: // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
003: //
004: // This library is free software; you can redistribute it and/or
005: // modify it under the terms of the GNU Lesser General Public
006: // License as published by the Free Software Foundation; either
007: // version 2.1 of the License, or (at your option) any later version.
008: //
009: // This library is distributed in the hope that it will be useful,
010: // but WITHOUT ANY WARRANTY; without even the implied warranty of
011: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: // GNU General Public License for more details.
013: //
014: // You should have received a copy of the GNU Lesser General Public
015: // License along with this program; if not, write to the Free Software
016: // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017: ///////////////////////////////////////////////////////////////////////////////
018:
019: package gnu.trove;
020:
021: import java.io.*;
022: import java.util.*;
023:
024: /**
025: * An implementation of the Map interface which uses an open addressed
026: * hash table to store its contents.
027: *
028: * Created: Sun Nov 4 08:52:45 2001
029: *
030: * @author Eric D. Friedman
031: * @version $Id: THashMap.java,v 1.26 2007/06/29 20:03:10 robeden Exp $
032: */
033: public class THashMap<K, V> extends TObjectHash<K> implements
034: Map<K, V>, Externalizable {
035: static final long serialVersionUID = 1L;
036:
037: /** the values of the map */
038: protected transient V[] _values;
039:
040: /**
041: * Creates a new <code>THashMap</code> instance with the default
042: * capacity and load factor.
043: */
044: public THashMap() {
045: super ();
046: }
047:
048: /**
049: * Creates a new <code>THashMap</code> instance with the default
050: * capacity and load factor.
051: * @param strategy used to compute hash codes and to compare objects.
052: */
053: public THashMap(TObjectHashingStrategy<K> strategy) {
054: super (strategy);
055: }
056:
057: /**
058: * Creates a new <code>THashMap</code> instance with a prime
059: * capacity equal to or greater than <tt>initialCapacity</tt> and
060: * with the default load factor.
061: *
062: * @param initialCapacity an <code>int</code> value
063: */
064: public THashMap(int initialCapacity) {
065: super (initialCapacity);
066: }
067:
068: /**
069: * Creates a new <code>THashMap</code> instance with a prime
070: * capacity equal to or greater than <tt>initialCapacity</tt> and
071: * with the default load factor.
072: *
073: * @param initialCapacity an <code>int</code> value
074: * @param strategy used to compute hash codes and to compare objects.
075: */
076: public THashMap(int initialCapacity,
077: TObjectHashingStrategy<K> strategy) {
078: super (initialCapacity, strategy);
079: }
080:
081: /**
082: * Creates a new <code>THashMap</code> instance with a prime
083: * capacity equal to or greater than <tt>initialCapacity</tt> and
084: * with the specified load factor.
085: *
086: * @param initialCapacity an <code>int</code> value
087: * @param loadFactor a <code>float</code> value
088: */
089: public THashMap(int initialCapacity, float loadFactor) {
090: super (initialCapacity, loadFactor);
091: }
092:
093: /**
094: * Creates a new <code>THashMap</code> instance with a prime
095: * capacity equal to or greater than <tt>initialCapacity</tt> and
096: * with the specified load factor.
097: *
098: * @param initialCapacity an <code>int</code> value
099: * @param loadFactor a <code>float</code> value
100: * @param strategy used to compute hash codes and to compare objects.
101: */
102: public THashMap(int initialCapacity, float loadFactor,
103: TObjectHashingStrategy<K> strategy) {
104: super (initialCapacity, loadFactor, strategy);
105: }
106:
107: /**
108: * Creates a new <code>THashMap</code> instance which contains the
109: * key/value pairs in <tt>map</tt>.
110: *
111: * @param map a <code>Map</code> value
112: */
113: public THashMap(Map<K, V> map) {
114: this (map.size());
115: putAll(map);
116: }
117:
118: /**
119: * Creates a new <code>THashMap</code> instance which contains the
120: * key/value pairs in <tt>map</tt>.
121: *
122: * @param map a <code>Map</code> value
123: * @param strategy used to compute hash codes and to compare objects.
124: */
125: public THashMap(Map<K, V> map, TObjectHashingStrategy<K> strategy) {
126: this (map.size(), strategy);
127: putAll(map);
128: }
129:
130: /**
131: * @return a shallow clone of this collection
132: */
133: public THashMap<K, V> clone() {
134: THashMap<K, V> m = (THashMap<K, V>) super .clone();
135: m._values = this ._values.clone();
136: return m;
137: }
138:
139: /**
140: * initialize the value array of the map.
141: *
142: * @param initialCapacity an <code>int</code> value
143: * @return an <code>int</code> value
144: */
145: protected int setUp(int initialCapacity) {
146: int capacity;
147:
148: capacity = super .setUp(initialCapacity);
149: _values = (V[]) new Object[capacity];
150: return capacity;
151: }
152:
153: /**
154: * Inserts a key/value pair into the map.
155: *
156: * @param key an <code>Object</code> value
157: * @param value an <code>Object</code> value
158: * @return the previous value associated with <tt>key</tt>,
159: * or null if none was found.
160: */
161: public V put(K key, V value) {
162: V previous = null;
163: Object oldKey;
164: int index = insertionIndex(key);
165: boolean isNewMapping = true;
166: if (index < 0) {
167: index = -index - 1;
168: previous = _values[index];
169: isNewMapping = false;
170: }
171: oldKey = _set[index];
172: _set[index] = key;
173: _values[index] = value;
174: if (isNewMapping) {
175: postInsertHook(oldKey == FREE);
176: }
177:
178: return previous;
179: }
180:
181: /**
182: * Compares this map with another map for equality of their stored
183: * entries.
184: *
185: * @param other an <code>Object</code> value
186: * @return a <code>boolean</code> value
187: */
188: public boolean equals(Object other) {
189: if (!(other instanceof Map)) {
190: return false;
191: }
192: Map<K, V> that = (Map<K, V>) other;
193: if (that.size() != this .size()) {
194: return false;
195: }
196: return forEachEntry(new EqProcedure<K, V>(that));
197: }
198:
199: public int hashCode() {
200: HashProcedure p = new HashProcedure();
201: forEachEntry(p);
202: return p.getHashCode();
203: }
204:
205: public String toString() {
206: final StringBuffer buf = new StringBuffer("{");
207: forEachEntry(new TObjectObjectProcedure() {
208: public boolean execute(Object key, Object value) {
209: buf.append(key);
210: buf.append("=");
211: buf.append(value);
212: buf.append(", ");
213: return true;
214: }
215: });
216: buf.append("}");
217: return buf.toString();
218: }
219:
220: private final class HashProcedure implements
221: TObjectObjectProcedure<K, V> {
222: private int h = 0;
223:
224: public int getHashCode() {
225: return h;
226: }
227:
228: public final boolean execute(K key, V value) {
229: h += _hashingStrategy.computeHashCode(key)
230: ^ (value == null ? 0 : value.hashCode());
231: return true;
232: }
233: }
234:
235: private static final class EqProcedure<K, V> implements
236: TObjectObjectProcedure<K, V> {
237: private final Map<K, V> _otherMap;
238:
239: EqProcedure(Map<K, V> otherMap) {
240: _otherMap = otherMap;
241: }
242:
243: public final boolean execute(K key, V value) {
244: // Check to make sure the key is there. This avoids problems that come up with
245: // null values. Since it is only caused in that cause, only do this when the
246: // value is null (to avoid extra work).
247: if (value == null && !_otherMap.containsKey(key))
248: return false;
249:
250: V oValue = _otherMap.get(key);
251: return oValue == value
252: || (oValue != null && oValue.equals(value));
253: }
254: }
255:
256: /**
257: * Executes <tt>procedure</tt> for each key in the map.
258: *
259: * @param procedure a <code>TObjectProcedure</code> value
260: * @return false if the loop over the keys terminated because
261: * the procedure returned false for some key.
262: */
263: public boolean forEachKey(TObjectProcedure<K> procedure) {
264: return forEach(procedure);
265: }
266:
267: /**
268: * Executes <tt>procedure</tt> for each value in the map.
269: *
270: * @param procedure a <code>TObjectProcedure</code> value
271: * @return false if the loop over the values terminated because
272: * the procedure returned false for some value.
273: */
274: public boolean forEachValue(TObjectProcedure<V> procedure) {
275: V[] values = _values;
276: Object[] set = _set;
277: for (int i = values.length; i-- > 0;) {
278: if (set[i] != FREE && set[i] != REMOVED
279: && !procedure.execute(values[i])) {
280: return false;
281: }
282: }
283: return true;
284: }
285:
286: /**
287: * Executes <tt>procedure</tt> for each key/value entry in the
288: * map.
289: *
290: * @param procedure a <code>TObjectObjectProcedure</code> value
291: * @return false if the loop over the entries terminated because
292: * the procedure returned false for some entry.
293: */
294: public boolean forEachEntry(TObjectObjectProcedure<K, V> procedure) {
295: Object[] keys = _set;
296: V[] values = _values;
297: for (int i = keys.length; i-- > 0;) {
298: if (keys[i] != FREE && keys[i] != REMOVED
299: && !procedure.execute((K) keys[i], values[i])) {
300: return false;
301: }
302: }
303: return true;
304: }
305:
306: /**
307: * Retains only those entries in the map for which the procedure
308: * returns a true value.
309: *
310: * @param procedure determines which entries to keep
311: * @return true if the map was modified.
312: */
313: public boolean retainEntries(TObjectObjectProcedure<K, V> procedure) {
314: boolean modified = false;
315: Object[] keys = _set;
316: V[] values = _values;
317:
318: // Temporarily disable compaction. This is a fix for bug #1738760
319: tempDisableAutoCompaction();
320: try {
321: for (int i = keys.length; i-- > 0;) {
322: if (keys[i] != FREE && keys[i] != REMOVED
323: && !procedure.execute((K) keys[i], values[i])) {
324: removeAt(i);
325: modified = true;
326: }
327: }
328: } finally {
329: reenableAutoCompaction(true);
330: }
331:
332: return modified;
333: }
334:
335: /**
336: * Transform the values in this map using <tt>function</tt>.
337: *
338: * @param function a <code>TObjectFunction</code> value
339: */
340: public void transformValues(TObjectFunction<V, V> function) {
341: V[] values = _values;
342: Object[] set = _set;
343: for (int i = values.length; i-- > 0;) {
344: if (set[i] != FREE && set[i] != REMOVED) {
345: values[i] = function.execute(values[i]);
346: }
347: }
348: }
349:
350: /**
351: * rehashes the map to the new capacity.
352: *
353: * @param newCapacity an <code>int</code> value
354: */
355: protected void rehash(int newCapacity) {
356: int oldCapacity = _set.length;
357: Object oldKeys[] = _set;
358: V oldVals[] = _values;
359:
360: _set = new Object[newCapacity];
361: Arrays.fill(_set, FREE);
362: _values = (V[]) new Object[newCapacity];
363:
364: for (int i = oldCapacity; i-- > 0;) {
365: if (oldKeys[i] != FREE && oldKeys[i] != REMOVED) {
366: Object o = oldKeys[i];
367: int index = insertionIndex((K) o);
368: if (index < 0) {
369: throwObjectContractViolation(_set[(-index - 1)], o);
370: }
371: _set[index] = o;
372: _values[index] = oldVals[i];
373: }
374: }
375: }
376:
377: /**
378: * retrieves the value for <tt>key</tt>
379: *
380: * @param key an <code>Object</code> value
381: * @return the value of <tt>key</tt> or null if no such mapping exists.
382: */
383: public V get(Object key) {
384: int index = index((K) key);
385: return index < 0 ? null : _values[index];
386: }
387:
388: /**
389: * Empties the map.
390: *
391: */
392: public void clear() {
393: if (size() == 0)
394: return; // optimization
395:
396: super .clear();
397: Object[] keys = _set;
398: V[] vals = _values;
399:
400: for (int i = keys.length; i-- > 0;) {
401: keys[i] = FREE;
402: vals[i] = null;
403: }
404: }
405:
406: /**
407: * Deletes a key/value pair from the map.
408: *
409: * @param key an <code>Object</code> value
410: * @return an <code>Object</code> value
411: */
412: public V remove(Object key) {
413: V prev = null;
414: int index = index((K) key);
415: if (index >= 0) {
416: prev = _values[index];
417: removeAt(index); // clear key,state; adjust size
418: }
419: return prev;
420: }
421:
422: /**
423: * removes the mapping at <tt>index</tt> from the map.
424: *
425: * @param index an <code>int</code> value
426: */
427: protected void removeAt(int index) {
428: _values[index] = null;
429: super .removeAt(index); // clear key, state; adjust size
430: }
431:
432: /**
433: * Returns a view on the values of the map.
434: *
435: * @return a <code>Collection</code> value
436: */
437: public Collection<V> values() {
438: return new ValueView();
439: }
440:
441: /**
442: * returns a Set view on the keys of the map.
443: *
444: * @return a <code>Set</code> value
445: */
446: public Set<K> keySet() {
447: return new KeyView();
448: }
449:
450: /**
451: * Returns a Set view on the entries of the map.
452: *
453: * @return a <code>Set</code> value
454: */
455: public Set<Map.Entry<K, V>> entrySet() {
456: return new EntryView();
457: }
458:
459: /**
460: * checks for the presence of <tt>val</tt> in the values of the map.
461: *
462: * @param val an <code>Object</code> value
463: * @return a <code>boolean</code> value
464: */
465: public boolean containsValue(Object val) {
466: Object[] set = _set;
467: V[] vals = _values;
468:
469: // special case null values so that we don't have to
470: // perform null checks before every call to equals()
471: if (null == val) {
472: for (int i = vals.length; i-- > 0;) {
473: if ((set[i] != FREE && set[i] != REMOVED)
474: && val == vals[i]) {
475: return true;
476: }
477: }
478: } else {
479: for (int i = vals.length; i-- > 0;) {
480: if ((set[i] != FREE && set[i] != REMOVED)
481: && (val == vals[i] || val.equals(vals[i]))) {
482: return true;
483: }
484: }
485: } // end of else
486: return false;
487: }
488:
489: /**
490: * checks for the present of <tt>key</tt> in the keys of the map.
491: *
492: * @param key an <code>Object</code> value
493: * @return a <code>boolean</code> value
494: */
495: public boolean containsKey(Object key) {
496: return contains(key);
497: }
498:
499: /**
500: * copies the key/value mappings in <tt>map</tt> into this map.
501: *
502: * @param map a <code>Map</code> value
503: */
504: public void putAll(Map<? extends K, ? extends V> map) {
505: ensureCapacity(map.size());
506: // could optimize this for cases when map instanceof THashMap
507: for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = map
508: .entrySet().iterator(); i.hasNext();) {
509: Map.Entry<? extends K, ? extends V> e = i.next();
510: put(e.getKey(), e.getValue());
511: }
512: }
513:
514: /**
515: * a view onto the values of the map.
516: *
517: */
518: protected class ValueView extends MapBackedView<V> {
519: public Iterator<V> iterator() {
520: return new THashIterator<V>(THashMap.this ) {
521: protected V objectAtIndex(int index) {
522: return _values[index];
523: }
524: };
525: }
526:
527: public boolean containsElement(V value) {
528: return containsValue(value);
529: }
530:
531: public boolean removeElement(V value) {
532: Object[] values = _values;
533: Object[] set = _set;
534:
535: for (int i = values.length; i-- > 0;) {
536: if ((set[i] != FREE && set[i] != REMOVED)
537: && value == values[i]
538: || (null != values[i] && values[i]
539: .equals(value))) {
540:
541: removeAt(i);
542: return true;
543: }
544: }
545:
546: return false;
547: }
548: }
549:
550: /**
551: * a view onto the entries of the map.
552: *
553: */
554: protected class EntryView extends MapBackedView<Map.Entry<K, V>> {
555: private final class EntryIterator extends
556: THashIterator<Map.Entry<K, V>> {
557: EntryIterator(THashMap<K, V> map) {
558: super (map);
559: }
560:
561: public Entry objectAtIndex(final int index) {
562: return new Entry((K) _set[index], _values[index], index);
563: }
564: }
565:
566: public Iterator<Map.Entry<K, V>> iterator() {
567: return new EntryIterator(THashMap.this );
568: }
569:
570: public boolean removeElement(Map.Entry<K, V> entry) {
571: // have to effectively reimplement Map.remove here
572: // because we need to return true/false depending on
573: // whether the removal took place. Since the Entry's
574: // value can be null, this means that we can't rely
575: // on the value of the object returned by Map.remove()
576: // to determine whether a deletion actually happened.
577: //
578: // Note also that the deletion is only legal if
579: // both the key and the value match.
580: Object val;
581: int index;
582:
583: K key = keyForEntry(entry);
584: index = index(key);
585: if (index >= 0) {
586: val = valueForEntry(entry);
587: if (val == _values[index]
588: || (null != val && val.equals(_values[index]))) {
589: removeAt(index); // clear key,state; adjust size
590: return true;
591: }
592: }
593: return false;
594: }
595:
596: public boolean containsElement(Map.Entry<K, V> entry) {
597: Object val = get(keyForEntry(entry));
598: Object entryValue = entry.getValue();
599: return entryValue == val
600: || (null != val && val.equals(entryValue));
601: }
602:
603: protected V valueForEntry(Map.Entry<K, V> entry) {
604: return entry.getValue();
605: }
606:
607: protected K keyForEntry(Map.Entry<K, V> entry) {
608: return entry.getKey();
609: }
610: }
611:
612: private abstract class MapBackedView<E> extends AbstractSet<E>
613: implements Set<E>, Iterable<E> {
614:
615: public abstract Iterator<E> iterator();
616:
617: public abstract boolean removeElement(E key);
618:
619: public abstract boolean containsElement(E key);
620:
621: public boolean contains(Object key) {
622: return containsElement((E) key);
623: }
624:
625: public boolean remove(Object o) {
626: return removeElement((E) o);
627: }
628:
629: public boolean containsAll(Collection<?> collection) {
630: for (Iterator i = collection.iterator(); i.hasNext();) {
631: if (!contains(i.next())) {
632: return false;
633: }
634: }
635: return true;
636: }
637:
638: public void clear() {
639: THashMap.this .clear();
640: }
641:
642: public boolean add(E obj) {
643: throw new UnsupportedOperationException();
644: }
645:
646: public int size() {
647: return THashMap.this .size();
648: }
649:
650: public Object[] toArray() {
651: Object[] result = new Object[size()];
652: Iterator e = iterator();
653: for (int i = 0; e.hasNext(); i++)
654: result[i] = e.next();
655: return result;
656: }
657:
658: public <T> T[] toArray(T[] a) {
659: int size = size();
660: if (a.length < size)
661: a = (T[]) java.lang.reflect.Array.newInstance(a
662: .getClass().getComponentType(), size);
663:
664: Iterator<E> it = iterator();
665: Object[] result = a;
666: for (int i = 0; i < size; i++) {
667: result[i] = it.next();
668: }
669:
670: if (a.length > size) {
671: a[size] = null;
672: }
673:
674: return a;
675: }
676:
677: public boolean isEmpty() {
678: return THashMap.this .isEmpty();
679: }
680:
681: public boolean addAll(Collection<? extends E> collection) {
682: throw new UnsupportedOperationException();
683: }
684:
685: public boolean retainAll(Collection<?> collection) {
686: boolean changed = false;
687: Iterator i = iterator();
688: while (i.hasNext()) {
689: if (!collection.contains(i.next())) {
690: i.remove();
691: changed = true;
692: }
693: }
694: return changed;
695: }
696: }
697:
698: /**
699: * a view onto the keys of the map.
700: */
701: protected class KeyView extends MapBackedView<K> {
702: public Iterator<K> iterator() {
703: return new TObjectHashIterator<K>(THashMap.this );
704: }
705:
706: public boolean removeElement(K key) {
707: return null != THashMap.this .remove(key);
708: }
709:
710: public boolean containsElement(K key) {
711: return THashMap.this .contains(key);
712: }
713: }
714:
715: final class Entry implements Map.Entry<K, V> {
716: private K key;
717: private V val;
718: private final int index;
719:
720: Entry(final K key, V value, final int index) {
721: this .key = key;
722: this .val = value;
723: this .index = index;
724: }
725:
726: void setKey(K aKey) {
727: this .key = aKey;
728: }
729:
730: void setValue0(V aValue) {
731: this .val = aValue;
732: }
733:
734: public K getKey() {
735: return key;
736: }
737:
738: public V getValue() {
739: return val;
740: }
741:
742: public V setValue(V o) {
743: if (_values[index] != val) {
744: throw new ConcurrentModificationException();
745: }
746: _values[index] = o;
747: o = val; // need to return previous value
748: val = o; // update this entry's value, in case
749: // setValue is called again
750: return o;
751: }
752:
753: public boolean equals(Object o) {
754: if (o instanceof Map.Entry) {
755: Map.Entry e1 = this ;
756: Map.Entry e2 = (Map.Entry) o;
757: return (e1.getKey() == null ? e2.getKey() == null : e1
758: .getKey().equals(e2.getKey()))
759: && (e1.getValue() == null ? e2.getValue() == null
760: : e1.getValue().equals(e2.getValue()));
761: }
762: return false;
763: }
764:
765: public int hashCode() {
766: return (getKey() == null ? 0 : getKey().hashCode())
767: ^ (getValue() == null ? 0 : getValue().hashCode());
768: }
769: }
770:
771: public void writeExternal(ObjectOutput out) throws IOException {
772: // VERSION
773: out.writeByte(0);
774:
775: // NUMBER OF ENTRIES
776: out.writeInt(_size);
777:
778: // ENTRIES
779: SerializationProcedure writeProcedure = new SerializationProcedure(
780: out);
781: if (!forEachEntry(writeProcedure)) {
782: throw writeProcedure.exception;
783: }
784: }
785:
786: public void readExternal(ObjectInput in) throws IOException,
787: ClassNotFoundException {
788:
789: // VERSION
790: in.readByte();
791:
792: // NUMBER OF ENTRIES
793: int size = in.readInt();
794: setUp(size);
795:
796: // ENTRIES
797: while (size-- > 0) {
798: K key = (K) in.readObject();
799: V val = (V) in.readObject();
800: put(key, val);
801: }
802: }
803: } // THashMap
|