巷で流行りの活動日記

木構造系のデータ構造の実装のベストプラクティスが知りたいと思いつつ，適当に非常に簡単なものを試作するなど．
競プロ用途などで，自分用に簡単なprint機能などを備えた木構造のライブラリなどを作っておきたいという気持ちはある．
TSから標準に入るoptionalを使えば不正値を表現出来るので親が居ないだとか，子が居ないという状態を持つのは楽になる筈．

とりあえず二分木にしたけれど，葉の数nを渡せるような形にしてi番目の子にインデックスアクセス出来る方が良いのかも．

http://melpon.org/wandbox/permlink/FDIoIYYovywpE6ym

#include <functional>
#include <iostream>
#include <memory>
#include <queue>

namespace tree {

struct pre_order_tag {};
static constexpr pre_order_tag pre_order{};

struct in_order_tag {};
static constexpr in_order_tag in_order{};

struct post_order_tag {};
static constexpr post_order_tag post_order{};

struct dfs_order_tag {};
static constexpr dfs_order_tag dfs_order{};

template <typename T>
struct binary_tree : std::enable_shared_from_this<binary_tree<T>> {
  binary_tree(T v,
              std::weak_ptr<binary_tree> p = {},
              std::shared_ptr<binary_tree> l = nullptr,
              std::shared_ptr<binary_tree> r = nullptr)
    : value(v), parent(p), left(l), right(r) {}
  binary_tree(const binary_tree&) = default;
  binary_tree(binary_tree&&) = default;

  std::shared_ptr<binary_tree> append_left(std::shared_ptr<binary_tree> c) {
    left = c;
    c->parent = this->shared_from_this();
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> append_right(std::shared_ptr<binary_tree> c) {
    right = c;
    c->parent = this->shared_from_this();
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> remove_left() {
    left = nullptr;
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> remove_right() {
    right = nullptr;
    return this->shared_from_this();
  }

  T value;
  std::weak_ptr<binary_tree> parent;
  std::shared_ptr<binary_tree> left;
  std::shared_ptr<binary_tree> right;
};

namespace detail {

  template <typename Tag>
  struct print;

  template <>
  struct print<pre_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       printer(t);
       eval(t->left, printer);
       eval(t->right, printer);
    }
  };

  template <>
  struct print<in_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       eval(t->left, printer);
       printer(t);
       eval(t->right, printer);
    }
  };

  template <>
  struct print<post_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       eval(t->left, printer);
       eval(t->right, printer);
       printer(t);
    }
  };

  template <>
  struct print<dfs_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
      if (t == nullptr) return;
      std::queue<T> q;
      q.push(t);
      while (!q.empty()) {
        const auto& tmp = q.front();
        q.pop();
        printer(tmp);
        if (tmp->left != nullptr) q.push(tmp->left);
        if (tmp->right != nullptr) q.push(tmp->right);
      }
    }
  };

}  // namespace detail

struct default_printer_t {
  template <typename T>
  void operator()(const T& t) const { std::cout << t->value << std::endl; }
};

static constexpr default_printer_t default_printer{};

template <typename T, typename Tag = pre_order_tag>
inline void print(const T& t,
           Tag = {}, const std::function<void(const T&)>& printer = default_printer) {
  if (t != nullptr) detail::print<Tag>::eval(t, printer);
}

}  // namespace tree

int main() {
  using tree_type = tree::binary_tree<int>;

  auto t = std::make_shared<tree_type>(0);
  t->append_left(std::make_shared<tree_type>(1));
  t->append_right(std::make_shared<tree_type>(2));
  t->left->append_left(std::make_shared<tree_type>(3));
  t->left->append_right(std::make_shared<tree_type>(4));
  t->right->append_left(std::make_shared<tree_type>(5));
  t->right->append_right(std::make_shared<tree_type>(6));

  std::cout << "pre_order:" << std::endl;
  tree::print(t);
 
  std::cout << "in_order:" << std::endl;
  tree::print(t, tree::in_order);
  
  std::cout << "post_order:" << std::endl;
  tree::print(t, tree::post_order);

  std::cout << "dfs_order:" << std::endl;
  tree::print(t, tree::dfs_order);
}