tpl_tree_node.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef TPL_TREE_H
#define TPL_TREE_H
 
#include <cassert>
#include <stdexcept>
#include <utility>
#include <dlink.H>
#include <ahDry.H>
#include <ah-dry-mixin.H>
#include <ahIterator.H>
#include <ahFunction.H>
#include <ahFunctional.H>
#include <htlist.H>
#include <tpl_dynListStack.H>
#include <tpl_dynListQueue.H>
#include <tpl_binNode.H>
#include <ah-errors.H>
 
#define ISROOT(p) ((p)->is_root())
#define ISLEAF(p) ((p)->is_leaf())
#define ISLEFTMOST(p) ((p)->is_leftmost())
#define ISRIGHTMOST(p) ((p)->is_rightmost())
 
#define SIBLING_LIST(p) ((p)->get_sibling_list())
#define CHILD_LIST(p) ((p)->get_child_list())
#define SIBLING_LINK(p) ((p)->get_sibling_list())
#define LCHILD(p) ((p)->get_left_child())
#define RSIBLING(p) ((p)->get_right_sibling())
#define IS_UNIQUE_SIBLING(p) (SIBLING_LIST(p)->is_empty())
 
namespace Aleph {
 
template <class T>
class Tree_Node;  // Forward declaration for CRTP
 
template <class T>
class Tree_Node : public FunctionalMixin<Tree_Node<T>, Tree_Node<T> *>
{
  T data;
  Dlink child;
  Dlink sibling;
 
  struct Flags
  {
    unsigned int is_root : 1;
    unsigned int is_leaf : 1;
    unsigned int is_leftmost : 1;
    unsigned int is_rightmost : 1;
    Flags() noexcept : is_root(1), is_leaf(1), is_leftmost(1), is_rightmost(1) {}
  };
 
  Flags flags;
 
  LINKNAME_TO_TYPE(Tree_Node, child);
  LINKNAME_TO_TYPE(Tree_Node, sibling);
 
  Tree_Node *upper_link() const noexcept
  {
    return child_to_Tree_Node(child.get_prev());
  }
 
  Tree_Node *lower_link() const noexcept
  {
    return child_to_Tree_Node(child.get_next());
  }
 
  Tree_Node *left_link() const noexcept
  {
    return sibling_to_Tree_Node(sibling.get_prev());
  }
 
  Tree_Node *right_link() const noexcept
  {
    return sibling_to_Tree_Node(sibling.get_next());
  }
 
public:
  using Item_Type = Tree_Node *;
 
  T &get_key() noexcept
  {
    return get_data();
  }
 
  [[nodiscard]] constexpr const T &get_key() const noexcept
  {
    return get_data();
  }
 
  T &get_data() noexcept
  {
    return data;
  }
 
  [[nodiscard]] constexpr const T &get_data() const noexcept
  {
    return data;
  }
 
  using key_type = T;
 
  Dlink *get_child_list() noexcept
  {
    return &child;
  }
 
  Dlink *get_sibling_list() noexcept
  {
    return &sibling;
  }
 
  [[nodiscard]] constexpr bool is_root() const noexcept
  {
    return flags.is_root;
  }
 
  [[nodiscard]] constexpr bool is_leaf() const noexcept
  {
    return flags.is_leaf;
  }
 
  [[nodiscard]] constexpr bool is_leftmost() const noexcept
  {
    return flags.is_leftmost;
  }
 
  [[nodiscard]] constexpr bool is_rightmost() const noexcept
  {
    return flags.is_rightmost;
  }
 
  void set_is_root(bool value) noexcept
  {
    flags.is_root = value;
  }
 
  void set_is_leaf(bool value) noexcept
  {
    flags.is_leaf = value;
  }
 
  void set_is_leftmost(bool value) noexcept
  {
    flags.is_leftmost = value;
  }
 
  void set_is_rightmost(bool value) noexcept
  {
    flags.is_rightmost = value;
  }
 
  Tree_Node() = default;
 
  Tree_Node(const T &d) : data(d)
  { /* empty */
  }
 
  Tree_Node(T &&d) : data(std::move(d))
  { /* empty */
  }
 
  Tree_Node *get_left_sibling() const noexcept
  {
    if (is_leftmost())
      return nullptr;
 
    return left_link();
  }
 
  Tree_Node *get_right_sibling() const noexcept
  {
    if (is_rightmost())
      return nullptr;
 
    return right_link();
  }
 
  Tree_Node *get_left_child() const noexcept
  {
    if (is_leaf())
      return nullptr;
 
    return lower_link();
  }
 
  Tree_Node *get_right_child() const noexcept
  {
    if (is_leaf())
      return nullptr;
 
    const Tree_Node *left_child = lower_link();
 
    assert(ISLEFTMOST(left_child));
 
    return left_child->left_link();
  }
 
  Tree_Node *get_child(const size_t i) const noexcept
  {
    Tree_Node *c = get_left_child();
    for (size_t j = 0; c != nullptr and j < i; ++j)
      c = c->get_right_sibling();
 
    return c;
  }
 
  Tree_Node *get_parent() const noexcept
  {
    if (is_root())
      return nullptr;
 
    auto *p = const_cast<Tree_Node *>(this);
    while (not ISLEFTMOST(p))  // go down to the leftmost node
      p = p->left_link();
 
    assert(not ISROOT(p));
    assert(not CHILD_LIST(p)->is_empty());
 
    return p->upper_link();
  }
 
  void insert_right_sibling(Tree_Node *p) noexcept
  {
    if (p == nullptr)
      return;
 
    assert(CHILD_LIST(p)->is_empty());
    assert(SIBLING_LIST(p)->is_empty());
    assert(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());
 
    if (this->is_root())
      {
        this->insert_tree_to_right(p);
        return;
      }
 
    p->set_is_root(false);
    p->set_is_leftmost(false);
 
    Tree_Node *old_next_node = get_right_sibling();
    if (old_next_node != nullptr)
      {
        assert(not this->is_rightmost());
        p->set_is_rightmost(false);
      }
    else
      {
        assert(this->is_rightmost());
        p->set_is_rightmost(true);
      }
 
    this->set_is_rightmost(false);
    this->sibling.insert(SIBLING_LIST(p));
  }
 
  void insert_left_sibling(Tree_Node *p)
  {
    if (p == nullptr)
      return;
 
    ah_domain_error_if(this->is_root()) << "Cannot insert sibling of a root";
 
    assert(CHILD_LIST(p)->is_empty());
    assert(SIBLING_LIST(p)->is_empty());
    assert(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());
 
    p->set_is_root(false);
    p->set_is_rightmost(false);
 
    Tree_Node *old_prev_node = this->get_left_sibling();
    if (old_prev_node != nullptr)
      {
        assert(not this->is_leftmost());
        p->set_is_leftmost(false);
      }
    else
      {  // this is the leftmost ==> p must become the first child
        assert(this->is_leftmost());
 
        Tree_Node *parent = this->get_parent();
 
        // Find the tree root. To do so, we look for the leaf of this
        Tree_Node *leaf = this;
        while (not leaf->is_leaf())
          {
            leaf = leaf->get_left_child();
            assert(leaf != nullptr);
          }
 
        Tree_Node *root = leaf->lower_link();
        assert(root != nullptr);
 
        Dlink tree = CHILD_LIST(root)->cut_list(CHILD_LIST(this));
        tree.del();
        CHILD_LIST(parent)->insert(CHILD_LIST(p));
        p->set_is_leftmost(true);
 
        assert(p->get_parent() == parent);
      }
 
    this->set_is_leftmost(false);
    this->sibling.append(SIBLING_LIST(p));
  }
 
  void insert_leftmost_child(Tree_Node *p) noexcept
  {
    if (p == nullptr)
      return;
 
    assert(CHILD_LIST(p)->is_empty());
    assert(SIBLING_LIST(p)->is_empty());
    assert(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());
 
    p->set_is_root(false);
    if (this->is_leaf())
      {
        this->set_is_leaf(false);
        CHILD_LIST(this)->insert(CHILD_LIST(p));
      }
    else
      {
        Tree_Node *old_left_child = this->lower_link();
        Tree_Node *leaf = old_left_child;
        while (not leaf->is_leaf())
          leaf = leaf->get_left_child();
 
        Tree_Node *root = leaf->lower_link();
        Dlink subtree = CHILD_LIST(root)->cut_list(CHILD_LIST(old_left_child));
        subtree.del();
        CHILD_LIST(this)->insert(CHILD_LIST(p));
        SIBLING_LIST(old_left_child)->append(SIBLING_LIST(p));
        old_left_child->set_is_leftmost(false);
        p->set_is_rightmost(false);
        assert(p->get_right_sibling() == old_left_child);
        assert(old_left_child->get_left_sibling() == p);
      }
    assert(p->is_leftmost());
  }
 
  void insert_rightmost_child(Tree_Node *p) noexcept
  {
    if (p == nullptr)
      return;
 
    assert(CHILD_LIST(p)->is_empty());
    assert(SIBLING_LIST(p)->is_empty());
    assert(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());
 
    p->set_is_root(false);
 
    if (this->is_leaf())
      {
        this->set_is_leaf(false);
        CHILD_LIST(this)->insert(CHILD_LIST(p));
      }
    else
      {
        Tree_Node *old_right_child_node = this->lower_link()->left_link();
        old_right_child_node->set_is_rightmost(false);
        p->set_is_leftmost(false);
        SIBLING_LIST(old_right_child_node)->insert(SIBLING_LIST(p));
      }
  }
 
  Tree_Node *join(Tree_Node *tree)
  {
    assert(this->is_root());
    assert(tree != nullptr);
    assert(tree->is_root() and tree->is_leftmost() and tree->is_rightmost());
 
    tree->set_is_root(false);
 
    if (this->is_leaf())
      {
        assert(CHILD_LIST(this)->is_empty() and SIBLING_LIST(this)->is_empty());
        this->set_is_leaf(false);
        CHILD_LIST(this)->splice(CHILD_LIST(tree));
      }
    else
      {
        Tree_Node *right_child = this->lower_link()->left_link();
        right_child->set_is_rightmost(false);
        tree->set_is_leftmost(false);
        SIBLING_LINK(right_child)->splice(SIBLING_LINK(tree));
      }
 
    return this;
  }
 
  void insert_tree_to_right(Tree_Node *tree)
  {
    if (tree == nullptr)
      return;
 
    ah_domain_error_if(not this->is_root()) << "\"this\" is not root";
 
    tree->set_is_leftmost(false);
    Tree_Node *old_next_tree = this->get_right_tree();
    if (old_next_tree != nullptr)
      {
        assert(not this->is_rightmost());
        tree->set_is_rightmost(false);
      }
 
    this->set_is_rightmost(false);
    SIBLING_LIST(this)->insert(SIBLING_LIST(tree));
  }
 
  Tree_Node *get_left_tree() const noexcept
  {
    if (is_leftmost())
      return nullptr;
    assert(not is_leftmost());
    return left_link();
  }
 
  Tree_Node *get_right_tree() const noexcept
  {
    if (is_rightmost())
      return nullptr;
 
    assert(not is_rightmost());
    return right_link();
  }
 
  Tree_Node *get_last_tree() const
  {
    ah_range_error_if(not is_leftmost()) << "\"this\" is not the leftmost tree in the forest";
 
    return left_link();
  }
 
  template <template <typename> class Container = DynList>
  Container<Tree_Node *> trees() const
  {
    Container<Tree_Node *> ret;
    for (auto t = const_cast<Tree_Node *>(this); t != nullptr; t = t->get_right_tree())
      ret.append(t);
    return ret;
  }
 
  template <typename Operation>
  void for_each_child(Operation &op) const
  {
    for (Tree_Node *child = get_left_child(); child != nullptr; child = child->get_right_sibling())
      op(child);
  }
 
  template <typename Operation>
  void for_each_child(Operation &&op = Operation()) const
  {
    for_each_child<Operation>(op);
  }
 
  template <template <typename> class Container = DynList>
  Container<Tree_Node *> children_nodes() const
  {
    Container<Tree_Node *> ret_val;
    this->for_each_child([&ret_val](Tree_Node *p)
      {
        ret_val.append(p);
      });
    return ret_val;
  }
 
  template <template <typename> class Container = DynList>
  Container<T> children() const
  {
    Container<T> ret_val;
    this->for_each_child([&ret_val](Tree_Node *p)
      {
        ret_val.append(p->get_key());
      });
    return ret_val;
  }
 
private:
  template <class Operation>
  static bool preorder(const Tree_Node *root, Operation &op)
  {
    if (root == nullptr)
      return true;
 
    if (not op(root))
      return false;
 
    for (Tree_Node *child = root->get_left_child(); child != nullptr;
         child = child->get_right_sibling())
      if (not preorder(child, op))
        return false;
 
    return true;
  }
 
public:
  template <class Operation>
  bool traverse(Operation op)
  {
    return preorder(this, op);
  }
 
  template <class Operation>
  bool traverse(Operation op) const
  {
    return const_cast<Tree_Node *>(this)->traverse(op);
  }
 
  template <class Op>
  bool level_traverse(Op op)
  {
    DynListQueue<Tree_Node *> q;
    q.put(this);
    while (not q.is_empty())
      {
        Tree_Node *p = q.get();
        if (not op(p))
          return false;
        p->for_each_child([&q](auto cptr)
          {
            q.put(cptr);
          });
      }
    return true;
  }
 
  template <class Op>
  bool level_traverse(Op op) const
  {
    return const_cast<Tree_Node *>(this)->level_traverse(op);
  }
 
  // Note: for_each(), all(), exists(), maps(), filter(), foldl(),
  // fold(), partition(), take(), drop(), rev(), length() are now
  // provided by FunctionalMixin<Tree_Node<T>, Tree_Node<T>*>
 
  class Children_Iterator
  {
    Tree_Node *curr = nullptr;
 
  public:
    Children_Iterator(const Tree_Node &p) noexcept : curr(p.get_left_child()) {}
 
    Children_Iterator(Tree_Node &p) noexcept : curr(p.get_left_child()) {}
 
    Children_Iterator(Tree_Node *p) noexcept : curr(p->get_left_child()) {}
 
    Children_Iterator(const Children_Iterator &it) noexcept
      : curr(it.curr)
    {}
 
    [[nodiscard]] bool has_curr() const noexcept
    {
      return curr != nullptr;
    }
 
    Tree_Node *get_curr_ne() const noexcept
    {
      return curr;
    }
 
    Tree_Node *get_curr() const
    {
      ah_overflow_error_if(curr == nullptr) << "Children_Iterator::get_curr()";
      return get_curr_ne();
    }
 
    void next_ne() noexcept
    {
      curr = curr->get_right_sibling();
    }
 
    void next()
    {
      ah_overflow_error_if(curr == nullptr) << "Children_Iterator::next()";
      next_ne();
    }
  };
 
  Children_Iterator children_it() const
  {
    return Children_Iterator(*this);
  }
 
  struct Children_Set
  {
    Children_Set(const Tree_Node &&) {}
    Children_Set(const Tree_Node &) {}
    struct Iterator : public Children_Iterator
    {
      using Children_Iterator::Children_Iterator;
    };
  };
 
  class Iterator
  {
    Tree_Node *root = nullptr;
    Tree_Node *curr = nullptr;
    long pos = 0;
    DynListStack<Tree_Node *> s;
 
  public:
    using Item_Type = Tree_Node *;
 
    void swap(Iterator &it) noexcept
    {
      std::swap(root, it.root);
      std::swap(curr, it.curr);
      std::swap(pos, it.pos);
      s.swap(it.s);
    }
 
    Iterator(Tree_Node *r = nullptr) noexcept : root(r), curr(root)
    {
      // empty
    }
 
    Iterator(Tree_Node &root) : Iterator(&root) {}
 
    Iterator(const Iterator &it) : root(it.root), curr(it.curr), pos(it.pos), s(it.s)
    {
      // empty
    }
 
    Iterator(Iterator &&it) noexcept : root(nullptr), curr(nullptr), pos(0), s()
    {
      swap(it);
    }
 
    Iterator &operator = (Iterator it)
    {
      it.swap(*this);
      return *this;
    }
 
    void reset_first() noexcept
    {
      s.empty();
      pos = 0;
      curr = root;
    }
 
    [[nodiscard]] bool has_curr() const noexcept
    {
      return curr != nullptr;
    }
 
    Tree_Node *get_curr_ne() const noexcept
    {
      return curr;
    }
 
    Tree_Node *get_curr() const
    {
      ah_overflow_error_if(not has_curr()) << "Iterator overflow";
      return get_curr_ne();
    }
 
    void next_ne() noexcept
    {
      ++pos;
      Tree_Node *lchild = curr->get_left_child();
      if (lchild == nullptr)
        {
          if (s.is_empty())
            curr = nullptr;
          else
            curr = s.pop();
 
          return;
        }
 
      for (auto p = curr->get_right_child(); p != lchild; p = p->get_left_sibling())
        s.push(p);
 
      curr = lchild;
    }
 
    void next()
    {
      ah_overflow_error_if(not has_curr()) << "Iterator overflow";
      next_ne();
    }
 
    void end()
    {
      curr = nullptr;
      s.empty();
      pos = -1;
    }
 
    // has_curr() == true
    [[nodiscard]] size_t get_pos() const
    {
      return pos;
    }
  };
 
  Iterator get_it() const
  {
    return Iterator(const_cast<Tree_Node *>(this));
  }
 
  STL_ALEPH_ITERATOR(Tree_Node);
};
 
template <typename T>
struct Tree_Node_Vtl : public Tree_Node<T>
{
  virtual ~Tree_Node_Vtl() = default;
};
 
template <class Node>
static inline void clone_tree(Node *src, Node *tgt)
{
  using It = typename Node::Children_Iterator;
  for (It it(src); it.has_curr(); it.next_ne())
    tgt->insert_rightmost_child(new Node(it.get_curr()->get_key()));
 
  using PItor = Pair_Iterator<It>;
  for (PItor itor{It(*src), It(*tgt)}; itor.has_curr(); itor.next_ne())
    {
      auto p = itor.get_curr();
      clone_tree(p.first, p.second);
    }
}
 
template <class Node>
Node *clone_tree(Node *root)
{
  if (root == nullptr)
    return nullptr;
  Node *ret = new Node(root->get_key());
  clone_tree(root, ret);
  return ret;
}
 
template <class Node>
static inline void __tree_preorder_traversal(Node *root, const int &level, const int &child_index,
                                             void (*visitFct)(Node *, int, int))
{
  (*visitFct)(root, level, child_index);
  Node *child = root->get_left_child();
  for (int i = 0; child != nullptr; ++i, child = child->get_right_sibling())
    __tree_preorder_traversal(child, level + 1, i, visitFct);
}
 
template <class Node>
inline void tree_preorder_traversal(Node *root, void (*visitFct)(Node *, int, int))
{
  ah_domain_error_if(not root->is_root()) << "root is not root";
 
  __tree_preorder_traversal(root, 0, 0, visitFct);
}
 
template <class Node>
inline void forest_preorder_traversal(Node *root, void (*visitFct)(Node *, int, int))
{
  ah_domain_error_if(not root->is_root()) << "root is not root";
 
  for (/* nothing */; root != nullptr; root = root->get_right_tree())
    {
      assert(root->is_root());
      __tree_preorder_traversal(root, 0, 0, visitFct);
    }
}
 
template <class Node>
static inline void __tree_postorder_traversal(Node *node, const int &level, const int &child_index,
                                              void (*visitFct)(Node *, int, int))
{
  Node *child = node->get_left_child();
 
  for (int i = 0; child not_eq nullptr; i++, child = child->get_right_sibling())
    __tree_postorder_traversal(child, level + 1, i, visitFct);
 
  (*visitFct)(node, level, child_index);
}
 
template <class Node>
inline void tree_postorder_traversal(Node *root, void (*visitFct)(Node *, int, int))
{
  __tree_postorder_traversal(root, 0, 0, visitFct);
}
 
template <class Node>
inline void forest_postorder_traversal(Node *root, void (*visitFct)(Node *, int, int))
{
  ah_domain_error_if(not root->is_leftmost()) << "root is not the leftmost node of forest";
 
  ah_domain_error_if(not root->is_root()) << "root is not root";
 
  for (/* nothing */; root not_eq nullptr; root = root->get_right_sibling())
    {
      assert(root->is_root());
      __tree_postorder_traversal(root, 0, 0, visitFct);
    }
}
 
template <class Node, class Eq>
inline bool are_tree_equal(Node *t1, Node *t2, Eq &eq)
{
  if (t1 == nullptr)
    return t2 == nullptr;
 
  if (t2 == nullptr)
    return false;
 
  if (not eq(t1->get_key(), t2->get_key()))
    return false;
 
  try
    {
      return zipEq(t1->children_nodes(), t2->children_nodes())
        .all([&eq](auto p)
        {
          return are_tree_equal(p.first, p.second, eq);
        });
    }
  catch (const std::length_error &)
    {
      return false;
    }
}
 
template <class Node, class Eq = std::equal_to<typename Node::key_type>>
inline bool are_tree_equal(Node *t1, Node *t2, Eq &&eq = Eq())
{
  return are_tree_equal<Node, Eq>(t1, t2, eq);
}
 
template <class Node>
inline void destroy_tree(Node *root)
{
  if (root == nullptr)
    return;
 
  // If `root` is the leftmost child of a live parent, its `child` field is
  // spine-linked to that parent (see the class-level note on the shared
  // spine trick): removing `root` must hand that spine slot to its right
  // sibling, promoted below to the new leftmost child. Captured before the
  // sibling list is touched; only usable once `root`'s own children have
  // been recursively destroyed (see below), so it is applied at the
  // `CHILD_LIST` cleanup near the end of this function, not here.
  Node *promoted_leftmost = nullptr;
 
  if (not IS_UNIQUE_SIBLING(root))
    {
      // `root` is about to be unlinked from its sibling list. If it was an
      // extremal sibling, the neighbor taking its place must inherit the
      // corresponding flag -- otherwise that neighbor is left with
      // is_rightmost()/is_leftmost() == false while actually being the new
      // extremum, so get_right_sibling()/get_left_sibling() no longer
      // short-circuit to nullptr and instead wrap around the remaining
      // circular sibling list, corrupting any get_right_sibling()-based
      // traversal (for_each_child(), Children_Iterator, ...) into an
      // infinite loop.
      if (root->is_rightmost())
        if (auto *new_last = root->get_left_sibling(); new_last != nullptr)
          new_last->set_is_rightmost(true);
 
      if (root->is_leftmost())
        if (auto *new_first = root->get_right_sibling(); new_first != nullptr)
          {
            new_first->set_is_leftmost(true);
            // Only a child-of-a-parent's `child` field is spine-linked (a
            // top-level forest tree's `child` field is purely private, no
            // spine to hand over), and only when the promoted sibling is
            // itself a leaf can that hand-over be done with a single
            // Dlink::swap(): when the promoted sibling already has its own
            // children, its `child` field is already the head of its own
            // (unrelated) spine, and swap() would splice root's parent
            // directly to that spine's *other* end, orphaning the
            // promoted sibling's real children -- a separate, deeper,
            // pre-existing gap in destroy_tree() (reproducible even
            // without this fix: destroying any node that has its own
            // children while its parent survives already corrupts the
            // parent's child spine). Left as a known gap, tracked
            // separately, rather than risking new corruption here.
            if (not root->is_root() and new_first->is_leaf())
              promoted_leftmost = static_cast<Node *>(new_first);
          }
 
      SIBLING_LIST(root)->del();  // no ==> remove from sibling list
    }
 
  // traverse subtrees from right to left
  for (Node *p = static_cast<Node *>(root->get_right_child()); p != nullptr; /* nada */)
    {
      Node *to_delete = p;                             // backup subtree to delete
      p = static_cast<Node *>(p->get_left_sibling());  // advance to left sibling
      destroy_tree(to_delete);                         // recursively delete tree
    }
 
  if (promoted_leftmost != nullptr)
    // root's own children are gone by now, so CHILD_LIST(root) is just its
    // spine pairing with its (live) parent; hand that slot to the promoted
    // sibling in one swap (promoted_leftmost is a leaf, i.e. its own
    // CHILD_LIST is empty, so Dlink::swap() simply relocates root's pairing
    // there instead of merging two unrelated non-empty lists).
    CHILD_LIST(root)->swap(CHILD_LIST(promoted_leftmost));
  else if (root->is_leftmost())  // remove children list?
    CHILD_LIST(root)->del();
 
  delete root;
}
 
template <class Node>
inline void destroy_forest(Node *root)
{
  if (root == nullptr)
    return;
 
  ah_domain_error_if(not root->is_leftmost()) << "root is not the leftmost tree of forest";
 
  ah_domain_error_if(not root->is_root()) << "root is not root";
 
  while (root != nullptr)  // traverse trees from left to right
    {
      Node *to_delete = root;                     // backup root
      root = (Node *) root->get_right_sibling();  // advance to next tree
      SIBLING_LIST(to_delete)->del();             // remove from tree list
      destroy_tree(to_delete);                    // delete the tree
    }
}
 
template <class Node>
size_t compute_height(Node *root)
{
  if (root == nullptr)
    return 0;
 
  size_t temp_h, max_h = 0;
  for (Node *aux = root->get_left_child(); aux != nullptr; aux = aux->get_right_sibling())
    if ((temp_h = compute_height(aux)) > max_h)
      max_h = temp_h;
 
  return max_h + 1;
}
 
template <class Node>
static inline Node *__deway_search(Node *node, int path[], const int &idx, const size_t &size)
{
  if (node == nullptr)
    return nullptr;
 
  ah_out_of_range_error_if(static_cast<size_t>(idx) >= size) << "index out of maximum range";
 
  if (path[idx] < 0)  // check whether the node has been reached
    return node;
  // advance to the next child path[0]
  Node *child = node->get_left_child();
  for (int i = 0; i < path[idx] and child != nullptr; ++i)
    child = child->get_right_sibling();
 
  return __deway_search(child, path, idx + 1, size);  // next level
}
 
template <class Node>
inline Node *deway_search(Node *root, int path[], const size_t &size)
{
  for (int i = 0; root != nullptr; i++, root = root->get_right_sibling())
    if (path[0] == i)
      return __deway_search(root, path, 1, size);
 
  return nullptr;
}
 
template <class Node, class Equal>
inline static Node *__search_deway(Node *root, const typename Node::key_type &key,
                                   const size_t &current_level, int deway[], const size_t &size,
                                   size_t &n);
 
template <class Node, class Equal = Aleph::equal_to<typename Node::key_type>>
inline Node *search_deway(Node *root, const typename Node::key_type &key, int deway[],
                          const size_t &size, size_t &n)
{
  n = 1;  // initial length value of the Dewey number
 
  ah_overflow_error_if(size < n) << "there is no enough space for deway array";
 
  for (int i = 0; root != nullptr; i++, root = root->get_right_sibling())
    {
      deway[0] = i;
      Node *result = __search_deway<Node, Equal>(root, key, 0, deway, size, n);
      if (result != nullptr)
        return result;
    }
 
  return nullptr;
}
 
template <class Node, class Equal>
inline static Node *__search_deway(Node *root, const typename Node::key_type &key,
                                   const size_t &current_level, int deway[], const size_t &size,
                                   size_t &n)
{
  ah_overflow_error_if(current_level >= size) << "there is no enough space for deway array";
 
  if (root == nullptr)
    return nullptr;
 
  if (Equal()(root->get_key(), key))
    {
      n = current_level + 1;  // length of the deway array
      return root;
    }
 
  Node *child = root->get_left_child();
  for (int i = 0; child != nullptr; i++, child = child->get_right_sibling())
    {
      ah_overflow_error_if(current_level + 1 >= size) << "there is no enough space for deway array";
      deway[current_level + 1] = i;
      Node *result = __search_deway<Node, Equal>(child, key, current_level + 1, deway, size, n);
 
      if (result != nullptr)
        return result;
    }
 
  return nullptr;
}
 
template <class TNode, class BNode>
BNode *forest_to_bin(TNode *root)
{
  if (root == nullptr)
    return BNode::NullPtr;
 
  auto *result = new BNode(root->get_key());
  LLINK(result) = static_cast<BNode *>(forest_to_bin<TNode, BNode>(root->get_left_child()));
  RLINK(result) = forest_to_bin<TNode, BNode>(root->get_right_sibling());
 
  return result;
}
 
template <class TNode, class BNode>
inline static void insert_child(BNode *lnode, TNode *tree_node)
{
  if (lnode == BNode::NullPtr)
    return;
 
  auto *child = new TNode(KEY(lnode));
  tree_node->insert_leftmost_child(child);
}
 
template <class TNode, class BNode>
inline static void insert_sibling(BNode *rnode, TNode *tree_node)
{
  if (rnode == BNode::NullPtr)
    return;
 
  auto *sibling = new TNode(KEY(rnode));
  tree_node->insert_right_sibling(sibling);
}
 
template <class TNode, class BNode>
inline static void bin_to_tree(BNode *broot, TNode *troot)
{
  if (broot == BNode::NullPtr)
    return;
 
  insert_child(LLINK(broot), troot);
  TNode *left_child = troot->get_left_child();
 
  bin_to_tree(LLINK(broot), left_child);
 
  insert_sibling(RLINK(broot), troot);
  TNode *right_sibling = troot->get_right_sibling();
 
  bin_to_tree(RLINK(broot), right_sibling);
}
 
template <class TNode, class BNode>
inline TNode *bin_to_forest(BNode *broot)
{
  if (broot == BNode::NullPtr)
    return nullptr;
 
  auto *troot = new TNode(KEY(broot));
  bin_to_tree(broot, troot);
  return troot;
}
 
}  // end namespace Aleph
 
#endif  // TPL_TREE_H