FileDocCategorySizeDatePackage
ObjectIntMap.javaAPI DocAndroid 1.5 API10994Wed May 06 22:41:16 BST 2009com.vladium.util

ObjectIntMap

public final class ObjectIntMap extends Object
MT-safety: an instance of this class is not safe for access from multiple concurrent threads [even if access is done by a single thread at a time]. The caller is expected to synchronize externally on an instance [the implementation does not do internal synchronization for the sake of efficiency]. java.util.ConcurrentModificationException is not supported either.
author
(C) 2001, Vlad Roubtsov

Fields Summary
private final float
m_loadFactor
private Entry[]
m_buckets
private int
m_size
private int
m_sizeThreshold
private static final String
EOL
Constructors Summary
public ObjectIntMap()
Equivalent to IntObjectMap(11, 0.75F).

        this (11, 0.75F);
public ObjectIntMap(int initialCapacity)
Equivalent to IntObjectMap(capacity, 0.75F).

        this (initialCapacity, 0.75F);
public ObjectIntMap(int initialCapacity, float loadFactor)
Constructs an IntObjectMap with specified initial capacity and load factor.

param
initialCapacity initial number of hash buckets in the table [may not be negative, 0 is equivalent to 1].
param
loadFactor the load factor to use to determine rehashing points [must be in (0.0, 1.0] range].

        if (initialCapacity < 0) throw new IllegalArgumentException ("negative input: initialCapacity [" + initialCapacity + "]");
        if ((loadFactor <= 0.0) || (loadFactor >= 1.0 + 1.0E-6))
            throw new IllegalArgumentException ("loadFactor not in (0.0, 1.0] range: " + loadFactor);
        
        if (initialCapacity == 0) initialCapacity = 1;
        
        m_loadFactor = loadFactor > 1.0 ? 1.0F : loadFactor;        
        m_sizeThreshold = (int) (initialCapacity * loadFactor);
        m_buckets = new Entry [initialCapacity];
Methods Summary
public booleancontains(java.lang.Object key)

        if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
        
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int keyHash = key.hashCode ();
        final int bucketIndex = (keyHash & 0x7FFFFFFF) % buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
                return true;
        }
        
        return false;
voiddebugDump(java.lang.StringBuffer out)

        if (out != null)
        {
            out.append (super.toString ()); out.append (EOL);
            out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
            out.append ("size threshold = " + m_sizeThreshold + EOL);
        }
public booleanget(java.lang.Object key, int[] out)
Returns the value that is mapped to a given 'key'. Returns false if this key has never been mapped.

param
key mapping key [may not be null]
param
out holder for the found value [must be at least of size 1]
return
'true' if this key was mapped to an existing value

        if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
        
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int keyHash = key.hashCode ();
        final int bucketIndex = (keyHash & 0x7FFFFFFF) % buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
            {
                out [0] = entry.m_value;
                return true;
            }
        }
        
        return false;
public java.lang.Object[]keys()

        final Object [] result = new Object [m_size];
        int scan = 0;
        
        for (int b = 0; b < m_buckets.length; ++ b)
        {
            for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
            {
                result [scan ++] = entry.m_key;
            }
        }
        
        return result;
public voidput(java.lang.Object key, int value)
Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.

param
key mapping key [may not be null]
param
value mapping value.

        if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
        
        Entry currentKeyEntry = null;
        
        // detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]:
        
        // index into the corresponding hash bucket:
        final int keyHash = key.hashCode ();
        int bucketIndex = (keyHash & 0x7FFFFFFF) % m_buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        Entry [] buckets = m_buckets;
        for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
            {
                currentKeyEntry = entry;
                break;
            }
        }
        
        if (currentKeyEntry != null)
        {
            // replace the current value:
                
            currentKeyEntry.m_value = value;
        }
        else
        {
            // add a new entry:
            
            if (m_size >= m_sizeThreshold) rehash ();
            
            buckets = m_buckets;
            bucketIndex = (keyHash & 0x7FFFFFFF) % buckets.length;
            final Entry bucketListHead = buckets [bucketIndex];
            final Entry newEntry = new Entry (key, value, bucketListHead);
            buckets [bucketIndex] = newEntry;
            
            ++ m_size;
        }
private voidrehash()
Re-hashes the table into a new array of buckets.

        // TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
        // and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
        // only grow in size
        
        final Entry [] buckets = m_buckets;
        
        final int newBucketCount = (m_buckets.length << 1) + 1;
        final Entry [] newBuckets = new Entry [newBucketCount];

        // rehash all entry chains in every bucket:
        for (int b = 0; b < buckets.length; ++ b)
        {
            for (Entry entry = buckets [b]; entry != null; )
            {
                final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry
                final int entryKeyHash = entry.m_key.hashCode () & 0x7FFFFFFF;
            
                // index into the corresponding new hash bucket:
                final int newBucketIndex = entryKeyHash % newBucketCount;
                
                final Entry bucketListHead = newBuckets [newBucketIndex];
                entry.m_next = bucketListHead;
                newBuckets [newBucketIndex] = entry;                                
                
                entry = next;
            }
        }
        

        m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
        m_buckets = newBuckets;
public voidremove(java.lang.Object key)
Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.

param
key mapping key [may not be null]

        if ($assert.ENABLED) $assert.ASSERT (key != null, "null input: key");
        
        // index into the corresponding hash bucket:
        final int keyHash = key.hashCode ();
        final int bucketIndex = (keyHash  & 0x7FFFFFFF) % m_buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        Entry [] buckets = m_buckets;
        for (Entry entry = buckets [bucketIndex], prev = entry; entry != null; )
        {
            final Entry next = entry.m_next;
            
            if ((keyHash == entry.m_key.hashCode ()) || entry.m_key.equals (key))
            {
                if (prev == entry)
                    buckets [bucketIndex] = next;
                else
                    prev.m_next = next;
                
                -- m_size;     
                break;
            }
            
            prev = entry;
            entry = next;
        }
public intsize()
Returns the number of key-value mappings in this map.

        return m_size;
public java.lang.StringtoString()
Overrides Object.toString() for debug purposes.

        final StringBuffer s = new StringBuffer ();
        debugDump (s);
        
        return s.toString ();