/* btree.cpp
 * Date: 2021-11-22
 * Author: Aryadev Chavali
 */

#include <iostream>

enum Order
{
  LT,
  GT,
  EQ
};

template <typename T>
struct BinaryTree
{
  T value;
  BinaryTree<T> *left, *right;
  enum Order (*compare)(T, T);
  BinaryTree(T val, BinaryTree<T> *l, BinaryTree<T> *r, enum Order (*cmp)(T, T))
  {
    value   = val;
    left    = l;
    right   = r;
    compare = cmp;
  }

  ~BinaryTree()
  {
    delete left;
    delete right;
  }
};

template <typename T>
BinaryTree<T> *insert(BinaryTree<T> *tree, T value)
{
  BinaryTree<T> **node = &tree;
  switch (tree->compare(value, tree->value))
  {
  case LT:
    node = &tree->left;
    break;
  case EQ:
  case GT:
    node = &tree->right;
    break;
  }
  *node = *node ? insert(*node, value)
                : new BinaryTree<T>(value, nullptr, nullptr, tree->compare);
  return tree;
}

template <typename T>
void rightRotate(BinaryTree<T> **tree)
{
  auto left   = *tree->left;
  *tree->left = left->right;
  left->right = *tree;
  *tree       = left;
}

template <typename T>
void leftRotate(BinaryTree<T> **tree)
{
  auto right     = (*tree)->right;
  (*tree)->right = right->left;
  right->left    = *tree;
  *tree          = right;
}

template <typename T>
std::ostream &operator<<(std::ostream &ostream, const BinaryTree<T> *btree)
{
  if (!btree)
    return ostream;
  ostream << btree->value << "(";
  if (btree->left)
    ostream << btree->left;
  if (btree->left && btree->right)
    ostream << ", ";
  if (btree->right)
    ostream << btree->right;
  ostream << ")";
  return ostream;
}

int main(void)
{
  auto cmp = [](int x, int y)
  {
    if (x < y)
      return LT;
    else if (x > y)
      return GT;
    else
      return EQ;
  };
  auto tree = new BinaryTree<int>(5, NULL, NULL, cmp);
  for (int i = 0; i <= 5; ++i)
    tree = insert(tree, i * 2);

  leftRotate(&tree);
  std::cout << tree << std::endl;

  delete tree;
  return 0;
}