package org.simantics.scl.compiler.internal.types;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;

public class HashConsing<T> {

    private static class Entry<T> extends WeakReference<T> {
        private final int hash;
        private Entry<T> next;

        Entry(T value, ReferenceQueue<T> queue, int hash, Entry<T> next) {
            super(value, queue);
            this.hash  = hash;
            this.next  = next;
        }
    }
    
    private double loadFactor = 0.75;
    @SuppressWarnings("unchecked")
    private Entry<T>[] table = new Entry[16];
    private int size = 0;
    private int threshold = (int)(table.length * loadFactor);    
    private final ReferenceQueue<T> queue = new ReferenceQueue<T>();
    
    public synchronized T canonical(T candidate) {        
        int h = hashCode(candidate);
        expungeStaleEntries();
        Entry<T>[] tab = table;
        int i = indexFor(h, tab.length);

        for (Entry<T> e = tab[i]; e != null; e = e.next) {
            T cur = e.get();
            if (h == e.hash && cur != null && equals(cur, candidate))
                return cur;
        }

        Entry<T> e = tab[i];
        tab[i] = new Entry<T>(candidate, queue, h, e);
        if (++size >= threshold)
            resize(tab.length * 2);
        return candidate;
    }
    
    private void resize(int newCapacity) {
        expungeStaleEntries();
        Entry<T>[] oldTable = table;

        @SuppressWarnings("unchecked")
        Entry<T>[] newTable = new Entry[newCapacity];
        transfer(oldTable, newTable);
        table = newTable;

        if (size >= threshold / 2) {
            threshold = (int)(newCapacity * loadFactor);
        } else {
            expungeStaleEntries();
            transfer(newTable, oldTable);
            table = oldTable;
        }
    }

    private void transfer(Entry<T>[] src, Entry<T>[] dest) {
        for (int j = 0; j < src.length; ++j) {
            Entry<T> e = src[j];
            src[j] = null;
            while (e != null) {
                Entry<T> next = e.next;
                Object key = e.get();
                if (key == null) {
                    e.next = null;
                    size--;
                } else {
                    int i = indexFor(e.hash, dest.length);
                    e.next = dest[i];
                    dest[i] = e;
                }
                e = next;
            }
        }
    }

    @SuppressWarnings("unchecked")
    private void expungeStaleEntries() {
        Entry<T> e;
        while ( (e = (Entry<T>) queue.poll()) != null) {
            int h = e.hash;
            int i = indexFor(h, table.length);

            Entry<T> prev = table[i];
            Entry<T> p = prev;
            while (p != null) {
                Entry<T> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    e.next = null;
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }

    private static int indexFor(int h, int length) {
        return h & (length-1);
    }
    
    protected int hashCode(T obj) {
        return obj.hashCode();
    }
    
    protected boolean equals(T a, T b) {
        return a.equals(b);
    }
    
}