package components.tree;

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

import components.sequence.Sequence;
import components.sequence.Sequence3;

/**
 * {@code Tree} represented as a recursive data structure, done "bare-handed",
 * with implementations of primary methods.
 *
 * @param <T>
 *            type of {@code Tree} labels
 * @mathsubtypes <pre>
 * TREE_REP is  (
 *   size: integer,
 *   height: integer,
 *   rootLabel: T,
 *   subtrees: string of TREE_REP
 *  )
 * </pre>
 * @mathdefinitions {@code
 * IS_LEGAL_REP (
 *   tr: TREE_REP
 *  ): boolean is
 *  0 <= tr.height <= tr.size  and
 *  (if tr.size > 0 then
 *   [tr.size = 1 + sum of the sizes of the TREE_REP in tr.subtrees]  and
 *   [tr.height = 1 + max of the heights of the TREE_REP in tr.subtrees]  and
 *   [tr.rootLabel is not null]  and
 *   [tr.subtrees is not null]  and
 *   STRING_IS_LEGAL_REP(tr.subtrees)
 *  else
 *   [tr.rootLabel is null]  and
 *   [tr.subtrees is null])
 *
 * STRING_IS_LEGAL_REP (
 *   s: string of TREE_REP
 *  ): string of tree of T satisfies
 *  if s = <> then
 *   STRING_IS_LEGAL_REP(s) = true
 *  else
 *   there exists t: TREE_REP, rest: string of TREE_REP
 *    (s = <t> * rest  and
 *     [t is not null]  and
 *     [t is not aliased to any of the TREE_REP in rest]  and
 *     STRING_IS_LEGAL_REP(s) = IS_LEGAL_REP(t) and STRING_IS_LEGAL_REP(rest))
 *
 * ABSTRACT_TREE (
 *   tr: TREE_REP
 *  ): tree of T satisfies
 *  if IS_LEGAL_REP(tr) then
 *   (if tr.size = 0 then
 *     ABSTRACT_TREE(tr) = empty_tree
 *    else
 *     ABSTRACT_TREE(tr) =
 *      compose(tr.rootLabel, STRING_ABSTRACT_TREE(tr.subtrees)))
 *
 * STRING_ABSTRACT_TREE (
 *   s: string of TREE_REP
 *  ): string of tree of T satisfies
 *  if STRING_IS_LEGAL_REP(s) then
 *   (if s = <> then
 *     STRING_ABSTRACT_TREE(s) = <>
 *    else
 *     there exists t: TREE_REP, rest: string of TREE_REP
 *      (s = <t> * rest and
 *       STRING_ABSTRACT_TREE(s) =
 *        ABSTRACT_TREE(t) * STRING_ABSTRACT_TREE(rest)))
 * }
 * @convention IS_LEGAL_REP($this)
 * @correspondence this = ABSTRACT_TREE($this)
 */
public class Tree1<T> extends TreeSecondary<T> {

    /*
     * Private members --------------------------------------------------------
     */

    /**
     * Size of tree.
     */
    private int size;

    /**
     * Height of tree.
     */
    private int height;

    /**
     * Root label.
     */

    private T rootLabel;

    /**
     * Subtrees.
     */
    private Sequence<Tree<T>> subtrees;

    /**
     * Creator of initial representation.
     */
    private void createNewRep() {
        this.size = 0;
        this.height = 0;
        this.rootLabel = null;
        this.subtrees = null;
    }

    /*
     * Constructors -----------------------------------------------------------
     */

    /**
     * No-argument constructor.
     */
    public Tree1() {
        this.createNewRep();
    }

    /*
     * Standard methods -------------------------------------------------------
     */

    @SuppressWarnings("unchecked")
    @Override
    public final Tree<T> newInstance() {
        try {
            return this.getClass().getConstructor().newInstance();
        } catch (ReflectiveOperationException e) {
            throw new AssertionError(
                    "Cannot construct object of type " + this.getClass());
        }
    }

    @Override
    public final void clear() {
        this.createNewRep();
    }

    @Override
    public final void transferFrom(Tree<T> source) {
        assert source != null : "Violation of: source is not null";
        assert source != this : "Violation of: source is not this";
        assert source instanceof Tree1<?>
                : "Violation of: source is of dynamic type Tree1<?>";
        /*
         * This cast cannot fail since the assert above would have stopped
         * execution in that case: source must be of dynamic type Tree1<?>, and
         * the ? must be T or the call would not have compiled.
         */
        Tree1<T> localSource = (Tree1<T>) source;
        this.size = localSource.size;
        this.height = localSource.height;
        this.rootLabel = localSource.rootLabel;
        this.subtrees = localSource.subtrees;
        localSource.createNewRep();
    }

    /*
     * Kernel methods ---------------------------------------------------------
     */

    @Override
    public final Sequence<Tree<T>> newSequenceOfTree() {
        return new Sequence3<Tree<T>>();
    }

    @Override
    public final void assemble(T root, Sequence<Tree<T>> children) {
        assert root != null : "Violation of: root is not null";
        assert children != null : "Violation of: children is not null";
        assert children instanceof Sequence3<?>
                : "Violation of: the dynamic type of children must be "
                        + "the same as that returned by newSequenceOfTree";
        for (Tree<T> t : children) {
            assert t != null : "Violation of: all children are not null";
            assert t != this : "Violation of: all children are not this";
            assert t instanceof Tree1<?>
                    : "Violation of: the dynamic type of each entry of "
                            + "children must be the same as the dynamic type of this";
        }

        this.rootLabel = root;
        this.subtrees = this.newSequenceOfTree();
        this.size = 1;
        int maxHeight = 0;
        for (Tree<T> t : children) {
            /*
             * These casts cannot fail since the asserts above would have
             * stopped execution in that case: all children must be of dynamic
             * type Tree1<?>, and the ? must be T or the call would not have
             * compiled.
             */
            Tree1<T> localT = (Tree1<T>) t;
            this.size += localT.size;
            if (localT.height > maxHeight) {
                maxHeight = localT.height;
            }
        }
        this.height = 1 + maxHeight;
        this.subtrees.transferFrom(children);
    }

    @Override
    public final T disassemble(Sequence<Tree<T>> children) {
        assert this.size() > 0 : "Violation of: this /= empty_tree";
        assert children != null : "Violation of: children is not null";
        assert children instanceof Sequence3<?>
                : "Violation of: the dynamic type of children must be "
                        + "the same as that returned by newSequenceOfTree";

        T localRootLabel = this.rootLabel;
        children.transferFrom(this.subtrees);
        this.createNewRep();
        return localRootLabel;
    }

    @Override
    public final int size() {
        return this.size;
    }

    @Override
    public final Iterator<T> iterator() {
        return new Tree1Iterator();
    }

    /**
     * Regions for iterator.
     */
    private enum IteratorRegion {
        /**
         * There is no next label.
         */
        NONE,
        /**
         * Next label is from the root.
         */
        ROOT,
        /**
         * Next label is from current subtree.
         */
        CHILD
    };

    /**
     * Implementation of {@code Iterator} interface for {@code Tree1}.
     */
    private final class Tree1Iterator implements Iterator<T> {

        /**
         * Region of tree from which next label will come.
         */
        private IteratorRegion region;

        /**
         * Iterator from which next label will come, if region is CHILD;
         * otherwise null.
         */
        private Iterator<T> operative;

        /**
         * Iterator from which next subtree will come, if region is CHILD;
         * otherwise null.
         */
        private Iterator<Tree<T>> subtree;

        /**
         * No-argument constructor.
         */
        Tree1Iterator() {
            /*
             * Iterator starts at root.
             */
            if (Tree1.this.size == 0) {
                this.region = IteratorRegion.NONE;
            } else {
                this.region = IteratorRegion.ROOT;
            }
            this.operative = null;
            this.subtree = null;
        }

        @Override
        public boolean hasNext() {
            return this.region != IteratorRegion.NONE;
        }

        @Override
        public T next() {
            assert this.hasNext() : "Violation of: ~this.unseen /= <>";
            if (!this.hasNext()) {
                /*
                 * Exception is supposed to be thrown in this case, but with
                 * assertion-checking enabled it cannot happen because of assert
                 * above.
                 */
                throw new NoSuchElementException();
            }
            T result = null;
            switch (this.region) {
                case NONE: {
                    /*
                     * Cannot happen because of code above.
                     */
                    throw new AssertionError("Unreachable branch.");
                }
                case ROOT: {
                    result = Tree1.this.rootLabel;
                    this.subtree = Tree1.this.subtrees.iterator();
                    while (this.subtree.hasNext()) {
                        this.operative = this.subtree.next().iterator();
                        if (this.operative.hasNext()) {
                            this.region = IteratorRegion.CHILD;
                            break;
                        }
                    }
                    if ((this.operative == null) || !this.operative.hasNext()) {
                        this.region = IteratorRegion.NONE;
                        this.operative = null;
                        this.subtree = null;
                    }
                    break;
                }
                case CHILD: {
                    result = this.operative.next();
                    if (!this.operative.hasNext()) {
                        while (this.subtree.hasNext()) {
                            this.operative = this.subtree.next().iterator();
                            if (this.operative.hasNext()) {
                                break;
                            }
                        }
                        if (!this.operative.hasNext()) {
                            this.region = IteratorRegion.NONE;
                            this.operative = null;
                            this.subtree = null;
                        }
                    }
                    break;
                }
                default: {
                    /*
                     * Cannot happen because of the type of the expression.
                     */
                    throw new AssertionError("Unreachable branch.");
                }
            }
            return result;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("remove operation not supported");
        }

    }

    /*
     * Other methods (overridden for performance reasons) ---------------------
     */

    @Override
    public final T root() {
        assert this.size() > 0 : "Violation of: this /= empty_tree";
        return this.rootLabel;
    }

    @Override
    public final T replaceRoot(T x) {
        assert this.size() > 0 : "Violation of: this /= empty_tree";
        T root = this.rootLabel;
        this.rootLabel = x;
        return root;
    }

    @Override
    public final int height() {
        return this.height;
    }

    //    @Override
    //    public final void addSubtree(int pos, Tree<T> st) {
    //        assert this.size() > 0 : "Violation of: this /= empty_tree";
    //        assert 0 <= pos : "Violation of: 0 <= pos";
    //        assert pos <= this.numberOfSubtrees() : ""
    //                + "Violation of: pos <= [number of children of this]";
    //        /*
    //         * Move st into new tree t and clear st
    //         */
    //        Tree<T> t = st.newInstance();
    //        t.transferFrom(st);
    //        /*
    //         * Update the size and height.
    //         */
    //        this.size += t.size();
    //        if (this.height <= t.height()) {
    //            this.height = t.height() + 1;
    //        }
    //        /*
    //         * Add the new tree t so that no alias to st is created
    //         */
    //        this.subtrees.add(pos, t);
    //    }

    //    @Override
    //    public final Tree<T> removeSubtree(int pos) {
    //        assert this.size() > 0 : "Violation of: this /= empty_tree";
    //        assert 0 <= pos : "Violation of: 0 <= pos";
    //        assert pos < this.numberOfSubtrees() : ""
    //                + "Violation of: pos < [number of children of this]";
    //        /*
    //         * Remove the subtree
    //         */
    //        Tree<T> t = this.subtrees.remove(pos);
    //        /*
    //         * Update the size and height.
    //         */
    //        this.size -= t.size();
    //        /*
    //         * PROBLEM: there is no efficient way to update the height
    //         */
    //        return t;
    //    }

    @Override
    public final int numberOfSubtrees() {
        assert this.size() > 0 : "Violation of: this /= empty_tree";
        return this.subtrees.length();
    }

}