/* Binary Search Tree*/
/* Rules:
                1. Values from the left node are smaller than the node's own value
                2. Values from the right node are larger than the node's own value
                // Example
                // [] Node
                // () leaf
                        [7]
                     /      \
                  [4]        [9]
                /    \     /    \
              [3]    [5]  ()   [10]
             /  \   /  \       /  \
            ()  () ()  ()     ()  ()
   */
module type Ord = {
  type t;
  let eq: (t, t) => bool;
  let lt: (t, t) => bool;
  let leq: (t, t) => bool;
};

module Integer: Ord with type t = int = {
  type t = int;
  let eq = (===);
  let lt = (<);
  let leq = (<=);
};

module type Print = {type t; let toString: t => string;};

module PrintInteger: Print with type t = Integer.t = {
  type t = int;
  let toString = a => string_of_int(a);
};

module type BinarySearchTree = {
  type t;
  type tree('t) =
    | Empty
    | Node(tree(t), t, tree(t)); /* Node(left Node, value, right Node)*/
  let contains: (tree(t), t) => bool;
  let insert: (tree(t), t) => tree(t);
  let remove: (tree(t), t) => tree(t);
  let minNode: tree(t) => tree(t);
  let print: tree(t) => string;
};

type create = string => string;

module MakeBinarySearchTree =
       (Elem: Ord, Print: Print with type t = Elem.t)
       : (BinarySearchTree with type t := Elem.t) => {
  type t = Elem.t;
  type tree('t) =
    | Empty
    | Node(tree(t), t, tree(t));
  let rec insert = (node, value) =>
    switch (node) {
    | Empty => Node(Empty, value, Empty)
    | Node(leftNode, currentValue, rightNode) =>
      if (Elem.lt(currentValue, value)) {
        /*Right side*/
        Node(leftNode, currentValue, insert(rightNode, value));
      } else {
        /*Left side*/
        Node(insert(leftNode, value), currentValue, rightNode);
      }
    };
  let rec contains = (node, value) =>
    switch (node) {
    | Empty => false
    | Node(leftNode, currentValue, rightNode) =>
      if (Elem.lt(value, currentValue)) {
        /* Check left side*/
        contains(leftNode, value);
      } else if (Elem.lt(currentValue, value)) {
        /* Check right side*/
        contains(rightNode, value);
      } else {
        /* value is found */
        Elem.eq(value, currentValue);
      }
    };
  let rec minNode = node =>
    switch (node) {
    | Empty => Empty
    | Node(leftNode, _, _) =>
      /* keep searching of a left node*/
      if (leftNode == Empty) {
        node;
      } else {
        minNode(leftNode);
      }
    };
  let rec remove = (node, value) =>
    switch (node) {
    /* Do nothing */
    | Empty => Empty
    /* Only a value no children nodes */
    | Node(Empty, currentValue, Empty) =>
      if (Elem.eq(value, currentValue)) {
        Empty;
      } else {
        node;
      }
    /* Only left node */
    | Node(leftNode, currentValue, Empty) =>
      if (Elem.eq(value, currentValue)) {
        leftNode;
      } else {
        Node(remove(leftNode, value), currentValue, Empty);
      }
    /* Only right node */
    | Node(Empty, currentValue, rightNode) =>
      if (Elem.eq(value, currentValue)) {
        rightNode;
      } else {
        Node(Empty, currentValue, remove(rightNode, value));
      }
    /* Left and right node exist */
    | Node(leftNode, currentValue, rightNode) =>
      if (Elem.lt(value, currentValue)) {
        Node(remove(leftNode, value), currentValue, rightNode);
      } else if (Elem.lt(currentValue, value)) {
        Node(leftNode, currentValue, remove(rightNode, value));
      } else {
        switch (minNode(rightNode)) {
        | Empty => node
        | Node(_, minNodValue, _) =>
          Node(leftNode, minNodValue, remove(rightNode, minNodValue))
        };
      }
    };
  let rec printer = (node, level) =>
    switch (node) {
    | Empty => "empty"
    | Node(leftNode, currentValue, rightNode) =>
      " [ "
      ++ Print.toString(currentValue)
      ++ ", "
      ++ printer(leftNode, level + 1)
      ++ ", "
      ++ printer(rightNode, level + 1)
      ++ " ]"
    };
  let print = node => printer(node, 1);
};

let run = () => {
  module Bst = MakeBinarySearchTree(Integer, PrintInteger);
  let t = Bst.insert(Empty, 6);
  let t = Bst.insert(t, 4);
  let t = Bst.insert(t, 10);
  let t = Bst.insert(t, 5);
  let t = Bst.insert(t, 7);
  Js.log(Bst.print(t));
  Js.log("contains 7?");
  Js.log(Bst.contains(t, 7));
  Js.log("contains 17?");
  Js.log(Bst.contains(t, 17));
  Js.log("contains 6?");
  Js.log(Bst.contains(t, 6));
  Js.log("contains 12?");
  Js.log(Bst.contains(t, 12));
  Js.log("contains 10?");
  Js.log(Bst.contains(t, 10));
  Js.log("remove 7");
  let t = Bst.remove(t, 7);
  Js.log("contains 7?");
  Js.log(Bst.contains(t, 7));
  Js.log(Bst.print(t));
};
run();