// Copyright (c) 1996-2002 Brian D. Carlstrom

package bdc.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
    A version of Hashtable that requires no synchronization, at the
    cost of not allowing entries to be removed.

    Specifically:
    <UL>

    <LI>Only has methods for querying and puting elements. There is no
    ability to remove an element.

    <LI>Has synchronization built in to allow the following:

    <OL>

    <LI>No synchronization is necessary (either internally or
    externally) on get() operations

    <LI>The put() method is internally synchronized on the this ref.
    If the program is not concerned about which object ends up in the
    table after two concurrent puts, no additional synchronization is
    needed. But if a program desires to ensure that only one is
    entered, external synchronization can be done on the object to
    allow synchronization between a retry of a failed get and a put.
    See the bdc.util.InternCharToString for an example of this.
    </OL>

    <LI>I believe that a clear() method could also be added without
    requiring synchronization, however I do not have the time to
    validate this.
    </UL>
*/
public class GrowOnlyHashtable
{
    private class Storage
    {
        int count;
        int totalCount;
        int shift;
        int capacity;
        int indexMask;

        Object keys[];
        Object elements[];
        public Storage ()
        {
        }
        public Storage (Storage o)
        {
            count = o.count;
            totalCount = o.totalCount;
            shift = o.shift;
            capacity = o.capacity;
            indexMask = o.indexMask;
        }
    }
    private Storage storage = new Storage();

    private static final int MaxStringLen = 254;

    /**
        For the multiplicative hash, choose the golden ratio.
        That is:
        <pre>
            A = ((sqrt(5) - 1) / 2) * (1 << 32)
        </pre>
        ala Knuth&hellip;
    */
    static final int A = 0x9e3779b9;

    static final String keysField = "keys";
    static final String elementsField = "elements";

    static final int DefaultSize = 4;

    static final Object DeletedMarker = new Object();

    /**
        Constructs an empty Hashtable. The Hashtable will grow on demand
        as more elements are added.
    */
    public GrowOnlyHashtable ()
    {
        super();
        storage.shift = 32 - MathUtil.log2(DefaultSize) + 1;
    }

    /**
        Constructs a Hashtable capable of holding at least
        <b>initialCapacity</b> elements before needing to grow.
    */
    public GrowOnlyHashtable (int initialCapacity)
    {
        this();

        if (initialCapacity < 0) {
            throw new IllegalArgumentException("initialCapacity must be >= 0");
        }

        grow(initialCapacity);
    }

    /**
        Returns the number of elements in the GrowOnlyHashtable.
    */
    public int count ()
    {
        Storage tmpStorage = storage;
        return tmpStorage.count;
    }

    /**
        Returns the number of elements in the GrowOnlyHashtable.
    */
    public int size ()
    {
        return count();
    }

    /**
        Returns <b>true</b> if there are no elements in the GrowOnlyHashtable.
    */
    public boolean isEmpty ()
    {
        return (count() == 0);
    }


    /**
        Returns <b>true</b> if the GrowOnlyHashtable contains the
        element. This method is slow -- O(n) -- because it must scan
        the table searching for the element.
    */
    public boolean contains (Object element)
    {
        int i;
        Object tmp;
        Storage tmpStorage = storage;
        // We need to short-circuit here since the data arrays may not have
        // been allocated yet.

        if (tmpStorage.count == 0) {
            return false;
        }

        if (element == null) {
            throw new NullPointerException();
        }

        if (tmpStorage.elements == null) {
            return false;
        }

        for (i = 0; i < tmpStorage.elements.length; i++) {
            tmp = tmpStorage.elements[i];
            if (tmp != null && tmp != DeletedMarker && element.equals(tmp)) {
                return true;
            }
        }

        return false;
    }

    /**
        Returns <b>true</b> if the GrowOnlyHashtable contains the key
        <b>key</b>.
    */
    public boolean containsKey (Object key)
    {
        return (get(key) != null);
    }

    /**
        Returns the element associated with the <b>key</b>. This
        method returns <b>null</b> if the GrowOnlyHashtable does not
        contain <b>key</b>.  GrowOnlyHashtable hashes and compares
        <b>key</b> using <b>hashCode()</b> and <b>equals()</b>.
    */
    public Object get (Object key)
    {
        // We need to short-circuit here since the data arrays may not have
        // been allocated yet.
        Storage tmpStorage = storage;
        if (tmpStorage.count == 0) {
            return null;
        }
        int index = tableIndexFor(tmpStorage, key, true);
        if (index == -1) {
            return null;
        }
        Object element = tmpStorage.elements[index];
        return (element == DeletedMarker)  ? null : element;
    }


    /**
        Places the <b>key</b>/<b>element</b> pair in the
        GrowOnlyHashtable. Neither <b>key</b> nor <b>element</b> may
        be <b>null</b>. Returns the old element associated with
        <b>key</b>, or <b>null</b> if the <b>key</b> was not present.
    */
    public Object put (Object key, Object element)
    {
        if (element == null) {
            throw new NullPointerException();
        }
        synchronized (this) {

                // Since we delay allocating the data arrays until we
                // actually need them, check to make sure they exist
                // before attempting to put something in them.

            if (storage.keys == null) {
                grow();
            }

            int index = tableIndexFor(storage, key, false);
            Object oldValue = storage.elements[index];

                // If the total number of occupied slots (either with
                // a real element or a removed marker) gets too big,
                // grow the table.

            if (oldValue == null || oldValue == DeletedMarker) {
                if (oldValue != DeletedMarker) {
                    if (storage.totalCount >= storage.capacity) {
                        grow();
                        return put(key, element);
                    }
                    storage.totalCount++;
                }
                storage.count++;
            }
                // put element first, so other methods can check for
                // key, and if the key exists, they know the element
                // is valid

            storage.elements[index] = element;
            storage.keys[index] = key;

            return (oldValue == DeletedMarker) ? null : oldValue;
        }
    }

    protected int getHashValueForObject (Object o)
    {
        return o.hashCode();
    }

    protected boolean objectsAreEqualEnough (Object obj1, Object obj2)
    {
            // Looking at the implimentation of visualcafe 1.1 and sun
            // String.equals() isn't smart enough to avoid full
            // compares when strings are pointer eq. (HP does)
        if (obj1 == obj2) {
            return true;
        }
        return obj1.equals(obj2);
    }

    /**
        Primitive method used internally to find slots in the table.
        If the key is present in the table, this method will return
        the index under which it is stored. If the key is not present,
        then this method will return the index under which it can be
        put. The caller must look at the hashCode at that index to
        differentiate between the two possibilities.
    */
    private int tableIndexFor (Storage tmpStorage,
                               Object key,
                               boolean failIfNoObject)
    {
        int hash = getHashValueForObject(key);
        int product = hash * A;
        int index = product >>> tmpStorage.shift;

        // Probe the first slot in the table.  We keep track of the first
        // index where we found a REMOVED marker so we can return that index
        // as the first available slot if the key is not already in the table.

        Object oldKey = tmpStorage.keys[index];
        if (oldKey == null || objectsAreEqualEnough(key, oldKey)) {
            return index;
        }

        int removedIndex = (oldKey == DeletedMarker) ? index : -1;

        // Our first probe has failed, so now we need to start looking
        // elsewhere in the table.

        int step = ((product >>> (2 * tmpStorage.shift - 32)) &
                    tmpStorage.indexMask) | 1;
        int probeCount = 1;
        do {
            probeCount++;
            index = (index + step) & tmpStorage.indexMask;

            Object testKey = tmpStorage.keys[index];
            if (testKey == null) {
                if (failIfNoObject) {
                    return -1;
                }
                if (removedIndex < 0) {
                    return index;
                }
                return removedIndex;
            }
            else if (objectsAreEqualEnough(key, testKey)) {
                return index;
            }
            else if (testKey == DeletedMarker && removedIndex == -1) {
                removedIndex = index;
            }

        }
        while (probeCount <= tmpStorage.totalCount);

        // Something very bad has happened.

        Assert.that(false, "GrowOnlyHashtable overflow");
        return -1;
    }

    /**
        Grows the table to accommodate at least capacity number of
        elements. Since this is only called from the constructor,
        don't need to worry about synchronization with the shift
        element of the storage.
    */
    private void grow (int capacity)
    {
        int tableSize, power;

        // Find the lowest power of 2 size for the table which will allow
        // us to insert initialCapacity number of objects before having to
        // grow.

        tableSize = (capacity * 4) / 3;

        power = 3;
        while ((1 << power) < tableSize)
            power++;

        // Once shift is set, then grow() will do the right thing when
        // called.

        storage.shift = 32 - power + 1;
        grow();
    }

    /**
        Grows the table by a factor of 2 (or creates it if necessary).
        All the REMOVED markers go away and the elements are rehashed
        into the bigger table.
    */
    private void grow ()
    {
        Storage tmpStorage = storage;
        Storage newStorage = new Storage(tmpStorage);

        int count = tmpStorage.count;
        // The table size needs to be a power of two, and it should double
        // when it grows.  We grow when we are more than 3/4 full.

        newStorage.shift--;
        int power = 32 - newStorage.shift;
        newStorage.indexMask = (1 << power) - 1;
        newStorage.capacity = (3 * (1 << power)) / 4;

        Object[] oldKeys = tmpStorage.keys;
        Object[] oldValues = tmpStorage.elements;

        newStorage.keys = new Object[1 << power];
        newStorage.elements = new Object[1 << power];

        // Reinsert the old elements into the new table if there are any.  Be
        // sure to reset the counts and increment them as the old entries are
        // put back in the table.

        newStorage.totalCount = 0;

        if (count > 0) {
            count = 0;

            for (int i = 0; i < oldKeys.length; i++) {
                Object key = oldKeys[i];

                if (key != null && key != DeletedMarker) {
                    int index = tableIndexFor(newStorage, key, false);

                    newStorage.keys[index] = key;
                    newStorage.elements[index] = oldValues[i];

                    count++;
                    newStorage.totalCount++;
                }
            }
        }
        newStorage.count = count;
        storage = newStorage;
    }
    
    /**
        Returns a List containing the Hashtable's keys.
    */
    public List keysList ()
    {
        int i, listCount;
        Object key;
        List list;

        Storage tmpStorage = storage;
        int count = tmpStorage.count;
        
        if (count == 0) {
            return new ArrayList();
        }

        list = new ArrayList(count);
        listCount = 0;

        Object keys[] = tmpStorage.keys;
        
        for (i = 0; i < keys.length && listCount < count; i++) {
            key = keys[i];
            if (key != null && key != DeletedMarker) {
                list.add(key);
                listCount++;
            }
        }

        return list;
    }

    public String toString ()
    {
        Storage tmpStorage = storage;
        HashMap output = new HashMap(tmpStorage.count);
        Object keys[] = tmpStorage.keys;
        Object values[] = tmpStorage.elements;
        for (int i=0; i<keys.length; i++) {
            Object key = keys[i];
            if (key != null && key != DeletedMarker) {
                output.put(key, values[i]);
            }
        }
        return output.toString();
    }
}