//----------------------------------------------------------------------------

#ifndef ALLOC_BINARY_TREE_HPP
#define ALLOC_BINARY_TREE_HPP

#include <memory>
#include <vector>
#include <queue>
#include <functional>

namespace alloc {

template<typename T>
class BinaryNode
{
public:

  BinaryNode(T value,
             std::unique_ptr<BinaryNode> left={},
             std::unique_ptr<BinaryNode> right={})
  : value_{std::move(value)}
  , left_{std::move(left)}
  , right_{std::move(right)}
  {
    // nothing more to be done
  }

  //-- provide copy --
  BinaryNode(const BinaryNode &rhs)
  : value_{rhs.value_} // copy
  , left_{}
  , right_{}
  {
    if(rhs.left_)
    {
      left_=std::make_unique<BinaryNode>(*rhs.left_); // copy
    }
    if(rhs.right_)
    {
      right_=std::make_unique<BinaryNode>(*rhs.right_); // copy
    }
  }

  BinaryNode&
  operator=(const BinaryNode &rhs)
  {
    value_=rhs.value_; // copy
    if(rhs.left_)
    {
      left_=std::make_unique<BinaryNode>(*rhs.left_); // copy
    }
    else
    {
      left_.reset();
    }
    if(rhs.right_)
    {
      right_=std::make_unique<BinaryNode>(*rhs.right_); // copy
    }
    else
    {
      right_.reset();
    }
    return *this;
  }

  //-- default move is suitable --
  BinaryNode(BinaryNode &&) =default;
  BinaryNode & operator=(BinaryNode &&) =default;

  //-- default destruction is suitable --
  ~BinaryNode() =default;

  const T &
  value() const
  {
    return value_;
  }

  const BinaryNode *
  left() const
  {
    return left_.get();
  }

  const BinaryNode *
  right() const
  {
    return right_.get();
  }

  template<typename Compare = std::less<T>>
  bool // inserted
  sorted_insert(T value,
                Compare compare={})
  {
    if(compare(value, value_)) // value is less than current
    {
      if(left_)
      {
        return left_->sorted_insert(std::move(value), compare);
      }
      else
      {
        left_=std::make_unique<BinaryNode>(std::move(value));
        return true;
      }
    }
    if(compare(value_, value)) // current is less than value
    {
      if(right_)
      {
        return right_->sorted_insert(std::move(value), compare);
      }
      else
      {
        right_=std::make_unique<BinaryNode>(std::move(value));
        return true;
      }
    }
    return false; // current is value
  }

private:
  T value_;
  std::unique_ptr<BinaryNode> left_;
  std::unique_ptr<BinaryNode> right_;
};

template<typename T,
         typename Fnct>
inline
bool // stop
pre_order(const BinaryNode<T> &node,
          Fnct fnct,
          int depth=0)
{
  return fnct(node, depth)
         ||(node.left()&&pre_order(*node.left(), fnct, depth+1))
         ||(node.right()&&pre_order(*node.right(), fnct, depth+1));
}

template<typename T,
         typename Fnct>
inline
bool // stop
in_order(const BinaryNode<T> &node,
         Fnct fnct,
         int depth=0)
{
  return (node.left()&&in_order(*node.left(), fnct, depth+1))
         ||fnct(node, depth)
         ||(node.right()&&in_order(*node.right(), fnct, depth+1));
}

template<typename T,
         typename Fnct>
inline
bool // stop
post_order(const BinaryNode<T> &node,
           Fnct fnct,
           int depth=0)
{
  return (node.left()&&post_order(*node.left(), fnct, depth+1))
         ||(node.right()&&post_order(*node.right(), fnct, depth+1))
         ||fnct(node, depth);
}

template<typename T,
         typename Fnct>
inline
bool // stop
breadth_first(const BinaryNode<T> &node,
              Fnct fnct)
{
  std::queue<const BinaryNode<T> *> pending;
  pending.emplace(&node);
  int depth=0;
  int next_depth=1;
  for(int done=0; !empty(pending); ++done)
  {
    if(done==next_depth)
    {
      ++depth;
      next_depth+=int(size(pending));
    }
    const auto &current=*pending.front();
    pending.pop();
    if(fnct(current, depth))
    {
      return true;
    }
    if(current.left())
    {
      pending.emplace(current.left());
    }
    if(current.right())
    {
      pending.emplace(current.right());
    }
  }
  return false;
}

template<typename T,
         typename Predicate>
inline
std::vector<const BinaryNode<T> *>
find_if(const BinaryNode<T> &node,
        Predicate predicate)
{
  std::vector<const BinaryNode<T> *> result;
  const bool found=pre_order(node,
    [&](const auto &elem, const auto &depth)
    {
      if(depth<int(size(result)))
      {
        result.resize(depth);
      }
      result.emplace_back(&elem);
      return predicate(elem);
    });
  if(!found)
  {
    result.clear();
  }
  return result;
}

template<typename T>
inline
std::vector<const BinaryNode<T> *>
find(const BinaryNode<T> &node,
     const T &value)
{
  return find_if(node,
    [&](const auto &elem)
    {
      return elem.value()==value;
    });
}

template<typename T,
         typename Compare = std::less<T>>
inline
std::vector<const BinaryNode<T> *>
sorted_find(const BinaryNode<T> &node,
            const T &value,
            Compare compare={})
{
  std::vector<const BinaryNode<T> *> result;
  result.emplace_back(&node);
  while(!empty(result))
  {
    const auto current=result.back();
    if(compare(value, current->value())) // value is less than current
    {
      const auto next=current->left();
      if(next)
      {
        result.emplace_back(next);
      }
      else
      {
        result.clear(); // not found
      }
    }
    else if(compare(current->value(), value)) // current is less than value
    {
      const auto next=current->right();
      if(next)
      {
        result.emplace_back(next);
      }
      else
      {
        result.clear(); // not found
      }
    }
    else // current is value
    {
      break;
    }
  }
  return result;
}

} // namespace alloc

#endif // ALLOC_BINARY_TREE_HPP

//----------------------------------------------------------------------------

//----------------------------------------------------------------------------

#include "binary_tree.hpp"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include <random>

const auto display=
  [](const auto &node,
     const auto &depth)
  {
    for(int i=0; i<depth; ++i)
    {
      std::cout << "| ";
    }
    std::cout << node.value() << '\n';
    return false;
  };

void
test_clades()
{
  std::cout << "\n~~~~ " << __func__ << "() ~~~~\n";
  using Clade = alloc::BinaryNode<std::string>;
  Clade primates{"Primates",
    std::make_unique<Clade>("Strepsirrhini",
      std::make_unique<Clade>("Lemuriformes",
        std::make_unique<Clade>("Lorisoidea"),
        std::make_unique<Clade>("Lemuroidea"))),
    std::make_unique<Clade>("Haplorhini",
      std::make_unique<Clade>("Tarsiiformes",
        std::make_unique<Clade>("Tarsioidea")),
      std::make_unique<Clade>("Simiiformes",
        std::make_unique<Clade>("Parvorder Platyrrhini"),
        std::make_unique<Clade>("Catarrhini",
          std::make_unique<Clade>("Cercopithecidae"),
          std::make_unique<Clade>("Homonoidea",
            std::make_unique<Clade>("Hylobatidae"),
            std::make_unique<Clade>("Hominidae",
              std::make_unique<Clade>("Ponginae"),
              std::make_unique<Clade>("Homininae",
                std::make_unique<Clade>("Gorillini",
                  std::make_unique<Clade>("Gorilla")),
                std::make_unique<Clade>("Hominini",
                  std::make_unique<Clade>("Pan"),
                  std::make_unique<Clade>("Homo"))))))))};
  Clade mammalia{"Mammalia",
    std::make_unique<Clade>("Monotremata"),
    std::make_unique<Clade>("Theria",
      std::make_unique<Clade>("Marsupiala"),
      std::make_unique<Clade>("Placentalia",
        std::make_unique<Clade>("Atlantogeneta",
          std::make_unique<Clade>("Afrotheria"),
          std::make_unique<Clade>("Xenarthra")),
        std::make_unique<Clade>("Boreoeutheria",
          std::make_unique<Clade>("Euarchontoglires",
            std::make_unique<Clade>("Euarchonta",
              std::make_unique<Clade>("Scandentia"),
              std::make_unique<Clade>("Primatomorpha",
                std::make_unique<Clade>("Dermoptera"),
#if 0
                std::make_unique<Clade>(std::move(primates)))),
#else
                std::make_unique<Clade>(primates))),
#endif
            std::make_unique<Clade>("Glires")),
          std::make_unique<Clade>("Laurasiatheria",
            std::make_unique<Clade>("Eulipotyphla"),
            std::make_unique<Clade>("Scrotifera",
              std::make_unique<Clade>("Chiroptera"),
              std::make_unique<Clade>("Fereuungulata",
                std::make_unique<Clade>("Euungulata",
                  std::make_unique<Clade>("Cetartiodactyla"),
                  std::make_unique<Clade>("Perissodactyla")),
                std::make_unique<Clade>("Ferae",
                  std::make_unique<Clade>("Pholidota"),
                  std::make_unique<Clade>("Carnivora"))))))))};
  std::cout << "~~ in_order ~~~~~~~~~~~~~~~~~~~~\n";
  in_order(mammalia, display);
  std::cout << "~~ pre_order ~~~~~~~~~~~~~~~~~~~\n";
  pre_order(mammalia, display);
  std::cout << "~~ post_order ~~~~~~~~~~~~~~~~~~\n";
  post_order(mammalia, display);
  std::cout << "~~ breadth_first ~~~~~~~~~~~~~~~\n";
  breadth_first(mammalia, display);
  std::cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";
  const auto show_ancestors=
    [&](const auto &ancestors_begin, const auto &ancestors_end)
    {
      std::string result;
      std::for_each(ancestors_begin, ancestors_end,
        [&](const auto &elem)
        {
          if(!empty(result))
          {
            result+=", ";
          }
          result+=elem->value();
        });
      return result;
    };
  const std::string a="Homo";
  const std::string b="Chiroptera";
  const auto a_ancestors=find(mammalia, a);
  const auto b_ancestors=find(mammalia, b);
  std::cout << a << " --> "
            << show_ancestors(cbegin(a_ancestors), cend(a_ancestors)) << '\n';
  std::cout << b << " --> "
            << show_ancestors(cbegin(b_ancestors), cend(b_ancestors)) << '\n';
  const auto m=std::mismatch(cbegin(a_ancestors), cend(a_ancestors),
                             cbegin(b_ancestors));
  std::cout << a << " & " << b << " --> "
            << show_ancestors(cbegin(a_ancestors), m.first) << '\n';
}

void
test_sorted()
{
  std::cout << "\n~~~~ " << __func__ << "() ~~~~\n";
  std::default_random_engine rnd_gen{std::random_device{}()};
  const int max_value=50;
  std::uniform_int_distribution<int> uni_dist{0, max_value};
  alloc::BinaryNode<int> numbers{uni_dist(rnd_gen)};
  for(int i=0; i<max_value; ++i)
  {
    const int value=uni_dist(rnd_gen);
    if(!numbers.sorted_insert(value))
    {
      std::cout << value << " already present\n";
    }
  }
  in_order(numbers, display);
  for(int i=0; i<=max_value; ++i)
  {
    const auto path=sorted_find(numbers, i);
    if(!empty(path))
    {
      std::cout << i << " -->";
      for(const auto &elem: path)
      {
        std::cout << ' ' << elem->value();
      }
      std::cout << '\n';
    }
  }
}

int
main()
{
  test_clades();
  test_sorted();
  return 0;
}

//----------------------------------------------------------------------------