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

// Binary search trees in modern C++

template<typename T>
struct BST {
  T val; // value at node
  unique_ptr<BST<T>> left;  // maybe by default set to nullptr
  unique_ptr<BST<T>> right;
  static function<int(T,T)> comparator; //defined externally, follows
  // protocal: 0 for ==, - for <, + for >
  
  // leave constructor
  BST(T v)
  {
    val = v;
    left = unique_ptr<BST<T>>(nullptr); // supposedly no extra memory overhead
    right = unique_ptr<BST<T>>(nullptr);  // this might be redundant
  }

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

  /// insert into tree (as set) returns true if inserted
  bool insert(T x)
  {
    int c = comparator(x,val);
    if (c<0) // go left
      {
        if (left) return left->insert(x);
	else left = make_unique<BST<T>>(x);
      }
    else if (c>0) // go right
      {
	if (right) return right->insert(x);
	else right = make_unique<BST<T>>(x);
      }
    else return false;   // don't insert duplicates
    return true;
  }//insert
  
  bool search(T x) // search for x in tree
  {
    int c = comparator(x,val);
    if (c==0) return true;
    else if (c<0 && left) return left->search(x);
    else if (c>0 && 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.

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

template<> //don't know why this is needed
function<int(int,int)> BST<int>::comparator{[](int x,int y){return x-y;}};

int main()
{
  function<int(int,int)> rcmp = [](int x,int y){return y-x;};
  auto tree = BST<int>(5);
  BST<int>::set_comparator(rcmp); // reverse left/right
  for (auto 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;

  // 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 = 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;
  return 0;
}//main