/**
 * (c) 2002 Spieleck
 */
package de.spieleck.util;

import java.io.Serializable;

import java.util.Dictionary;
import java.util.Enumeration;

/**
 * A more efficient version of <code>java.util.Hashtable</code>.
 * <P>
 * This is faster for the following reasons: <UL>
 * <LI>It is not synchronized.
 * <LI>It uses its own algorithm.
 * <LI>Methods are finalized and can get better optimized by the JVM.
 * <LI>It only performs allocation when the hash table is resized.
 * </UL>
 * The original source of this has been found in James Clark XP
 * SAXParser, but it has been improved and is even faster. This is 
 * achieved by better use of given arrays (by different load factor and
 * different usedLimit calculation).
 * <P>
 * <B>Note</B> within larger projekts this class might have secondary
 * benefits since it doesn't allocate objects unlike the
 * sun implementation of Hashtable and HashMap.
 * <P>
 * @author fsn
 * @version 1
 */
public class SpeedHashtable
 extends Dictionary
 implements Serializable
{
    private static final int INIT_SIZE = 5;
    private final static int HASHSTEP  = 5;

    /**
     * The array of entries and keys.
     * The first half of table contains the keys, the second half the values.
     * The value for a key at index i is at index i + capacity
     */
    private Object[] table;

    /** 
     * The current capacity of the array (half of table.length). 
     * This implementation requires capacity to be a power of 2.
     */
    protected int capacity;

    /** capacity - 1. */
    protected int capacity1;

    /** The actually number of used entries in the array. */
    protected int used;

    /** The load factor allowed by this table. */
    private double loadFactor;

    /** The limit where the table is resized (approx used * loadFactor). */
    private int usedLimit;

    /**
   * Creates a hash table with standard initial capacity.
   */
    public SpeedHashtable()
    {
        this(INIT_SIZE, 0.75);
    }

    /**
   * Creates a hash table with the specified initial capacity.
   */
    public SpeedHashtable(int n)
    {
        this(n, 0.75);
    }

    /**
   * Create hashtable with non standard load factor
   */
    public SpeedHashtable(double loadFactor)
    {
        this(INIT_SIZE, loadFactor);
    }

    /**
   * Create hashtable with non standard load factor and special size
   */
    public SpeedHashtable(int n, double loadFactor)
    {
        this.loadFactor = loadFactor;
        n               = (int)((n + 1) / loadFactor);
        int h           = 4;
        while (h < n)
            h += h;
        used = 0;
        internalInit(h);
    }

    /** Init the internal structures. */
    private final void internalInit(int size)
    {
        capacity  = size;
        capacity1 = size - 1;
        table     = new Object[size << 1];
        usedLimit = (int)(size * loadFactor);
    }

    public final int size()
    {
        return used;
    }

    public final boolean isEmpty()
    {
        return used == 0;
    }

    /**
   * Exploration strategy for the heap
   */
    private final int nextIndex(int i)
    {
        return i < HASHSTEP
                   ? capacity + i - HASHSTEP
                   : i - HASHSTEP;
    }

    /**
   * First hash index.
   * <P>
   * XXX: Note that if we could delay the & (capacity-1), we could
   * use the remaining bits of the hashCode for secondary of free 
   * spaces and could avoid that all elements travel along the same
   * way. But this would mean rather inconvenient changes in the whole
   * class and is proably outweight by the fact that we strictly leave
   * 25% of the spaces empty anyway.
   */
    private final int firstIndex(Object key)
    {
        return hashCode(key) & capacity1;
    }

    /**
   * This is a customization API to replace hashCode()
   * by more efficient methods.
   */
    protected int hashCode(Object key)
    {
        return key.hashCode();
    }

    /** This API is obviously useless :-) */
    public final boolean containsKey(Object key)
    {
        return get(key) != null;
    }

    /** This data allows nice threadunsafe optimizations. */
    protected int lastGetIndex;

    /** This data allows nice threadunsafe optimizations. */
    protected Object lastKey;

    public Object get(Object key)
    {
        if (key != null)
        {
            lastKey = key;
            int i = firstIndex(key);
            for (; table[i] != null; i = nextIndex(i))
                if (table[i].equals(key))
                {
                    lastGetIndex = i;
                    return table[i | capacity];
                }
            lastGetIndex = i;
        }
        return null;
    }

    public Object put(Object key, Object value)
    {
        if (value == null || key == null)
            throw new NullPointerException();

        return unsafePut(key, value);
    }

    /**
   * Slightly dirty solution to the double hash and search effect
   * in the (very common sequence):
   * <PRE>
   * SpeedHashtable fh = ...
   * Object something = fh.get(key);
   * if ( something ... )
   * {
   *   Object somethingdifferent = ...
   *   fh.put(key, somethingdifferent);
   * }
   * </PRE>
   * This can now be written more efficient as
   * <PRE>
   * Object something = fh.get(key);
   * if ( something ... )
   * {
   *   Object somethingdifferent = ...
   *   fh.replaceLastGet(somethingdifferent);
   * }
   * </PRE>
   * <B>Caution:</B> Due to rehashing can only be called once per get()!
   * This is not at all a thread safe mechanism
   */
    public Object replaceLastGet(Object value)
    {
        if (value == null)
            throw new NullPointerException();
        int h      = lastGetIndex | capacity;
        Object old = table[h];
        table[h]   = value;
        // New entries need some bookkeeping
        if (old == null)
        {
            table[lastGetIndex] = lastKey;
            if (++used > usedLimit)
                rehash();
        }
        return old;
    }

    /**
   * Internal Version of the putter, not as fail safe...
   */
    protected final Object unsafePut(Object key, Object value)
    {
        int h;
        for (h = firstIndex(key); table[h] != null; h = nextIndex(h))
            if (key.equals(table[h]))
            {
                h |= capacity;
                Object old = table[h];
                table[h] = value;

                return old;
            }

        // Not the below could be programmed shorter but slightly slower
        // if we first inserted and later on rehashed!
        if (++used > usedLimit)
        {
            rehash();
            for (h = firstIndex(key);
                 table[h] != null;
                 h = nextIndex(h))
                ;
        }
        table[h]            = key;
        table[h | capacity] = value;

        return null;
    }

    /**
   * Rehash the table to a larger size
   */
    private final void rehash()
    {
        int j;
        int oldCap = capacity;
        Object[] oTable = table;
        internalInit(capacity * 2);
        for (int i = oldCap; i > 0;)
        {
            if (oTable[--i] != null)
            {
                for (j = firstIndex(oTable[i]);
                     table[j] != null;
                     j = nextIndex(j))
                    ;
                table[j]            = oTable[i];
                table[j | capacity] = oTable[i | oldCap];
            }
        }
    }

    /**
   * Append contents from another SpeedHashtable.
   * <P>XXX Could be a bit more optimized and avoid the tab2.get() ...
   */
    public void append(SpeedHashtable tab2)
    {
        Enumeration en = tab2.keys();
        while (en.hasMoreElements())
        {
            Object key = en.nextElement();
            unsafePut(key, tab2.get(key));
        }
    }

    /**
   * Removes the object with the specified key from the table.
   * Returns the object removed or null if there was no such object
   * in the table.
   */
    public Object remove(Object key)
    {
        if (used > 0)
        {
            for (int i = firstIndex(key);
                table[i] != null;
                i = nextIndex(i))
                if (table[i].equals(key))
                {
                    Object obj = table[i];
                    do
                    {
                        table[i]            = null;
                        table[i | capacity] = null;
                        int j               = i;
                        int r;
                        do
                        {
                            i = nextIndex(i);
                            if (table[i] == null)
                                break;
                            r = firstIndex(table[i]);
                        }
                        while ((i <= r && r < j) || (r < j && j < i)
                               || (j < i && i <= r));
                        table[j] = table[i];
                        table[j | capacity] = table[i | capacity];
                    }
                    while (table[i] != null);
                    --used;

                    return obj;
                }
        }

        return null;
    }

    /** 
   * Snapshot hashtable keys.
   * <P>Looks like the fastest way to get fairly safe access to
   * many keys in a fast changing SpeedHashtable.
   * Still not synchronized according to SpeedHashtable principle,
   * but obviously meaningless when certain changes happen in
   * background.
   */
    public Object[] getKeySnap()
    {
        // Internal snapshot to decrease likelihood of problems when
        // container gets restructured...
        Object[] tab = table;
        int used     = this.used;
        Object[] res = new Object[used];
        for (int i = capacity, j = 0; j < used && i > 0;)
            if (tab[--i] != null)
                res[j++] = tab[i];
        return res;
    }

    /** 
   * Snapshot hashtable elements.
   * @see #getKeySnap()
   */
    public Object[] getElementSnap()
    {
        Object[] tab = table;
        int used = this.used;
        Object[] res = new Object[used];
        for (int i = capacity, j = 0; j < used && i < table.length;)
            if (tab[i] != null)
                res[j++] = tab[i++];
        return res;
    }

    /**
   * Removes all objects from the hash table, so that the hash table
   * becomes empty.
   */
    public void clear()
    {
        int i = capacity;
        // Note table[i | capacity ] = null is not needed for the Hashtable
        // to work, but for the GC to realize the object can be freed!!!!
        while (--i >= 0)
            table[i] = table[i | capacity] = null;
        used = 0;
    }

    public Enumeration keys()
    {
        return new Enumerator(table, 0);
    }

    public Enumeration elements()
    {
        return new Enumerator(table, capacity);
    }

    private static class Enumerator
     implements Enumeration
    {
        private final Object[] table;
        private final int offset;
        private int i;

        Enumerator(Object[] table, int offset)
        {
            this.table  = table;
            this.offset = offset;
            if (table == null)
                i = -1;
            else
            {
                i = (table.length >> 1);
                skip();
            }
        }

        private final void skip()
        {
            while (--i >= 0 && table[i] == null)
                ;
        }

        public boolean hasMoreElements()
        {
            return i >= 0;
        }

        public Object nextElement()
        {
            if (i < 0)
                throw new java.util.NoSuchElementException();
            Object result = table[i + offset];
            skip();

            return result;
        }
    }
}