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

package net.ranides.assira.collection.sets;

import net.ranides.assira.collection.BlockCollection;
import net.ranides.assira.collection.arrays.ArrayAllocator;
import net.ranides.assira.collection.arrays.ArraySort;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.iterators.RandomAccessIterator;
import net.ranides.assira.generic.CompareUtils;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.SortedSet;

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

    private static final long serialVersionUID = 1L;

    private final Class<?> type;
    private V[] data;
    private int size;

    private final Comparator<? super V> 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 data keys
     */
    public ArraySet(V[] data) {
        this(data, 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 data keys
     * @param comparator comparator
     */
    public ArraySet(V[] data, Comparator<? super V> comparator) {
        this.type = data.getClass().getComponentType();
        this.data = data.clone();
        this.size = data.length;
        this.cmp = comparator;
        sort();
    }

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

        int i = 0;
        for(V item : set) {
            k[i] = item;
            i++;
        }

        this.type = Object.class;
        this.data = (V[])k;
        this.size = data.length;
        this.cmp = set.comparator();
    }
    
    private void sort() {
      ArraySort.quickSort(data, cmp);
    }

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

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

    @Override
    public boolean reserve(int capacity) {
        data = ArrayAllocator.ensureCapacity(data, capacity, size);
        return true;
    }

    @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.data = ArrayUtils.slice(data, 0, n);
        return true;
    }

    public V get(int index) {
        return data[index];
    }

    @Override
    public ListIterator<V> iterator() {
        return new KeyIterator(0);
    }

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

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

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

        @SuppressWarnings("unchecked")
        int pos = Arrays.binarySearch(data, 0, size, (V)key, cmp);
        if(pos<0) {
            return false;
        }
        $remove(pos);
        return true;
    }

    @Override
    public boolean add(V key) {
        int pos = Arrays.binarySearch(data, 0, size, key, cmp);
        if(pos >=0) {
            return false;
        } else {
            $add(-pos - 1, key);
            return true;
        }
    }

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

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

        size--;
        data[size] = null;
    }

    private void $add(int index, V key) {
        data = ArrayAllocator.grow(data, size+1);

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

    private class KeyIterator extends RandomAccessIterator<V> {

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

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

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

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

    }

}
