/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.db.procore.cluster;

import gnu.trove.impl.PrimeFinder;

import org.simantics.db.exception.DatabaseException;
import org.simantics.db.impl.ClusterI;
import org.simantics.db.impl.IntAllocatorI;
import org.simantics.db.impl.Modifier;

final class IntHash2 extends IntHashTrait {
    static final int HeaderSize = 4;
    private static final int REAL_SIZE = -4; // Number of allocated slots.
    private static final int USED_SIZE = -3; // Number of used slots.
    private static final int FREE_SIZE = -2; // Number of free slots.
    private static final int MAX_SIZE = -1; // Max number of used slots.

    public static int getRealSize(int[] table, int hashBase) {
        return table[hashBase + REAL_SIZE];
    }

    private static void setRealSize(int[] table, int hashBase, int realSize) {
        assert(realSize > 0);
        table[hashBase + REAL_SIZE] = realSize;
    }

    public static int getUsedSize(int[] table, int hashBase) {
        return table[hashBase + USED_SIZE];
    }

    static void setUsedSize(int[] table, int hashBase, int usedSize) {
        assert(usedSize >= 0);
        table[hashBase + USED_SIZE] = usedSize;
    }

    // return value after decrement
    static int decUsedSize(int[] table, int hashBase) {
        table[hashBase + USED_SIZE] -= 1;
        return table[hashBase + USED_SIZE];
    }

    // return value after increment
    static int incUsedSize(int[] table, int hashBase) {
        table[hashBase + USED_SIZE] += 1;
        return table[hashBase + USED_SIZE];
    }
    static void setUsedAndRealSize(int[] table, int hashBase, int used, int real) {
        setUsedSize(table, hashBase, used);
        setRealSize(table, hashBase, real);
    }
    static int getFreeSize(int[] table, int hashBase) {
        return table[hashBase + FREE_SIZE];
    }

    static void setFreeSize(int[] table, int hashBase, int freeSize) {
        assert(freeSize >= 0);
        table[hashBase + FREE_SIZE] = freeSize;
    }

    static void decFreeSize(int[] table, int hashBase) {
        table[hashBase + FREE_SIZE] -= 1;
    }
    
    static int getMaxSize(int[] table, int hashBase) {
        return table[hashBase + MAX_SIZE];
    }

    static void setMaxSize(int[] table, int hashBase, int maxSize) {
        assert(maxSize > 0);
        table[hashBase + MAX_SIZE] = maxSize;
    }
    
    static void setMaxAndFreeSize(int[] table, int hashBase, int max, int free) {
        setMaxSize(table, hashBase, max);
        setFreeSize(table, hashBase, free);
    }

    public static int getAllocatedSize(int[] table, int hashBase) {
        return getRealSize(table, hashBase)*2 + HeaderSize;
    }
    public static int create(int[] keys, int[] vals, IntAllocatorI allocator) {
        assert(keys.length > 0);
        assert(keys.length == vals.length);
        int desiredSize = keys.length;
        int hashBase = create(desiredSize, allocator);
        for (int i=0; i<desiredSize; ++i)
            hashBase = add(allocator.getTable(), hashBase, keys[i], vals[i], allocator);
        return hashBase;
    }
    private static int create(int desiredSize, IntAllocatorI allocator) {
        int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);
        int hashBase = allocator.allocate(capacity*2 + HeaderSize) + HeaderSize;
        int[] table = allocator.getTable();
        setUsedAndRealSize(table, hashBase, 0, capacity);
        setMaxAndFreeSize(table, hashBase, capacity >> 1, capacity);
        return hashBase;
    }
    public static int add(int[] table, int hashBase, int key, int val, IntAllocatorI allocator) {
        assert(isFull(key));
        int index = insertionIndex(table, hashBase, key);
        if (index < 0) {
            int realIndex = -index;
            assert(table[realIndex] == key);
            if (table[realIndex+1] == val)
                return 0; // value not modified
            table[realIndex+1] = val;
            return hashBase; // value modified
        }
        int previousState = table[index];
        table[index] = key;
        table[index+1] = val;
        return postInsertHook(table, hashBase, isFree(previousState), allocator);
    }

    public static boolean remove(int[] table, int hashBase, int a) {
        int index = index(table, hashBase, a);
        if (index >= 0) {
            table[index] = setRemoved();
            table[index+1] = setFree();
            decUsedSize(table, hashBase);
            return true; // yes, we removed something
        }
        return false; // not in set, nothing to remove
    }

    public static int get(int[] table, int hashBase, int a) {
        int index = index(table, hashBase, a);
        if (index < 0)
            return setFree();
        return table[index+1];
    }

    public static boolean contains(int[] table, int hashBase, int a) {
        return index(table, hashBase, a) >= 0;
    }

    public static boolean isEmpty(int[] table, int hashBase) {
        return 0 == getUsedSize(table, hashBase);
    }

    public static void clear(int[] table, int hashBase) {
        int[] set = table;
        int free = setFree();
        int capacity = getRealSize(table, hashBase);
        for (int i = hashBase + capacity*2; i-- > hashBase;) {
            set[i] = free;
        }
        setUsedSize(table, hashBase, 0);
        setFreeSize(table, hashBase, capacity);
    }
    
    /**
     * Ensure that this hashtable has sufficient capacity to hold
     * <tt>desiredCapacity<tt> <b>additional</b> elements without
     * requiring a rehash.  This is a tuning method you can call
     * before doing a large insert.
     *
     * @param desiredSize an <code>int</code> value
     */
    public static boolean ensureSize(int[] table, int hashBase, int desiredSize, IntAllocatorI allocator) {
        int size = getUsedSize(table, hashBase);
        if (desiredSize > (getMaxSize(table, hashBase) - size)) {
            int newCapacity = ((desiredSize + size) << 1) + 1;
            rehash(table, hashBase, PrimeFinder.nextPrime(newCapacity), allocator);
            return true;
        }
        return false;
    }

    /**
     * Compresses the hashtable to the minimum prime size (as defined by
     * PrimeFinder) that will hold all of the elements currently in the table.
     * If you have done a lot of <tt>remove</tt> operations and plan to do a
     * lot of queries or insertions or iteration, it is a good idea to invoke
     * this method. Doing so will accomplish two things:
     * 
     * <ol>
     * <li> You'll free memory allocated to the table but no longer needed
     * because of the remove()s.</li>
     * 
     * <li> You'll get better query/insert/iterator performance because there
     * won't be any <tt>REMOVED</tt> slots to skip over when probing for
     * indices in the table.</li>
     * </ol>
     */
    public static void compact(int[] table, int hashBase, IntAllocatorI allocator) {
        // need at least one free spot for open addressing
        rehash(table, hashBase, PrimeFinder.nextPrime((getUsedSize(table, hashBase) << 1) + 1), allocator);
    }

    static <Context> boolean foreachInt(int[] table, int base
    		, ClusterI.PredicateProcedure<Context> procedure, Context context, Modifier modifier) throws DatabaseException {
        int capacity = getRealSize(table, base);
        final int size = getUsedSize(table, base);
        int count = 0;
        for (int i = capacity*2 + base;
            (count < size) && (i-- > base);) {
            int v = table[i];
            int o = table[--i];
            if (isFull(o)) {
            	int key;
            	if (null != modifier)
            		key = modifier.execute(o);
            	else
            		key = o;
	            if (procedure.execute(context, key, v))
	            	return true; // loop was broken by procedure
            	if (size == ++count)
            		return false; // loop finished
            }
        }
        assert(size == count);
        return false; // loop finished
    }

    /**
     * Expands the set to accomodate new values.
     * 
     * @param newCapacity
     *            an <code>int</code> value
     */
    private static final int rehash(int[] oldTable, int oldHashBase, int newCapacity,
            IntAllocatorI allocator) {
        assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);
        int oldCapacity = getRealSize(oldTable, oldHashBase);
        int oldSize = getUsedSize(oldTable, oldHashBase);
        // new hash base is initialized to freeSet()
        int newHashBase = allocator.allocate(newCapacity*2 + HeaderSize) + HeaderSize;
        int[] newtable = allocator.getTable();
        setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);
        setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);
        for (int i = oldCapacity*2 + oldHashBase; i-- > oldHashBase;) {
            int v = oldTable[i];
            int o = oldTable[--i];
            if (isFull(o)) {
                int index = insertionIndex(newtable, newHashBase, o);
                newtable[index] = o;
                newtable[index+1] = v;
            }
        }
        return newHashBase;
    }

    /**
     * After an insert, this hook is called to adjust the size/free values of
     * the set and to perform rehashing if necessary.
     */
    private static final int postInsertHook(int[] table, int hashBase,
            boolean usedFreeSlot, IntAllocatorI allocator) {
        if (usedFreeSlot) {
            decFreeSize(table, hashBase);
        }

        // rehash whenever we exhaust the available space in the table
        if (incUsedSize(table, hashBase) > getMaxSize(table, hashBase)
                || getFreeSize(table, hashBase) == 0) {
            // choose a new capacity suited to the new state of the table
            // if we've grown beyond our maximum size, double capacity;
            // if we've exhausted the free spots, rehash to the same capacity,
            // which will free up any stale removed slots for reuse.
            int newCapacity = getUsedSize(table, hashBase) > getMaxSize(table,
                    hashBase) ? PrimeFinder.nextPrime(getRealSize(table,
                    hashBase) << 1) : getRealSize(table, hashBase);
            return rehash(table, hashBase, newCapacity, allocator);
        }
        return hashBase;
    }

    /**
     * Locates the index of <tt>val</tt>.
     * 
     * @param val
     *            an <code>int</code> value
     * @return the index of <tt>val</tt> or -1 if it isn't in the set.
     */
    private static int index(int[] table, int hashBase, int a) {
        int hash, probe, index, length, hashIndex;
        int[] set = table;
        length = getRealSize(table, hashBase);
        hash = computeHashCode(a);
        index = hash % length;
        hashIndex = hashBase + index*2;

        if (!isFree(set[hashIndex])
                && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
            // see Knuth, p. 529
            probe = 1 + (hash % (length - 2));

            do {
                index -= probe;
                if (index < 0) {
                    index += length;
                }
                hashIndex = hashBase + index*2;
            } while (!isFree(set[hashIndex])
                    && (isRemoved(set[hashIndex]) || set[hashIndex] != a));
        }

        return isFree(set[hashIndex]) ? -1  : hashIndex;
    }

    /**
     * Locates the index at which <tt>val</tt> can be inserted. if there is
     * already a value equal()ing <tt>val</tt> in the set, returns that value
     * as a negative integer.
     * 
     * @param val
     *            an <code>int</code> value
     * @return an <code>int</code> value
     */
    private static final int insertionIndex(int[] table, int hashBase, int a) {
        int hash, probe, index, length, hashIndex;
        int[] set = table;
        length = getRealSize(table, hashBase);
        hash = computeHashCode(a);
        index = hash % length;
        assert(0 != hashBase);
        hashIndex = hashBase + index*2;
        
        if (isFree(set[hashIndex])) {
            return hashIndex; // empty, all done
        } else if (isFull(set[hashIndex]) && set[hashIndex] == a) {
            return -hashIndex; // already stored
        } else { // already FULL or REMOVED, must probe
            // compute the double hash
            probe = 1 + (hash % (length - 2));

            // if the slot we landed on is FULL (but not removed), probe
            // until we find an empty slot, a REMOVED slot, or an element
            // equal to the one we are trying to insert.
            // finding an empty slot means that the value is not present
            // and that we should use that slot as the insertion point;
            // finding a REMOVED slot means that we need to keep searching,
            // however we want to remember the offset of that REMOVED slot
            // so we can reuse it in case a "new" insertion (i.e. not an update)
            // is possible.
            // finding a matching value means that we've found that our desired
            // key is already in the table

            if (!isRemoved(set[hashIndex])) {
                // starting at the natural offset, probe until we find an
                // offset that isn't full.
                do {
                    index -= probe;
                    if (index < 0) {
                        index += length;
                    }
                    hashIndex = hashBase + index*2;
                } while (isFull(set[hashIndex]) && set[hashIndex] != a);
            }

            // if the index we found was removed: continue probing until we
            // locate a free location or an element which equal()s the
            // one we have.
            if (isRemoved(set[hashIndex])) {
                int firstRemoved = hashIndex;
                while (!isFree(set[hashIndex])
                        && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
                    index -= probe;
                    if (index < 0) {
                        index += length;
                    }
                    hashIndex = hashBase + index*2;
                }
                return isFull(set[hashIndex]) ? -hashIndex : firstRemoved;
            }
            // if it's full, the key is already stored
            return isFull(set[hashIndex]) ? -hashIndex : hashIndex;
        }
    }

    private static final int computeHashCode(int aKey) {
        int hash = aKey * 31;
        return hash & 0x7fffffff; // Top bit reserved.
    }
}