#include<iostream>
#include<memory>
#include<functional>
#include<experimental/optional>
using namespace std;
using experimental::optional; // supposed to be standard in C++ 2017
using experimental::nullopt;

// Binary search trees in C++

template<typename T>
struct BST {
  T val; // value at node
  optional<unique_ptr<BST<T>>> left;
  optional<unique_ptr<BST<T>>> right;
  static function<int(T,T)> comparator; //defined externally, follows
  // protocal: 0 or ==, - for <, + for >
  
  // leave constructor
  BST(T v)
  {
    val = v;
    left = nullopt; //better than unique_ptr<BST<T>>(nullptr);
    right = nullopt; 
  }

  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) (*left)->insert(x);
	else left = make_unique<BST<T>>(x);
      }
    else if (c>0) // go right
      {
	if (right) (*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) return (*left)->search(x);
    else return (*right)->search(x);
  }
  // note that both insert and search are tail-recursive

  bool madsearch(T x) // no recursion for me!
  {
    BST<T>* current = this;
    while (current!=nullptr)
      {
	int c = comparator(x,current->val);
	if (c==0) return true;
	else if (c<0) current = current->left.get();
	else current = current->right.get();
      }
    return false;
  }
  bool searchndestroy(T x)
  {
    cout << "HERE1\n";
    unique_ptr<BST<T>> current(this);
    while (current) {
    cout << "HERE2\n";      
      int c = comparator(x,current->val);
      if (c==0) return true;
      else if (c<0) current = move(current->left);
      else current = move(current->right);
    }//while
    return false;
  }

  
  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);
  }

  bool search_for(function<bool(T)> p) { // pre-order search for p(x)=true
    return
      p(val) ||
      (left && (*left)->map_search(p)) ||
      (right && (*right)->map_search(p));
  }

  // compute depth of tree
  int depth()
  {
    int dleft = 0, dright = 0;
    if (left) dleft = (*left)->depth();
    if (right) dright = (*right)->depth();
    if (dleft>dright) return dleft+1; else return dright+1;
  }
};//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;
  int sum = 0;
  tree.map_inorder([&](auto x) mutable {size++; sum+=x;});
  cout << "size: " << size << endl;
  cout << "sum: " << sum << endl;
  cout << "depth: " << tree.depth() << endl;
  cout << tree.search(1) << endl;
  //tree.map_inorder([](auto x){cout << x << " ";}); cout << endl; 
  return 0;
}//main