/**
 * Jednosmerne zretezeny spojovy seznam
 * @author Pavel Micka
 * @param <ENTITY> typovy parametr specifikujici ukladany typ
 */
public class MyLinkedList<ENTITY>{

    private Node first;
    private Node last;
    private int size;

    /**
     * Konstruktor spojoveho seznamu
     */
    public MyLinkedList() {
        this.size = 0;
    }

    /**
     * Vlozi na konec seznamu prvek
     * @param i prvek k vlozeni
     */
    public void add(ENTITY i) {
        Node n = new Node(i);
        if (size == 0) {
            this.first = n;
            this.last = n;
        } else {
            this.last.next = n;
            this.last = n;
        }
        size++;
    }

    /**
     * Vrati prvek na indexu i
     * @param i index prvku
     * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
     * @throws IllegalArgumentException pokud je i zaporne
     * @return prvek na indexu i
     */
    public ENTITY get(int i) {
        if (i >= size) {
            throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
        }
        if (i < 0) {
            throw new IllegalArgumentException("Index mensi nez 0");
        }
        Node curr = first;
        for (int j = 0; j < i; j++) {
            curr = curr.next;
        }
        return curr.value;
    }

    /**
     * Smaze prvek na indexu i
     * @param i index mazaneho prvku
     * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
     * @throws IllegalArgumentException pokud je i zaporne
     */
    public void remove(int i) {
        if (i >= size) {
            throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
        }
        if (i < 0) {
            throw new IllegalArgumentException("Index mensi nez 0");
        }
        if (i == 0) {
            first = first.next;
        } else {
            Node curr = first;
            for (int j = 0; j < i - 1; j++) { //najdeme predchozi
                curr = curr.next;
            }
            curr.next = curr.next.next; //a mazany prvek vynechame
            if (i == size - 1) { //pokud mazeme posledni
                last = curr;
            }
        }
        size--;
    }

    /**
     * Dotaz na delku seznamu
     * @return delka seznamu
     */
    public int size() {
        return this.size;
    }

    /**
     * Klasicka toString metoda, vraci textovou reprezentaci objektu
     * @return textova reprezentace objektu
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node curr = first;
        for (int i = 0; i < this.size; i++) {
            builder.append(curr.value);
            builder.append(" ");
            curr = curr.next;
        }
        return builder.toString();
    }

    public Iterator<ENTITY> iterator() {
        return new LinkedListIterator();
    }
    
    /**
     * Vnitrni trida reprezentujici jeden uzel spojoveho seznamu
     */
    private class Node {

        private ENTITY value;
        private Node next;

        private Node(ENTITY value) {
            this.value = value;
        }
    }    
    
    /* *************************************************
     *                   ITERATOR                      *  
     * *************************************************/
     
    /**
     * Jednoduchy iterator pro spojovy seznam
     * Neresi situaci, kdy je iteratoru pod rukou pozmena kolekce (tj. neni fail fast)
     * @param <ENTITY> typovy parametr specifikujici typ ulozeny v prochazene kolekce
     * 
     * Poznamka: Jelikoz je iterator vytvaren jako soukroma vnitrni trida, tak 
     * je dokanale skryt (zapouzdren) pred okolnim svetem. Veskera jeho volani
     * mohou byt uskutecnena pouze skrze inteface iterator
     * 
     * Poznamka2: V realnem Java svete bychom pouzili pro iterator interface
     * java.util.Iterator a pro iterovanou tridu interface java.lang.Iterable.
     * Tato implementace slouzi pouze jako ukazka vzoru samotneho bez navaznosti
     * na tato Java-specific rozhrani 
     */
    private class LinkedListIterator implements Iterator<ENTITY>{
        /**
         * Odkaz na soucasny uzel spojoveho seznamu
         */
        private Node currNode;
        /**
         * Priznak toho, ze je iterator nastaven na -1 prvek 
         * (tj. jeste nebyl pouzit k prechodu na prvni prvek)
         */
        private boolean start;

        public LinkedListIterator() {
            this.currNode = null;
            this.start = true;
        }

        @Override
        public boolean hasNext() {
            if (start) {
                return first != null;
            }
            return currNode.next != null;
        }

        @Override
        public ENTITY next() {
            if (start) {
                start = false;
                currNode = first;
            } else {
                currNode = currNode.next;
            }
            return currNode.value;
        }
    }
}

/**
 * Rozhrani iteratoru. Iterator slouzi k sekvencnimu pruchodu pres objekty ulozene v kolekci/kontejneru
 * @author Pavel Micka
 * @param <ENTITY> typovy parametr iteratoru 
 */
interface Iterator<ENTITY>{
    /**
     * Dotaz na existenci dalsiho prvku
     * @return @true, pokud dalsi prvek existuje, @false v opacnem pripade
     */
    public boolean hasNext();
    /**
     * Navrati dalsi entitu
     * @return dalsi entita ("dalsi" je zavisle na konkretni implementaci iteratoru)
     */
    public ENTITY next();
}