import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

import sun.org.mozilla.javascript.internal.Node;

/**
 * Iterator zum Durchlaufen von Binärbäumen nach der präfixen WLR Methode.
 * @author csdixi
 * @param <K>Primärschlüssel
 * @param <D>Daten die an die einzelnen Primärschlüssel gebunden sind
 */
class WLR<K extends Comparable<K>, D> implements Iterator<Pair<K, D>> {

    protected Stack<Node<K, D>> stack = new Stack<Node<K, D>>();
    protected Node<K, D> ergebnis;

    /**
     * Konstruktor, der beim erstellen des Objekt die übergebene Wurzel in den
     * Stack legt
     *
     * @param root ist die Wurzel des Baumes
     */
    public WLR(Node<K, D> root) {
        stack.push(root);
    }

    @Override
    /**
     * Methode die überprüft ob ein weiteres Element in Binärbaum vorhanden ist
     */
    public boolean hasNext() {

        if (ergebnis.left == null && stack.empty()) {
            return false;
        }
        return true;
    }

    @Override
    /**
     * Methode das nächste Element ausgibt
     */
    public Pair<K, D> next() throws NoSuchElementException {

        // Wurzel ist das nächste Element
        if (ergebnis == null && !stack.empty()) {
            ergebnis = stack.pop();
        //Knoten hat linken und rechten Knoten
        } else if (ergebnis.left != null && ergebnis.right != null) {
            stack.push(ergebnis.right);
            ergebnis = ergebnis.left;
        //Knoten hat linken aber keinen rechten Knoten
        } else if (ergebnis.left != null && ergebnis.right == null) {
            ergebnis = ergebnis.left;
        //Knoten hat keinen linken aber rechten Knoten
        } else if (ergebnis.left == null && ergebnis.right != null) {
            ergebnis = ergebnis.right;
        //Knoten hat keinen linken und keinen rechten Knoten
        } else if (ergebnis.left == null && ergebnis.right == null
                && !stack.empty()) {
            ergebnis = stack.pop();
        //Kein weiteres Element vorhanden
        } else {
            throw new NoSuchElementException(
                    "Fehler, es gibt kein weiteres linkes Element und der Stack ist leer!");
        }

        return new Pair<K, D>(ergebnis.key, ergebnis.data);
    }

    @Override
    public void remove() {

        throw new UnsupportedOperationException();

    }

}