#include<iostream>
#include<memory>
#include<functional>
using namespace std;

// Binary search trees in modern C++  (compile with g++ -std=c++17)

template<typename T, typename Cmp=std::less<T>>
struct BST {
  T val; // value at node
  unique_ptr<BST<T,Cmp>> left; 
  unique_ptr<BST<T,Cmp>> right;
  static constexpr Cmp cmp = Cmp{};  // cmp(x,y) if x<y
  
  // leave constructor
  BST(T v)
  {
    val = v;
    //left = unique_ptr<BST<T,Cmp>>(nullptr); // this is redundant
    // supposedly no extra memory overhead with unique_ptr;
  }

  // aggregate constructor with r-value refs
  BST(T v, unique_ptr<BST<T,Cmp>>&& l, unique_ptr<BST<T,Cmp>>&& r) noexcept
  {
    val = v;
    if (l) left = move(l);  //why is move still needed?
    if (r) right = move(r);
  }

  /// insert into tree (as set) returns true if inserted
  bool insert(T x)
  {
    if (cmp(x,val)) // go left
      {
        if (left) return left->insert(x);
	else left = make_unique<BST<T,Cmp>>(x);
      }
    else if (cmp(val,x)) // go right
      {
	if (right) return right->insert(x);
	else right = make_unique<BST<T,Cmp>>(x);
      }
    else return false;   // don't insert duplicates
    return true;
  }//insert
  
  bool search(T x) // search for x in tree
  {
    bool less = cmp(x,val);
    bool greater = cmp(val,x);
    if (!less && !greater) return true; //assume total ordering
    else if (less && left) return left->search(x);
    else if (greater && right) return right->search(x);
    else return false;
  }
  // note that both insert and search are tail-recursive but
  // g++ is not eliminating the recursive calls.  It's not eliminating
  // tail recursion even though the function is NOT marked 'virtual'.

  void map_inorder(function<void(T)> f) // in-order traversal with operation f
  {
    if (left) left->map_inorder(f);
    f(val);
    if (right) right->map_inorder(f);
  }

  // attempt to create a bad tree:
  void nasty() //not compiled until called because of template
  {
    //left = right;   //won't compile when template instantiated
    left = move(right);  // compiles but destroys right half of tree
  } 
  
};//BST

void leakproof(); // defined below main

int main()
{
  auto tree = BST<int,std::greater<int>>(5); // bst w/inverted ordering
  for (int x:{7,2,9,1,6,4,3}) tree.insert(x);
  // print tree using map_inorder:
  tree.map_inorder([](auto x){cout << x << " ";});  cout << endl; 
  // calculate size, sum of tree using map_inorder:
  int size = 0, sum = 0;
  tree.map_inorder([&](auto x) mutable {size++; sum+=x;});
  cout << "size: " << size << endl;
  cout << "sum: " << sum << endl;
  cout << "search 1: " << tree.search(1) << endl;
  cout << "search 12: " << tree.search(12) << endl;

  tree.nasty(); // what will this do to tree?
  tree.map_inorder([](auto x){cout << x << " ";});  cout << endl;   

  // testing the aggregate constructor:
  auto left = make_unique<BST<int>>(10);
  auto right = make_unique<BST<int>>(30);
  auto root1 = BST<int>(20, move(left), move(right));

  auto root = make_unique<BST<int>>(5, make_unique<BST<int>>(2), make_unique<BST<int>>(8));
  root1.map_inorder([](auto x){cout << x << " ";});  cout << endl;  
  root->map_inorder([](auto x){cout << x << " ";});  cout << endl;

  // try to create loop in tree:
  //root->left = root; // won't compile.  PRAISE THE LORD!
  root->left = move(root); // compiles but destroys entire tree
  // hoping this is not a mem leak ...
  if (root) root->map_inorder([](auto x){cout << x << " ";});
  else cout << "root is now nullptr!\n";

  while (1) leakproof(); //observe mem usage with system monitor *********
  
  return 0;
}//main


void leakproof()  // tests if this program produces a memory leak...
{
  unique_ptr<BST<int>> root = make_unique<BST<int>>(5, make_unique<BST<int>>(2), make_unique<BST<int>>(8));
  //auto root = make_unique<BST<int>>(5);  // also causes leak
  root->insert(4); root->insert(3); root->insert(9);
  // try to create loop in tree:
  root->left = move(root); // compiles but destroys entire tree...
  //does this create a mem leak?  MEM LEAK OBSERVED!
}

// OOPS. Memory leak observed even though there's no use of raw pointers
// anywhere in this program.