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

import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.RandomAccess;
import net.ranides.assira.annotations.Meta;
import net.ranides.assira.collection.IntCollection;
import net.ranides.assira.collection.arrays.NativeArrayAllocator;
import net.ranides.assira.collection.iterators.IntIterator;
import net.ranides.assira.collection.BlockCollection;
import net.ranides.assira.collection.arrays.ArrayAllocator;
import net.ranides.assira.collection.arrays.ArrayUtils;

/**
 * A type-specific array-based list; provides some additional methods that use
 polymorphism to avoid (un)boxing.
 *
 * <P>Instances of this class represent a list with
 * an array that is enlarged as needed when new entries are created (by doubling
 * its current length), but is
 * <em>never</em> made smaller (even on a {@link #clear()}). A family of
 * {@linkplain #trim() trimming methods} lets you control the size of the
 backing array; this is particularly useful if you reuse instances of this
 class. Range checks are equivalent to those of {@link java.util}'s classes,
 * but they are delayed as much as possible. The backing array is exposed by the
 * {@link #elements()} method.
 *
 * <p>This class implements the bulk methods
 * <code>removeElements()</code>,
 * <code>addElements()</code> and
 * <code>getElements()</code> using high-performance system calls (e.g., {@link
 * System#arraycopy(Object,int,Object,int,int) System.arraycopy()} instead of
 * expensive loops.
 *
 * @see java.util.ArrayList
 * 
 */
public class IntArrayList extends AIntList implements BlockCollection<Integer>, RandomAccess {
	
	private static final int[] EMPTY = new int[0];
    
    private static final long serialVersionUID = 2;
    
    protected static final int DEFAULT_INITIAL_CAPACITY = 16;

    protected transient int data[];
    
    protected int size;

    /**
     * Creates a new array list with given capacity.
     *
     * @param capacity the initial capacity of the array list (may be 0).
     */
    public IntArrayList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("Initial capacity (" + capacity + ") is negative");
        }
		if(capacity == 0) {
			data = EMPTY;
		}
        data = new int[capacity];
    }

    /**
     * Creates a new array list with {@link #DEFAULT_INITIAL_CAPACITY} capacity.
     */
    public IntArrayList() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    /**
     * Creates a new array list and fills it with a given collection.
     *
     * @param values a collection that will be used to fill the array list.
     */
    public IntArrayList(Collection<? extends Integer> values) {
        this(values.size());
        size = ArrayUtils.collect(values.iterator(), data);
    }

    /**
     * Creates a new array list and fills it with a given type-specific
     * collection.
     *
     * @param values a type-specific collection that will be used to fill the
     * array list.
     */
    public IntArrayList(IntCollection values) {
        this(values.size());
        size = ArrayUtils.collect(values.iterator(), data);
    }

    /**
     * Creates a new array list and fills it with a given type-specific list.
     *
     * @param list a type-specific list that will be used to fill the array
     * list.
     */
    public IntArrayList(IntList list) {
        this(list.size());
        list.getElements(0, data, 0, size = list.size());
    }

    /**
     * Creates a new array list and fills it with the elements of a given array.
     *
     * @param array an array whose elements will be used to fill the array list.
     */
    public IntArrayList(int array[]) {
        this(array, 0, array.length);
    }

    /**
     * Creates a new array list and fills it with the elements of a given array.
     *
     * @param array an array whose elements will be used to fill the array list.
     * @param offset the first element to use.
     * @param length the number of elements to use.
     */
    public IntArrayList(int array[], int offset, int length) {
        this(length);
        System.arraycopy(array, offset, this.data, 0, length);
        size = length;
    }

    /**
     * Creates a new array list and fills it with the elements returned by an
     * iterator..
     *
     * @param iterator an iterator whose returned elements will fill the array
     * list.
     */
    public IntArrayList(Iterator<? extends Integer> iterator) {
        this();
        while (iterator.hasNext()) {
            this.add(iterator.next());
        }
    }

    /**
     * Creates a new array list and fills it with the elements returned by a
     * type-specific iterator..
     *
     * @param iterator a type-specific iterator whose returned elements will
     * fill the array list.
     */
    @SuppressWarnings({
        "OverridableMethodCallInConstructor",
        "PMD.ConstructorCallsOverridableMethod"
    })
    public IntArrayList(IntIterator iterator) {
        this();
        while (iterator.hasNext()) {
            this.add(iterator.nextInt());
        }
    }

    /**
     * Returns the backing array of this list.
     *
     * @return the backing array.
     */
    @SuppressWarnings("PMD.MethodReturnsInternalArray")
    @SuppressFBWarnings("EI_EXPOSE_REP")
    @Meta.Unsafe
    public int[] elements() {
        return data;
    }

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

    /**
     * Grows this array list, ensuring that it can contain the given number of
     * entries without resizing, and in case enlarging it at least by a factor
     * of two.
     *
     * @param capacity the new minimum capacity for this array list.
     */
    private void grow(int capacity) {
        data = ArrayAllocator.grow(data, capacity, size);
    }

    @Override
    public void add(int index, int k) {
        checkIndex(index);
        grow(size + 1);
        if (index != size) {
            System.arraycopy(data, index, data, index + 1, size - index);
        }
        data[ index] = k;
        size++;
    }

    @Override
    public int getInt(int index) {
        checkIndexElement(index);
        return data[ index];
    }

    @Override
    public int indexOf(int k) {
        for (int i = 0; i < size; i++) {
            if (k == data[ i]) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(int k) {
        for (int i = size; i-- != 0;) {
            if (k == data[ i]) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int removeInt(int index) {
        if (index<0 || index >= size) {
            throw new IndexOutOfBoundsException("Index (" + index + ") is greater than or equal to list size (" + size + ")");
        }
        int old = data[ index];
        size--;
        if (index != size) {
            System.arraycopy(data, index + 1, data, index, size - index);
        }
        return old;
    }

    @Override
    public int set(int index, int k) {
        if (index<0 || index >= size) {
            throw new IndexOutOfBoundsException("Index (" + index + ") is greater than or equal to list size (" + size + ")");
        }
        int old = data[ index];
        data[ index] = k;
        return old;
    }

    @Override
    public void clear() {
        size = 0;
    }

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

    public void resize(int size) {
        if (size > data.length) {
            reserve(size);
        }
        if (size > this.size) {
            ArrayUtils.fill(data, this.size, size, 0);
        }
        this.size = size;
    }

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

    /**
     * Trims this array list so that the capacity is equal to the size.
     *
     * @see java.util.ArrayList#trimToSize()
     */
    @Override
    public boolean trim() {
        return trim(size);
    }
    
    /**
     * Trims the backing array if it is too large.
     *
     * If the current array length is smaller than or equal to
     * <code>n</code>, this method does nothing. Otherwise, it trims the array
     * length to the maximum between
     * <code>n</code> and {@link #size()}.
     *
     * <P>This method is useful when reusing lists. {@linkplain #clear() Clearing a
     * list} leaves the array length untouched. If you are reusing a list many
     * times, you can call this method with a typical size to avoid keeping
     * around a very large array just because of a few large transient lists.
     *
     * @param n the threshold for the trimming.
     */
    @Override
    public boolean trim(int n) {
        if (n >= data.length || size == data.length) {
            return true;
        }
        if(n<size) {
            throw new IllegalArgumentException(String.format("n= %d is too small (size=%d)", n, size));
        }
        try {
            int t[] = new int[Math.max(n, size)];
            System.arraycopy(data, 0, t, 0, size);
            data = t;
            return true;
        } catch(OutOfMemoryError e) {
            return false;
        }
        
    }

    /**
     * Copies element of this type-specific list into the given array using
     * optimized system calls.
     *
     * @param from the start index (inclusive).
     * @param target the destination array.
     * @param offset the offset into the destination array where to store the
     * first element copied.
     * @param length the number of elements to be copied.
     */
    @Override
    public void getElements(int from, int[] target, int offset, int length) {
        ArrayAllocator.ensureOffsetLength(target, offset, length);
        System.arraycopy(this.data, from, target, offset, length);
    }

    /**
     * Removes elements of this type-specific list using optimized system calls.
     *
     * @param from the start index (inclusive).
     * @param to the end index (exclusive).
     */
    @Override
    public void removeElements(int from, int to) {
        NativeArrayAllocator.ensureFromTo(size, from, to);
        System.arraycopy(data, to, data, from, size - to);
        size -= (to - from);
    }

    /**
     * Adds elements to this type-specific list using optimized system calls.
     *
     * @param index the index at which to add elements.
     * @param array the array containing the elements.
     * @param offset the offset of the first element to add.
     * @param length the number of elements to add.
     */
    @Override
    public void addElements(int index, int array[], int offset, int length) {
        checkIndex(index);
        ArrayAllocator.ensureOffsetLength(array, offset, length);
        grow(size + length);
        System.arraycopy(this.data, index, this.data, index + length, size - index);
        System.arraycopy(array, offset, this.data, index, length);
        size += length;
    }

    @Override
    public int[] toIntArray(int target[]) {
        if (target == null || target.length < size) {
            target = new int[size];
        }
        System.arraycopy(this.data, 0, target, 0, size);
        return target;
    }

    @Override
    public boolean addAll(int index, IntCollection values) {
        checkIndex(index);
        int n = values.size();
        if (n == 0) {
            return false;
        }
        grow(size + n);
        if (index != size) {
            System.arraycopy(data, index, data, index + n, size - index);
        }
        IntIterator itr = values.iterator();
        size += n;
        while (n-- != 0) {
            data[ index++] = itr.nextInt();
        }
        return true;
    }

    @Override
    public boolean addAll(int index, IntList values) {
        checkIndex(index);
        int n = values.size();
        if (n == 0) {
            return false;
        }
        grow(size + n);
        if (index != size) {
            System.arraycopy(data, index, data, index + n, size - index);
        }
        values.getElements(0, data, index, n);
        size += n;
        return true;
    }

    @Override
    public IntList subList(int from, int to) {
        checkIndex(from);
        checkIndex(to);
        if (from > to) {
            throw new IllegalArgumentException("Start index (" + from + ") is greater than end index (" + to + ")");
        }
        return new IntArrayFragment(from, to);
    }

    @Override
    public int compareTo(List<? extends Integer> list) {
        return list instanceof IntArrayList ? compareTo((IntArrayList)list) : super.compareTo(list);
    }
    
    /**
     * Compares this array list to another array list.
     *
     * <P>This method exists only for sake of efficiency. The implementation
     * inherited begin the abstract implementation would already work.
     *
     * @param list
     * @return a negative integer, zero, or a positive integer as this list is
     * lexicographically less than, equal to, or greater than the argument.
     */
    @SuppressFBWarnings("CO_SELF_NO_OBJECT")
    public int compareTo(IntArrayList list) {
        int s1 = size(), s2 = list.size();
        int a1[] = data, a2[] = list.data;
        int e1, e2;
        int r, i;
        for (i = 0; i < s1 && i < s2; i++) {
            e1 = a1[ i];
            e2 = a2[ i];
            if ((r = ((e1) < (e2) ? -1 : ((e1) == (e2) ? 0 : 1))) != 0) {
                return r;
            }
        }
        return i < s2 ? -1 : (i < s1 ? 1 : 0);
    }

    private void writeObject(java.io.ObjectOutputStream ostream) throws java.io.IOException {
        ostream.defaultWriteObject();
        for (int i = 0; i < size; i++) {
            ostream.writeInt(data[ i]);
        }
    }

    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream istream) throws java.io.IOException, ClassNotFoundException {
        istream.defaultReadObject();
        data = new int[size];
        for (int i = 0; i < size; i++) {
            data[ i] = istream.readInt();
        }
    }
    
    private final class IntArrayFragment extends AIntList implements RandomAccess {
        
        private static final long serialVersionUID = 2;

        protected int begin;
        protected int end;

        protected IntArrayFragment(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }

        @Override
        public void add(int index, int k) {
            IntArrayList.this.add(begin+index, k);
            end++;
        }

        @Override
        public int getInt(int index) {
            return IntArrayList.this.getInt(begin+index);
        }

        @Override
        public int indexOf(int k) {
            for (int i = begin; i <end; i++) {
                if (k == data[i]) {
                    return i-begin;
                }
            }
            return -1;
        }

        @Override
        public int lastIndexOf(int k) {
            for (int i = end; i-- != begin;) {
                if (k == data[i]) {
                    return i-begin;
                }
            }
            return -1;
        }

        @Override
        public int removeInt(int index) {
            int old = IntArrayList.this.removeInt(begin+index);
            end--;
            return old;
        }

        @Override
        public int set(int index, int k) {
            return IntArrayList.this.set(begin+index, k);
        }

        @Override
        public void clear() {
            IntArrayList.this.removeElements(begin, end);
            end = begin;
        }

        @Override
        public int size() {
            return end-begin;
        }

        @Override
        public void getElements(int from, int[] target, int offset, int length) {
            IntArrayList.this.getElements(begin+from, target, offset, Math.min(size(),length));
        }

        @Override
        public void removeElements(int from, int to) {
            IntArrayList.this.removeElements(begin+from, begin+to);
            end -= (to-from);
        }

        /**
         * Adds elements to this type-specific list using optimized system calls.
         *
         * @param index the index at which to add elements.
         * @param array the array containing the elements.
         * @param offset the offset of the first element to add.
         * @param length the number of elements to add.
         */
        @Override
        public void addElements(int index, int array[], int offset, int length) {
            IntArrayList.this.addElements(begin+index, array, offset, length);
            end += length;
        }

        @Override
        public int[] toIntArray(int target[]) {
            target = ArrayAllocator.ensureCapacity(target, size(), 0);
            System.arraycopy(data, begin, target, 0, size());
            return target;
        }

        @Override
        public boolean addAll(int index, IntCollection values) {
            IntArrayList.this.addAll(index+begin, values);
            end += values.size();
            return true;
        }

        @Override
        public boolean addAll(int index, IntList values) {
            IntArrayList.this.addAll(index+begin, values);
            end += values.size();
            return true;
            
        }

    }
    
}
