package es.upm.dit.adsw.tema2;

import es.upm.dit.adsw.ej2.OpMeter;
import es.upm.dit.adsw.ej5.My;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * BST - Binary Search Tree.
 * Arbol binario de busqueda.
 */
public class BST {
    private Node root;

    /**
     * Constructor.
     */
    public BST() {
        root = null;
    }

    public int depth() {
        return depth(root);
    }

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

    public int size() {
        return size(root);
    }

    private int size(Node node) {
        if (node == null)
            return 0;
        return 1 + size(node.left) + size(node.right);
    }

    public Object getMin1() {
        if (root == null)
            return null;
        return getMin1(root);
    }

    private Object getMin1(Node node) {
        if (node.left != null)
            return getMin1(node.left);
        return node.val;
    }

    public Object getMin2() {
        if (root == null)
            return null;
        Node node = root;
        while (node.left != null)
            node = node.left;
        return node.val;
    }

    /**
     * Mete un valor nuevo.
     * Si ya existe uno con misma clave, reemplaza el valor.
     *
     * @param key
     * @param val
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     * @throws RuntimeException         Si no cabe la clave.
     */
    public void put(String key, Object val) {
        if (key == null || key.length() == 0)
            throw new IllegalArgumentException("put(null, valor)");
        root = put(root, key, val);
    }
    private Node put(Node node, String key, Object val) {
        if (node == null)
            return new Node(key, val);
        int cmp = key.compareTo(node.key);
        if (cmp < 0)
            node.left = put(node.left, key, val);
        else if (cmp > 0)
            node.right = put(node.right, key, val);
        else
            node.val = val;
        return node;
    }

    public void put2(String key, Object val) {
        if (key == null || key.length() == 0)
            throw new IllegalArgumentException("put(null, valor)");
        if (root == null) {
            root = new Node(key, val);
            return;
        }
        Node parent = null;
        Node current = root;
        while (current != null) {
            int cmp = key.compareTo(current.key);
            if (cmp == 0) {
                current.val = val;
                return;
            }
            parent = current;
            if (cmp < 0)
                current = current.left;
            else
                current = current.right;
        }
        int cmp = key.compareTo(parent.key);
        if (cmp < 0)
            parent.left = new Node(key, val);
        else
            parent.right = new Node(key, val);
    }

    /**
     * Saca el valor asociado a la clave.
     *
     * @param key
     * @return null si no está la clave.
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     */
    public Object get(String key) {
        if (key == null || key.length() == 0)
            throw new IllegalArgumentException("get(null)");
        return get(root, key);
    }

    private Object get(Node node, String key) {
        if (node == null)
            return null;
        int cmp = key.compareTo(node.key);
        if (cmp == 0)
            return node.val;
        if (cmp < 0)
            return get(node.left, key);
        else
            return get(node.right, key);
    }

    public Object get2(String key) {
        Node node = root;
        while (node != null) {
            if (node.key.equals(key))
                return node.val;
            if (key.compareTo(node.key) < 0)
                node = node.left;
            else
                node = node.right;
        }
        return null;
    }

    /**
     * Elimina el objeto asociado a la clave, si está.
     *
     * @param key
     * @return devuelve el valor asociado si estaba la clave; devuelve null si no está la clave
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     */
    public Object remove(String key) {
        if (key == null || key.length() == 0)
            throw new IllegalArgumentException("remove(null)");
        Object found = get(key);
        if (found == null)
            return null;
        root = remove(root, key);
        return found;
    }

    private Node remove(Node node, String key) {
        if (node == null)
            return null;
        int cmp = OpMeter.compareTo(key, node.key);
        if (cmp == 0)
            return remove(node);
        if (cmp < 0)
            node.left = remove(node.left, key);
        else
            node.right = remove(node.right, key);
        return node;
    }

    private Node remove(Node nodo) {
        if (nodo.left == null && nodo.right == null)
            return null;
        if (nodo.left == null)
            return nodo.right;
        if (nodo.right == null)
            return nodo.left;
        Node maxIzq = extraeMaxIzq(nodo.left);
        nodo.key = maxIzq.key;
        nodo.val = maxIzq.val;
        nodo.left = remove(nodo.left, maxIzq.key);
        return nodo;
    }

    private Node extraeMaxIzq(Node nodo) {
        if (nodo.right == null)
            return nodo;
        return extraeMaxIzq(nodo.right);
    }

    /**
     * Elimina todas las claves.
     */
    public void clear() {
        root = null;
    }

    /**
     * Getter.
     *
     * @return nodo raiz.
     */
    public Node getRoot() {
        return root;
    }

    private void check(Node nodo) {
        if (nodo == null)
            return;
        String clave = nodo.key;
        Node izq = nodo.left;
        Node der = nodo.right;
        if (izq != null && izq.key.compareTo(clave) > 0)
            System.out.printf("error: %s > %s$n", izq.key, clave);
        if (der != null && clave.compareTo(der.key) > 0)
            System.out.printf("error: %s > %s$n", clave, der.key);
        check(izq);
        check(der);
    }

    private void dump(int level, Node node) {
        if (node == null) {
            for (int i = 0; i < level; i++)
                System.out.print(".");
            System.out.println("<>");
            return;
        }
        dump(level + 1, node.right);
        for (int i = 0; i < level; i++)
            System.out.print(".");
        System.out.println("<" + node.key + ">");
        dump(level + 1, node.left);
    }

    public List<String> inorder() {
        List<String> list = new ArrayList<>();
        inorder(list, root);
        return list;
    }

    private void inorder(List<String> list, Node node) {
        if (node != null) {
            inorder(list, node.left);
            list.add(node.key);
            inorder(list, node.right);
        }
    }

    public List<String> preorder() {
        List<String> list = new ArrayList<>();
        preorder(list, root);
        return list;
    }

    private void preorder(List<String> list, Node node) {
        if (node != null) {
            list.add(node.key);
            preorder(list, node.left);
            preorder(list, node.right);
        }
    }

    public List<String> postorder() {
        List<String> list = new ArrayList<>();
        postorder(list, root);
        return list;
    }

    private void postorder(List<String> list, Node node) {
        if (node != null) {
            postorder(list, node.left);
            postorder(list, node.right);
            list.add(node.key);
        }
    }

    private class Node {
        String key;
        Object val;
        Node left;
        Node right;

        Node(String clave, Object valor) {
            this.key = clave;
            this.val = valor;
        }
    }

    // smoke test
    public static void main(String[] args) {
        BST tree = new BST();
        put(tree, 15);
        put(tree, 8);
        put(tree, 24);
        put(tree, 5);
        put(tree, 19);
        put(tree, 12);
        put(tree, 9);
        put(tree, 30);
        put(tree, 28);
        put(tree, 17);
        put(tree, 20);

        My.assertEquals(11, tree.size());
        My.assertEquals(4, tree.depth());

        {
            List<String> preorder = Arrays.asList(
                    "0015", "0008", "0005", "0012", "0009",
                    "0024", "0019", "0017", "0020", "0030", "0028");
            My.assertTrue(preorder.equals(tree.preorder()));

            List<String> inorder = Arrays.asList(
                    "0005", "0008", "0009", "0012", "0015",
                    "0017", "0019", "0020", "0024", "0028", "0030");
            My.assertTrue(inorder.equals(tree.inorder()));

            List<String> postorder = Arrays.asList(
                    "0005", "0009", "0012", "0008",
                    "0017", "0020", "0019", "0028", "0030", "0024", "0015");
            My.assertTrue(postorder.equals(tree.postorder()));
        }

        My.assertEquals("0015", tree.root.val);
        My.assertEquals("0008", tree.root.left.val);
        My.assertEquals("0005", tree.root.left.left.val);
        My.assertEquals("0012", tree.root.left.right.val);
        My.assertEquals("0009", tree.root.left.right.left.val);
        My.assertEquals("0024", tree.root.right.val);
        My.assertEquals("0019", tree.root.right.left.val);
        My.assertEquals("0030", tree.root.right.right.val);
        My.assertEquals("0028", tree.root.right.right.left.val);

        del(tree, 5);
        del(tree, 8);
        del(tree, 24);
        del(tree, 15);
        del(tree, 20);

        My.assertEquals(6, tree.size());
        My.assertEquals(4, tree.depth());

        {
            List<String> preorder = Arrays.asList(
                    "0012", "0009", "0019", "0017", "0030", "0028");
            My.assertTrue(preorder.equals(tree.preorder()));

            List<String> inorder = Arrays.asList(
                    "0009", "0012", "0017", "0019", "0028", "0030");
            My.assertTrue(inorder.equals(tree.inorder()));

            List<String> postorder = Arrays.asList(
                    "0009", "0017", "0028", "0030", "0019", "0012");
            My.assertTrue(postorder.equals(tree.postorder()));
        }

    }

    private static void put(BST tree, int k) {
        String str = String.format("%04d", k);
        tree.put(str, str);
    }

    private static void del(BST tree, int k) {
        String str = String.format("%04d", k);
        tree.remove(str);
    }

}