TObjectIntHashMap


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 int values.
29   *
30   * Created: Sun Nov  4 08:52:45 2001
31   *
32   * @author Eric D. Friedman
33   * @version $Id: TObjectIntHashMap.java,v 1.15 2005/03/26 17:52:56 ericdf Exp $
34   */
35  public class TObjectIntHashMap 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 int[] _values;
42  
43      /**
44       * Creates a new <code>TObjectIntHashMap</code> instance with the default
45       * capacity and load factor.
46       */
47      public TObjectIntHashMap() {
48          super();
49      }
50  
51      /**
52       * Creates a new <code>TObjectIntHashMap</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 TObjectIntHashMap(int initialCapacity) {
59          super(initialCapacity);
60      }
61  
62      /**
63       * Creates a new <code>TObjectIntHashMap</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 TObjectIntHashMap(int initialCapacity, float loadFactor) {
71          super(initialCapacity, loadFactor);
72      }
73  
74      /**
75       * Creates a new <code>TObjectIntHashMap</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 TObjectIntHashMap(TObjectHashingStrategy strategy) {
80          super(strategy);
81      }
82  
83      /**
84       * Creates a new <code>TObjectIntHashMap</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 TObjectIntHashMap(int initialCapacity, TObjectHashingStrategy strategy) {
92          super(initialCapacity, strategy);
93      }
94  
95      /**
96       * Creates a new <code>TObjectIntHashMap</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 TObjectIntHashMap(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 TObjectIntIterator iterator() {
112         return new TObjectIntIterator(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 int[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>int</code> value
135      * @return the previous value associated with <tt>key</tt>,
136      * or null if none was found.
137      */
138     public int put(Object key, int value) {
139         int previous = (int)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         int oldVals[] = _values;
166 
167         _set = new Object[newCapacity];
168         Arrays.fill(_set, FREE);
169         _values = new int[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 int get(Object key) {
191         int index = index(key);
192         return index < 0 ? (int)0 : _values[index];
193     }
194 
195     /**
196      * Empties the map.
197      *
198      */
199     public void clear() {
200         super.clear();
201         Object[] keys = _set;
202         int[] vals = _values;
203 
204         for (int i = keys.length; i-- > 0;) {
205             keys[i] = FREE;
206             vals[i] = (int)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>int</code> value
215      */
216     public int remove(Object key) {
217         int prev = (int)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 TObjectIntHashMap)) {
235             return false;
236         }
237         TObjectIntHashMap that = (TObjectIntHashMap)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 TObjectIntProcedure {
245         private final TObjectIntHashMap _otherMap;
246 
247         EqProcedure(TObjectIntHashMap otherMap) {
248             _otherMap = otherMap;
249         }
250 
251         public final boolean execute(Object key, int 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 ints for equality.
261          */
262         private final boolean eq(int v1, int 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] = (int)0;
276     }
277 
278     /**
279      * Returns the values of the map.
280      *
281      * @return a <code>Collection</code> value
282      */
283     public int[] getValues() {
284         int[] vals = new int[size()];
285         int[] 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>int</code> value
317      * @return a <code>boolean</code> value
318      */
319     public boolean containsValue(int val) {
320         Object[] keys = _set;
321         int[] 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>TIntProcedure</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(TIntProcedure procedure) {
361         Object[] keys = _set;
362         int[] 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>TOObjectIntProcedure</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(TObjectIntProcedure procedure) {
381         Object[] keys = _set;
382         int[] 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(TObjectIntProcedure procedure) {
401         boolean modified = false;
402         Object[] keys = _set;
403         int[] 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>TIntFunction</code> value
419      */
420     public void transformValues(TIntFunction function) {
421         Object[] keys = _set;
422         int[] 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, (int)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, int 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             int val = stream.readInt();
480             put(key, val);
481         }
482     }
483 } // TObjectIntHashMap
484
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Java Books Remove Frame
Popular Tags