public class MyArrayList<E> implements MyList<E> {
  public static final int INITIAL_CAPACITY = 16;
  private E[] data = (E[])new Object[INITIAL_CAPACITY];
  private int size = 0; // Liczba elementów na liście

  /** Tworzenie pustej listy */
  public MyArrayList() {
  }

  /** Tworzenie listy na podstawie tablicy obiektów */
  public MyArrayList(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      add(objects[i]); // Ostrzeżenie: nie używaj wywołania super(objects)!
  }

  @Override /** Dodawanie nowego elementu o podanym indeksie */
  public void add(int index, E e) {   
    // Upewnianie się, że indeks zawiera się w odpowiednim przedziale
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException
        ("Indeks: " + index + ", Wielkość: " + size);
    
    ensureCapacity();

    // Przesuwanie elementów po podanym indeksie w prawo 
    for (int i = size - 1; i >= index; i--)
      data[i + 1] = data[i];

    // Wstawianie nowego elementu na pozycji data[index]
    data[index] = e;

    // Zwiększanie wielkości o 1
    size++;
  } // zobacz https://liveexample.pearsoncmg.com/dsanimation/Figure24_4.html

  /** Tworzenie nowej większej tablicy (podwajanie bieżącej i dodawanie 1) */
  private void ensureCapacity() {
    if (size >= data.length) {
      E[] newData = (E[])(new Object[size * 2 + 1]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    }
  }

  @Override /** Opróżnianie listy */
  public void clear() {
    data = (E[])new Object[INITIAL_CAPACITY];
    size = 0;
  }

  @Override /** Zwraca true, jeśli lista zawiera dany element */
  public boolean contains(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return true;

    return false;
  }

  @Override /** Zwraca element o podanym indeksie */
  public E get(int index) {
    checkIndex(index);
    return data[index];
  }

  private void checkIndex(int index) {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException
        ("Indeks: " + index + ", Wielkość: " + size);
  }
  
  @Override /** Zwraca indeks pierwszego pasującego elementu
    * listy. -1 oznacza brak dopasowania. */
  public int indexOf(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Zwraca indeks ostatniego pasującego elementu
     * listy. -1 oznacza brak dopasowania. */
  public int lastIndexOf(E e) {
    for (int i = size - 1; i >= 0; i--)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Usuwa z listy element o podanej pozycji.
     * Dalsze elementy są przesuwane w lewo.
     * Zwraca usunięty element. */
  public E remove(int index) {
    checkIndex(index);
    
    E e = data[index];

    // Przesuwanie danych w lewo
    for (int j = index; j < size - 1; j++)
      data[j] = data[j + 1];

    data[size - 1] = null; // Element jest teraz równy null

    // Zmniejszanie wielkości
    size--;

    return e;
  } // Zobacz https://liveexample.pearsoncmg.com/dsanimation/Figure24_5.html

  @Override /** Zastępowanie elementu ze wskazanej pozycji listy
    * podanym elementem. */
  public E set(int index, E e) {
    checkIndex(index);
    E old = data[index];
    data[index] = e;
    return old;
  }

  @Override
  public String toString() {
    StringBuilder result = new StringBuilder("[");

    for (int i = 0; i < size; i++) {
      result.append(data[i]);
      if (i < size - 1) result.append(", ");
    }

    return result.toString() + "]";
  }

  /** Zmniejsza pojemność do bieżącej wielkości */
  public void trimToSize() {
    if (size != data.length) { 
      E[] newData = (E[])(new Object[size]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    } // Gdy size == capacity, nie trzeba zmniejszać pojemności
  }

  @Override /** Przesłania metodę iterator() zdefiniowaną w interfejsie Iterable */
  public java.util.Iterator<E> iterator() {
    return new ArrayListIterator();
  }
 
  private class ArrayListIterator 
      implements java.util.Iterator<E> {
    private int current = 0; // Bieżący indeks

    @Override
    public boolean hasNext() {
      return current < size;
    }

    @Override
    public E next() {
      return data[current++];
    }

    @Override // Usuwa element zwrócony przez ostatnie wywołanie next()
    public void remove() {
    	if (current == 0) // Metoda next() nie została jeszcze wywołana
        throw new IllegalStateException(); 
      MyArrayList.this.remove(--current);
    }
  }
  
  @Override /** Zwraca liczbę elementów na liście */
  public int size() {
    return size;
  }
}
