// Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
//
// You may modify, copy, and redistribute this code under the terms of
// the GNU Library Public License version 2.1, with the exception of
// the portion of clause 6a after the semicolon (aka the "obnoxious
// relink clause")

package org.xwt.util;

import java.util.*;

/** Implementation of an unsynchronized hash table, with one or two
 *  keys, using Radke's quadradic residue linear probing instead of
 *  buckets to minimize object count (less allocations, faster GC).
 *  See C. Radke, Communications of the ACM, 1970, 103-105
 *
 *  Not threadsafe.
 */
public class Hash {
    /** this object is inserted as key in a slot when the
     *  corresponding value is removed -- this ensures that the
     *  probing sequence for any given key remains the same even if
     *  other keys are removed.
     */
    private static Object placeholder = new Object();

    /** the number of entries with at least one non-null key */
    private int usedslots = 0;

    /** the number of entries with non-null values */
    protected int size = 0;

    /** when num_slots < loadFactor * size, rehash into a bigger table */
    private final int loadFactor;

    /** primary keys */
    private Object[] keys1 = null;

    /** secondary keys; null if no secondary key has ever been added */
    private Object[] keys2 = null;

    /** the values for the table */
    private Object[] vals = null;
    
    /** the number of entries with a non-null value */
    public int size() { return size; }

    /** empties the table */
    public void clear() {
        size = 0;
        usedslots = 0;
        for(int i=0; i<vals.length; i++) {
            vals[i] = null;
            keys1[i] = null;
            if (keys2 != null) keys2[i] = null;
        }
    }

    /** returns all the primary keys in the table */
    public Enumeration keys() { return new HashEnum(); }

    public Hash() { this(25, 3); }
    public Hash(int initialcapacity, int loadFactor) {
        // using a pseudoprime in the form 4x+3 ensures full coverage
        initialcapacity = initialcapacity / 4;
        initialcapacity = 4 * initialcapacity + 3;
        keys1 = new Object[initialcapacity];
        vals = new Object[initialcapacity];
        this.loadFactor = loadFactor;
    }
    
    public void remove(Object k1) { remove(k1, null); }
    public void remove(Object k1, Object k2) { put_(k1, k2, null); }

    private void rehash() {
        Object[] oldkeys1 = keys1;
        Object[] oldkeys2 = keys2;
        Object[] oldvals = vals;
        keys1 = new Object[oldvals.length * 2];
        keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
        vals = new Object[oldvals.length * 2];
        size = 0;
        usedslots = 0;
        for(int i=0; i<oldvals.length; i++)
            if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
                put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
    }

    public Object get(Object k1) { return get(k1, null); }
    public Object get(Object k1, Object k2) {
        if (k2 != null && keys2 == null) return null;
        int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
        int dest = Math.abs(hash) % vals.length;
        int odest = dest;
        int tries = 1;
        boolean plus = true;
        while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
            Object hk1 = keys1[dest];
            Object hk2 = keys2 == null ? null : keys2[dest];
            if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
                (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
                return vals[dest];
            }
            dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
            if (plus) tries++;
            plus = !plus;
        }
        return null;
    }

    public void put(Object k1, Object v) { put(k1, null, v); }
    public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
    private void put_(Object k1, Object k2, Object v) {
        if (usedslots * loadFactor > vals.length) rehash();
        int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
        int dest = Math.abs(hash) % vals.length;
        int odest = dest;
        boolean plus = true;
        int tries = 1;
        while (true) {
            Object hk1 = keys1[dest];
            Object hk2 = keys2 == null ? null : keys2[dest];
            if (hk1 == null && hk2 == null) {                                         // empty slot
                if (v == null) return;
                size++;
                usedslots++;
                break;
            }

            if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&       // replacing former entry
                (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {

                // we don't actually remove things from the table; rather, we insert a placeholder
                if (v == null) {
                    k1 = placeholder;
                    k2 = null;
                    size--;
                }
                break;
            }

            dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
            if (plus) tries++;
            plus = !plus;
        }

        keys1[dest] = k1;
        if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
        if (keys2 != null) keys2[dest] = k2;
        vals[dest] = v;
    }

    private class HashEnum implements java.util.Enumeration {
        private int iterator = 0;
        private int found = 0;
        
        public HashEnum () { }
        
        public boolean hasMoreElements() {
            return found < usedslots;
        }

        public Object nextElement() {
            if (!hasMoreElements()) throw new java.util.NoSuchElementException();

            Object o = null;
            while (o == null) o = keys1[iterator++];
            if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");
            found++;
            
            return o;
        }
    }
}