KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > vladium > util > IntObjectMap


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: IntObjectMap.java,v 1.1.1.1 2004/05/09 16:57:53 vlad_r Exp $
8  */

9 package com.vladium.util;
10
11 import java.io.Serializable JavaDoc;
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 Vlad Roubtsov, (C) 2001
23  */

24 public
25 final class IntObjectMap implements Serializable JavaDoc
26 {
27     // public: ................................................................
28

29     /**
30      * Equivalent to <CODE>IntObjectMap(11, 0.75F)</CODE>.
31      */

32     public IntObjectMap ()
33     {
34         this (11, 0.75F);
35     }
36     
37     /**
38      * Equivalent to <CODE>IntObjectMap(capacity, 0.75F)</CODE>.
39      */

40     public IntObjectMap (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 IntObjectMap (int initialCapacity, final float loadFactor)
52     {
53         if (initialCapacity < 0) throw new IllegalArgumentException JavaDoc ("negative input: initialCapacity [" + initialCapacity + "]");
54         if ((loadFactor <= 0.0) || (loadFactor >= 1.0 + 1.0E-6))
55             throw new IllegalArgumentException JavaDoc ("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 JavaDoc toString ()
69     {
70         final StringBuffer JavaDoc s = new StringBuffer JavaDoc ();
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)
94                 return true;
95         }
96         
97         return false;
98     }
99     
100     /**
101      * Returns the value that is mapped to a given 'key'. Returns
102      * null if (a) this key has never been mapped or (b) it has been
103      * mapped to a null value.
104      *
105      * @param key mapping key
106      *
107      * @return Object value mapping for 'key' [can be null].
108      */

109     public Object JavaDoc get (final int key)
110     {
111         // index into the corresponding hash bucket:
112
final Entry [] buckets = m_buckets;
113         final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
114         
115         // traverse the singly-linked list of entries in the bucket:
116
for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
117         {
118             if (key == entry.m_key)
119                 return entry.m_value;
120         }
121         
122         return null;
123     }
124     
125     public int [] keys ()
126     {
127         if (m_size == 0)
128             return IConstants.EMPTY_INT_ARRAY;
129         else
130         {
131             final int [] result = new int [m_size];
132             int scan = 0;
133             
134             for (int b = 0; b < m_buckets.length; ++ b)
135             {
136                 for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
137                 {
138                     result [scan ++] = entry.m_key;
139                 }
140             }
141             
142             return result;
143         }
144     }
145     
146     /**
147      * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
148      *
149      * @param key mapping key
150      * @param value mapping value [can be null].
151      *
152      * @return Object previous value mapping for 'key' [can be null]
153      */

154     public Object JavaDoc put (final int key, final Object JavaDoc value)
155     {
156         Entry currentKeyEntry = null;
157         
158         // detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]:
159

160         // index into the corresponding hash bucket:
161
int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length;
162         
163         // traverse the singly-linked list of entries in the bucket:
164
Entry [] buckets = m_buckets;
165         for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
166         {
167             if (key == entry.m_key)
168             {
169                 currentKeyEntry = entry;
170                 break;
171             }
172         }
173         
174         if (currentKeyEntry != null)
175         {
176             // replace the current value:
177

178             final Object JavaDoc currentKeyValue = currentKeyEntry.m_value;
179             currentKeyEntry.m_value = value;
180             
181             return currentKeyValue;
182         }
183         else
184         {
185             // add a new entry:
186

187             if (m_size >= m_sizeThreshold) rehash ();
188             
189             buckets = m_buckets;
190             bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
191             final Entry bucketListHead = buckets [bucketIndex];
192             final Entry newEntry = new Entry (key, value, bucketListHead);
193             buckets [bucketIndex] = newEntry;
194             
195             ++ m_size;
196             
197             return null;
198         }
199     }
200     
201     // protected: .............................................................
202

203     // package: ...............................................................
204

205     
206     void debugDump (final StringBuffer JavaDoc out)
207     {
208         if (out != null)
209         {
210             out.append (super.toString ()); out.append (EOL);
211             out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
212             out.append ("size threshold = " + m_sizeThreshold + EOL);
213         }
214     }
215
216     // private: ...............................................................
217

218     
219     /**
220      * The structure used for chaining colliding keys.
221      */

222     private static final class Entry implements Serializable JavaDoc
223     {
224         Entry (final int key, final Object JavaDoc value, final Entry next)
225         {
226             m_key = key;
227             m_value = value;
228             m_next = next;
229         }
230         
231         Object JavaDoc m_value; // reference to the value [never null]
232
final int m_key;
233         
234         Entry m_next; // singly-linked list link
235

236     } // end of nested class
237

238
239     /**
240      * Re-hashes the table into a new array of buckets.
241      */

242     private void rehash ()
243     {
244         // TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
245
// and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
246
// only grow in size
247

248         final Entry [] buckets = m_buckets;
249         
250         final int newBucketCount = (m_buckets.length << 1) + 1;
251         final Entry [] newBuckets = new Entry [newBucketCount];
252
253         // rehash all entry chains in every bucket:
254
for (int b = 0; b < buckets.length; ++ b)
255         {
256             for (Entry entry = buckets [b]; entry != null; )
257             {
258                 final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry
259
final int entryKey = entry.m_key;
260             
261                 // index into the corresponding new hash bucket:
262
final int newBucketIndex = (entryKey & 0x7FFFFFFF) % newBucketCount;
263                 
264                 final Entry bucketListHead = newBuckets [newBucketIndex];
265                 entry.m_next = bucketListHead;
266                 newBuckets [newBucketIndex] = entry;
267                 
268                 entry = next;
269             }
270         }
271         
272
273         m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
274         m_buckets = newBuckets;
275     }
276     
277     
278     private final float m_loadFactor; // determines the setting of m_sizeThreshold
279

280     private Entry [] m_buckets; // table of buckets
281
private int m_size; // number of keys in the table, not cleared as of last check
282
private int m_sizeThreshold; // size threshold for rehashing
283

284     private static final String JavaDoc EOL = System.getProperty ("line.separator", "\n");
285     
286 } // end of class
287
// ----------------------------------------------------------------------------
288

289
Popular Tags