package modified;

import java.util.Arrays;
import java.util.Iterator;

/**
 * A list based on a partially-filled array.
 * 
 * @author Chad Hogg, William Killian
 * @param <E> The type of element stored in the list.
 */
public class MUArrayList<E> implements MUList<E> {

	// Class Invariants:
	// Let N be the number of elements in the list.
	// The size variable always contains N.
	// Positions 0 through N-1 in data contain the elements of the list, with
	// the first element in position 0, the next in 1, etc.
	// We don't care what is stored in data[N] or later positions.

	/** The length of the initial array. */
	public static final int DEFAULT_CAPACITY = 10;
	/** A partially-filled array containing the list elements. */
	private E[] data;
	/** The number of elements in the list. */
	private int size;

	/**
	 * Constructs a new empty list with the default capacity.
	 */
	@SuppressWarnings("unchecked")
	public MUArrayList() {
		data = (E[]) new Object[DEFAULT_CAPACITY];
		size = 0;
	}

	/**
	 * Ensures that this has some minimum capacity, growing if necessary.
	 * 
	 * @param minimumCapacity The desired minimum capacity.
	 * @postcondition The length of data is at least minimumCapacity, but possibly
	 *                larger.
	 * @throws OutOfMemoryError If there is not enough memory to store the larger
	 *                          array.
	 */
	public void ensureCapacity(int minimumCapacity) {
		if (data.length < minimumCapacity) {
			data = Arrays.copyOf(data, minimumCapacity);
		}
	}

	/**
	 * Doubles the capacity of this, but only if it is full.
	 * 
	 * @postcondition If the size and capacity were the same, capacity is now twice
	 *                as large.
	 */
	private void growIfFull() {
		if (size == data.length) {
			ensureCapacity(size * 2);
		}
	}

	/**
	 * Gets the number of elements in this list.
	 * 
	 * @return The number of elements.
	 */
	@Override
	public int size() {
		return size;
	}

	/**
	 * Gets whether or not this list contains no elements.
	 * 
	 * @return True if this list contains no elements, or false.
	 */
	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * Gets a String representation of this list.
	 * 
	 * @return A string like "( 1 4 8 )".
	 */
	public String toString() {
		final StringBuilder sb = new StringBuilder("( ");
		forEach((E elem) -> {
			sb.append(elem.toString()).append(' ');
		});
		sb.append(')');
		return sb.toString();
	}

	/**
	 * Moves all elements between lowestIndexToShift and size-1 to 1 later in the
	 * array.
	 * 
	 * @param lowestIndexToShift The index of the first element to move, which must
	 *                           be between 0 and size-1 inclusive.
	 * @postcondition Elements in positions less than lowestIndexToShift have not
	 *                changed, but elements in positions at or above
	 *                lowestIndexToShfit are now at the next index.
	 * @precondition The array may not be completely full.
	 * @throws IllegalStateException    If the array is full.
	 * @throws IllegalArgumentException If the index is out of bounds.
	 */
	private void shiftForward(int lowestIndexToShift) {
		final int elems = size - lowestIndexToShift;
		System.arraycopy(data, lowestIndexToShift, data, lowestIndexToShift + 1, elems);
	}

	/**
	 * Moves all elements between lowestIndexToShift and size-1 to 1 earlier in the
	 * array.
	 * 
	 * @param lowestIndexToShift The index of the first element to move, which must
	 *                           be between 1 and size-1 inclusive.
	 * @postcondition Elements in positions less than lowestIndexToShift-1 have not
	 *                changed, but the element at lowestIndexToShift has been
	 *                overwritten and all later elements are now at the previous
	 *                index.
	 * @throws IllegalArgumentException If the index is out of bounds.
	 */
	private void shiftBackward(int lowestIndexToShift) {
		final int elems = size - lowestIndexToShift;
		System.arraycopy(data, lowestIndexToShift, data, lowestIndexToShift - 1, elems);
	}

	/**
	 * Inserts a new value at the beginning of this list.
	 * 
	 * @param value The value to add.
	 * @postcondition The value is the first element in the list, preceding all
	 *                other elements.
	 */
	@Override
	public void insertFront(E value) {
		insertBefore(0, value);
	}

	/**
	 * Inserts a new value at the end of this list.
	 * 
	 * @param value The value to add.
	 * @postcondition The value is the last element in the list, following all other
	 *                elements.
	 */
	@Override
	public void insertBack(E value) {
		insertBefore(size, value);
	}

	/**
	 * Inserts a new value before an existing element.
	 * 
	 * @param index The 0-based index of that element, which must be at least 0 and
	 *              no greater than size.
	 * @param value The value to insert.
	 * @postcondition The value is in the list, between index-1 and index.
	 * @throws IllegalArgumentException If the index is out of range.
	 */
	@Override
	public void insertBefore(int index, E value) {
		// It's okay to insert before (size + 1) for an array
		if (index < 0 || index > size + 1) {
			throw new IllegalArgumentException("Index is out of range.");
		}
		growIfFull();
		shiftForward(index);
		data[index] = value;
		size++;
	}

	/**
	 * Inserts a new value after an existing element.
	 * 
	 * @param index The 0-based index of that element, which must be at least 0 and
	 *              less than size.
	 * @param value The value to insert.
	 * @postcondition The value is in the list, between index and index+1.
	 * @throws IllegalArgumentException If the index is out of range.
	 */
	@Override
	public void insertAfter(int index, E value) {
		insertBefore(index + 1, value);
	}

	/**
	 * Removes the first element of this list.
	 * 
	 * @precondition The list may not be empty.
	 * @return The element that was removed.
	 * @postcondition The first element of the list was removed.
	 * @throws IllegalStateException If this list is empty.
	 */
	@Override
	public E removeFront() {
		if (isEmpty()) {
			throw new IllegalStateException("May not remove from empty list.");
		}
		return removeAt(0);
	}

	/**
	 * Removes the last element of this list.
	 * 
	 * @precondition The list may not be empty.
	 * @return The element that was removed.
	 * @postcondition The last element of the list was removed.
	 * @throws IllegalStateException If this list is empty.
	 */
	@Override
	public E removeBack() {
		if (isEmpty()) {
			throw new IllegalStateException("May not remove from empty list.");
		}
		return removeAt(size - 1);
	}

	/**
	 * Removes an element of this list.
	 * 
	 * @param index The 0-based index of the element to remove, which must be at
	 *              least 0 and less than size.
	 * @return The element that was removed.
	 * @postcondition The element has been removed.
	 * @throws IllegalArgumentException If the index is out of range.
	 */
	@Override
	public E removeAt(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Index is out of range.");
		}
		E result = data[index];
		shiftBackward(index + 1);
		size--;
		return result;
	}

	/**
	 * Removes all elements from this list.
	 */
	@Override
	public void clear() {
		size = 0;
	}

	/**
	 * Gets the element at a specified index.
	 * 
	 * @param index The 0-based index of the element to get, which must be at least
	 *              0 and less than size.
	 * @return The element at that index.
	 * @throws IllegalArgumentException If the index is out of range.
	 */
	@Override
	public E get(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Index out of range.");
		}
		return data[index];
	}

	/**
	 * Sets the element at a specified index.
	 * 
	 * @param index The 0 based-index of the element to set, which must be at least
	 *              0 and less than size.
	 * @param value The value to replace.
	 * @return The element previously at that index.
	 * @postcondition The value is in the list, replacing the element that used to
	 *                be at that index.
	 * @throws IllegalArgumentException If the index is out of range.
	 */
	@Override
	public E set(int index, E value) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Index out of range.");
		}
		E oldValue = data[index];
		data[index] = value;
		return oldValue;
	}

	@Override
	public Iterator<E> iterator() {
		return new MUArrayListIterator();
	}

	private class MUArrayListIterator implements Iterator<E> {

		private int currentIndex;

		public MUArrayListIterator() {
			this.currentIndex = 0;
		}

		@Override
		public boolean hasNext() {
			return currentIndex < MUArrayList.this.size;
		}

		@Override
		public E next() {
			E value = MUArrayList.this.get(currentIndex);
			++currentIndex;
			return value;
		}

		@Override
		public void remove() {
			--currentIndex;
			MUArrayList.this.removeAt(currentIndex);
		}
	}
}