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 */
9package com.vladium.util;
10
11import java.io.Serializable;
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 */
24public
25final class IntObjectMap implements Serializable
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 ("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)
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 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 put (final int key, final Object 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 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 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
223    {
224        Entry (final int key, final Object value, final Entry next)
225        {
226            m_key = key;
227            m_value = value;
228            m_next = next;
229        }
230
231        Object 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 EOL = System.getProperty ("line.separator", "\n");
285
286} // end of class
287// ----------------------------------------------------------------------------
288
289