KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > trove > TObjectByteHashMap


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 import java.util.Arrays;
26
27 /**
28  * An open addressed Map implementation for Object keys and byte values.
29  *
30  * Created: Sun Nov 4 08:52:45 2001
31  *
32  * @author Eric D. Friedman
33  * @version $Id: TObjectByteHashMap.java,v 1.2 2005/03/26 17:52:56 ericdf Exp $
34  */

35 public class TObjectByteHashMap extends TObjectHash implements Serializable {
36
37     /** compatible serialization ID - not present in 1.1b3 and earlier */
38     static final long serialVersionUID = 1L;
39
40     /** the values of the map */
41     protected transient byte[] _values;
42
43     /**
44      * Creates a new <code>TObjectByteHashMap</code> instance with the default
45      * capacity and load factor.
46      */

47     public TObjectByteHashMap() {
48         super();
49     }
50
51     /**
52      * Creates a new <code>TObjectByteHashMap</code> instance with a prime
53      * capacity equal to or greater than <tt>initialCapacity</tt> and
54      * with the default load factor.
55      *
56      * @param initialCapacity an <code>int</code> value
57      */

58     public TObjectByteHashMap(int initialCapacity) {
59         super(initialCapacity);
60     }
61
62     /**
63      * Creates a new <code>TObjectByteHashMap</code> instance with a prime
64      * capacity equal to or greater than <tt>initialCapacity</tt> and
65      * with the specified load factor.
66      *
67      * @param initialCapacity an <code>int</code> value
68      * @param loadFactor a <code>float</code> value
69      */

70     public TObjectByteHashMap(int initialCapacity, float loadFactor) {
71         super(initialCapacity, loadFactor);
72     }
73
74     /**
75      * Creates a new <code>TObjectByteHashMap</code> instance with the default
76      * capacity and load factor.
77      * @param strategy used to compute hash codes and to compare keys.
78      */

79     public TObjectByteHashMap(TObjectHashingStrategy strategy) {
80         super(strategy);
81     }
82
83     /**
84      * Creates a new <code>TObjectByteHashMap</code> instance whose capacity
85      * is the next highest prime above <tt>initialCapacity + 1</tt>
86      * unless that value is already prime.
87      *
88      * @param initialCapacity an <code>int</code> value
89      * @param strategy used to compute hash codes and to compare keys.
90      */

91     public TObjectByteHashMap(int initialCapacity, TObjectHashingStrategy strategy) {
92         super(initialCapacity, strategy);
93     }
94
95     /**
96      * Creates a new <code>TObjectByteHashMap</code> instance with a prime
97      * value at or near the specified capacity and load factor.
98      *
99      * @param initialCapacity used to find a prime capacity for the table.
100      * @param loadFactor used to calculate the threshold over which
101      * rehashing takes place.
102      * @param strategy used to compute hash codes and to compare keys.
103      */

104     public TObjectByteHashMap(int initialCapacity, float loadFactor, TObjectHashingStrategy strategy) {
105         super(initialCapacity, loadFactor, strategy);
106     }
107
108     /**
109      * @return an iterator over the entries in this map
110      */

111     public TObjectByteIterator iterator() {
112         return new TObjectByteIterator(this);
113     }
114
115     /**
116      * initializes the hashtable to a prime capacity which is at least
117      * <tt>initialCapacity + 1</tt>.
118      *
119      * @param initialCapacity an <code>int</code> value
120      * @return the actual capacity chosen
121      */

122     protected int setUp(int initialCapacity) {
123         int capacity;
124
125         capacity = super.setUp(initialCapacity);
126         _values = new byte[capacity];
127         return capacity;
128     }
129
130     /**
131      * Inserts a key/value pair into the map.
132      *
133      * @param key an <code>Object</code> value
134      * @param value an <code>byte</code> value
135      * @return the previous value associated with <tt>key</tt>,
136      * or null if none was found.
137      */

138     public byte put(Object key, byte value) {
139         byte previous = (byte)0;
140         int index = insertionIndex(key);
141         boolean isNewMapping = true;
142         if (index < 0) {
143             index = -index -1;
144             previous = _values[index];
145             isNewMapping = false;
146         }
147         Object oldKey = _set[index];
148         _set[index] = key;
149         _values[index] = value;
150
151         if (isNewMapping) {
152             postInsertHook(oldKey == FREE);
153         }
154         return previous;
155     }
156
157     /**
158      * rehashes the map to the new capacity.
159      *
160      * @param newCapacity an <code>int</code> value
161      */

162     protected void rehash(int newCapacity) {
163         int oldCapacity = _set.length;
164         Object oldKeys[] = _set;
165         byte oldVals[] = _values;
166
167         _set = new Object[newCapacity];
168         Arrays.fill(_set, FREE);
169         _values = new byte[newCapacity];
170
171         for (int i = oldCapacity; i-- > 0;) {
172           if(oldKeys[i] != FREE && oldKeys[i] != REMOVED) {
173                 Object o = oldKeys[i];
174                 int index = insertionIndex(o);
175                 if (index < 0) {
176                     throwObjectContractViolation(_set[(-index -1)], o);
177                 }
178                 _set[index] = o;
179                 _values[index] = oldVals[i];
180             }
181         }
182     }
183
184     /**
185      * retrieves the value for <tt>key</tt>
186      *
187      * @param key an <code>Object</code> value
188      * @return the value of <tt>key</tt> or null if no such mapping exists.
189      */

190     public byte get(Object key) {
191         int index = index(key);
192         return index < 0 ? (byte)0 : _values[index];
193     }
194
195     /**
196      * Empties the map.
197      *
198      */

199     public void clear() {
200         super.clear();
201         Object[] keys = _set;
202         byte[] vals = _values;
203
204         for (int i = keys.length; i-- > 0;) {
205             keys[i] = FREE;
206             vals[i] = (byte)0;
207         }
208     }
209
210     /**
211      * Deletes a key/value pair from the map.
212      *
213      * @param key an <code>Object</code> value
214      * @return an <code>byte</code> value
215      */

216     public byte remove(Object key) {
217         byte prev = (byte)0;
218         int index = index(key);
219         if (index >= 0) {
220             prev = _values[index];
221             removeAt(index); // clear key,state; adjust size
222
}
223         return prev;
224     }
225
226     /**
227      * Compares this map with another map for equality of their stored
228      * entries.
229      *
230      * @param other an <code>Object</code> value
231      * @return a <code>boolean</code> value
232      */

233     public boolean equals(Object other) {
234         if (! (other instanceof TObjectByteHashMap)) {
235             return false;
236         }
237         TObjectByteHashMap that = (TObjectByteHashMap)other;
238         if (that.size() != this.size()) {
239             return false;
240         }
241         return forEachEntry(new EqProcedure(that));
242     }
243
244     private static final class EqProcedure implements TObjectByteProcedure {
245         private final TObjectByteHashMap _otherMap;
246
247         EqProcedure(TObjectByteHashMap otherMap) {
248             _otherMap = otherMap;
249         }
250
251         public final boolean execute(Object key, byte value) {
252             int index = _otherMap.index(key);
253             if (index >= 0 && eq(value, _otherMap.get(key))) {
254                 return true;
255             }
256             return false;
257         }
258
259         /**
260          * Compare two bytes for equality.
261          */

262         private final boolean eq(byte v1, byte v2) {
263             return v1 == v2;
264         }
265
266     }
267
268     /**
269      * removes the mapping at <tt>index</tt> from the map.
270      *
271      * @param index an <code>int</code> value
272      */

273     protected void removeAt(int index) {
274         super.removeAt(index); // clear key, state; adjust size
275
_values[index] = (byte)0;
276     }
277
278     /**
279      * Returns the values of the map.
280      *
281      * @return a <code>Collection</code> value
282      */

283     public byte[] getValues() {
284         byte[] vals = new byte[size()];
285         byte[] v = _values;
286         Object[] keys = _set;
287
288         for (int i = v.length, j = 0; i-- > 0;) {
289           if (keys[i] != FREE && keys[i] != REMOVED) {
290             vals[j++] = v[i];
291           }
292         }
293         return vals;
294     }
295
296     /**
297      * returns the keys of the map.
298      *
299      * @return a <code>Set</code> value
300      */

301     public Object[] keys() {
302         Object[] keys = new Object[size()];
303         Object[] k = _set;
304
305         for (int i = k.length, j = 0; i-- > 0;) {
306           if (k[i] != FREE && k[i] != REMOVED) {
307             keys[j++] = k[i];
308           }
309         }
310         return keys;
311     }
312
313     /**
314      * checks for the presence of <tt>val</tt> in the values of the map.
315      *
316      * @param val an <code>byte</code> value
317      * @return a <code>boolean</code> value
318      */

319     public boolean containsValue(byte val) {
320         Object[] keys = _set;
321         byte[] vals = _values;
322
323         for (int i = vals.length; i-- > 0;) {
324             if (keys[i] != FREE && keys[i] != REMOVED && val == vals[i]) {
325                 return true;
326             }
327         }
328         return false;
329     }
330
331
332     /**
333      * checks for the present of <tt>key</tt> in the keys of the map.
334      *
335      * @param key an <code>Object</code> value
336      * @return a <code>boolean</code> value
337      */

338     public boolean containsKey(Object key) {
339         return contains(key);
340     }
341
342     /**
343      * Executes <tt>procedure</tt> for each key in the map.
344      *
345      * @param procedure a <code>TObjectProcedure</code> value
346      * @return false if the loop over the keys terminated because
347      * the procedure returned false for some key.
348      */

349     public boolean forEachKey(TObjectProcedure procedure) {
350         return forEach(procedure);
351     }
352
353     /**
354      * Executes <tt>procedure</tt> for each value in the map.
355      *
356      * @param procedure a <code>TByteProcedure</code> value
357      * @return false if the loop over the values terminated because
358      * the procedure returned false for some value.
359      */

360     public boolean forEachValue(TByteProcedure procedure) {
361         Object[] keys = _set;
362         byte[] values = _values;
363         for (int i = values.length; i-- > 0;) {
364             if (keys[i] != FREE && keys[i] != REMOVED
365                 && ! procedure.execute(values[i])) {
366                 return false;
367             }
368         }
369         return true;
370     }
371
372     /**
373      * Executes <tt>procedure</tt> for each key/value entry in the
374      * map.
375      *
376      * @param procedure a <code>TOObjectByteProcedure</code> value
377      * @return false if the loop over the entries terminated because
378      * the procedure returned false for some entry.
379      */

380     public boolean forEachEntry(TObjectByteProcedure procedure) {
381         Object[] keys = _set;
382         byte[] values = _values;
383         for (int i = keys.length; i-- > 0;) {
384             if (keys[i] != FREE
385                 && keys[i] != REMOVED
386                 && ! procedure.execute(keys[i],values[i])) {
387                 return false;
388             }
389         }
390         return true;
391     }
392
393     /**
394      * Retains only those entries in the map for which the procedure
395      * returns a true value.
396      *
397      * @param procedure determines which entries to keep
398      * @return true if the map was modified.
399      */

400     public boolean retainEntries(TObjectByteProcedure procedure) {
401         boolean modified = false;
402         Object[] keys = _set;
403         byte[] values = _values;
404         for (int i = keys.length; i-- > 0;) {
405             if (keys[i] != FREE
406                 && keys[i] != REMOVED
407                 && ! procedure.execute(keys[i],values[i])) {
408                 removeAt(i);
409                 modified = true;
410             }
411         }
412         return modified;
413     }
414
415     /**
416      * Transform the values in this map using <tt>function</tt>.
417      *
418      * @param function a <code>TByteFunction</code> value
419      */

420     public void transformValues(TByteFunction function) {
421         Object[] keys = _set;
422         byte[] values = _values;
423         for (int i = values.length; i-- > 0;) {
424             if (keys[i] != FREE && keys[i] != REMOVED) {
425                 values[i] = function.execute(values[i]);
426             }
427         }
428     }
429
430     /**
431      * Increments the primitive value mapped to key by 1
432      *
433      * @param key the key of the value to increment
434      * @return true if a mapping was found and modified.
435      */

436     public boolean increment(Object key) {
437         return adjustValue(key, (byte)1);
438     }
439
440     /**
441      * Adjusts the primitive value mapped to key.
442      *
443      * @param key the key of the value to increment
444      * @param amount the amount to adjust the value by.
445      * @return true if a mapping was found and modified.
446      */

447     public boolean adjustValue(Object key, byte amount) {
448         int index = index(key);
449         if (index < 0) {
450             return false;
451         } else {
452             _values[index] += amount;
453             return true;
454         }
455     }
456
457
458     private void writeObject(ObjectOutputStream stream)
459         throws IOException {
460         stream.defaultWriteObject();
461
462         // number of entries
463
stream.writeInt(_size);
464
465         SerializationProcedure writeProcedure = new SerializationProcedure(stream);
466         if (! forEachEntry(writeProcedure)) {
467             throw writeProcedure.exception;
468         }
469     }
470
471     private void readObject(ObjectInputStream stream)
472         throws IOException, ClassNotFoundException {
473         stream.defaultReadObject();
474
475         int size = stream.readInt();
476         setUp(size);
477         while (size-- > 0) {
478             Object key = stream.readObject();
479             byte val = stream.readByte();
480             put(key, val);
481         }
482     }
483 } // TObjectByteHashMap
484
Popular Tags