KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > trove > TDoubleObjectHashMap


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

34 public class TDoubleObjectHashMap extends TDoubleHash 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>TDoubleObjectHashMap</code> instance with the default
44      * capacity and load factor.
45      */

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

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

119     public TDoubleObjectIterator iterator() {
120         return new TDoubleObjectIterator(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>double</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(double 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         double oldKeys[] = _set;
175         Object oldVals[] = _values;
176         byte oldStates[] = _states;
177
178         _set = new double[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                 double 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>double</code> value
197      * @return the value of <tt>key</tt> or null if no such mapping exists.
198      */

199     public Object get(double 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         double[] keys = _set;
211         Object[] vals = _values;
212         byte[] states = _states;
213
214         for (int i = keys.length; i-- > 0;) {
215             keys[i] = (double)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>double</code> value
225      * @return an <code>Object</code> value, or null if no mapping for key exists
226      */

227     public Object remove(double 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 TDoubleObjectHashMap)) {
246             return false;
247         }
248         TDoubleObjectHashMap that = (TDoubleObjectHashMap)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 TDoubleObjectProcedure {
262         private int h = 0;
263         
264         public int getHashCode() {
265             return h;
266         }
267         
268         public final boolean execute(double key, Object value) {
269             h += (_hashingStrategy.computeHashCode(key) ^ HashFunctions.hash(value));
270             return true;
271         }
272     }
273
274     private static final class EqProcedure implements TDoubleObjectProcedure {
275         private final TDoubleObjectHashMap _otherMap;
276
277         EqProcedure(TDoubleObjectHashMap otherMap) {
278             _otherMap = otherMap;
279         }
280
281         public final boolean execute(double 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 double[] keys() {
332         double[] keys = new double[size()];
333         double[] 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>double</code> value
379      * @return a <code>boolean</code> value
380      */

381     public boolean containsKey(double 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>TDoubleProcedure</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(TDoubleProcedure 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>TODoubleObjectProcedure</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(TDoubleObjectProcedure procedure) {
423         byte[] states = _states;
424         double[] 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(TDoubleObjectProcedure procedure) {
442         boolean modified = false;
443         byte[] states = _states;
444         double[] 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             double key = stream.readDouble();
493             Object val = stream.readObject();
494             put(key, val);
495         }
496     }
497 } // TDoubleObjectHashMap
498
Popular Tags