/*
 * @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.IntComparator;
import net.ranides.assira.collection.arrays.ArrayAllocator;
import net.ranides.assira.collection.arrays.ArraySearch;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArraySort;
import net.ranides.assira.collection.iterators.IntIterator;
import net.ranides.assira.collection.iterators.RandomAccessIntIterator;
import net.ranides.assira.collection.iterators.RandomAccessIterator;
import net.ranides.assira.collection.sets.AIntSet;
import net.ranides.assira.collection.sets.IntSet;
import net.ranides.assira.generic.CompareUtils;

import java.util.AbstractList;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

/**
 * IntMap which stores key-value mappings inside sorted arrays.
 * It can be modified in effective way (modification wont trigger whole sort).
 * It uses binary search for read and write operations, so complexity is O(logN)
 *
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @param <V> type of value
 */
public class IntArrayMap<V> extends AIntMap<V> implements BlockMap<Integer, V> {

    private static final long serialVersionUID = 1L;

    private int[] keys;
    private V[] vars;
    private int size;

    private final IntComparator cmp;

    /**
     * Creates map with specified content.
     * It copies specified arrays and uses quicksort.
     * It uses natural ascending IntComparator.
     *
     * @param keys keys
     * @param vars vars
     */
    public IntArrayMap(int[] keys, V[] vars) {
        this(keys, vars, IntComparator.ASC);
    }

    /**
     * Creates map with specified content.
     * It copies specified arrays and uses quicksort.
     * It uses specified comparator for internal ordering.
     *
     * @param keys keys
     * @param vars vars
     * @param comparator comparator
     */
    public IntArrayMap(int[] keys, V[] vars, IntComparator comparator) {
        this.keys = keys.clone();
        this.vars = vars.clone();
        this.size = vars.length;
        this.cmp = comparator;
        sort();
    }
    
    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(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<IntEntry<V>> fastEntrySet() {
        return new AbstractSet<IntEntry<V>>() {
            @Override
            public Iterator<IntEntry<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 IntArrayMap.this.remove(entry.getKey(), entry.getValue());
                }
                return false;
            }

            @Override
            public void clear() {
                IntArrayMap.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 IntSet keySet() {
        return new AIntSet() {


            @Override
            public IntIterator 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;
                IntArrayMap.this.remove(o);
                return prev != size;
            }

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

    @Override
    public V get(int key) {
        int i = ArraySearch.binarySearch(keys, 0, size, key, cmp);
        return i<0 ? null : vars[i];
    }

    @Override
    public boolean containsKey(int key) {
        int i = ArraySearch.binarySearch(keys, 0, size, 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(int key) {
        int pos = ArraySearch.binarySearch(keys, 0, size, key, cmp);
        if(pos<0) {
            return null;
        }
        V prev = vars[pos];
        $remove(pos);
        return prev;
    }

    @Override
    public boolean remove(int key, Object value) {
        int pos = ArraySearch.binarySearch(keys, 0, size, 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] == key; s--) {
            if(CompareUtils.equals(value, vars[s])) {
                $remove(s);
                return true;
            }
        }

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

    @Override
    public V put(int key, V value) {
        int pos = ArraySearch.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, 0);
        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] = 0;
        vars[size] = null;
    }

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

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

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

        @Override
        protected IntEntry<V> get(int index) {
            return new PEntry(index);
        }

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

    }

    private class KeyIterator extends RandomAccessIntIterator {

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

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

        @Override
        protected int 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 PEntry extends AIntEntry<V> {
    
        private final int index;

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

        @Override
        public int getIntKey() {
            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;
        }
        
    }

}
