THashMap


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