IntIntMap


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