KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > trove > TShortFloatHashMap


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 short keys and float values.
28  *
29  * Created: Sun Nov 4 08:52:45 2001
30  *
31  * @author Eric D. Friedman
32  * @version $Id: TShortFloatHashMap.java,v 1.2 2005/03/26 17:52:56 ericdf Exp $
33  */

34 public class TShortFloatHashMap extends TShortHash 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 float[] _values;
41
42     /**
43      * Creates a new <code>TShortFloatHashMap</code> instance with the default
44      * capacity and load factor.
45      */

46     public TShortFloatHashMap() {
47         super();
48     }
49
50     /**
51      * Creates a new <code>TShortFloatHashMap</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 TShortFloatHashMap(int initialCapacity) {
58         super(initialCapacity);
59     }
60
61     /**
62      * Creates a new <code>TShortFloatHashMap</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 TShortFloatHashMap(int initialCapacity, float loadFactor) {
70         super(initialCapacity, loadFactor);
71     }
72
73     /**
74      * Creates a new <code>TShortFloatHashMap</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 TShortFloatHashMap(TShortHashingStrategy strategy) {
79         super(strategy);
80     }
81
82     /**
83      * Creates a new <code>TShortFloatHashMap</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 TShortFloatHashMap(int initialCapacity, TShortHashingStrategy strategy) {
91         super(initialCapacity, strategy);
92     }
93
94     /**
95      * Creates a new <code>TShortFloatHashMap</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 TShortFloatHashMap(int initialCapacity, float loadFactor, TShortHashingStrategy strategy) {
104         super(initialCapacity, loadFactor, strategy);
105     }
106
107     /**
108      * @return a deep clone of this collection
109      */

110     public Object clone() {
111       TShortFloatHashMap m = (TShortFloatHashMap)super.clone();
112       m._values = (float[])this._values.clone();
113       return m;
114     }
115
116     /**
117      * @return a TShortFloatIterator with access to this map's keys and values
118      */

119     public TShortFloatIterator iterator() {
120         return new TShortFloatIterator(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 float[capacity];
135         return capacity;
136     }
137
138     /**
139      * Inserts a key/value pair into the map.
140      *
141      * @param key an <code>short</code> value
142      * @param value an <code>float</code> value
143      * @return the previous value associated with <tt>key</tt>,
144      * or (float)0 if none was found.
145      */

146     public float put(short key, float value) {
147         byte previousState;
148         float previous = (float)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         short oldKeys[] = _set;
175         float oldVals[] = _values;
176         byte oldStates[] = _states;
177
178         _set = new short[newCapacity];
179         _values = new float[newCapacity];
180         _states = new byte[newCapacity];
181
182         for (int i = oldCapacity; i-- > 0;) {
183             if(oldStates[i] == FULL) {
184                 short 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>short</code> value
197      * @return the value of <tt>key</tt> or (float)0 if no such mapping exists.
198      */

199     public float get(short key) {
200         int index = index(key);
201         return index < 0 ? (float)0 : _values[index];
202     }
203
204     /**
205      * Empties the map.
206      *
207      */

208     public void clear() {
209         super.clear();
210         short[] keys = _set;
211         float[] vals = _values;
212         byte[] states = _states;
213
214         for (int i = keys.length; i-- > 0;) {
215             keys[i] = (short)0;
216             vals[i] = (float)0;
217             states[i] = FREE;
218         }
219     }
220
221     /**
222      * Deletes a key/value pair from the map.
223      *
224      * @param key an <code>short</code> value
225      * @return an <code>float</code> value, or (float)0 if no mapping for key exists
226      */

227     public float remove(short key) {
228         float prev = (float)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 TShortFloatHashMap)) {
246             return false;
247         }
248         TShortFloatHashMap that = (TShortFloatHashMap)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 TShortFloatProcedure {
262         private int h = 0;
263         
264         public int getHashCode() {
265             return h;
266         }
267         
268         public final boolean execute(short key, float value) {
269             h += (_hashingStrategy.computeHashCode(key) ^ HashFunctions.hash(value));
270             return true;
271         }
272     }
273
274     private static final class EqProcedure implements TShortFloatProcedure {
275         private final TShortFloatHashMap _otherMap;
276
277         EqProcedure(TShortFloatHashMap otherMap) {
278             _otherMap = otherMap;
279         }
280
281         public final boolean execute(short key, float 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 floats for equality.
291          */

292         private final boolean eq(float v1, float 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] = (float)0;
306     }
307
308     /**
309      * Returns the values of the map.
310      *
311      * @return a <code>Collection</code> value
312      */

313     public float[] getValues() {
314         float[] vals = new float[size()];
315         float[] 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 short[] keys() {
332         short[] keys = new short[size()];
333         short[] 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>float</code> value
348      * @return a <code>boolean</code> value
349      */

350     public boolean containsValue(float val) {
351         byte[] states = _states;
352         float[] 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>short</code> value
367      * @return a <code>boolean</code> value
368      */

369     public boolean containsKey(short 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>TShortProcedure</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(TShortProcedure 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>TFloatProcedure</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(TFloatProcedure procedure) {
392         byte[] states = _states;
393         float[] 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>TOShortFloatProcedure</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(TShortFloatProcedure procedure) {
411         byte[] states = _states;
412         short[] keys = _set;
413         float[] 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(TShortFloatProcedure procedure) {
430         boolean modified = false;
431         byte[] states = _states;
432         short[] keys = _set;
433         float[] 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>TFloatFunction</code> value
447      */

448     public void transformValues(TFloatFunction function) {
449         byte[] states = _states;
450         float[] 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(short key) {
465         return adjustValue(key, (float)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(short key, float 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             short key = stream.readShort();
507             float val = stream.readFloat();
508             put(key, val);
509         }
510     }
511 } // TShortFloatHashMap
512
Popular Tags