package edu.hm.cs.katz.algdat.trees;

import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;

/**
 * Class representing a binary tree storing only key values (like sets). This class does not provide
 * any operations changing the tree, as any dynamic operations have to be provided by the subclasses
 * adding additional restrictions.
 *
 * @author katz.bastian
 */
public class BinaryTree<T> {

    /** Root node of the tree, may be null for empty tree. */
    private TreeNode<T> root;

    /**
     * Constructor to define from an existing structure of {@link TreeNode}s.
     *
     * @param root root node
     */
    BinaryTree(TreeNode<T> root) {
        this.root = root;
    }

    /**
     * Constructor to define an empty tree.
     */
    public BinaryTree() {
        // intentionally left blank.
    }

    /* Query operations */

    /**
     * @return number of nodes in the tree.
     */
    int getSize() {
        return getSize(root);
    }

    /**
     * Helper method. Recursively calculates the number of nodes in the (sub)tree.
     *
     * @param node tree node
     * @return number of nodes in the subtree of the given node
     */
    private int getSize(TreeNode<T> node) {
        if (node == null) {
            return 0;
        }
        return 1 + getSize(node.left) + getSize(node.right);
    }

    /**
     * Calculates the height of the tree. By definition, the empty tree has height 0, a tree with
     * one node has height 1.
     *
     * @return the height of the tree.
     */
    int getHeight() {
        return getHeight(root);
    }

    /**
     * Helper method. Recursively calculates the height of a (sub)tree.
     *
     * @param node tree node
     * @return height of the subtree of the given node.
     */
    private int getHeight(TreeNode<T> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

    /**
     * @return number of leaves of the tree.
     */
    int getLeafCount() {
        // TODO: Aufgabe 13.1
        return getLeafCount(root);
    }

    private int getLeafCount(TreeNode<T> node) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        return getLeafCount(node.left) + getLeafCount(node.right);
    }

    /**
     * @param element key
     * @return true if the key is contained in the tree, false otherwise.
     */
    boolean contains(T element) {
        // TODO: Aufgabe 13.2
        return contains(root, element);
    }

    private boolean contains(TreeNode<T> node, T element) {
        if (node == null) {
            return false;
        }
        return node.data.equals(element) || contains(node.left, element)
                || contains(node.right, element);
    }

    /**
     * Vertauscht in allen Knoten linken und rechten Teilbaum.
     */
    void invert() {
        // TODO: Aufgabe 13.4
        invertTree(root);
    }

    private TreeNode<T> invertTree(TreeNode<T> node) {
        if (node == null) {
            return null;
        }
        TreeNode right = invertTree(node.right);
        TreeNode left = invertTree(node.left);
        node.left = right;
        node.right = left;
        return node;
    }

    /**
     * Entfernt alle Blätter, die den übergebenen Wert enthalten
     *
     * @param element Wert
     */
    void removeLeaves(T element) {
        // TODO: Aufgabe 13.5
        deleteLeaf(root, element);
    }

    private TreeNode<T> deleteLeaf(TreeNode<T> node, T key) {
        if (node == null) return node;
        if (contains(node.left, key)) {
            node.left = deleteLeaf(node.left, key);
        } else if (contains(node.right, key)) {
            node.right = deleteLeaf(node.right, key);
        }
        else {
            if (node.left == null)
                return node.right;
            else if (node.right == null)
                return node.left;
        }

        return node;
    }

    /* Traversal operations. */

    /**
     * Applies an operation on all nodes in the tree in level-order.
     *
     * @param operation operation to be applied to all nodes
     */
    void visitNodesBfs(Consumer<T> operation) {
        Queue<TreeNode<T>> bfsQueue = new LinkedList<>();

        // Initial wartet nur die Wurzel
        bfsQueue.add(root);

        // Solange noch Knoten warten
        while (!bfsQueue.isEmpty()) {

            // Nimm nächsten Knoten
            TreeNode<T> node = bfsQueue.remove();
            if (node != null) {
                // Bearbeite Knoten
                operation.accept(node.data);

                // Füge Kinder in Schlange ein
                bfsQueue.add(node.left);
                bfsQueue.add(node.right);
            }
        }
    }

    /**
     * Applies an operation on all nodes in the tree in pre-, in- or post-order, i.e. in any order
     * produces by depth-first-search.
     *
     * @param operation operation to be applied to all nodes
     * @param order     defines in which order the operation is applied to the node and the subtrees
     */
    void visitNodesDfs(Consumer<T> operation, DfsOrder order) {
        visitNodesDfs(root, operation, order);
    }

    /**
     * Helper method to recursively apply an operation on all nodes in the tree in pre-, in- or
     * post-order, i.e. in any order produces by depth-first-search.
     *
     * @param node      tree node
     * @param operation operation to be applied to all nodes in the subtree of the given node
     * @param order     defines in which order the operation is applied to the node and the subtrees
     */
    private void visitNodesDfs(TreeNode<T> node, Consumer<T> operation, DfsOrder order) {
        if (node != null) {

            // start with the node in pre-order
            if (order == DfsOrder.PREORDER) {
                operation.accept(node.data);
            }

            // recursively visit nodes in left subtree
            visitNodesDfs(node.left, operation, order);

            if (order == DfsOrder.INORDER) {
                operation.accept(node.data);
            }

            visitNodesDfs(node.right, operation, order);

            if (order == DfsOrder.POSTORDER) {
                operation.accept(node.data);
            }
        }
    }
}