TLongShortHashMap


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.IOException;
22  import java.io.ObjectInputStream;
23  import java.io.ObjectOutputStream;
24  import java.io.Serializable;
25  
26  /**
27   * An open addressed Map implementation for long keys and short values.
28   *
29   * Created: Sun Nov  4 08:52:45 2001
30   *
31   * @author Eric D. Friedman
32   * @version $Id: TLongShortHashMap.java,v 1.2 2005/03/26 17:52:56 ericdf Exp $
33   */
34  public class TLongShortHashMap extends TLongHash implements Serializable {
35  
36      /** compatible serialization ID - not present in 1.1b3 and earlier */
37      static final long serialVersionUID = 1L;
38  
39      /** the values of the map */
40      protected transient short[] _values;
41  
42      /**
43       * Creates a new <code>TLongShortHashMap</code> instance with the default
44       * capacity and load factor.
45       */
46      public TLongShortHashMap() {
47          super();
48      }
49  
50      /**
51       * Creates a new <code>TLongShortHashMap</code> instance with a prime
52       * capacity equal to or greater than <tt>initialCapacity</tt> and
53       * with the default load factor.
54       *
55       * @param initialCapacity an <code>int</code> value
56       */
57      public TLongShortHashMap(int initialCapacity) {
58          super(initialCapacity);
59      }
60  
61      /**
62       * Creates a new <code>TLongShortHashMap</code> instance with a prime
63       * capacity equal to or greater than <tt>initialCapacity</tt> and
64       * with the specified load factor.
65       *
66       * @param initialCapacity an <code>int</code> value
67       * @param loadFactor a <code>float</code> value
68       */
69      public TLongShortHashMap(int initialCapacity, float loadFactor) {
70          super(initialCapacity, loadFactor);
71      }
72  
73      /**
74       * Creates a new <code>TLongShortHashMap</code> instance with the default
75       * capacity and load factor.
76       * @param strategy used to compute hash codes and to compare keys.
77       */
78      public TLongShortHashMap(TLongHashingStrategy strategy) {
79          super(strategy);
80      }
81  
82      /**
83       * Creates a new <code>TLongShortHashMap</code> instance whose capacity
84       * is the next highest prime above <tt>initialCapacity + 1</tt>
85       * unless that value is already prime.
86       *
87       * @param initialCapacity an <code>int</code> value
88       * @param strategy used to compute hash codes and to compare keys.
89       */
90      public TLongShortHashMap(int initialCapacity, TLongHashingStrategy strategy) {
91          super(initialCapacity, strategy);
92      }
93  
94      /**
95       * Creates a new <code>TLongShortHashMap</code> instance with a prime
96       * value at or near the specified capacity and load factor.
97       *
98       * @param initialCapacity used to find a prime capacity for the table.
99       * @param loadFactor used to calculate the threshold over which
100      * rehashing takes place.
101      * @param strategy used to compute hash codes and to compare keys.
102      */
103     public TLongShortHashMap(int initialCapacity, float loadFactor, TLongHashingStrategy strategy) {
104         super(initialCapacity, loadFactor, strategy);
105     }
106 
107     /**
108      * @return a deep clone of this collection
109      */
110     public Object clone() {
111       TLongShortHashMap m = (TLongShortHashMap)super.clone();
112       m._values = (short[])this._values.clone();
113       return m;
114     }
115 
116     /**
117      * @return a TLongShortIterator with access to this map's keys and values
118      */
119     public TLongShortIterator iterator() {
120         return new TLongShortIterator(this);
121     }
122 
123     /**
124      * initializes the hashtable to a prime capacity which is at least
125      * <tt>initialCapacity + 1</tt>.  
126      *
127      * @param initialCapacity an <code>int</code> value
128      * @return the actual capacity chosen
129      */
130     protected int setUp(int initialCapacity) {
131         int capacity;
132 
133         capacity = super.setUp(initialCapacity);
134         _values = new short[capacity];
135         return capacity;
136     }
137 
138     /**
139      * Inserts a key/value pair into the map.
140      *
141      * @param key an <code>long</code> value
142      * @param value an <code>short</code> value
143      * @return the previous value associated with <tt>key</tt>,
144      * or (short)0 if none was found.
145      */
146     public short put(long key, short value) {
147         byte previousState;
148         short previous = (short)0;
149         int index = insertionIndex(key);
150         boolean isNewMapping = true;
151         if (index < 0) {
152             index = -index -1;
153             previous = _values[index];
154             isNewMapping = false;
155         }
156         previousState = _states[index];
157         _set[index] = key;
158         _states[index] = FULL;
159         _values[index] = value;
160         if (isNewMapping) {
161             postInsertHook(previousState == FREE);
162         }
163 
164         return previous;
165     }
166 
167     /**
168      * rehashes the map to the new capacity.
169      *
170      * @param newCapacity an <code>int</code> value
171      */
172     protected void rehash(int newCapacity) {
173         int oldCapacity = _set.length;
174         long oldKeys[] = _set;
175         short oldVals[] = _values;
176         byte oldStates[] = _states;
177 
178         _set = new long[newCapacity];
179         _values = new short[newCapacity];
180         _states = new byte[newCapacity];
181 
182         for (int i = oldCapacity; i-- > 0;) {
183             if(oldStates[i] == FULL) {
184                 long o = oldKeys[i];
185                 int index = insertionIndex(o);
186                 _set[index] = o;
187                 _values[index] = oldVals[i];
188                 _states[index] = FULL;
189             }
190         }
191     }
192 
193     /**
194      * retrieves the value for <tt>key</tt>
195      *
196      * @param key an <code>long</code> value
197      * @return the value of <tt>key</tt> or (short)0 if no such mapping exists.
198      */
199     public short get(long key) {
200         int index = index(key);
201         return index < 0 ? (short)0 : _values[index];
202     }
203 
204     /**
205      * Empties the map.
206      *
207      */
208     public void clear() {
209         super.clear();
210         long[] keys = _set;
211         short[] vals = _values;
212         byte[] states = _states;
213 
214         for (int i = keys.length; i-- > 0;) {
215             keys[i] = (long)0;
216             vals[i] = (short)0;
217             states[i] = FREE;
218         }
219     }
220 
221     /**
222      * Deletes a key/value pair from the map.
223      *
224      * @param key an <code>long</code> value
225      * @return an <code>short</code> value, or (short)0 if no mapping for key exists
226      */
227     public short remove(long key) {
228         short prev = (short)0;
229         int index = index(key);
230         if (index >= 0) {
231             prev = _values[index];
232             removeAt(index);    // clear key,state; adjust size
233         }
234         return prev;
235     }
236 
237     /**
238      * Compares this map with another map for equality of their stored
239      * entries.
240      *
241      * @param other an <code>Object</code> value
242      * @return a <code>boolean</code> value
243      */
244     public boolean equals(Object other) {
245         if (! (other instanceof TLongShortHashMap)) {
246             return false;
247         }
248         TLongShortHashMap that = (TLongShortHashMap)other;
249         if (that.size() != this.size()) {
250             return false;
251         }
252         return forEachEntry(new EqProcedure(that));
253     }
254 
255     public int hashCode() {
256         HashProcedure p = new HashProcedure();
257         forEachEntry(p);
258         return p.getHashCode();
259     }   
260 
261     private final class HashProcedure implements TLongShortProcedure {
262         private int h = 0;
263         
264         public int getHashCode() {
265             return h;
266         }
267         
268         public final boolean execute(long key, short value) {
269             h += (_hashingStrategy.computeHashCode(key) ^ HashFunctions.hash(value));
270             return true;
271         }
272     }
273 
274     private static final class EqProcedure implements TLongShortProcedure {
275         private final TLongShortHashMap _otherMap;
276 
277         EqProcedure(TLongShortHashMap otherMap) {
278             _otherMap = otherMap;
279         }
280 
281         public final boolean execute(long key, short value) {
282             int index = _otherMap.index(key);
283             if (index >= 0 && eq(value, _otherMap.get(key))) {
284                 return true;
285             }
286             return false;
287         }
288 
289         /**
290          * Compare two shorts for equality.
291          */
292         private final boolean eq(short v1, short v2) {
293             return v1 == v2;
294         }
295 
296     }
297 
298     /**
299      * removes the mapping at <tt>index</tt> from the map.
300      *
301      * @param index an <code>int</code> value
302      */
303     protected void removeAt(int index) {
304         super.removeAt(index);  // clear key, state; adjust size
305         _values[index] = (short)0;
306     }
307 
308     /**
309      * Returns the values of the map.
310      *
311      * @return a <code>Collection</code> value
312      */
313     public short[] getValues() {
314         short[] vals = new short[size()];
315         short[] v = _values;
316         byte[] states = _states;
317 
318         for (int i = v.length, j = 0; i-- > 0;) {
319           if (states[i] == FULL) {
320             vals[j++] = v[i];
321           }
322         }
323         return vals;
324     }
325 
326     /**
327      * returns the keys of the map.
328      *
329      * @return a <code>Set</code> value
330      */
331     public long[] keys() {
332         long[] keys = new long[size()];
333         long[] k = _set;
334         byte[] states = _states;
335 
336         for (int i = k.length, j = 0; i-- > 0;) {
337           if (states[i] == FULL) {
338             keys[j++] = k[i];
339           }
340         }
341         return keys;
342     }
343 
344     /**
345      * checks for the presence of <tt>val</tt> in the values of the map.
346      *
347      * @param val an <code>short</code> value
348      * @return a <code>boolean</code> value
349      */
350     public boolean containsValue(short val) {
351         byte[] states = _states;
352         short[] vals = _values;
353 
354         for (int i = vals.length; i-- > 0;) {
355             if (states[i] == FULL && val == vals[i]) {
356                 return true;
357             }
358         }
359         return false;
360     }
361 
362 
363     /**
364      * checks for the present of <tt>key</tt> in the keys of the map.
365      *
366      * @param key an <code>long</code> value
367      * @return a <code>boolean</code> value
368      */
369     public boolean containsKey(long key) {
370         return contains(key);
371     }
372 
373     /**
374      * Executes <tt>procedure</tt> for each key in the map.
375      *
376      * @param procedure a <code>TLongProcedure</code> value
377      * @return false if the loop over the keys terminated because
378      * the procedure returned false for some key.
379      */
380     public boolean forEachKey(TLongProcedure procedure) {
381         return forEach(procedure);
382     }
383 
384     /**
385      * Executes <tt>procedure</tt> for each value in the map.
386      *
387      * @param procedure a <code>TShortProcedure</code> value
388      * @return false if the loop over the values terminated because
389      * the procedure returned false for some value.
390      */
391     public boolean forEachValue(TShortProcedure procedure) {
392         byte[] states = _states;
393         short[] values = _values;
394         for (int i = values.length; i-- > 0;) {
395             if (states[i] == FULL && ! procedure.execute(values[i])) {
396                 return false;
397             }
398         }
399         return true;
400     }
401 
402     /**
403      * Executes <tt>procedure</tt> for each key/value entry in the
404      * map.
405      *
406      * @param procedure a <code>TOLongShortProcedure</code> value
407      * @return false if the loop over the entries terminated because
408      * the procedure returned false for some entry.
409      */
410     public boolean forEachEntry(TLongShortProcedure procedure) {
411         byte[] states = _states;
412         long[] keys = _set;
413         short[] values = _values;
414         for (int i = keys.length; i-- > 0;) {
415             if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
416                 return false;
417             }
418         }
419         return true;
420     }
421 
422     /**
423      * Retains only those entries in the map for which the procedure
424      * returns a true value.
425      *
426      * @param procedure determines which entries to keep
427      * @return true if the map was modified.
428      */
429     public boolean retainEntries(TLongShortProcedure procedure) {
430         boolean modified = false;
431         byte[] states = _states;
432         long[] keys = _set;
433         short[] values = _values;
434         for (int i = keys.length; i-- > 0;) {
435             if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
436                 removeAt(i);
437                 modified = true;
438             }
439         }
440         return modified;
441     }
442 
443     /**
444      * Transform the values in this map using <tt>function</tt>.
445      *
446      * @param function a <code>TShortFunction</code> value
447      */
448     public void transformValues(TShortFunction function) {
449         byte[] states = _states;
450         short[] values = _values;
451         for (int i = values.length; i-- > 0;) {
452             if (states[i] == FULL) {
453                 values[i] = function.execute(values[i]);
454             }
455         }
456     }
457 
458     /**
459      * Increments the primitive value mapped to key by 1
460      *
461      * @param key the key of the value to increment
462      * @return true if a mapping was found and modified.
463      */
464     public boolean increment(long key) {
465         return adjustValue(key, (short)1);
466     }
467 
468     /**
469      * Adjusts the primitive value mapped to key.
470      *
471      * @param key the key of the value to increment
472      * @param amount the amount to adjust the value by.
473      * @return true if a mapping was found and modified.
474      */
475     public boolean adjustValue(long key, short amount) {
476         int index = index(key);
477         if (index < 0) {
478             return false;
479         } else {
480             _values[index] += amount;
481             return true;
482         }
483     }
484 
485 
486     private void writeObject(ObjectOutputStream stream)
487         throws IOException {
488         stream.defaultWriteObject();
489 
490         // number of entries
491         stream.writeInt(_size);
492 
493         SerializationProcedure writeProcedure = new SerializationProcedure(stream);
494         if (! forEachEntry(writeProcedure)) {
495             throw writeProcedure.exception;
496         }
497     }
498 
499     private void readObject(ObjectInputStream stream)
500         throws IOException, ClassNotFoundException {
501         stream.defaultReadObject();
502 
503         int size = stream.readInt();
504         setUp(size);
505         while (size-- > 0) {
506             long key = stream.readLong();
507             short val = stream.readShort();
508             put(key, val);
509         }
510     }
511 } // TLongShortHashMap
512
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Java Books Remove Frame
Popular Tags