#include <iostream>
#include <list>
#include <string>
#include <vector>


template <typename TreeKind>
struct TreeTraits {
  // By ensuring that this is nonsense for TreeKind, we know that this
  // version of the template can never apply, and a specialization
  // must be used.
  using Unresolved = typename TreeKind::UnspecializedTraitError;
  // must publish
  //   types
  //     node type
  //     value_type
  //   behaviors
  //     get_root
  //     get_children
  //     get_value
};


template<typename TreeKind, typename Traits = TreeTraits<TreeKind>>
bool
printGraphviz(const TreeKind& tree) {
  using node_type = typename Traits::node_type;

  auto traverse = [&tree] (node_type& node, auto& traverse) -> void {
    auto children = Traits::get_children(tree, node);
    auto value = Traits::get_value(node);
    for (node_type child : children) {
      auto child_value = Traits::get_value(child);
      std::cout << " " << value << " -> " << child_value << ";\n";
      traverse(child, traverse);
    }
  };
  
  std::cout << "digraph {\n";
  auto root = Traits::get_root(tree);
  traverse(root, traverse);
  std::cout << "}\n";
}


template <typename T>
struct TreeTraits<std::list<T>> {
  using tree = std::list<T>;
  using node_type = typename tree::const_iterator;
  using value_type = T;

  static node_type
  get_root(const tree& t) noexcept {
    return t.cbegin();
  }

  static std::vector<node_type>
  get_children(const tree& t, const node_type& node) noexcept {
    auto next = node;
    ++next;
    if (next == t.end()) {
      return {};
    } else {
      return std::vector<node_type>{ next };
    }
  }

  static value_type
  get_value(const node_type& node) noexcept {
    return *node;
  }
};


template<class Element>
struct Node {
  Element e;
  Node* left = nullptr;
  Node* right = nullptr;
};


template <typename T>
struct TreeTraits<Node<T>> {
  using tree = Node<T>;
  using node_type = const Node<T>*;
  using value_type = T;

  static node_type
  get_root(const tree& t) noexcept {
    return &t;
  }

  static std::vector<node_type>
  get_children(const tree& t, const node_type node) noexcept {
    std::vector<node_type> children;
    children.reserve(2);
    if (node->left) {
      children.push_back(node->left);
    }
    if (node->right) {
      children.push_back(node->right);
    }
    return children;
  }

  static value_type
  get_value(const node_type node) noexcept {
    return node->e;
  }
};


int
main(int argc, const char** argv) {
  std::list<int> numbers = { 1, 2, 3, 5, 8, 13 };
  std::list<std::string> strings = { "one", "two", "three", "five", "eight", "thirteen" };

  printGraphviz(numbers);
  printGraphviz(strings);

  // This works not only for other element types, 
  // but for other *tree* kinds as well!!
  Node<int> a{1};
  Node<int> b{2};
  Node<int> c{3};
  Node<int> d{4};
  Node<int> e{5};
  a.left = &b;
  a.right = &c;
  c.left = &d;
  c.right = &e;
  printGraphviz(a);
 
  return 0;
}