vladium/util/IntIntMap.java

/* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
 *
 * This program and the accompanying materials are made available under
 * the terms of the Common Public License v1.0 which accompanies this distribution,
 * and is available at http://www.eclipse.org/legal/cpl-v10.html
 *
 * $Id: IntIntMap.java,v 1.1.1.1 2004/05/09 16:57:53 vlad_r Exp $
 */
package com.vladium.util;

// ----------------------------------------------------------------------------
/**
 *
 * MT-safety: an instance of this class is <I>not</I> 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 Vlad Roubtsov, (C) 2001
 */
public
final class IntIntMap
{
    // public: ................................................................

    // TODO: optimize key comparisons using key.hash == entry.key.hash condition

    /**
     * Equivalent to <CODE>IntObjectMap(11, 0.75F)</CODE>.
     */
    public IntIntMap ()
    {
        this (11, 0.75F);
    }

    /**
     * Equivalent to <CODE>IntObjectMap(capacity, 0.75F)</CODE>.
     */
    public IntIntMap (final int initialCapacity)
    {
        this (initialCapacity, 0.75F);
    }

    /**
     * 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].
     */
    public IntIntMap (int initialCapacity, final float loadFactor)
    {
        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];
    }


    /**
     * Overrides Object.toString() for debug purposes.
     */
    public String toString ()
    {
        final StringBuffer s = new StringBuffer ();
        debugDump (s);

        return s.toString ();
    }

    /**
     * Returns the number of key-value mappings in this map.
     */
    public int size ()
    {
        return m_size;
    }

    public boolean contains (final int key)
    {
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int bucketIndex = (key & 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 (key == entry.m_key) return true;
        }

        return false;
    }

    /**
     * Returns the value that is mapped to a given 'key'. Returns
     * false if this key has never been mapped.
     *
     * @param key mapping key
     * @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
     */
    public boolean get (final int key, final int [] out)
    {
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int bucketIndex = (key & 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 (key == entry.m_key)
            {
                out [0] = entry.m_value;
                return true;
            }
        }

        return false;
    }

    public boolean get (final int key, final int [] out, final int index)
    {
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int bucketIndex = (key & 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 (key == entry.m_key)
            {
                out [index] = entry.m_value;
                return true;
            }
        }

        return false;
    }

    public int [] keys ()
    {
        final int [] result = new int [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;
    }

    /**
     * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
     *
     * @param key mapping key
     * @param value mapping value
     */
    public void put (final int key, final int value)
    {
        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:
        int bucketIndex = (key & 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 (key == entry.m_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 = (key & 0x7FFFFFFF) % buckets.length;
            final Entry bucketListHead = buckets [bucketIndex];
            final Entry newEntry = new Entry (key, value, bucketListHead);
            buckets [bucketIndex] = newEntry;

            ++ m_size;
        }
    }

    /**
     * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
     *
     * @param key mapping key
     */
    public void remove (final int key)
    {
        // index into the corresponding hash bucket:
        final int bucketIndex = (key  & 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 (key == entry.m_key)
            {
                if (prev == entry)
                    buckets [bucketIndex] = next;
                else
                    prev.m_next = next;

                -- m_size;
                break;
            }

            prev = entry;
            entry = next;
        }
    }


    // protected: .............................................................

    // package: ...............................................................


    void debugDump (final 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);
        }
    }

    // private: ...............................................................


    /**
     * The structure used for chaining colliding keys.
     */
    private static final class Entry
    {
        Entry (final int key, final int value, final Entry next)
        {
            m_key = key;
            m_value = value;
            m_next = next;
        }

        int m_key;
        int m_value;

        Entry m_next; // singly-linked list link

    } // end of nested class


    /**
     * Re-hashes the table into a new array of buckets.
     */
    private void rehash ()
    {
        // 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 & 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;
    }


    private final float m_loadFactor; // determines the setting of m_sizeThreshold

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

    private static final String EOL = System.getProperty ("line.separator", "\n");

} // end of class
// ----------------------------------------------------------------------------