ObjectIntMap


1   /* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
2    * 
3    * This program and the accompanying materials are made available under
4    * the terms of the Common Public License v1.0 which accompanies this distribution,
5    * and is available at http://www.eclipse.org/legal/cpl-v10.html
6    * 
7    * $Id: ObjectIntMap.java,v 1.1.1.1 2004/05/09 16:57:54 vlad_r Exp $
8    */
9   package com.vladium.util;
10  
11  import com.vladium.util.asserts.$assert;
12  
13  // ----------------------------------------------------------------------------
14  /**
15   *
16   * MT-safety: an instance of this class is <I>not</I> safe for access from
17   * multiple concurrent threads [even if access is done by a single thread at a
18   * time]. The caller is expected to synchronize externally on an instance [the
19   * implementation does not do internal synchronization for the sake of efficiency].
20   * java.util.ConcurrentModificationException is not supported either.
21   *
22   * @author (C) 2001, Vlad Roubtsov
23   */
24  public
25  final class ObjectIntMap
26  {
27      // public: ................................................................
28      
29      // TODO: optimize key comparisons using key.hash == entry.key.hash condition
30  
31      /**
32       * Equivalent to <CODE>IntObjectMap(11, 0.75F)</CODE>.
33       */
34      public ObjectIntMap ()
35      {
36          this (11, 0.75F);
37      }
38      
39      /**
40       * Equivalent to <CODE>IntObjectMap(capacity, 0.75F)</CODE>.
41       */
42      public ObjectIntMap (final int initialCapacity)
43      {
44          this (initialCapacity, 0.75F);
45      }
46      
47      /**
48       * Constructs an IntObjectMap with specified initial capacity and load factor.
49       *
50       * @param initialCapacity initial number of hash buckets in the table [may not be negative, 0 is equivalent to 1].
51       * @param loadFactor the load factor to use to determine rehashing points [must be in (0.0, 1.0] range].
52       */
53      public ObjectIntMap (int initialCapacity, final float loadFactor)
54      {
55          if (initialCapacity < 0) throw new IllegalArgumentException   ("negative input: initialCapacity [" + initialCapacity + "]");
56          if ((loadFactor <= 0.0) || (loadFactor >= 1.0 + 1.0E-6))
57              throw new IllegalArgumentException   ("loadFactor not in (0.0, 1.0] range: " + loadFactor);
58          
59          if (initialCapacity == 0) initialCapacity = 1;
60          
61          m_loadFactor = loadFactor > 1.0 ? 1.0F : loadFactor;        
62          m_sizeThreshold = (int) (initialCapacity * loadFactor);
63          m_buckets = new Entry [initialCapacity];
64      }
65      
66      
67      /**
68       * Overrides Object.toString() for debug purposes.
69       */
70      public String   toString ()
71      {
72          final StringBuffer   s = new StringBuffer   ();
73          debugDump (s);
74          
75          return s.toString ();
76      }
77      
78      /**
79       * Returns the number of key-value mappings in this map.
80       */
81      public int size ()
82      {
83          return m_size;
84      }
85  
86      public boolean contains (final Object   key)
87      {
88          if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
89          
90          // index into the corresponding hash bucket:
91          final Entry [] buckets = m_buckets;
92          final int keyHash = key.hashCode ();
93          final int bucketIndex = (keyHash & 0x7FFFFFFF) % buckets.length;
94          
95          // traverse the singly-linked list of entries in the bucket:
96          for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
97          {
98              if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
99                  return true;
100         }
101         
102         return false;
103     }
104     
105     /**
106      * Returns the value that is mapped to a given 'key'. Returns
107      * false if this key has never been mapped.
108      *
109      * @param key mapping key [may not be null]
110      * @param out holder for the found value [must be at least of size 1]
111      *
112      * @return 'true' if this key was mapped to an existing value
113      */
114     public boolean get (final Object   key, final int [] out)
115     {
116         if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
117         
118         // index into the corresponding hash bucket:
119         final Entry [] buckets = m_buckets;
120         final int keyHash = key.hashCode ();
121         final int bucketIndex = (keyHash & 0x7FFFFFFF) % buckets.length;
122         
123         // traverse the singly-linked list of entries in the bucket:
124         for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
125         {
126             if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
127             {
128                 out [0] = entry.m_value;
129                 return true;
130             }
131         }
132         
133         return false;
134     }
135     
136     public Object   [] keys ()
137     {
138         final Object   [] result = new Object   [m_size];
139         int scan = 0;
140         
141         for (int b = 0; b < m_buckets.length; ++ b)
142         {
143             for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
144             {
145                 result [scan ++] = entry.m_key;
146             }
147         }
148         
149         return result;
150     }
151     
152     /**
153      * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
154      *
155      * @param key mapping key [may not be null]
156      * @param value mapping value.
157      */
158     public void put (final Object   key, final int value)
159     {
160         if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
161         
162         Entry currentKeyEntry = null;
163         
164         // detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]:
165         
166         // index into the corresponding hash bucket:
167         final int keyHash = key.hashCode ();
168         int bucketIndex = (keyHash & 0x7FFFFFFF) % m_buckets.length;
169         
170         // traverse the singly-linked list of entries in the bucket:
171         Entry [] buckets = m_buckets;
172         for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
173         {
174             if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
175             {
176                 currentKeyEntry = entry;
177                 break;
178             }
179         }
180         
181         if (currentKeyEntry != null)
182         {
183             // replace the current value:
184                 
185             currentKeyEntry.m_value = value;
186         }
187         else
188         {
189             // add a new entry:
190             
191             if (m_size >= m_sizeThreshold) rehash ();
192             
193             buckets = m_buckets;
194             bucketIndex = (keyHash & 0x7FFFFFFF) % buckets.length;
195             final Entry bucketListHead = buckets [bucketIndex];
196             final Entry newEntry = new Entry (key, value, bucketListHead);
197             buckets [bucketIndex] = newEntry;
198             
199             ++ m_size;
200         }
201     }
202     
203     /**
204      * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
205      *
206      * @param key mapping key [may not be null]
207      */
208     public void remove (final Object   key)
209     {
210         if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
211         
212         // index into the corresponding hash bucket:
213         final int keyHash = key.hashCode ();
214         final int bucketIndex = (keyHash  & 0x7FFFFFFF) % m_buckets.length;
215         
216         // traverse the singly-linked list of entries in the bucket:
217         Entry [] buckets = m_buckets;
218         for (Entry entry = buckets [bucketIndex], prev = entry; entry != null; )
219         {
220             final Entry next = entry.m_next;
221             
222             if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
223             {
224                 if (prev == entry)
225                     buckets [bucketIndex] = next;
226                 else
227                     prev.m_next = next;
228                 
229                 -- m_size;     
230                 break;
231             }
232             
233             prev = entry;
234             entry = next;
235         }
236     }
237 
238     
239     // protected: .............................................................
240 
241     // package: ...............................................................
242     
243     
244     void debugDump (final StringBuffer   out)
245     {
246         if (out != null)
247         {
248             out.append (super.toString ()); out.append (EOL);
249             out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
250             out.append ("size threshold = " + m_sizeThreshold + EOL);
251         }
252     }
253 
254     // private: ...............................................................
255 
256     
257     /**
258      * The structure used for chaining colliding keys.
259      */
260     private static final class Entry
261     {
262         Entry (final Object   key, final int value, final Entry next)
263         {
264             m_key = key; 
265             m_value = value;
266             m_next = next;
267         }
268         
269         Object   m_key;     // reference to the value [never null]
270         int m_value;
271         
272         Entry m_next; // singly-linked list link
273         
274     } // end of nested class
275     
276 
277     /**
278      * Re-hashes the table into a new array of buckets.
279      */
280     private void rehash ()
281     {
282         // TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
283         // and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
284         // only grow in size
285         
286         final Entry [] buckets = m_buckets;
287         
288         final int newBucketCount = (m_buckets.length << 1) + 1;
289         final Entry [] newBuckets = new Entry [newBucketCount];
290 
291         // rehash all entry chains in every bucket:
292         for (int b = 0; b < buckets.length; ++ b)
293         {
294             for (Entry entry = buckets [b]; entry != null; )
295             {
296                 final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry
297                 final int entryKeyHash = entry.m_key.hashCode () & 0x7FFFFFFF;
298             
299                 // index into the corresponding new hash bucket:
300                 final int newBucketIndex = entryKeyHash % newBucketCount;
301                 
302                 final Entry bucketListHead = newBuckets [newBucketIndex];
303                 entry.m_next = bucketListHead;
304                 newBuckets [newBucketIndex] = entry;                                
305                 
306                 entry = next;
307             }
308         }
309         
310 
311         m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
312         m_buckets = newBuckets;
313     }
314     
315     
316     private final float m_loadFactor; // determines the setting of m_sizeThreshold
317     
318     private Entry [] m_buckets; // table of buckets
319     private int m_size; // number of keys in the table, not cleared as of last check
320     private int m_sizeThreshold; // size threshold for rehashing
321         
322     private static final String   EOL = System.getProperty ("line.separator", "\n");
323     
324 } // end of class
325 // ----------------------------------------------------------------------------
326 
327
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags