/*******************************************************************************
 * 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 org.simantics.db.exception.DatabaseException;
import org.simantics.db.impl.ClusterI.Procedure;
import org.simantics.db.impl.ClusterSupport;
import org.simantics.db.impl.Modifier;
import org.simantics.db.impl.Table;
import org.simantics.db.impl.TableFactory;
import org.simantics.db.impl.TableSizeListener;

import gnu.trove.impl.PrimeFinder;

class TableIntHash extends Table<int[]> {
    private static final int INITIAL_SIZE = 1000;
    private static final int ENTRY_SIZE = 3;
    protected static final int HeaderSize = 5;
    private static final int Capacity = -5; // Number of allocated slots.
    private static final int Size = -4; // Number of used slots.
    private static final int Free = -3; // Number of free slots.
    private static final int MaxInsert = -2; // Limit for increasing number of allocated slots.
    private static final int MaxRemove = -1; // Limit for removing removed slots.
    protected int[] ints;
    protected int hashBase;
    TableIntHash(TableSizeListener sizeListener, int[] header, int headerBase) {
        super(TableFactory.getIntFactory(), sizeListener, header, headerBase);
        int capacity = PrimeFinder.nextPrime(INITIAL_SIZE);
        int tableSize = ENTRY_SIZE * capacity + HeaderSize;
        createNewTable(tableSize, tableSize, 1); // size, capacity, count
        ints = getTable();
        hashBase = getTableBase() + HeaderSize;
        capacitySet(capacity);
        sizeSet(0);
        freeSet(capacity);
        computeMaxInsert(capacity);
        computeMaxRemove(maxInsertGet());
    }
    TableIntHash(TableSizeListener sizeListener, int[] header, int headerBase, int[] ints) {
        super(TableFactory.getIntFactory(), sizeListener, header, headerBase, ints);
        this.ints = getTable();
        this.hashBase = getTableBase() + HeaderSize;
    }
    static final boolean isFree(int v) {
        return IntHashTrait.isFree(v);
    }

    static final boolean isFull(int v) {
        return IntHashTrait.isFull(v);
    }

    final boolean isFullByIndex(int index) {
        return isFull(setGet(index));
    }

    static final boolean isRemoved(int v) {
        return IntHashTrait.isRemoved(v);
    }

    static final int setFree() {
        return IntHashTrait.setFree();
    }

    static final int setFull(int v) {
        return IntHashTrait.setFull(v);
    }

    static final int setRemoved() {
        return IntHashTrait.setRemoved();
    }
    final int capacityGet() {
        return ints[hashBase + Capacity];
    }
    final void capacitySet(int a) {
        ints[hashBase + Capacity] = a;
    }
    final int sizeGet() {
        return ints[hashBase + Size];
    }
    final void sizeSet(int a) {
        ints[hashBase + Size] = a;
    }
    final int freeGet() {
        return ints[hashBase + Free];
    }
    final void freeSet(int a) {
        ints[hashBase + Free] = a;
    }
    final int maxInsertGet() {
        return ints[hashBase + MaxInsert];
    }
    final void maxInsertSet(int a) {
        ints[hashBase + MaxInsert] = a;
    }
    final int maxRemoveGet() {
        return ints[hashBase + MaxRemove];
    }
    void maxRemoveSet(int a) {
        ints[hashBase + MaxRemove] = a;
    }
    final int setGet(final int index) {
        return ints[hashBase + index * ENTRY_SIZE + 2];
    }
    final void setSet(int index, int value) {
        ints[hashBase + index * ENTRY_SIZE + 2] = value;
    }
    final void setKeyAndValue(int index, int key1, int key2, int value) {
        int realIndex = index * ENTRY_SIZE;
        ints[hashBase + realIndex] = key1;
        ints[hashBase + realIndex + 1] = key2;
        ints[hashBase + realIndex + 2] = value;
    }
    final boolean isFreeByIndex(final int index) {
    	return isFree(ints[hashBase + index * ENTRY_SIZE + 2]);
    }
    final boolean isRemovedByIndex(final int index) {
    	return isRemoved(ints[hashBase + index * ENTRY_SIZE + 2]);
    }
    final boolean isEqualByIndex(final int index, final int key1, final int key2) {
        int realIndex = index * ENTRY_SIZE;
        return key1 == ints[hashBase + realIndex] && key2 == ints[hashBase + realIndex + 1];
    }
    final void computeMaxInsert(int capacity) {
        // need at least one free slot for open addressing
        int maxSize = Math.min(capacity - 1, capacity >> 1);
        maxInsertSet(maxSize);
        freeSet(capacity - sizeGet()); // reset the free element count
    }
    
    final void computeMaxRemove(int removeCapacity) {
        maxRemoveSet((removeCapacity >> 1) + 1);
    }
    /**
     * retrieves the value for <tt>key</tt>
     * 
     * @param key an <code>int</code> value
     * @return the value of <tt>key</tt> or (int)0 if no such mapping exists.
     */
    final int getValue(int key1, int key2) {
        int index = index(key1, key2);
        return index < 0 ?  0 : setGet(index);
    }
    final boolean removeValue(int key1, int key2) {
        int index = index(key1, key2);
        if (index < 0)
            return false;
        setSet(index, setRemoved());
        return true;
        
    }
    final boolean setValue(int key1, int key2, int value) {
    	assert(!isFree(value));
    	assert(!isRemoved(value));
        int index = insertionIndex(key1, key2);
        boolean added = true;
        boolean isNewMapping = true;
        boolean previousStateWasFree = false;
        if (index < 0) { // old entry
            index = -index - 1;
            setSet(index, value);
            isNewMapping = false;
        } else { // new entry
             if (isFreeByIndex(index))
                 previousStateWasFree = true;
             setKeyAndValue(index, key1, key2, value);
        }
        if (isNewMapping)
            postInsertHook(previousStateWasFree);
        return added;
        
    }
    /**
     * Locates the index of <tt>akey</tt>.
     *
     * @param akey an <code>int</code> value
     * @return the index of <tt>akey</tt> or -1 if it isn't in the set.
     */
    final int index(final int akey1, final int akey2) {
        int hash, probe, index, length;
        //IntArray set = _set;
        length = capacityGet();
        hash = computeHashCode(akey1, akey2);
        index = hash % length;
        if (!isFreeByIndex(index) &&
            (isRemovedByIndex(index) ||
             !isEqualByIndex(index, akey1, akey2))) {
            // see Knuth, p. 529
            probe = 1 + (hash % (length - 2));
            do {
                index -= probe;
                if (index < 0) {
                    index += length;
                }
            } while (!isFreeByIndex(index) &&
                     (isRemovedByIndex(index) ||
                    		 !isEqualByIndex(index, akey1, akey2)));
        }

        return isFreeByIndex(index) ? -1 : index;
    }
    /**
     * Locates the index at which <tt>akey</tt> can be inserted.  if
     * there is already a key equaling <tt>akey</tt> in the set,
     * returns that key as a negative integer.
     *
     * @param akey an <code>long</code> value
     * @return an <code>int</code> value
     */
    final int insertionIndex(int akey1, int akey2) {
        int hash, probe, index, length;
        //IntArray set = _set;
        length = capacityGet();
        hash = computeHashCode(akey1, akey2);
        index = hash % length;
        if (isFreeByIndex(index)) {
            return index; // empty, all done
        } else if (isFullByIndex(index) && isEqualByIndex(index, akey1, akey2)) {
            return -index -1; // 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 (!isRemovedByIndex(index)) {
                // starting at the natural offset, probe until we find an
                // offset that isn't full.
                do {
                    index -= probe;
                    if (index < 0) {
                        index += length;
                    }
                } while (isFullByIndex(index) && !isEqualByIndex(index, akey1, akey2));
            }

            // 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 (isRemovedByIndex(index)) {
                int firstRemoved = index;
                while (!isFreeByIndex(index) &&
                       (isRemovedByIndex(index) || !isEqualByIndex(index, akey1, akey2))) {
                    index -= probe;
                    if (index < 0) {
                        index += length;
                    }
                }
                return isFullByIndex(index) ? -index -1 : firstRemoved;
            }
            // if it's full, the key is already stored
            return isFullByIndex(index) ? -index -1 : index;
        }
    }

    static final int computeHashCode(int key1, int key2) {
        // Multiple by prime to make sure hash can't be negative (see Knuth v3, p. 515-516)
        int hash;
        if (key1 == key2)
            hash = key1 * 31;
        else
            hash = ((int)(key1 ^ key2)) * 31;
        return hash & 0x7fffffff;
    }
    /**
     * After an insert, this hook is called to adjust the size/free
     * values of the set and to perform rehashing if necessary.
     */
    protected final void postInsertHook(boolean usedFreeSlot) {
        if (usedFreeSlot) {
            freeSet(freeGet()-1);
        }
        // rehash whenever we exhaust the available space in the table
        int size = sizeGet() + 1;
        sizeSet(size);
        int maxSize = maxInsertGet();
        int capacity = capacityGet();
        int free = freeGet();
        if (size >  maxSize || free == 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 = size > maxSize ? PrimeFinder.nextPrime(capacity << 1) : capacity;
            rehash(newCapacity);
        } 
    }
    final private void rehash(int newCapacity) {
        int oldCapacity = capacityGet();
        int oldHashBase = hashBase;
        int newTableCapacity = newCapacity*ENTRY_SIZE + HeaderSize;
        int[] oldInts = createNewTable(newTableCapacity, newTableCapacity, 1);
        ints = getTable();
        hashBase = getTableBase() + HeaderSize;
        capacitySet(newCapacity);
        sizeSet(0);
        freeSet(newCapacity);
        computeMaxInsert(newCapacity);
        computeMaxRemove(maxInsertGet());
        for (int i = oldCapacity; i-- > 0;) {
            int realIndex = oldHashBase + i*ENTRY_SIZE;
            if (isFull(oldInts[realIndex+2])) {
                int hashIndex = insertionIndex(oldInts[realIndex], oldInts[realIndex+1]);
                assert(hashIndex >= 0);
                int value = oldInts[realIndex+2];
            	assert(!isFree(value));
            	assert(!isRemoved(value));
                setKeyAndValue(hashIndex, oldInts[realIndex], oldInts[realIndex+1], value);
            }
        }
    }

    @Override
    public <Context> boolean foreach(int setIndex, Procedure procedure, Context context, ClusterSupport support, Modifier modifier) throws DatabaseException {
        throw new UnsupportedOperationException();
    }

}