/**
 * 
 */
package com.allendowney.thinkdast;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * @author downey
 * @param <T>
 *
 */
public class MyLinkedList<T> implements List<T> {

   /**
    * Klasa Node jest taka sama jak klasa ListNode przedstawiona w przykładzie, ale sparametryzowana za pomocą T
    *
    * @author downey
    *
    */
   private class Node {
      public T data;
      public Node next;

      public Node(T data) {
         this.data = data;
         this.next = null;
      }

      public Node(T data, Node next) {
         this.data = data;
         this.next = next;
      }
      public String toString() {
         return "Węzeł(" + data.toString() + ")";
      }
   }

   private int size;    // przechowuje bieżącą liczbę elementów
   private Node head;   // referencja do pierwszego węzła

   /**
    *
    */
   public MyLinkedList() {
      head = null;
      size = 0;
   }

   /**
    * @param args
    */
   public static void main(String[] args) {
      // wykonuje kilka prostych testów
      List<Integer> mll = new MyLinkedList<Integer>();
      mll.add(1);
      mll.add(2);
      mll.add(3);
      System.out.println(Arrays.toString(mll.toArray()) + " rozmiar = " + mll.size());

      mll.remove(new Integer(2));
      System.out.println(Arrays.toString(mll.toArray()) + " rozmiar = " + mll.size());
   }

   @Override
   public boolean add(T element) {
      if (head == null) {
         head = new Node(element);
      } else {
         Node node = head;
         // przejdź za pomocą pętli aż do ostatniego węzła
         for ( ; node.next != null; node = node.next) {}
         node.next = new Node(element);
      }
      size++;
      return true;
   }

   @Override
   public void add(int index, T element) {
      // nie trzeba sprawdzać zakresu; zrobi to już metoda getNode.
      if (index == 0) {
         head = new Node(element, head);
      } else {
         Node node = getNode(index-1);
         node.next = new Node(element, node.next);
      }
      size++;
   }

   @Override
   public boolean addAll(Collection<? extends T> collection) {
      boolean flag = true;
      for (T element: collection) {
         flag &= add(element);
      }
      return flag;
   }

   @Override
   public boolean addAll(int index, Collection<? extends T> collection) {
      throw new UnsupportedOperationException();
   }

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

   @Override
   public boolean contains(Object obj) {
      return indexOf(obj) != -1;
   }

   @Override
   public boolean containsAll(Collection<?> collection) {
      for (Object obj: collection) {
         if (!contains(obj)) {
            return false;
         }
      }
      return true;
   }

   @Override
   public T get(int index) {
      Node node = getNode(index);
      return node.data;
   }

   /** Zwraca element występujący pod podanym indeksem.
    * @param index
    * @return
    */
   private Node getNode(int index) {
      if (index < 0 || index >= size) {
         throw new IndexOutOfBoundsException();
      }
      Node node = head;
      for (int i=0; i<index; i++) {
         node = node.next;
      }
      return node;
   }

   @Override
   public int indexOf(Object target) {
      Node node = head;
      for (int i=0; i<size; i++) {
         if (equals(target, node.data)) {
            return i;
         }
         node = node.next;
      }
      return -1;
   }

   /** Sprawdza, czy element listy jest podanym elementem.
    *
    * Obsługuje szczególny przypadek, gdy podany element ma wartość null.
    *
    * @param target
    * @param object
    */
   private boolean equals(Object target, Object element) {
      if (target == null) {
         return element == null;
      } else {
         return target.equals(element);
      }
   }

   @Override
   public boolean isEmpty() {
      return size == 0;
   }

   @Override
   public Iterator<T> iterator() {
      T[] array = (T[]) toArray();
      return Arrays.asList(array).iterator();
   }

   @Override
   public int lastIndexOf(Object target) {
      Node node = head;
      int index = -1;
      for (int i=0; i<size; i++) {
         if (equals(target, node.data)) {
            index = i;
         }
         node = node.next;
      }
      return index;
   }

   @Override
   public ListIterator<T> listIterator() {
      return null;
   }

   @Override
   public ListIterator<T> listIterator(int index) {
      return null;
   }

   @Override
   public boolean remove(Object obj) {
      int index = indexOf(obj);
      if (index == -1) {
         return false;
      }
      remove(index);
      return true;
   }

   @Override
   public T remove(int index) {
      T element = get(index);
      if (index == 0) {
         head = head.next;
      } else {
         Node node = getNode(index-1);
         node.next = node.next.next;
      }
      size--;
      return element;
   }

   @Override
   public boolean removeAll(Collection<?> collection) {
      boolean flag = true;
      for (Object obj: collection) {
         flag &= remove(obj);
      }
      return flag;
   }

   @Override
   public boolean retainAll(Collection<?> collection) {
      throw new UnsupportedOperationException();
   }

   @Override
   public T set(int index, T element) {
      Node node = getNode(index);
      T old = node.data;
      node.data = element;
      return old;
   }

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

   @Override
   public List<T> subList(int fromIndex, int toIndex) {
      if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
         throw new IndexOutOfBoundsException();
      }
      // TODO: sklasyfikuj i ulepsz tę metodę.
      int i = 0;
      MyLinkedList<T> list = new MyLinkedList<T>();
      for (Node node=head; node != null; node = node.next) {
         if (i >= fromIndex && i <= toIndex) {
            list.add(node.data);
         }
         i++;
      }
      return list;
   }

   @Override
   public Object[] toArray() {
      Object[] array = new Object[size];
      int i = 0;
      for (Node node=head; node != null; node = node.next) {
         // System.out.println(node);
         array[i] = node.data;
         i++;
      }
      return array;
   }

   @Override
   public <T> T[] toArray(T[] a) {
      throw new UnsupportedOperationException();
   }
}