/*
 * @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.ArrayAllocator;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArraySort;
import net.ranides.assira.collection.iterators.RandomAccessIterator;
import net.ranides.assira.generic.CompareUtils;

import java.util.*;

/**
 * Memory efficient map.
 * It stores elements inside sorted array and uses binary search for access.
 *
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @param <K> K
 * @param <V> V
 */
public class ArrayMap<K,V> extends AMap<K, V> implements BlockMap<K,V> {

    private static final long serialVersionUID = 1L;
    
    private final Class<?> type;
    private K[] keys;
    private V[] vars;
    private int size;

    private final Comparator<? super K> 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 ArrayMap(K[] keys, V[] 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 ArrayMap(K[] keys, V[] 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 the same comparator as source map.
     *
     * @param map map
     */
    @SuppressWarnings("unchecked")
    public ArrayMap(SortedMap<K,V> map) {
        int n = map.size();
        Object[] k = new Object[n];
        Object[] v = new Object[n];

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

        this.type = Object.class;
        this.keys = (K[])k;
        this.vars = (V[])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 <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<Entry<K, V>> entrySet() {
        return new AbstractSet<Entry<K, V>>() {
            @Override
            public Iterator<Entry<K, V>> iterator() {
                return new EntryIterator(0);
            }

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

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

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

    @Override
    public Collection<V> values() {
        return new AbstractList<V>() {
            @Override
            public Iterator<V> iterator() {
                return new ValueIterator(0);
            }

            @Override
            public ListIterator<V> listIterator(int index) {
                return new ValueIterator(index);
            }

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

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

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

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

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

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

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

    @Override
    public V get(Object key) {
        if(!type.isInstance(key)) {
            return null;
        }
        @SuppressWarnings("unchecked")
        int i = Arrays.binarySearch(keys, 0, size, (K)key, cmp);
        return i<0 ? null : 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(Object value) {
        if (value==null) {
            for (int i=0; i<size; i++) {
                if (vars[i]==null) { return true; }
            }
        } else {
            for(int i=0; i<size; i++) {
                if( value.equals(vars[i]) ) { return true; }
            }
        }
        return false;
    }
    
    @Override
    public int size() {
        return size;
    }

    @Override
    public V remove(Object key) {
        if(!type.isInstance(key)) {
            return null;
        }

        @SuppressWarnings("unchecked")
        int pos = Arrays.binarySearch(keys, 0, size, (K)key, cmp);
        if(pos<0) {
            return null;
        }
        V 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 V put(K key, V value) {
        int pos = Arrays.binarySearch(keys, 0, size, key, cmp);
        if(pos >=0) {
            V prev = vars[pos];
            vars[pos] = value;
            return prev;
        } else {
            $add(-pos - 1, key, value);
            return null;
        }
    }

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

    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] = null;
    }

    private void $add(int index, K key, V 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<Entry<K,V>> {

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

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

        @Override
        protected Entry<K, V> 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 RandomAccessIterator<V> {

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

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

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

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

    }

    private class AMEntry extends AEntry<K,V> {

        private final int index;

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

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

        @Override
        public V getValue() {
            return vars[index];
        }

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

    }

}
