//--- BEGIN HEADER FILE ---//
#ifndef _TREE_H_
#define _TREE_H_

#include <iostream>
#include <exception>
#include <string>

using key_t = int;
using val_t = int;

class Tree
{
public:
  
  Tree();

  // the three important !
  ~Tree();
  Tree(Tree const&);
  Tree& operator=(Tree const&);

  // and two move versions for efficiency !
  Tree(Tree&&);
  Tree& operator=(Tree&&);

  // main features
  val_t find(key_t k) const;
  val_t recursive_find(key_t key) const;
  bool insert(key_t k, val_t v);
  bool remove(key_t k); // NOT IMPLEMENTED
  void print(std::ostream& os) const;
  Tree clone() const;

  // not a member of Tree class, but friend
  // (actually, we do not need to be friend either)
  friend std::ostream& operator<<(std::ostream& os, Tree const& t);
  
private:
  
  class Tree_Node
  {
  public:
    Tree_Node(int k, int v, Tree_Node* lt = nullptr, Tree_Node* gt = nullptr);
    ~Tree_Node();

    // we will never need to copy Tree_Node objects, tell compiler to forbid it
    Tree_Node(Tree_Node&) = delete;
    Tree_Node& operator=(Tree_Node&) = delete;
    val_t find(key_t k) const;

    // since Tree_Node is private in Tree we can leave this public for now
    Tree_Node* lesser;
    Tree_Node* larger;
    key_t key;
    val_t value;
  };

  // private help functions and constructors
  // we do not want to reveal any Tree_Node stuff to main program
  // but using it for parameter and return is helpful internally
  // so we create Tree_Node* versions private
  Tree(Tree_Node* r);

  void print(std::ostream& os, Tree_Node* n) const;
  Tree_Node* clone(Tree_Node* n) const;
  
  Tree_Node* root;
};

// used when something goes wrong in our Tree
class Tree_Error : public std::exception
{
public:
  Tree_Error(std::string const& msg) noexcept : message(msg) {}

  const char* what() const noexcept { return message.c_str(); }
  
private:
  std::string message;
};

#endif
//--- END HEADER FILE ---//


//--- BEGIN IMPLEMENTATION FILE ---//
#include <utility>

// scope resolution: "Tree::" specify constructor is located "inside" Tree
Tree::Tree() : root(nullptr) {}

Tree::Tree(Tree_Node* r) : root(r) {}

Tree::~Tree()
{
  // when deleting a Tree_Node we will trigger the destructor of that automatically
  // that destructor will delete it's lesser and larger node recursively
  // nullptr can always be deleted, nothing will happen
  delete root;
}

// copy constructor, just create a deep clone of the right hand side Tree
Tree::Tree(Tree const& rhs) : root(clone(rhs.root)) {}

Tree::Tree_Node::~Tree_Node()
{
  // warning !! delete trigger destructor on object pointed to !!
  delete lesser;
  delete larger;
}

// safe, generic, and elegant "copy-and-swap" assignment operator
Tree& Tree::operator=(Tree const& rhs)
{
  if (this != &rhs)
  {
    Tree copy(rhs); // utilize copy constructor
    std::swap(root, copy.root);
    // utilize destructor to get rid of preexisting Tree
  }
  return *this;
}

// this constructor allow us to create and initiate a new node in one statement
// specially useful in clone
Tree::Tree_Node::Tree_Node(key_t k, val_t v, Tree_Node* lt, Tree_Node* gt)
  : lesser(lt), larger(gt), key(k), value(v) {}

Tree::Tree(Tree&& t) : root(nullptr)
{
  // && means that t is about to be destroyed, it will not need it's Tree anymore
  // we steal it and put a nullptr instead, it's safe to delete a nullptr
  std::swap(root, t.root);
}

Tree& Tree::operator=(Tree&& rhs)
{
  // && means that t is about to be destroyed, it will not need it's Tree anymore
  // we swap it so ours is destroyed instead
  std::swap(root, rhs.root);
  return *this;
}

// iteratively find insertion point and insert our key and value
bool Tree::insert(key_t key, val_t value)
{
  Tree_Node* prev = nullptr;
  Tree_Node* curr = root;

  // find insertion point (in a simple binary tree always a leaf)
  while (curr != 0)
  {
    prev = curr;
    
    if (key > curr->key )
      curr = curr->larger;
    else if (key < curr->key )
      curr = curr->lesser;
    else
      return false; // duplicate key already inserted in this case
  }

  // constructor force us to specify parameters
  Tree_Node* node = new Tree_Node(key, value);
  
  // do insertion
  if (prev == 0) // zero iterations, tree was empty
    this->root = node;
  else if (key > prev->key )
    prev->larger = node;
  else if (key < prev->key )
    prev->lesser = node;
  else
    throw Tree_Error("Miniproblem: why should this never happen?");

  return true;
}

// iterative find function
val_t Tree::find(key_t key) const
{
  Tree_Node* current = root;
  
  while (current)
  {
    if (key > current->key)
      current = current->larger;
    else if (key < current->key)
      current = current->lesser;
    else // (key == current->key)
      return current->value;
  }
  throw Tree_Error("ERROR: Key not found.");
}

// recursive find function
val_t Tree::recursive_find(key_t key) const
{
  return root->find(key);
}

// recursive find function, recursive functions are sometimes "simpler"
val_t Tree::Tree_Node::find(key_t key) const
{
  // compare parameter key to this key
  if ( key == this->key )
    return value;

  else if ( key < value && lesser != nullptr )
    return lesser->find(key);

  else if ( larger != nullptr )
    return larger->find(key);
  
  throw Tree_Error("ERROR: Key not found.");
}

Tree::Tree_Node* Tree::clone(Tree_Node* node) const
{
  if (node == 0)
    return 0;

  // constructor and recursion makes the code "simpler"
  return new Tree_Node(node->key, node->value,
                       clone(node->larger),
                       clone(node->lesser));
}

Tree Tree::clone() const
{
  return Tree(clone(root)); // thanks to private constructor
}

void Tree::print(std::ostream& os, Tree::Tree_Node* current) const
{
  if (current == 0)
    return;
  
  // preorder printing
//  os << key << " : " << value << std::endl;
  
  print(os, current->lesser);
  
  // inorder printing
  os << current->key << " : " << current->value << std::endl;
  
  print(os, current->larger);
  
  // postorder printing
//  os << key << " : " << value << std::endl;
}

void Tree::print(std::ostream& os) const
{
  print(os, root);
}

// not a member of Tree class
std::ostream& operator<<(std::ostream& os, Tree const& t)
{
  t.print(os);
  return os;
}
//--- END IMPLEMENTATION FILE ---//


//--- BEGIN TEST FILE ---//
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int data;

  // !! INCOMPLETE !! More needed to test all features !
  try
  {
    Tree tomte;   // constructor called !! this = &tomte
    Tree nisse;
    
    while (cin >> data)
    {
      tomte.insert(data, -data); // this = &tomte;
      nisse.insert(-data, data); // this = &nisse;
    }
    
    Tree hohoho;
    hohoho.insert(7,5);
    
    cout << tomte << endl;
    cout << nisse << endl;
    cout << hohoho << endl;

    nisse = hohoho;
    
    cout << tomte << endl;
    cout << nisse << endl;
    cout << hohoho << endl;
    
    // automatic: destructor called on tomte, nisse and hohoho
  }
  catch (exception& e)
  {
    cerr << e.what() << endl;
  }
  return 0;
}