package fr.istic.prg1.tree_util;

import java.util.Stack;

public class BinaryTree<T>
{
    private Root element;
    private static boolean firstTime;

    static {
        BinaryTree.firstTime = true;
    }

    public BinaryTree() {
        if (BinaryTree.firstTime) {
            System.out.println("mise en oeuvre arbre binaire - pile des peres - version enseignant");
            BinaryTree.firstTime = false;
        }
        this.element = new Root();
    }

    public Iterator<T> iterator() {
        return new Element((Element)null);
    }

    public boolean isEmpty() {
        return this.element.isEmpty();
    }

    public static void controle() {
        final double v = 2013.0322;
        System.out.println("valeur de controle " + v);
    }

    private class Root
    {
        public T nextRoot;
        public Root doubleRoot;
        public Root simpleRoot;

        public Root() {
            this.nextRoot = null;
            this.doubleRoot = null;
            this.simpleRoot = null;
        }

        public boolean isEmpty() {
            return this.doubleRoot == null && this.simpleRoot == null;
        }
    }

    public class Element implements Iterator<T>
    {
        private Root root;
        private Stack<Root> stack;

        private Element() {
            this.stack = new Stack<Root>();
            this.root = BinaryTree.this.element;
        }

        @Override
        public void goLeft() {
            try {
                assert !this.isEmpty() : "le butoir n'a pas de fils";
                assert this.root.doubleRoot != null : "le fils gauche d'existe pas";
            }
            catch (AssertionError e) {
                e.printStackTrace();
                System.exit(0);
            }
            this.stack.push(this.root);
            this.root = this.root.doubleRoot;
        }

        @Override
        public void goRight() {
            try {
                assert !this.isEmpty() : "le butoir n'a pas de fils";
                assert this.root.simpleRoot != null : "le fils droit d'existe pas";
            }
            catch (AssertionError e) {
                e.printStackTrace();
                System.exit(0);
            }
            this.stack.push(this.root);
            this.root = this.root.simpleRoot;
        }

        @Override
        public void goUp() {
            try {
                assert !this.stack.empty() : " la racine n'a pas de pere";
            }
            catch (AssertionError e) {
                e.printStackTrace();
                System.exit(0);
            }
            this.root = this.stack.pop();
        }

        @Override
        public void goRoot() {
            this.stack.clear();
            this.root = BinaryTree.this.element;
        }

        @Override
        public boolean isEmpty() {
            return this.root.isEmpty();
        }

        @Override
        public NodeType nodeType() {
            if (this.isEmpty()) {
                return NodeType.SENTINEL;
            }
            if (this.root.doubleRoot.isEmpty()) {
                if (this.root.simpleRoot.isEmpty()) {
                    return NodeType.LEAF;
                }
                return NodeType.SIMPLE_RIGHT;
            }
            else {
                if (this.root.simpleRoot.isEmpty()) {
                    return NodeType.SIMPLE_LEFT;
                }
                return NodeType.DOUBLE;
            }
        }

        @Override
        public void remove() {
            try {
                assert this.nodeType() != NodeType.DOUBLE : "retirer : retrait d'un noeud double non permis";
            }
            catch (AssertionError e) {
                e.printStackTrace();
                System.exit(0);
            }
            Root sentinel = null;
            switch (this.nodeType()) {
                case SENTINEL: {
                    return;
                }
                case SIMPLE_LEFT: {
                    sentinel = this.root.doubleRoot;
                    break;
                }
                case SIMPLE_RIGHT: {
                    sentinel = this.root.simpleRoot;
                    break;
                }
                case LEAF: {
                    sentinel = new Root();
                    break;
                }
            }
            this.root.nextRoot = sentinel.nextRoot;
            this.root.doubleRoot = sentinel.doubleRoot;
            this.root.simpleRoot = sentinel.simpleRoot;
        }

        @Override
        public void clear() {
            this.root.nextRoot = null;
            this.root.doubleRoot = null;
            this.root.simpleRoot = null;
        }

        @Override
        public T getValue() {
            return this.root.nextRoot;
        }

        @Override
        public void addValue(final T v) {
            try {
                assert this.isEmpty() : "Ajouter : on n'est pas sur un butoir";
            }
            catch (AssertionError e) {
                e.printStackTrace();
                System.exit(0);
            }
            this.root.nextRoot = v;
            this.root.doubleRoot = new Root();
            this.root.simpleRoot = new Root();
        }

        @Override
        public void setValue(final T v) {
            this.root.nextRoot = v;
        }

        private void ancestor(final int i, final int j) {
            try {
                assert !this.stack.empty() : "switchValue : argument trop grand";
            }
            catch (AssertionError e) {
                e.printStackTrace();
                System.exit(0);
            }
            final Root x = this.stack.pop();
            if (j < i) {
                this.ancestor(i, j + 1);
            }
            else {
                final T v = x.nextRoot;
                x.nextRoot = this.root.nextRoot;
                this.root.nextRoot = v;
            }
            this.stack.push(x);
        }

        @Override
        public void switchValue(final int i) {
            try {
                assert i >= 0 : "switchValue : argument negatif";
            }
            catch (AssertionError e) {
                e.printStackTrace();
                System.exit(0);
            }
            if (i > 0) {
                this.ancestor(i, 1);
            }
        }
    }
}