// list in array

import java.lang.StringBuilder;
import java.util.Iterator;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;
import java.lang.UnsupportedOperationException;


public class ArrayList2<E> implements Iterable<E> {

	private E[] data;
	private int n;

    private int modCount = 0;


    @SuppressWarnings({"unchecked"})
	public ArrayList2(int size) {
        // Cannot create E[] array, create instead Object[]
		data = (E[]) (new Object[size]);
		n = 0;
	}

	public ArrayList2() {
        this(20);
	}

    @SuppressWarnings({"unchecked"})
    private void doubleCapacity() {
        E[] data2 = (E[]) (new Object[2*data.length]);
        for (int i = 0; i < n; i++)
            data2[i] = data[i];
        data = data2;
    }

	public int EOL() {
		return n;
	}

	public void insert(int p, E x) {
		if (p > n || p < 0)
			throw new ListException("Insert: invalid position" + p);

        if (n == data.length)
            doubleCapacity();

		for (int i = n; i > p; i--)
			data[i+1] = data[i];
		data[p] = x;
		n++;
        modCount++;
	}

	public E remove(int p) {
		if (p >= n || p < 0)
			throw new ListException("Remove: invalid position" + p);

		E x = data[p];

		for (int i = p; i < n-1; i++)
			data[i] = data[i+1];
		n--;

        modCount++;
		return x;
	}

	public int first() {
		return 0;
	}

	public int last() {
		return n-1;
	}

    public E getElement(int p) {
        return data[p];
    }

	public int getNext(int p) {
		if (p >= n || p < 0)
			throw new ListException("Next: invalid position" + p);

		return p+1;
	}

	public int size() {
        return n;
	}

    // content to string
	public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(data[i].toString());
            sb.append(" ");
        }
        return sb.toString();
    }

    // implementation of Iterable
    public Iterator<E> iterator() {
        return new ArrayList2Iter();
    }

    // Iterator class
    // This is not parametrized, but instead uses E of the List class.
    private class ArrayList2Iter implements Iterator<E> {

        // current location
        int ind;

        // maintain information of original modCount
        // if modified frmo elsewhere, change is detected here
        int initialModCount;

        public ArrayList2Iter() {
            ind = 0;
            initialModCount = modCount;
        }

        public boolean hasNext() {
            checkModCount();
            return ind < n;
        }

        public E next() {
            checkModCount();
            if (ind >= n) {
                throw new NoSuchElementException(
                      "next() called without hasNext()");
            }
            return data[ind++];

        }

        public void remove() {
            throw new UnsupportedOperationException("remove() not implemented");
            // if remove would be implemented, then it would update
            // initialModCount = ++modCount;
        }


        // check if modCount has changed
        void checkModCount() {
            if (modCount != initialModCount)
                throw new ConcurrentModificationException(
                      "List changes during iteration");
        }
    } // class ArrayList2Iter


} // class ArrayList2