package tree;

import com.tree.Tree;

import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;
import java.util.Stack;


/**
 * @author xjn
 * @since 2020-05-07
 */
public class AVLTree implements Tree {
    private class Node {
        public E e;
        public Node left;
        public Node right;
        public int height;

        public Node(E e) {
            this.e = e;
            this.left = this.right = null;
            this.height = 1;
        }

        public Node(Node node) {
            this.e = node.e;
            this.left = node.left;
            this.right = node.right;
            this.height = node.height;
        }


        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node root;
    private int size;

    public AVLTree() {
        this.root = null;
        this.size = 0;
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    public boolean isAVL() {
        return isAVL(this.root);
    }

    private boolean isAVL(Node node) {
        if (node == null) {
            return true;
        }
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return false;
        }
        return isAVL(node.left) && isAVL(node.right);
    }


    @Override
    public boolean isEmpty() {
        return size == 0;
    }

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

    @Override
    public void add(E e) {

    }

    private Node addRecursive(Node node, E e) {
        if (node == null) {
            node = new Node(e);
            size++;
            return node;
        }
        if (node.e.compareTo(e) < 0) {
            node.left = addRecursive(node.left, e);
        } else if (node.e.compareTo(e) > 0) {
            node.right = addRecursive(node.right, e);
        }
        //height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        //
        int balanceFactory = getBalanceFactor(node);

        //RR
        if (balanceFactory > 1 && getBalanceFactor(node.left) >= 0) {
            return rotateRight(node);
        }

        //LL
        if (balanceFactory < -1 && getBalanceFactor(node.right)  1 && getBalanceFactor(node.left) < 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }

        //RL
        if (balanceFactory < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }
        return node;
    }


    private Node rotateRight(Node y) {
        Node x = y.left;
        Node t3 = x.right;

        x.right = y;
        y.left = t3;
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.right), getHeight(x.left)) + 1;
        return x;
    }

    private Node rotateLeft(Node y) {
        Node x = y.right;
        Node t3 = x.left;

        x.left = y;
        y.right = t3;

        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }

    @Override
    public boolean contains(E e) {
        return false;
    }

    private boolean containsRecursive(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (node.e.compareTo(e) == 0) {
            return true;
        } else if (node.e.compareTo(e) > 0) {
            return containsRecursive(node.left, e);
        } else {
            return containsRecursive(node.right, e);
        }
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node);
        preOrder(node.left);
        preOrder(node.right);
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        preOrder(node.left);
        System.out.print(node);
        preOrder(node.right);
    }

    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node);
    }

    @Override
    public void bfs() {
        Queue queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.remove();
            System.out.print(node + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    @Override
    public void dfs() {
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node nodeFromStack = stack.pop();
            System.out.print(nodeFromStack.e + " ");
            if (nodeFromStack.right != null) {
                stack.push(nodeFromStack.right);
            }
            if (nodeFromStack.left != null) {
                stack.push(nodeFromStack.left);
            }
        }
    }

    @Override
    public int getTreeDepth() {
        return getTreeDepth(root);
    }

    private int getTreeDepth(Node node) {
        if (node == null) {
            return 0;
        }
        int left = getTreeDepth(node.left) + 1;
        int right = getTreeDepth(node.right) + 1;
        return Math.max(left, right);
    }

    @Override
    public E maximum() {
        return maximum(root).e;
    }

    private Node maximum(Node node) {
        if (node == null || node.left == null) {
            return node;
        }
        return maximum(node.left);
    }

    @Override
    public E minimum() {
        return minimum(root).e;
    }

    private Node minimum(Node node) {
        if (node == null || node.right == null) {
            return node;
        }
        return minimum(node.right);
    }

    @Override
    public E removeMaximum() {
        E e = maximum();
        root = removeMaximum(root);
        return e;
    }

    private Node removeMaximum(Node node) {
        if (node.left == null) {
            size--;
            return node.right;
        }
        node.left = removeMaximum(node.left);
        return node;
    }

    @Override
    public E removeMinimum() {
        return null;
    }

    private Node removeMinimum(Node node) {
        if (node.right == null) {
            size--;
            return node.left;
        }
        node.right = removeMinimum(node.right);
        return node;
    }

    @Override
    public void remove(E e) {

    }

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        Node retNode = null;
        if (node.e.compareTo(e) < 0) {
            node.left = remove(node.left, e);
            retNode = node;
        } else if (node.e.compareTo(e) > 0) {
            node.right = remove(node.right, e);
            retNode = node;
        }
        // node

        //
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            retNode = rightNode;
        } else if (node.right == null) {
            //
            Node leftNode = node.left;
            node.left = null;
            size--;
            retNode = leftNode;
        } else {
            //
            Node successor = minimum(node.right);
            successor.left = node.left;
            successor.right = removeMinimum(node.right);
            node.left = node.right = null;
            retNode = successor;
        }

        if (retNode == null) {
            return null;
        }
        //height
        retNode.height = Math.max(getHeight(retNode.right), getHeight(retNode.left)) + 1;

        //
        int balanceFactor = getBalanceFactor(retNode);

        //
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
            return rotateRight(retNode);
        }
        //
        if (balanceFactor < -1 && getBalanceFactor(retNode.right)  1 && getBalanceFactor(retNode.left) < 0) {
            retNode.left = rotateLeft(retNode.left);
            return rotateRight(retNode);
        }
        //RL
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            retNode.right = rotateRight(retNode.right);
            return rotateLeft(retNode);
        }
        return retNode;
    }

    private void writeArray(Node node, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        //
        if (node == null) {
            return;
        }
        //
        res[rowIndex][columnIndex] = String.valueOf(node.e);
        //
        int currLevel = (rowIndex + 1) / 2;
        //,
        if (currLevel == treeDepth) {
            return;
        }
        // 
        int gap = treeDepth - currLevel - 1;
        // "/"
        if (node.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(node.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }
        // "\"
        if (node.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(node.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }

    private String show(Node node) {
        StringBuilder builder = new StringBuilder();
        if (root == null) {
            return "EMPTY!";
        }
        int treeDepth = getTreeDepth();
        // 2n - 131
        // 
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2  1 && i  4 ? 2 : line[i].length() - 1;
                }
            }
            builder.append(sb.toString() + "\n");
        }
        return builder.toString();
    }
}