/* 
 * Kodkod -- Copyright (c) 2005-2011, Emina Torlak
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package kodkod.util.ints;

/**
 * A mutable implementation of the <tt>IntVector</tt> interface.  Implements
 * all optional IntVector operations.  In addition to implementing the <tt>IntVector</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the elements of the IntVector. <p>
 *
 * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * and <tt>iterator</tt> operations run in constant
 * time.  The <tt>insert</tt> operations run in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  <p>
 *
 * Each <tt>MutableIntVector</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to a MutableIntVector,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.<p> 
 *
 * An application can increase the capacity of an <tt>MutableIntVector</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.<p>
 * 
 * This impementation is not synchronized and its iterators are not fail-fast.
 * 
 * @author Emina Torlak
 */
public final class ArrayIntVector extends AbstractIntVector {

	private int[] elements;
	private int size;

	/**
	 * Constructs an empty <tt>MutableIntVector</tt> with the specified initial capacity.
	 *
	 * @exception IllegalArgumentException if the specified initial capacity
	 *            is negative
	 */
	public ArrayIntVector(int initialCapacity) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal Capacity: "+
					initialCapacity);
		this.elements = new int[initialCapacity];
	}

	/**
	 * Constructs an empty <tt>MutableIntVector</tt> with an initial capacity of ten.
	 */
	public ArrayIntVector() {
		this(10);
	}

	/**
	 * Constructs a <tt>MutableIntVector</tt> containing the elements of the specified
	 * array, in proper sequence.  The <tt>MutableIntVector</tt> instance has an initial capacity of
	 * 110% the size of the specified collection.
	 *
	 * @throws NullPointerException if the specified array is null.
	 */
	public ArrayIntVector(int[] array) {
		size = array.length;
		// Allow 10% room for growth
		int capacity = (int) Math.min((size*110L)/100, Integer.MAX_VALUE);
		elements = new int[capacity];
		System.arraycopy(array, 0, elements, 0, size);
	}

	/**
	 * Trims the capacity of this <tt>MutableIntVector</tt> instance to be the
	 * list's current size.  An application can use this operation to minimize
	 * the storage of an <tt>MutableIntVector</tt> instance.
	 */
	public void trimToSize() {

		int oldCapacity = elements.length;
		if (size < oldCapacity) {
			int[] oldData = elements;
			elements = new int[size];
			System.arraycopy(oldData, 0, elements, 0, size);
		}
	}

	/**
	 * Increases the capacity of this <tt>MutableIntVector</tt> instance, if
	 * necessary, to ensure  that it can hold at least the number of elements
	 * specified by the minimum capacity argument. 
	 */
	public void ensureCapacity(int minCapacity) {

		int oldCapacity = elements.length;
		if (minCapacity > oldCapacity) {
			int[] oldData = elements;
			int newCapacity = (oldCapacity * 3)/2 + 1;
			if (newCapacity < minCapacity)
				newCapacity = minCapacity;
			elements = new int[newCapacity];
			System.arraycopy(oldData, 0, elements, 0, size);
		}
	}
	
	

	/**
	 * @throws IndexOutOfBoundsException  index < 0 or index >= size
	 */
	private void checkExcludeLength(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException();
	}
	
	/**
	 * @throws IndexOutOfBoundsException  index < 0 or index > size
	 */
	private void checkIncludeLength(int index) {
		if (index < 0 || index > size)
			throw new IndexOutOfBoundsException();
	}
	
	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.IntVector#get(int)
	 */
	public int get(int index) {
		checkExcludeLength(index);
		return elements[index];
	}

	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.IntVector#size()
	 */
	public int size() {
		return size;
	}

	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.IntVector#set(int, int)
	 */
	@Override
	public int set(int index, int element) {
		final int oldValue = get(index);
		elements[index] = element;
		return oldValue;
	}

	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.IntVector#add(int)
	 */
	@Override
	public boolean add(int element) {
		ensureCapacity(size+1);
		elements[size++] = element;
		return true;
	}
	
	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.IntVector#add(int, int)
	 */
	@Override
	public void add(int index, int element) {
		checkIncludeLength(index);

		ensureCapacity(size+1); 
		System.arraycopy(elements, index, elements, index + 1, size - index);
		elements[index] = element;
		size++;
	}

	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.IntVector#addAll(int, kodkod.util.ints.IntCollection)
	 */
	@Override
	public boolean addAll(int index, IntCollection c) {
		checkIncludeLength(index);
		
		final int csize = c.size();
		if (csize==0) return false;
		
		ensureCapacity(size+csize); 
		System.arraycopy(elements, index, elements, index + csize, size - index);
		
		for(IntIterator iter = c.iterator(); iter.hasNext(); ) {
			elements[index++] = iter.next();
		}
		
		return true;
	}
	
	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.AbstractIntVector#removeAt(int)
	 */
	@Override
	public int removeAt(int index) { 
		checkExcludeLength(index);
		final int old = elements[index];
		System.arraycopy(elements, index+1, elements, index, size - index - 1);
		size--;
	   	return old;
	}
	
	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.AbstractIntCollection#toArray(int[])
	 */
	@Override
	public int[] toArray(int[] array) {
		if (array.length < size) {
			array = new int[size];
		}
		System.arraycopy(elements, 0, array, 0, size);
		return array;
	}
}
