/*
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.maps;

import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArray;
import net.ranides.assira.collection.arrays.NativeArrayUtils;
import net.ranides.assira.collection.sets.ASet;
import net.ranides.assira.collection.utils.HashCollection;
import net.ranides.assira.generic.HashUtils;

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

/**
 * WeakIdentMap stores weak reference to mappings.
 *
 * It uses System.identityHashCode(v) and identity to compare objects.
 *
 * Internally it uses open hash table.
 *
 * @param <K> K
 * @param <V> V
 */
public final class WeakIdentMap<K,V> extends AMap<K,V> {

    private WeakEntry<K,V>[] entries;

    private boolean[] used;

    private final float factor;

    private int n;

    private int capacity;

    private int mask;

    private int size;

    private final ReferenceQueue<K> queue;

    /**
     * Creates new map
     */
    public WeakIdentMap() {
        this(HashCollection.INITIAL_SIZE, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates new map with expected size
     *
     * @param expected expected
     */
    public WeakIdentMap(int expected) {
        this(expected, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates new map with expected size and load factor
     *
     * @param expected expected
     * @param factor factor
     */
    @SuppressWarnings("unchecked")
    public WeakIdentMap(int expected, float factor) {
        if (factor <= 0 || factor > 1) {
            throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1");
        }
        if (expected < 0) {
            throw new IllegalArgumentException("The expected number of elements must be nonnegative");
        }
        this.factor = factor;
        this.n = HashCollection.arraysize(expected, factor);
        this.mask = n - 1;
        this.capacity = HashCollection.factorsize(n, factor);
        this.entries = new WeakEntry[n];
        this.used = new boolean[n];
        this.queue = new ReferenceQueue<>();
    }

    @Override
    public int size() {
        icleanup();
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return new EntryView();
    }

    @Override
    public boolean containsKey(Object key) {
        return used[ifind(key)];
    }

    @Override
    public boolean containsValue(Object value) {
        return entrySet().stream().anyMatch(e -> Objects.equals(value, e.getValue()));
    }

    @Override
    public V get(Object key) {
        int pos = ifind(key);
        return used[pos] ? entries[pos].value : null;
    }

    @Override
    public V put(K key, V value) {
        icleanup();
        int pos = ifind(key);
        if(used[pos]) {
            V prev = entries[pos].value;
            entries[pos].value = value;
            return prev;
        } else {
            iinsert(pos, key, value);
            return null;
        }
    }

    @Override
    public V remove(Object key) {
        if(key == null) {
            return null;
        }
        int pos = ifind(key);
        if(!used[pos]) {
            return null;
        }
        V prev = entries[pos].value;
        ishift(pos);
        return prev;
    }

    @Override
    public boolean remove(Object key, Object value) {
        int pos = ifind(key);
        if(used[pos] && Objects.equals(value, entries[pos].getValue())) {
            ishift(pos);
            return true;
        }
        return false;
    }

    @Override
    public void clear() {
        if (size == 0) {
            return;
        }
        size = 0;
        NativeArrayUtils.fill(NativeArray.wrap(used), false);
        ArrayUtils.fill(entries, null);
    }

    private static int hash(Object key) {
        return HashUtils.murmurHash3(System.identityHashCode(key));
    }

    private boolean icmp(WeakEntry<?,?> entry1, Object key) {
        return entry1.getKey() == key;
    }

    @SuppressWarnings("unchecked")
    private void irehash(int newN) {
        int i = 0, pos;
        final boolean[] iused = this.used;
        WeakEntry cEntry;
        final WeakEntry[] ikeys = this.entries;
        final int newMask = newN - 1;
        final WeakEntry[] newKey = new WeakEntry[newN];
        final boolean[] newUsed = new boolean[newN];
        for (int j = size; j-- != 0; ) {
            while (!iused[i]) {
                i++;
            }
            cEntry = ikeys[i];
            pos = cEntry.hash & newMask;
            while (newUsed[pos]) {
                pos = (pos + 1) & newMask;
            }
            newUsed[pos] = true;
            newKey[pos] = cEntry;
            i++;
        }
        n = newN;
        mask = newMask;
        capacity = HashCollection.factorsize(n, factor);
        this.entries = newKey;
        this.used = newUsed;
    }

    private int ifind(Object key) {
        int i = hash(key) & mask;
        // There's always an unused entry.
        while (used[i] && !icmp(entries[i], key)) {
            i = (i + 1) & mask;
        }
        return i;
    }

    private boolean iinsert(int segment, K key, V value) {
        used[segment] = true;
        entries[segment] = new WeakEntry<>(queue, key, value);

        if (++size >= capacity) {
            irehash(HashCollection.arraysize(size + 1, factor));
        }
        return true;
    }

    private boolean ishift(int pos) {
        size--;
        int last;
        for (; ; ) {
            last = pos;
            pos = inext(pos);
            if (!used[pos]) {
                break;
            }
            imove(last, pos);
        }
        iclear(last);
        return true;
    }

    private int inext(int last) {
        int pos = (last + 1) & mask;
        while (used[pos]) {

            int slot = entries[pos].hash & mask;
            if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) {
                break;
            }
            pos = (pos + 1) & mask;
        }
        return pos;
    }

    private void imove(int target, int source) {
        entries[target] = entries[source];
    }

    private void iclear(int segment) {
        used[segment] = false;
        entries[segment] = null;
    }

    private void icleanup() {
        // cleanup after cleared References.
        WeakEntry ref;
        while ((ref = (WeakEntry)this.queue.poll()) != null) {
            icleanup(ref);
        }
    }

    private void icleanup(WeakEntry entry) {
        int pos = entry.hash & mask;

        // There's always an unused entry.
        while (used[pos] && entries[pos].hash!=entry.hash && entries[pos].getKey()!=null) {
            pos = (pos + 1) & mask;
        }
        if(used[pos]) {
            ishift(pos);
        }
    }

    private class EntryView extends ASet<Entry<K, V>> {

        @Override
        public Iterator<Entry<K, V>> iterator() {
            return new EntryIterator();
        }

        @Override
        public int size() {
            return size;
        }

        @Override
        public boolean remove(Object value) {
            if(value instanceof Map.Entry) {
                Entry entry = (Entry)value;
                return WeakIdentMap.this.remove(entry.getKey(), entry.getValue());
            } else {
                return false;
            }
        }

        @Override
        public boolean add(Entry<K, V> entry) {
            return null != WeakIdentMap.this.put(entry.getKey(), entry.getValue());
        }
    }

    private class EntryIterator implements Iterator<Map.Entry<K,V>> {

        int mpos;

        int mlast;

        int counter;

        ArrayList<WeakEntry<K,V>> wrapped;

        public EntryIterator() {
            this.mpos = WeakIdentMap.this.n;
            this.mlast = -1;
            this.counter = size;
            this.wrapped = null;
            boolean[] used = WeakIdentMap.this.used;
            if (counter != 0) {
                while (!used[--mpos]) { } // NOPMD
            }
        }

        @Override
        public boolean hasNext() {
            return counter != 0;
        }

        @Override
        public WeakEntry<K,V> next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            counter--;
            // We are just enumerating elements from the wrapped list.
            if (mpos < 0) {
                return wrapped.get(-(mlast = --mpos) - 2);
            }
            final WeakEntry<K,V> retVal = entries[mlast = mpos];
            if (counter != 0) {
                final boolean[] used = WeakIdentMap.this.used;
                while (mpos-- != 0 && !used[mpos]) { } // NOPMD
                // When here pos < 0 there are no more elements to be enumerated by scanning, but wrapped might be nonempty.
            }
            return retVal;
        }

        private int ishift(int pos) {
            int last;
            for (; ; ) {
                last = pos;
                pos = inext(last);
                if (!used[pos]) {
                    break;
                }
                if (pos < last) {
                    if (wrapped == null) {
                        wrapped = new ArrayList<>();
                    }
                    wrapped.add(entries[pos]);
                }
                imove(last, pos);
            }
            iclear(last);
            return last;
        }

        @Override
        public void remove() {
            if (mlast == -1) {
                throw new IllegalStateException();
            }
            if (mpos < -1) {
                // We're removing wrapped entries.
                WeakIdentMap.this.remove(wrapped.set(-mpos - 2, null).getKey());
                mlast = -1;
                return;
            }
            size--;
            if (ishift(mlast) == mpos && counter > 0) {
                counter++;
                next();
            }
            mlast = -1; // You can no longer remove this entry.
        }
    }

    private static final class WeakEntry<K,V> extends WeakReference<K> implements Map.Entry<K, V> {
        final int hash;
        V value;

        WeakEntry(ReferenceQueue<K> queue, K key, V value) {
            super(key, queue);
            this.hash = hash(key);
            this.value = value;
        }

        @Override
        public void clear() {
            // Do nothing if reference is explicity cleared. This prevents
            // backdoor modification of map entries.
        }

        @Override
        public K getKey() {
            return this.get();
        }

        @Override
        public V getValue() {
            return this.value;
        }

        @Override
        public V setValue(V value) {
            V prev = this.value;
            this.value = value;
            return prev;
        }

        @Override
        public boolean equals(Object obj) {
            return (obj instanceof Map.Entry) && equals((Map.Entry<?,?>)obj);
        }

        boolean equals(Map.Entry<?, ?> e) {
            return getKey() == e.getKey();
        }

        @Override
        public int hashCode() {
            return this.hash;
        }

        @Override
        public String toString() {
            return getKey() + "=" + getValue();
        }

    }

}
