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

package net.ranides.assira.collection.lookups;

import net.ranides.assira.collection.IntCollection;
import net.ranides.assira.collection.arrays.ArrayAllocator;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArraySort;
import net.ranides.assira.collection.iterators.IntListIterator;
import net.ranides.assira.collection.iterators.RandomAccessIntIterator;
import net.ranides.assira.collection.iterators.RandomAccessIterator;
import net.ranides.assira.collection.iterators.RandomAccessSpliterator;
import net.ranides.assira.collection.lists.AIntList;
import net.ranides.assira.collection.maps.BlockMap;
import net.ranides.assira.generic.CompareUtils;

import java.util.*;

/**
 * Container stores elements inside sorted array and uses binary search for access.
 *
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @param <K> type of key
 */
public class ArrayLookup<K> extends ALookup<K> implements BlockMap<K,Integer> {

    private static final long serialVersionUID = 1L;

    private static final Object[] EMPTY = new Object[0];
    private static final int[] EMPTY_INT = new int[0];

    private final Class<?> type;
    private K[] keys;
    private int[] vars;
    private int size;

    private final Comparator<? super K> cmp;

    /**
     * Creates new empty map with default, natural key comparator.
     */
    public ArrayLookup() {
        this(CompareUtils.comparator());
    }

    /**
     * Creates new map with specified key comparator.
     * @param cmp cmp
     */
    @SuppressWarnings("unchecked")
    public ArrayLookup(Comparator<? super K> cmp) {
        this.type = Object.class;
        this.keys = (K[]) EMPTY;
        this.vars = EMPTY_INT;
        this.size = 0;
        this.cmp = cmp;
    }

    /**
     * Creates new map with provided keys and values.
     * Please note, that keys must be comparable.
     * Please note, that map does not preserve order of keys.
     *
     * @param keys keys
     * @param vars values
     */
    public ArrayLookup(K[] keys, int[] vars) {
        this(keys, vars, CompareUtils.comparator());
    }

    /**
     * Creates new map with provided keys and values.
     * It uses comparator function for sorting keys.
     * Please note, that map does not preserve order of keys.
     *
     * @param keys keys
     * @param vars values
     * @param comparator comparator
     */
    public ArrayLookup(K[] keys, int[] vars, Comparator<? super K> comparator) {
        this.type = keys.getClass().getComponentType();
        this.keys = keys.clone();
        this.vars = vars.clone();
        this.size = vars.length;
        this.cmp = comparator;
        sort();
    }

    /**
     * Creates new map with content from source map.
     * Created ArrayMap uses natural comparator.
     *
     * @param values values
     */
    @SuppressWarnings("unchecked")
    public ArrayLookup(Map<? extends K, ? extends Integer> values) {
        int n = values.size();
        Object[] k = new Object[n];
        int[] v = new int[n];

        int i = 0;
        for(Entry<? extends K, ? extends Integer> e : values.entrySet()) {
            k[i] = e.getKey();
            v[i] = e.getValue();
            i++;
        }

        this.type = Object.class;
        this.keys = (K[])k;
        this.vars = v;
        this.size = vars.length;
        this.cmp = CompareUtils.comparator();
    }

    /**
     * Creates new map with content from source map.
     * Created ArrayMap uses the same comparator as source map.
     *
     * @param map map
     */
    @SuppressWarnings("unchecked")
    public ArrayLookup(SortedMap<K, Integer> map) {
        int n = map.size();
        Object[] k = new Object[n];
        int[] v = new int[n];

        int i = 0;
        for(Entry<K, Integer> e : map.entrySet()) {
            k[i] = e.getKey();
            v[i] = e.getValue();
            i++;
        }

        this.type = Object.class;
        this.keys = (K[])k;
        this.vars = v;
        this.size = vars.length;
        this.cmp = map.comparator();
    }

    /**
     * Creates new map with content from source map.
     * Created ArrayMap uses the same comparator as source map.
     *
     * @param map map
     */
    @SuppressWarnings("unchecked")
    public ArrayLookup(SortedLookup<K> map) {
        int n = map.size();
        Object[] k = new Object[n];
        int[] v = new int[n];

        int i = 0;
        for(LookupEntry<K> e : map.fastEntrySet()) {
            k[i] = e.getKey();
            v[i] = e.getIntValue();
            i++;
        }

        this.type = Object.class;
        this.keys = (K[])k;
        this.vars = v;
        this.size = vars.length;
        this.cmp = map.comparator();
    }

    private void sort() {
        NativeArraySort.quickSort(0, size, (a,b) -> cmp.compare(keys[a],keys[b]), (a,b) -> {
            swap(keys, a, b);
            swap(vars, a, b);
        });
    }

    private static void swap(int[] array, int a, int b) {
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }

    private static <T> void swap(T[] array, int a, int b) {
        T t = array[a];
        array[a] = array[b];
        array[b] = t;
    }

    @Override
    public int capacity() {
        return keys.length;
    }

    @Override
    public boolean trim() {
        return trim(keys.length);
    }

    @Override
    public boolean trim(int n) {
        if(n > capacity()) {
            return false;
        }
        if(n<size) {
            throw new IllegalArgumentException(String.format("n= %d is too small (size=%d)", n, size));
        }
        this.keys = ArrayUtils.slice(keys, 0, n);
        this.vars = ArrayUtils.slice(vars, 0, n);
        return true;
    }

    @Override
    public Set<LookupEntry<K>> fastEntrySet() {
        return new AbstractSet<LookupEntry<K>>() {
            @Override
            public Iterator<LookupEntry<K>> iterator() {
                return new EntryIterator(0);
            }

            @Override
            public Spliterator<LookupEntry<K>> spliterator() {
                return RandomAccessSpliterator.of(size, AMEntry::new);
            }

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

            @Override
            public boolean remove(Object object) {
                if (object instanceof Map.Entry) {
                    Entry<?, ?> entry = (Entry<?,?>) object;
                    return ArrayLookup.this.remove(entry.getKey(), entry.getValue());
                }
                return false;
            }

            @Override
            public void clear() {
                ArrayLookup.this.clear();
            }
        };
    }

    @Override
    public IntCollection values() {
        return new AIntList() {
            @Override
            public IntListIterator iterator() {
                return new ValueIterator(0);
            }

            @Override
            public IntListIterator listIterator(int index) {
                return new ValueIterator(index);
            }

            @Override
            public Spliterator<Integer> spliterator() {
                return RandomAccessSpliterator.of(size, i -> vars[i]);
            }

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

            @Override
            public int getInt(int index) {
                if(index <0 || index>=size) {
                    throw new IndexOutOfBoundsException(index + " out of bound " + size);
                }
                return vars[index];
            }

            @Override
            public void add(int index, int k) {
                throw new UnsupportedOperationException();
            }

            @Override
            public int removeInt(int index) {
                if(index <0 || index>=size) {
                    throw new IndexOutOfBoundsException(index + " out of bound " + size);
                }
                int prev = vars[index];
                $remove(index);
                return prev;
            }

            @Override
            public int set(int index, int k) {
                throw new UnsupportedOperationException();
            }
        };
    }

    @Override
    public Set<K> keySet() {
        return new AbstractSet<K>() {
            @Override
            public Iterator<K> iterator() {
                return new KeyIterator(0);
            }

            @Override
            public Spliterator<K> spliterator() {
                return RandomAccessSpliterator.of(size, i -> keys[i]);
            }

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

            @Override
            public boolean contains(Object o) {
                return containsKey(o);
            }

            @Override
            public boolean remove(Object o) {
                int prev = size;
                ArrayLookup.this.remove(o);
                return prev != size;
            }

            @Override
            public void clear() {
                ArrayLookup.this.clear();
            }
        };
    }

    @Override
    public int getInt(Object key) {
        if(!type.isInstance(key)) {
            return defaultReturnValue();
        }
        @SuppressWarnings("unchecked")
        int i = Arrays.binarySearch(keys, 0, size, (K)key, cmp);
        return i<0 ? defaultReturnValue() : vars[i];
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean containsKey(Object key) {
        if(!type.isInstance(key)) {
            return false;
        }
        @SuppressWarnings("unchecked")
        int i = Arrays.binarySearch(keys, 0, size, (K)key, cmp);
        return i >= 0;
    }

    @Override
    public boolean containsValue(int value) {
        for(int i=0; i<size; i++) {
            if (value == vars[i]) { return true; }
        }
        return false;
    }
    
    @Override
    public int size() {
        return size;
    }

    @Override
    public int removeInt(Object key) {
        if(!type.isInstance(key)) {
            return defaultReturnValue();
        }

        @SuppressWarnings("unchecked")
        int pos = Arrays.binarySearch(keys, 0, size, (K)key, cmp);
        if(pos<0) {
            return defaultReturnValue();
        }
        int prev = vars[pos];
        $remove(pos);
        return prev;
    }

    @Override
    public boolean remove(Object key, Object value) {
        if(!type.isInstance(key)) {
            return false;
        }

        @SuppressWarnings("unchecked")
        int pos = Arrays.binarySearch(keys, 0, size, (K)key, cmp);
        if(pos<0) {
            return false;
        }
        if(CompareUtils.equals(value, vars[pos])) {
            $remove(pos);
            return true;
        }

        for(int s = pos-1; s>0 && keys[s].equals(key); s--) {
            if(CompareUtils.equals(value, vars[s])) {
                $remove(s);
                return true;
            }
        }

        for(int s = pos+1; s<size && keys[s].equals(key); s++) {
            if(CompareUtils.equals(value, vars[s])) {
                $remove(s);
                return true;
            }
        }
        return false;
    }

    @Override
    public int put(K key, int value) {
        int pos = Arrays.binarySearch(keys, 0, size, key, cmp);
        if(pos >=0) {
            int prev = vars[pos];
            vars[pos] = value;
            return prev;
        } else {
            $add(-pos - 1, key, value);
            return defaultReturnValue();
        }
    }

    @Override
    public void clear() {
        size = 0;
        Arrays.fill(keys, null);
        Arrays.fill(vars, defaultReturnValue());
    }

    private void $remove(int index) {
        int shift = size - index - 1;
        if (shift > 0) {
            System.arraycopy(keys, index + 1, keys, index, shift);
            System.arraycopy(vars, index + 1, vars, index, shift);
        }

        size--;
        keys[size] = null;
        vars[size] = defaultReturnValue();
    }

    private void $add(int index, K key, int value) {
        keys = ArrayAllocator.grow(keys, size+1);
        vars = ArrayAllocator.grow(vars, size+1);

        int shift = size - index;
        if (shift > 0) {
            System.arraycopy(keys, index, keys, index + 1, shift);
            System.arraycopy(vars, index, vars, index + 1, shift);
        }
        keys[index] = key;
        vars[index] = value;
        size++;
    }

    private class EntryIterator extends RandomAccessIterator<LookupEntry<K>> {

        public EntryIterator(int index) {
            super(index);
        }

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

        @Override
        protected LookupEntry<K> get(int index) {
            return new AMEntry(index);
        }

        @Override
        protected void remove(int index) {
            $remove(index);
        }

    }

    private class KeyIterator extends RandomAccessIterator<K> {

        public KeyIterator(int index) {
            super(index);
        }

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

        @Override
        protected K get(int index) {
            return keys[index];
        }

        @Override
        protected void remove(int index) {
            $remove(index);
        }

    }

    private class ValueIterator extends RandomAccessIntIterator {

        public ValueIterator(int index) {
            super(index);
        }

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

        @Override
        protected int get(int index) {
            return vars[index];
        }

        @Override
        protected void remove(int index) {
            $remove(index);
        }

    }

    private class AMEntry extends ALookupEntry<K> {

        private final int index;

        public AMEntry(int index) {
            this.index = index;
        }

        @Override
        public K getKey() {
            return keys[index];
        }

        @Override
        public int getIntValue() {
            return vars[index];
        }

        @Override
        public int setValue(int value) {
            int prev = vars[index];
            vars[index] = value;
            return prev;
        }

    }

}
