A dummy trie

#ifndef TREE_HH
#define TREE_HH

#include <utility>

#include <boost/serialization/export.hpp>
#include <boost/serialization/tracking.hpp>
#include <boost/serialization/split_member.hpp>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/preprocessor/tuple/enum.hpp>

#include <unordered_map>
#include <iostream>

using namespace std;

#define FOO_CLASS_TRACKING(E, PARAMETER_TUPLE, ...)             \
  namespace boost {                                             \
  namespace serialization {                                     \
  template<BOOST_PP_TUPLE_ENUM(PARAMETER_TUPLE)>                \
  struct tracking_level< __VA_ARGS__ >                          \
  {                                                             \
    typedef mpl::integral_c_tag tag;                            \
    typedef mpl::int_< E> type;                                 \
    BOOST_STATIC_CONSTANT(                                      \
                          int,                                  \
                          value = tracking_level::type::value   \
                                             );                 \
    /* tracking for a class  */                                 \
    BOOST_STATIC_ASSERT((                                       \
                         mpl::greater<                          \
                         /* that is a prmitive */               \
                         implementation_level< __VA_ARGS__ >,   \
                         mpl::int_<primitive_type>              \
                         >::value                               \
                                             ));                \
  };                                                            \
  }}

namespace Tree
{

class NodeInterface
{
public:
  NodeInterface()
  {}

  virtual NodeInterface *get_child(const uint8_t i) const = 0;

  virtual NodeInterface *set_child(const uint8_t i) = 0;
  virtual void set_child(const uint8_t i, NodeInterface *child) = 0;
  virtual NodeInterface *upgrade() = 0;

  virtual void print(int indention = 0) const = 0;

  template <typename Archive>
  void save(Archive &ar, const unsigned int version) const
  {
  }

  template <typename Archive>
  void load(Archive &ar, const unsigned int version)
  {
  }

  BOOST_SERIALIZATION_SPLIT_MEMBER()

  friend class boost::serialization::access;

  virtual ~NodeInterface()
  {}
};

template <uint8_t num_elem = 1>
class Node;

template<uint8_t num_elem>
NodeInterface *upgrade_node(const Node<num_elem> &node)
{
  return new Node<num_elem + 1>;
}

template<>
NodeInterface *upgrade_node(const Node<10> &node)
{
  return nullptr;
}

template<uint8_t num_elem>
class Node : public NodeInterface
{
public:
  Node():
    NodeInterface()
  {
    for (int i = 0; i < num_elem; ++i)
      children[i] = make_pair(0, nullptr);
  }

  pair<uint8_t, NodeInterface*> children[num_elem];

  NodeInterface *get_child(const uint8_t in) const override
  {
    assert(in < 10);
    for (int i = 0; i < num_elem; ++i)
    {
      if (children[i].second && children[i].first == in)
      {
        return children[i].second;
      }
    }

    return nullptr;
  }

  NodeInterface *set_child(const uint8_t in) override
  {
    assert(in < 10);

    for (int i = 0; i < num_elem; ++i)
    {
      if (children[i].second == nullptr)
      {
        auto new_node = new Node;
        children[i] = make_pair(in, new_node);

        return new_node;
      }
    }

    return nullptr;
  }

  void set_child(const uint8_t in, NodeInterface *child) override
  {
    assert(in < 10);
    for (int i = 0; i < num_elem; ++i)
    {
      if (children[i].first == in)
      {
        delete children[i].second;
        children[i].second = child;
        return;
      }
      else if (children[i].second == nullptr)
      {
        children[i] = make_pair(in, child);
        return;
      }
    }
  }

  void print(int indention = 0) const override
  {
    string indent_str(indention, ' ');

    for (auto & child : children)
    {
      if (child.second)
      {
        cout << indent_str << ": " << to_string(child.first) << endl;
        child.second->print(indention + 2);
      }
    }
  }

  NodeInterface *upgrade() override
  {
    auto new_node = upgrade_node(*this);
    if (new_node)
    {
      for (int i = 0; i < num_elem; ++i)
      {
        new_node->set_child(children[i].first, children[i].second);
        children[i].second = nullptr;
      }
    }

    return new_node;
  }

  template <typename Archive>
  void save(Archive &ar, const unsigned int version) const
  {
    ar & boost::serialization::base_object<NodeInterface>(*this);

    ar & children;
  }

  template <typename Archive>
  void load(Archive &ar, const unsigned int version)
  {
    ar & boost::serialization::base_object<NodeInterface>(*this);
    ar & children;
  }

  BOOST_SERIALIZATION_SPLIT_MEMBER()

  friend class boost::serialization::access;

  ~Node()
  {
    for (int i = 0; i < num_elem; ++i)
    {
      if (children[i].second)
        delete children[i].second;
    }
  }
};

class Tree
{
public:
  NodeInterface *root;

  Tree():
    root(new Node<>)
  {}

  void insert(size_t i)
  {
    auto last_s = root;
    auto s = root;

    uint32_t last_i = i;
    auto temp = root;

    while ((temp = s->get_child(i%10)))
    {
      last_s = s;
      last_i = i;
      s = temp;
      i /= 10;
    }

    while (i > 0)
    {
      auto temp = s->set_child(i % 10);

      if (temp == nullptr)
      {
        if (s == root)
        {
          s = s->upgrade();
          delete root;
          root = s;
          last_s = root;
        }
        else
        {
          s = s->upgrade();
          last_s->set_child(last_i % 10, s);
        }

        last_s = s;
        s = s->set_child(i % 10);
      }
      else
      {
        last_s = s;
        s = temp;
      }

      last_i = i;
      i /= 10;
    }
  }

  void print() const
  {
    root->print();
  }

  template <typename Archive>
  void save(Archive &ar, const unsigned int version) const
  {
    ar & root;
  }

  template <typename Archive>
  void load(Archive &ar, const unsigned int version)
  {
    ar & root;
  }

  BOOST_SERIALIZATION_SPLIT_MEMBER()

  friend class boost::serialization::access;

  ~Tree()
  {
    delete root;
  }

};
} // Tree namepspace

BOOST_CLASS_EXPORT(Tree::Node<1>)
BOOST_CLASS_EXPORT(Tree::Node<2>)
BOOST_CLASS_EXPORT(Tree::Node<3>)
BOOST_CLASS_EXPORT(Tree::Node<4>)
BOOST_CLASS_EXPORT(Tree::Node<5>)
BOOST_CLASS_EXPORT(Tree::Node<6>)
BOOST_CLASS_EXPORT(Tree::Node<7>)
BOOST_CLASS_EXPORT(Tree::Node<8>)
BOOST_CLASS_EXPORT(Tree::Node<9>)
BOOST_CLASS_EXPORT(Tree::Node<10>)
BOOST_CLASS_TRACKING(Tree::NodeInterface, boost::serialization::track_never)
FOO_CLASS_TRACKING(boost::serialization::track_never, (uint8_t num_elem), Tree::Node<num_elem>)
FOO_CLASS_TRACKING(boost::serialization::track_never, (), pair<const uint8_t, Tree::NodeInterface*>)

#endif /* TREE_HH */

================= main.cc =======================

#include "tree.hh"

#include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>

#include <fstream>

#define MAX_NUM 10000000

int main(int argc, char *argv[])
{
  Tree::Tree tree;

  for (int i = 0; i < MAX_NUM; ++i)
    tree.insert(i);

  const char* text_file_name = "/tmp/tree.txt";
  {
    std::ofstream ofs(text_file_name, ios::binary | ios::out);
    std::filebuf *fb = ofs.rdbuf();

    boost::archive::binary_oarchive ar(*fb, boost::archive::no_tracking);
    cout << "Start serialization..." << endl;
    ar & tree;
    cout << "Serialization done." << endl;
  }

  // {
  //   std::ifstream ifs(text_file_name);

  //   boost::archive::binary_iarchive ar(ifs);

  //   Tree::Tree tree1;

  //   ar & tree1;

  //   tree1.print();
  // }

  return 0;
}