package components.binarytree;

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

/**
 * {@code BinaryTree} represented as a recursive data structure, done
 * "bare-handed", with implementations of primary methods.
 *
 * <p>
 * Execution-time performance of all methods implemented in this class is O(1).
 *
 * @param <T>
 *            type of {@code BinaryTree} labels
 * @mathsubtypes <pre>
 * TREE_REP is  (
 *   size: integer,
 *   height: integer,
 *   rootLabel: T,
 *   leftSubtree: TREE_REP,
 *   rightSubtree: TREE_REP
 *  )
 * </pre>
 * @mathdefinitions {@code
 * IS_LEGAL_REP (
 *   tr: TREE_REP
 *  ): boolean is
 *  0 <= tr.height <= tr.size <= (2^tr.height - 1)  and
 *  (if tr.size > 0 then
 *   tr.size = 1 + tr.leftSubtree.size + tr.rightSubtree.size  and
 *   tr.height = 1 + max(tr.leftSubtree.height, tr.rightSubtree.height)  and
 *   [tr.rootLabel is not null]  and
 *   [tr.leftSubtree is not null]  and
 *   [tr.rightSubtree is not null]  and
 *   [tr.leftSubtree and tr.rightSubtree are not aliases]  and
 *   IS_LEGAL_REP(tr.leftSubtree)  and
 *   IS_LEGAL_REP(tr.rightSubtree))
 *
 * ABSTRACT_TREE (
 *   tr: TREE_REP
 *  ): binary 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, ABSTRACT_TREE(tr.leftSubtree),
 *                 ABSTRACT_TREE(tr.rightSubtree)))
 * }
 * @convention IS_LEGAL_REP($this)
 * @correspondence this = ABSTRACT_TREE($this)
 */
public class BinaryTree1<T> extends BinaryTreeSecondary<T> {

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

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

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

    /**
     * Root label.
     */

    private T rootLabel;

    /**
     * Left subtree.
     */
    private BinaryTree1<T> leftSubtree;

    /**
     * Right subtree.
     */
    private BinaryTree1<T> rightSubtree;

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

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

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

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

    @SuppressWarnings("unchecked")
    @Override
    public final BinaryTree<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(BinaryTree<T> source) {
        assert source != null : "Violation of: source is not null";
        assert source != this : "Violation of: source is not this";
        assert source instanceof BinaryTree1<?>
                : "Violation of: source is of dynamic type BinaryTree1<?>";
        /*
         * This cast cannot fail since the assert above would have stopped
         * execution in that case: source must be of dynamic type
         * BinaryTree1<?>, and the ? must be T or the call would not have
         * compiled.
         */
        BinaryTree1<T> localSource = (BinaryTree1<T>) source;
        this.size = localSource.size;
        this.height = localSource.height;
        this.rootLabel = localSource.rootLabel;
        this.leftSubtree = localSource.leftSubtree;
        this.rightSubtree = localSource.rightSubtree;
        localSource.createNewRep();
    }

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

    @Override
    public final void assemble(T root, BinaryTree<T> left, BinaryTree<T> right) {
        assert root != null : "Violation of: root is not null";
        assert left != null : "Violation of: left is not null";
        assert right != null : "Violation of: right is not null";
        assert left != this : "Violation of: left is not this";
        assert right != this : "Violation of: right is not this";
        assert left != right : "Violation of: left is not right";
        assert left instanceof BinaryTree1<?> : "Violation of: left is a BinaryTree1<?>";
        assert right instanceof BinaryTree1<?>
                : "Violation of: right is a BinaryTree1<?>";
        /*
         * These casts cannot fail since the asserts above would have stopped
         * execution in that case: both left and right must be of dynamic type
         * BinaryTree1<?>, and the ? must be T or the call would not have
         * compiled.
         */
        /*
         * There's a choice here between treating parameters left and right from
         * the client or the implementer point of view. Here we chose to use the
         * implementer point of view because it results in (small) performance
         * gains. Note that transferFrom is used despite this choice, which is
         * an apparent violation of the kernel purity rule. We considered the
         * alternative, to make a private version of transferFrom, and call it
         * here and from the public transferFrom, and decided it was not worth
         * doing it in this special case.
         */
        BinaryTree1<T> localLeft = (BinaryTree1<T>) left;
        BinaryTree1<T> localRight = (BinaryTree1<T>) right;
        this.size = 1 + localLeft.size + localRight.size;
        if (localLeft.height > localRight.height) {
            this.height = 1 + localLeft.height;
        } else {
            this.height = 1 + localRight.height;
        }
        this.rootLabel = root;
        if (this.leftSubtree == null) {
            this.leftSubtree = new BinaryTree1<T>();
        }
        this.leftSubtree.transferFrom(localLeft);
        if (this.rightSubtree == null) {
            this.rightSubtree = new BinaryTree1<T>();
        }
        this.rightSubtree.transferFrom(localRight);
    }

    @Override
    public final T disassemble(BinaryTree<T> left, BinaryTree<T> right) {
        assert left != null : "Violation of: left is not null";
        assert right != null : "Violation of: right is not null";
        assert left != this : "Violation of: left is not this";
        assert right != this : "Violation of: right is not this";
        assert left != right : "Violation of: left is not right";
        assert left instanceof BinaryTree1<?> : "Violation of: left is a BinaryTree1<?>";
        assert right instanceof BinaryTree1<?>
                : "Violation of: right is a BinaryTree1<?>";
        assert this.size != 0 : "Violation of: this /= empty_tree";
        /*
         * The casts below cannot fail since the asserts above would have
         * stopped execution in that case: left and right must be of dynamic
         * type BinaryTree1<?>, and the ? must be T or the call would not have
         * compiled.
         */
        T localRootLabel = this.rootLabel;
        BinaryTree1<T> localLeft = (BinaryTree1<T>) left;
        BinaryTree1<T> localRight = (BinaryTree1<T>) right;
        localLeft.transferFrom(this.leftSubtree);
        localRight.transferFrom(this.rightSubtree);
        this.createNewRep();
        return localRootLabel;
    }

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

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

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

    /**
     * Implementation of {@code Iterator} interface for {@code BinaryTree1}.
     */
    private final class BinaryTree1Iterator 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 LEFT or RIGHT;
         * otherwise null.
         */
        private Iterator<T> operative;

        /**
         * No-argument constructor.
         */
        private BinaryTree1Iterator() {
            /*
             * Iterator cannot start in right subtree, so there is no case for
             * that.
             */
            if (BinaryTree1.this.size == 0) {
                this.region = IteratorRegion.NONE;
                this.operative = null;
            } else if (BinaryTree1.this.leftSubtree.size > 0) {
                this.region = IteratorRegion.LEFT;
                this.operative = BinaryTree1.this.leftSubtree.iterator();
            } else {
                this.region = IteratorRegion.ROOT;
                this.operative = 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 LEFT: {
                    result = this.operative.next();
                    if (!this.operative.hasNext()) {
                        this.region = IteratorRegion.ROOT;
                        this.operative = null;
                    }
                    break;
                }
                case ROOT: {
                    result = BinaryTree1.this.rootLabel;
                    if (BinaryTree1.this.rightSubtree.size > 0) {
                        this.region = IteratorRegion.RIGHT;
                        this.operative = BinaryTree1.this.rightSubtree.iterator();
                    } else {
                        this.region = IteratorRegion.NONE;
                        this.operative = null;
                    }
                    break;
                }
                case RIGHT: {
                    result = this.operative.next();
                    if (!this.operative.hasNext()) {
                        this.region = IteratorRegion.NONE;
                        this.operative = 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;
    }

}