TByteObjectHashMap


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 byte keys and Object values.
28   *
29   * Created: Sun Nov  4 08:52:45 2001
30   *
31   * @author Eric D. Friedman
32   * @version $Id: TByteObjectHashMap.java,v 1.2 2005/03/26 17:52:55 ericdf Exp $
33   */
34  public class TByteObjectHashMap extends TByteHash 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 Object[] _values;
41  
42      /**
43       * Creates a new <code>TByteObjectHashMap</code> instance with the default
44       * capacity and load factor.
45       */
46      public TByteObjectHashMap() {
47          super();
48      }
49  
50      /**
51       * Creates a new <code>TByteObjectHashMap</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 TByteObjectHashMap(int initialCapacity) {
58          super(initialCapacity);
59      }
60  
61      /**
62       * Creates a new <code>TByteObjectHashMap</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 TByteObjectHashMap(int initialCapacity, float loadFactor) {
70          super(initialCapacity, loadFactor);
71      }
72  
73      /**
74       * Creates a new <code>TByteObjectHashMap</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 TByteObjectHashMap(TByteHashingStrategy strategy) {
79          super(strategy);
80      }
81  
82      /**
83       * Creates a new <code>TByteObjectHashMap</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 TByteObjectHashMap(int initialCapacity, TByteHashingStrategy strategy) {
91          super(initialCapacity, strategy);
92      }
93  
94      /**
95       * Creates a new <code>TByteObjectHashMap</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 TByteObjectHashMap(int initialCapacity, float loadFactor, TByteHashingStrategy strategy) {
104         super(initialCapacity, loadFactor, strategy);
105     }
106 
107     /**
108      * @return a deep clone of this collection
109      */
110     public Object clone() {
111       TByteObjectHashMap m = (TByteObjectHashMap)super.clone();
112       m._values = (Object[])this._values.clone();
113       return m;
114     }
115 
116     /**
117      * @return a TByteObjectIterator with access to this map's keys and values
118      */
119     public TByteObjectIterator iterator() {
120         return new TByteObjectIterator(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 Object[capacity];
135         return capacity;
136     }
137 
138     /**
139      * Inserts a key/value pair into the map.
140      *
141      * @param key an <code>byte</code> value
142      * @param value an <code>Object</code> value
143      * @return the previous value associated with <tt>key</tt>,
144      * or null if none was found.
145      */
146     public Object put(byte key, Object value) {
147         byte previousState;
148         Object previous = null;
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         byte oldKeys[] = _set;
175         Object oldVals[] = _values;
176         byte oldStates[] = _states;
177 
178         _set = new byte[newCapacity];
179         _values = new Object[newCapacity];
180         _states = new byte[newCapacity];
181 
182         for (int i = oldCapacity; i-- > 0;) {
183             if(oldStates[i] == FULL) {
184                 byte 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>byte</code> value
197      * @return the value of <tt>key</tt> or null if no such mapping exists.
198      */
199     public Object get(byte key) {
200         int index = index(key);
201         return index < 0 ? null : _values[index];
202     }
203 
204     /**
205      * Empties the map.
206      *
207      */
208     public void clear() {
209         super.clear();
210         byte[] keys = _set;
211         Object[] vals = _values;
212         byte[] states = _states;
213 
214         for (int i = keys.length; i-- > 0;) {
215             keys[i] = (byte)0;
216             vals[i] = null;
217             states[i] = FREE;
218         }
219     }
220 
221     /**
222      * Deletes a key/value pair from the map.
223      *
224      * @param key an <code>byte</code> value
225      * @return an <code>Object</code> value, or null if no mapping for key exists
226      */
227     public Object remove(byte key) {
228         Object prev = null;
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 TByteObjectHashMap)) {
246             return false;
247         }
248         TByteObjectHashMap that = (TByteObjectHashMap)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 TByteObjectProcedure {
262         private int h = 0;
263         
264         public int getHashCode() {
265             return h;
266         }
267         
268         public final boolean execute(byte key, Object value) {
269             h += (_hashingStrategy.computeHashCode(key) ^ HashFunctions.hash(value));
270             return true;
271         }
272     }
273 
274     private static final class EqProcedure implements TByteObjectProcedure {
275         private final TByteObjectHashMap _otherMap;
276 
277         EqProcedure(TByteObjectHashMap otherMap) {
278             _otherMap = otherMap;
279         }
280 
281         public final boolean execute(byte key, Object 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 objects for equality.
291          */
292         private final boolean eq(Object o1, Object o2) {
293             return o1 == o2 || ((o1 != null) && o1.equals(o2));
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] = null;
306     }
307 
308     /**
309      * Returns the values of the map.
310      *
311      * @return a <code>Collection</code> value
312      */
313     public Object[] getValues() {
314         Object[] vals = new Object[size()];
315         Object[] 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 byte[] keys() {
332         byte[] keys = new byte[size()];
333         byte[] 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>Object</code> value
348      * @return a <code>boolean</code> value
349      */
350     public boolean containsValue(Object val) {
351         byte[] states = _states;
352         Object[] vals = _values;
353 
354         // special case null values so that we don't have to
355         // perform null checks before every call to equals()
356         if (null == val) {
357             for (int i = vals.length; i-- > 0;) {
358                 if (states[i] == FULL &&
359                     val == vals[i]) {
360                     return true;
361                 }
362             }
363         } else {
364             for (int i = vals.length; i-- > 0;) {
365                 if (states[i] == FULL &&
366                     (val == vals[i] || val.equals(vals[i]))) {
367                     return true;
368                 }
369             }
370         } // end of else
371         return false;
372     }
373 
374 
375     /**
376      * checks for the present of <tt>key</tt> in the keys of the map.
377      *
378      * @param key an <code>byte</code> value
379      * @return a <code>boolean</code> value
380      */
381     public boolean containsKey(byte key) {
382         return contains(key);
383     }
384 
385     /**
386      * Executes <tt>procedure</tt> for each key in the map.
387      *
388      * @param procedure a <code>TByteProcedure</code> value
389      * @return false if the loop over the keys terminated because
390      * the procedure returned false for some key.
391      */
392     public boolean forEachKey(TByteProcedure procedure) {
393         return forEach(procedure);
394     }
395 
396     /**
397      * Executes <tt>procedure</tt> for each value in the map.
398      *
399      * @param procedure a <code>TObjectProcedure</code> value
400      * @return false if the loop over the values terminated because
401      * the procedure returned false for some value.
402      */
403     public boolean forEachValue(TObjectProcedure procedure) {
404         byte[] states = _states;
405         Object[] values = _values;
406         for (int i = values.length; i-- > 0;) {
407             if (states[i] == FULL && ! procedure.execute(values[i])) {
408                 return false;
409             }
410         }
411         return true;
412     }
413 
414     /**
415      * Executes <tt>procedure</tt> for each key/value entry in the
416      * map.
417      *
418      * @param procedure a <code>TOByteObjectProcedure</code> value
419      * @return false if the loop over the entries terminated because
420      * the procedure returned false for some entry.
421      */
422     public boolean forEachEntry(TByteObjectProcedure procedure) {
423         byte[] states = _states;
424         byte[] keys = _set;
425         Object[] values = _values;
426         for (int i = keys.length; i-- > 0;) {
427             if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
428                 return false;
429             }
430         }
431         return true;
432     }
433 
434     /**
435      * Retains only those entries in the map for which the procedure
436      * returns a true value.
437      *
438      * @param procedure determines which entries to keep
439      * @return true if the map was modified.
440      */
441     public boolean retainEntries(TByteObjectProcedure procedure) {
442         boolean modified = false;
443         byte[] states = _states;
444         byte[] keys = _set;
445         Object[] values = _values;
446         for (int i = keys.length; i-- > 0;) {
447             if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
448                 removeAt(i);
449                 modified = true;
450             }
451         }
452         return modified;
453     }
454 
455     /**
456      * Transform the values in this map using <tt>function</tt>.
457      *
458      * @param function a <code>TObjectFunction</code> value
459      */
460     public void transformValues(TObjectFunction function) {
461         byte[] states = _states;
462         Object[] values = _values;
463         for (int i = values.length; i-- > 0;) {
464             if (states[i] == FULL) {
465                 values[i] = function.execute(values[i]);
466             }
467         }
468     }
469 
470 
471 
472     private void writeObject(ObjectOutputStream stream)
473         throws IOException {
474         stream.defaultWriteObject();
475 
476         // number of entries
477         stream.writeInt(_size);
478 
479         SerializationProcedure writeProcedure = new SerializationProcedure(stream);
480         if (! forEachEntry(writeProcedure)) {
481             throw writeProcedure.exception;
482         }
483     }
484 
485     private void readObject(ObjectInputStream stream)
486         throws IOException, ClassNotFoundException {
487         stream.defaultReadObject();
488 
489         int size = stream.readInt();
490         setUp(size);
491         while (size-- > 0) {
492             byte key = stream.readByte();
493             Object val = stream.readObject();
494             put(key, val);
495         }
496     }
497 } // TByteObjectHashMap
498
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Java Books Remove Frame
Popular Tags