tpl_binNodeUtils.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_BINNODEUTILS_H
#define TPL_BINNODEUTILS_H
 
# include <ah-concepts.H>
 
#include <ahFunction.H>
#include <tpl_arrayStack.H>
#include <tpl_arrayQueue.H>
#include <tpl_dynListQueue.H>
#include <bitArray.H>
#include <tpl_dynDlist.H>
#include <tpl_binNode.H>
#include <ah-errors.H>
# include <cassert>
 
namespace Aleph {
 
template <BinNodeLike Node>
inline void assert_valid_tree_root([[maybe_unused]] const Node *root) noexcept
{
  assert((Node::NullPtr == nullptr or root != nullptr) and
         "nullptr is not an empty tree for a node type with a sentinel; use Node::NullPtr");
}
template <BinNodeLike Node>
inline void inorder_rec_helper(Node *node, const int &level, int &position,
                                      void (*visitFct)(Node *, int, int))
{
  if (node == Node::NullPtr)
    return;
 
  inorder_rec_helper(LLINK(node), level + 1, position, visitFct);
 
  (*visitFct)(node, level, position);
  ++position;
 
  inorder_rec_helper(RLINK(node), level + 1, position, visitFct);
}
 
template <BinNodeLike Node>
inline int inOrderRec(Node *root, void (*visitFct)(Node *, int, int))
{
  assert_valid_tree_root(root);
  int position = 0;
  inorder_rec_helper(root, 0, position, visitFct);
  return position;
}
 
template <BinNodeLike Node>
inline void preorder_rec_helper(Node *p, const int &level, int &position,
                                       void (*visitFct)(Node *, int, int))
{
  if (p == Node::NullPtr)
    return;
 
  (*visitFct)(p, level, position);
  ++position;
 
  preorder_rec_helper(LLINK(p), level + 1, position, visitFct);
  preorder_rec_helper(RLINK(p), level + 1, position, visitFct);
}
 
template <BinNodeLike Node>
inline int preOrderRec(Node *root, void (*visitFct)(Node *, int, int))
{
  assert_valid_tree_root(root);
  int position = 0;
  preorder_rec_helper(root, 0, position, visitFct);
  return position;
}
 
template <BinNodeLike Node>
inline void postorder_rec_helper(Node *node, const int &level, int &position,
                                        void (*visitFct)(Node *, int, int))
{
  if (node == Node::NullPtr)
    return;
 
  postorder_rec_helper(LLINK(node), level + 1, position, visitFct);
  postorder_rec_helper(RLINK(node), level + 1, position, visitFct);
 
  (*visitFct)(node, level, position);
  ++position;
}
 
template <BinNodeLike Node>
inline int postOrderRec(Node *root, void (*visitFct)(Node *, int, int))
{
  assert_valid_tree_root(root);
  int position = 0;
  postorder_rec_helper(root, 0, position, visitFct);
  return position;
}
 
template <class Node>
class For_Each_In_Order
{
  template <class Op>
  static void for_each_inorder(Node *root, Op &&op)
  {
    if (root == Node::NullPtr)
      return;
 
    for_each_inorder(LLINK(root), std::forward<Op>(op));
    op(root);
    for_each_inorder(RLINK(root), std::forward<Op>(op));
  }
 
public:
  template <class Op>
  void traverse(Node *root, Op &&op) const
  {
    for_each_inorder(root, std::forward<Op>(op));
  }
 
  template <class Op>
  void operator () (Node *root, Op &op) const
  {
    for_each_inorder(root, op);
  }
 
  template <class Op>
  void operator () (Node *root, Op &&op) const
  {
    for_each_inorder(root, std::forward<Op>(op));
  }
};
 
template <BinNodeLike Node, class Op>
inline void for_each_in_order(Node *root, Op &&op)
{
  return For_Each_In_Order<Node>().traverse(root, std::forward<Op>(op));
}
 
template <class Node>
class For_Each_Preorder
{
  template <class Op>
  static void preorder(Node *root, Op &&op)
  {
    if (root == Node::NullPtr)
      return;
 
    op(root);
    preorder(LLINK(root), std::forward<Op>(op));
    preorder(RLINK(root), std::forward<Op>(op));
  }
 
public:
  template <class Op>
  void traverse(Node *root, Op &&op) const
  {
    return preorder(root, std::forward<Op>(op));
  }
 
  template <class Op>
  void operator () (Node *root, Op &op) const
  {
    preorder(root, op);
  }
 
  template <class Op>
  void operator () (Node *root, Op &&op = Op()) const
  {
    preorder(root, std::forward<Op>(op));
  }
};
 
template <BinNodeLike Node, class Op>
void for_each_preorder(Node *root, Op &&op)
{
  For_Each_Preorder<Node>().traverse(root, std::forward<Op>(op));
}
 
template <class Node>
class For_Each_Postorder
{
  template <class Op>
  static void postorder(Node *root, Op &&op)
  {
    if (root == Node::NullPtr)
      return;
 
    postorder(LLINK(root), std::forward<Op>(op));
    postorder(RLINK(root), std::forward<Op>(op));
    op(root);
  }
 
public:
  template <class Op>
  void traverse(Node *root, Op &&op) const
  {
    return postorder(root, std::forward<Op>(op));
  }
 
  template <class Op>
  void operator () (Node *root, Op &op) const
  {
    postorder(root, op);
  }
 
  template <class Op>
  void operator () (Node *root, Op &&op = Op()) const
  {
    postorder(root, std::forward<Op>(op));
  }
};
 
template <BinNodeLike Node, class Op>
void for_each_postorder(Node *root, Op &&op)
{
  For_Each_Postorder<Node>().traverse(root, std::forward<Op>(op));
}
 
template <BinNodeLike Node>
static void prefix(Node *root, DynList<Node *> &acc)
{
  if (root == Node::NullPtr)
    return;
 
  acc.append(root);
  prefix(LLINK(root), acc);
  prefix(RLINK(root), acc);
}
 
template <BinNodeLike Node>
static void infix(Node *root, DynList<Node *> &acc)
{
  if (root == Node::NullPtr)
    return;
 
  infix(LLINK(root), acc);
  acc.append(root);
  infix(RLINK(root), acc);
}
 
template <BinNodeLike Node>
static void suffix(Node *root, DynList<Node *> &acc)
{
  if (root == Node::NullPtr)
    return;
 
  suffix(LLINK(root), acc);
  suffix(RLINK(root), acc);
  acc.append(root);
}
 
template <BinNodeLike Node>
DynList<Node *> prefix(Node *root)
{
  DynList<Node *> ret_val;
  prefix(root, ret_val);
  return ret_val;
}
 
template <BinNodeLike Node>
DynList<Node *> infix(Node *root)
{
  DynList<Node *> ret_val;
  infix(root, ret_val);
  return ret_val;
}
 
template <BinNodeLike Node>
DynList<Node *> suffix(Node *root)
{
  DynList<Node *> ret_val;
  suffix(root, ret_val);
  return ret_val;
}
 
template <BinNodeLike Node>
inline size_t compute_cardinality_rec(Node *root) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return 0;
 
  return compute_cardinality_rec(LLINK(root)) + 1 + compute_cardinality_rec(RLINK(root));
}
 
template <BinNodeLike Node>
inline size_t size(Node *root) noexcept
{
  return compute_cardinality_rec(root);
}
 
template <BinNodeLike Node>
inline size_t computeHeightRec(Node *root) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return 0;
 
  const size_t left_height = computeHeightRec(LLINK(root));
  const size_t right_height = computeHeightRec(RLINK(root));
 
  return 1 + std::max(left_height, right_height);
}
 
template <BinNodeLike Node>
inline void destroyRec(Node *&root) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return;
 
  destroyRec(LLINK(root));
  destroyRec(RLINK(root));
  delete root;
  root = Node::NullPtr;
}
 
template <BinNodeLike Node>
inline void callKeyDestructorsRec(Node *&root) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return;
 
  using Key = typename Node::key_type;
 
  callKeyDestructorsRec(LLINK(root));
  callKeyDestructorsRec(RLINK(root));
  root->get_key().~Key();
  root = Node::NullPtr;
}
 
template <BinNodeLike Node>
[[nodiscard]] inline Node *copyRec(Node *root)
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return Node::NullPtr;
 
  Node *tgt_root = new Node(*root);
 
  try
    {
      LLINK(tgt_root) = copyRec<Node>(LLINK(root));
      RLINK(tgt_root) = copyRec<Node>(RLINK(root));
    }
  catch (...)
    {
      assert(RLINK(tgt_root) == Node::NullPtr);
 
      if (LLINK(tgt_root) != Node::NullPtr)
        destroyRec(LLINK(tgt_root));  // TODO: diff de Node*&
 
      delete tgt_root;
 
      throw;
    }
 
  return tgt_root;
}
 
template <BinNodeLike Node>
inline bool areSimilar(Node *t1, Node *t2) noexcept
{
  if (t1 == t2)  // that include the case when t1 and t2 are the same
    // or both are Node::NullPtr
    return true;
 
  if (t1 == Node::NullPtr or t2 == Node::NullPtr)
    return false;
 
  return areSimilar(LLINK(t1), LLINK(t2)) and areSimilar(RLINK(t1), RLINK(t2));
}
 
template <BinNodeLike Node, class Equal>
inline bool areEquivalents(Node *t1, Node *t2, Equal &op) noexcept
{
  if (t1 == t2)
    return true;
 
  if (t1 == Node::NullPtr or t2 == Node::NullPtr)
    return false;
 
  if (not op(KEY(t1), KEY(t2)))
    return false;
 
  return areEquivalents(LLINK(t1), LLINK(t2), op) and areEquivalents(RLINK(t1), RLINK(t2), op);
}
 
template <BinNodeLike Node, class Equal = std::equal_to<typename Node::key_type>>
inline bool areEquivalents(Node *t1, Node *t2, Equal &&op = Equal()) noexcept
{
  return areEquivalents(t1, t2, op);
}
 
template <BinNodeLike Node>
inline void levelOrder(Node *root, void (*visitFct)(Node *, int, bool))
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return;
 
  DynListQueue<std::pair<Node *, bool>> queue;
  queue.put(std::pair<Node *, bool>(root, bool()));
 
  for (int pos = 0; not queue.is_empty(); pos++)
    {
      std::pair<Node *, bool> pr = queue.get();
      Node *&p = pr.first;
 
      (*visitFct)(p, pos, pr.second);
 
      if (LLINK(p) != Node::NullPtr)
        queue.put(std::pair<Node *, bool>(LLINK(p), true));
 
      if (RLINK(p) != Node::NullPtr)
        queue.put(std::pair<Node *, bool>(RLINK(p), false));
    }
}
 
template <BinNodeLike Node, class Operation>
inline bool level_traverse(Node *root, Operation &operation)
{
  if (root == Node::NullPtr)
    return true;
 
  DynListQueue<Node *> queue;
  queue.put(root);
  while (not queue.is_empty())
    {
      Node *p = queue.get();
      if (not operation(p))
        return false;
 
      if (LLINK(p) != Node::NullPtr)
        queue.put(LLINK(p));
 
      if (RLINK(p) != Node::NullPtr)
        queue.put(RLINK(p));
    }
  return true;
}
 
template <BinNodeLike Node, class Operation>
inline bool level_traverse(Node *root, Operation &&operation)
{
  return level_traverse<Node, Operation>(root, operation);
}
 
template <template <class> class Node, typename Key>
inline Node<Key> *build_tree(const DynArray<Key> &preorder, long l_p, long r_p,
                             const DynArray<Key> &inorder, long l_i, long r_i)
{
  if (l_p > r_p)
    {
      assert(l_i > r_i);
      return Node<Key>::NullPtr;
    }
 
  assert(r_p - l_p == r_i - l_i);
 
  auto *root = new Node<Key>(preorder[l_p]);
  if (r_p == l_p)
    return root;
 
  assert(l_i <= r_i);
 
  // Find root key position in inorder array
  int i = -1;
  for (int j = l_i; j <= r_i; ++j)
    if (inorder[j] == preorder[l_p])
      {
        i = j - l_i;
        break;
      }
 
  // Validate that root key was found in inorder array
  ah_domain_error_if(i < 0) << "build_tree: root key not found in inorder array (corrupted input)";
 
  assert(i <= r_i - l_i);
 
  LLINK(root) = build_tree<Node, Key>(preorder, l_p + 1, l_p + i, inorder, l_i, l_i + (i - 1));
  RLINK(root) = build_tree<Node, Key>(preorder, l_p + i + 1, r_p, inorder, l_i + i + 1, r_i);
  return root;
}
 
template <template <class> class Node, typename Key>
inline Node<Key> *build_postorder(const DynArray<Key> &post, long lp, long rp,
                                  const DynArray<Key> &in, long li, long ri)
{
  assert(rp - lp == ri - li);
  if (lp > rp)
    return Node<Key>::NullPtr;
 
  auto *root = new Node<Key>(post[rp]);
 
  // Search in inorder array the index of root
  int i = li;
  for (; i <= ri; ++i)
    if (in[i] == post[rp])
      break;
 
  // Validate that root key was found in inorder array
  ah_domain_error_if(i > ri)
    << "build_postorder: root key not found in inorder array (corrupted input)";
 
  assert(i <= ri);
 
  LLINK(root) = build_postorder<Node, Key>(post, lp, lp + (i - li) - 1, in, li, i - 1);
  RLINK(root) = build_postorder<Node, Key>(post, rp - (ri - i), rp - 1, in, i + 1, ri);
  return root;
}
 
template <BinNodeLike Node>
inline void compute_nodes_in_level_helper(Node *root, long level, const long current_level,
                                                 DynDlist<Node *> &level_list)
{
  if (root == Node::NullPtr)
    return;
 
  if (current_level == level)
    {
      level_list.append(root);
      return;  // it is not worth descending further
    }
 
  compute_nodes_in_level_helper(LLINK(root), level, current_level + 1, level_list);
  compute_nodes_in_level_helper(RLINK(root), level, current_level + 1, level_list);
}
 
template <BinNodeLike Node>
inline DynDlist<Node *> compute_nodes_in_level(Node *root, const int &level)
{
  DynDlist<Node *> list;
  compute_nodes_in_level_helper(root, level, 0, list);
  return list;
}
 
template <BinNodeLike Node>
inline void inOrderThreaded(Node *root, void (*visitFct)(Node *))
{
  if (root == Node::NullPtr)
    return;
 
  Node *p = root, *r = Node::NullPtr;
  while (p != Node::NullPtr)
    {
      Node *q = LLINK(p);
      if (q == Node::NullPtr)
        {  // No left branch ==> visit p
          (*visitFct)(p);
          r = p;
          p = RLINK(p);
          continue;
        }
 
      // Move towards the rightmost node of the left branch
      while (q != r and RLINK(q) != Node::NullPtr)
        q = RLINK(q);
 
      if (q != r)        // Does p have a predecessor?
        {                // yes ==> leave a thread in order to later come back and visit p
          RLINK(q) = p;  // place the thread here
          p = LLINK(p);  // keep descending on the left
          continue;
        }
 
      (*visitFct)(p);
 
      RLINK(q) = Node::NullPtr;  // delete thread
      r = p;
      p = RLINK(p);  // advance to the right branch
    }
}
 
template <BinNodeLike Node>
inline void preOrderThreaded(Node *node, void (*visitFct)(Node *))
{
  if (node == Node::NullPtr)
    return;
 
  Node *p = node, *r = Node::NullPtr;
  while (p != Node::NullPtr)
    {
      Node *q = LLINK(p);
 
      if (q == Node::NullPtr)
        {
          (*visitFct)(p);
          r = p;
          p = RLINK(p);
          continue;
        }
 
      // advance towards the rightmost node of the left branch
      while (q != r and RLINK(q) != Node::NullPtr)
        q = RLINK(q);
 
      if (q != r)
        {
          RLINK(q) = p;
          (*visitFct)(p);
          p = LLINK(p);
          continue;
        }
 
      RLINK(q) = Node::NullPtr; /* delete thread */
      r = p;
      p = RLINK(p); /* advance to right branch */
    }
}
 
template <BinNodeLike Node>
inline size_t internal_path_length_helper(Node *p, const size_t &level) noexcept
{
  if (p == Node::NullPtr)
    return 0;
 
  return level + internal_path_length_helper(LLINK(p), level + 1) +
    internal_path_length_helper(RLINK(p), level + 1);
}
 
template <BinNodeLike Node>
inline size_t internal_path_length(Node *p) noexcept
{
  assert_valid_tree_root(p);
  return internal_path_length_helper(p, 0);
}
 
template <BinNodeLike Node>
inline void tree_to_bits(Node *root, BitArray &array)
{
  if (root == Node::NullPtr)
    {
      array.push(1);
      return;
    }
 
  array.push(0);
  tree_to_bits(LLINK(root), array);
  tree_to_bits(RLINK(root), array);
}
 
template <BinNodeLike Node>
inline BitArray tree_to_bits(Node *root)
{
  BitArray ret_val;
  tree_to_bits(root, ret_val);
  return ret_val;
}
 
template <BinNodeLike Node>
inline std::string code(Node *root)
{
  const BitArray bits = tree_to_bits(root);
  const size_t n = bits.size();
  std::string str;
  str.reserve(n);
  for (size_t i = 0; i < n; ++i)
    str.push_back(bits(i) ? 'b' : 'a');
 
  return str;
}
 
template <BinNodeLike Node>
inline Node *bits_to_tree_helper(const BitArray &array, int &i)
{
  // Bounds check: ensure we don't read past the end of the bit array
  ah_domain_error_if(i >= static_cast<int>(array.size()))
    << "bits_to_tree_helper: bit array index out of bounds (malformed input)";
 
  if (const int bit = array.read_bit(i++); bit == 1)
    return Node::NullPtr;
 
  Node *p = new Node;
  Node *left = Node::NullPtr;
  Node *right = Node::NullPtr;
  try
    {
      left = bits_to_tree_helper<Node>(array, i);
      right = bits_to_tree_helper<Node>(array, i);
    }
  catch (...)
    {
      destroyRec(left);
      destroyRec(right);
      delete p;
      throw;
    }
 
  LLINK(p) = left;
  RLINK(p) = right;
 
  return p;
}
 
template <BinNodeLike Node>
inline Node *bits_to_tree(const BitArray &array, int idx = 0)
{
  return bits_to_tree_helper<Node>(array, idx);
}
 
template <BinNodeLike Node>
inline void save_tree_keys_in_prefix(Node *root, std::ostream &output)
{
  if (root == Node::NullPtr)
    return;
 
  output << root->get_key() << " ";
 
  save_tree_keys_in_prefix(LLINK(root), output);
  save_tree_keys_in_prefix(RLINK(root), output);
}
 
template <BinNodeLike Node>
inline void load_tree_keys_in_prefix(Node *root, std::istream &input)
{
  if (root == Node::NullPtr)
    return;
 
  input >> root->get_key();
  ah_runtime_error_if(not input) << "load_tree_keys_in_prefix: input stream error";
 
  load_tree_keys_in_prefix(LLINK(root), input);
  load_tree_keys_in_prefix(RLINK(root), input);
}
 
template <BinNodeLike Node>
inline void save_tree(Node *root, std::ostream &output)
{
  BitArray prefix;
  tree_to_bits(root, prefix);
  prefix.save(output);
  save_tree_keys_in_prefix(root, output);
}
 
template <BinNodeLike Node>
inline Node *load_tree(std::istream &input)
{
  BitArray prefix;
  prefix.load(input);
  Node *root = bits_to_tree<Node>(prefix);
  try
    {
      load_tree_keys_in_prefix(root, input);
    }
  catch (...)
    {
      destroyRec(root);  // Cleanup partially loaded tree on exception
      throw;
    }
  return root;
}
 
template <BinNodeLike Node, class Get_Key>
inline void put_tree_keys_in_array(Node *root, std::ostream &out)
{
  if (root == Node::NullPtr)
    return;
 
  const std::string str = Get_Key()(root);
  out << "\"";
  for (const char ch : str)
    {
      switch (ch)
        {
        case '\n':
          out << "\\n";
          break;
        case '\t':
          out << "\\t";
          break;
        case '\\':
          out << "\\\\";
          break;
        case '"':
          out << "\\\"";
          break;
        default:
          out << ch;
          break;
        }
    }
  out << "\", ";
 
  put_tree_keys_in_array<Node, Get_Key>(LLINK(root), out);
  put_tree_keys_in_array<Node, Get_Key>(RLINK(root), out);
}
 
template <BinNodeLike Node, class Load_Key>
inline void load_tree_keys_from_array(Node *root, const char *keys[], int &idx)
{
  if (root == Node::NullPtr)
    return;
 
  if (Load_Key()(root, keys[idx]))
    ++idx;
 
  load_tree_keys_from_array<Node, Load_Key>(LLINK(root), keys, idx);
  load_tree_keys_from_array<Node, Load_Key>(RLINK(root), keys, idx);
}
 
template <BinNodeLike Node, class Get_Key>
inline void save_tree_in_array_of_chars(Node *root, const std::string &array_name,
                                        std::ostream &output)
{
  BitArray prefix;
  tree_to_bits(root, prefix);
  prefix.save_in_array_of_chars(array_name + "_cdp", output);
  output << "const char * " << array_name << "_k[] = { " << '\n';
  put_tree_keys_in_array<Node, Get_Key>(root, output);
  output << "nullptr };" << '\n';
}
 
template <BinNodeLike Node, class Load_Key>
inline Node *load_tree_from_array(const unsigned char bits[], const size_t &num_bits,
                                  const char *keys[])
{
  BitArray prefix;
  prefix.load_from_array_of_chars(bits, num_bits);
  Node *root = bits_to_tree<Node>(prefix);
  int i = 0;
  load_tree_keys_from_array<Node, Load_Key>(root, keys, i);
  return root;
}
 
template <BinNodeLike Node, class Compare>
inline bool check_bst_range(Node *p, const typename Node::key_type *min_key,
                                   const typename Node::key_type *max_key, const Compare &cmp)
{
  if (p == Node::NullPtr)
    return true;
 
  const auto &key = KEY(p);
  if (min_key != nullptr and not less_or_equal_than(*min_key, key, cmp))
    return false;
  if (max_key != nullptr and not less_or_equal_than(key, *max_key, cmp))
    return false;
 
  return check_bst_range<Node, Compare>(LLINK(p), min_key, &key, cmp) and
    check_bst_range<Node, Compare>(RLINK(p), &key, max_key, cmp);
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline bool check_bst(Node *p, const Compare &cmp = Compare())
{
  assert_valid_tree_root(p);
  return check_bst_range<Node, Compare>(p, nullptr, nullptr, cmp);
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *preorder_to_bst(DynArray<typename Node::key_type> &preorder, int l, int r,
                             const Compare &cmp = Compare())
{
  if (l > r)
    return Node::NullPtr;
 
  Node *root = new Node(preorder[l]);
 
  if (l == r)
    return root;
 
  int first_greater = l + 1;
  while ((first_greater <= r) and cmp(preorder[first_greater], preorder[l]))
    ++first_greater;
 
  LLINK(root) = preorder_to_bst<Node, Compare>(preorder, l + 1, first_greater - 1, cmp);
  RLINK(root) = preorder_to_bst<Node, Compare>(preorder, first_greater, r, cmp);
 
  return root;
}
 
enum ThreeWayCmp : int
{
  CmpLess = -1,   
  CmpEqual = 0,   
  CmpGreater = 1  
};
 
template <typename T, class Compare = Aleph::less<T>>
inline ThreeWayCmp three_way_compare(const T &a, const T &b, const Compare &cmp = Compare()) noexcept
{
  if (cmp(a, b))
    return CmpLess;
  if (cmp(b, a))
    return CmpGreater;
  return CmpEqual;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
[[nodiscard]] inline Node *searchInBinTree(Node *root, const typename Node::key_type &key,
                                           const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  Node *candidate = nullptr;  // Tracks potential match when going right
 
  while (root != Node::NullPtr)
    {
      __builtin_prefetch(LLINK(root));
      __builtin_prefetch(RLINK(root));
 
      if (cmp(key, KEY(root)))  // key < root: go left
        root = LLINK(root);
      else  // key >= root: go right, mark as candidate
        {
          candidate = root;
          root = RLINK(root);
        }
    }
 
  // Optimistic check: if candidate exists and key == candidate, return it
  if (candidate != nullptr and not cmp(KEY(candidate), key)) [[unlikely]]
    return candidate;
 
  return Node::NullPtr;
}
 
template <BinNodeLike Node>
[[nodiscard]] inline Node *find_min(Node *root) noexcept
{
  assert_valid_tree_root(root);
  assert(root != Node::NullPtr && "find_min called on empty tree");
  while (LLINK(root) != Node::NullPtr)
    root = LLINK(root);
 
  return root;
}
 
template <BinNodeLike Node>
[[nodiscard]] inline Node *find_max(Node *root) noexcept
{
  assert_valid_tree_root(root);
  assert(root != Node::NullPtr && "find_max called on empty tree");
  while (RLINK(root) != Node::NullPtr)
    root = RLINK(root);
 
  return root;
}
 
template <BinNodeLike Node>
inline Node *find_successor(Node *p, Node *&pp) noexcept
{
  assert(p != Node::NullPtr);
  assert(RLINK(p) != Node::NullPtr);
 
  pp = p;
  p = RLINK(p);
  while (LLINK(p) != Node::NullPtr)
    {
      pp = p;
      p = LLINK(p);
    }
 
  return p;
}
 
template <BinNodeLike Node>
inline Node *find_predecessor(Node *p, Node *&pp) noexcept
{
  assert(p != Node::NullPtr);
  assert(LLINK(p) != Node::NullPtr);
 
  pp = p;
  p = LLINK(p);
 
  while (RLINK(p) != Node::NullPtr)
    {
      pp = p;
      p = RLINK(p);
    }
 
  return p;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *search_parent(Node *root, const typename Node::key_type &key, Node *&parent,
                           const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  assert((LLINK(parent) == root) or (RLINK(parent) == root));
  assert(root != Node::NullPtr);
 
  while (true)
    {
      const auto c = three_way_compare(key, KEY(root), cmp);
      if (c == CmpLess) [[likely]]
        {
          if (LLINK(root) == Node::NullPtr)
            return root;
 
          parent = root;
          root = LLINK(root);
        }
      else if (c == CmpGreater) [[likely]]
        {
          if (RLINK(root) == Node::NullPtr)
            return root;
 
          parent = root;
          root = RLINK(root);
        }
      else [[unlikely]]
        return root;
    }
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *search_rank_parent(Node *root, const typename Node::key_type &key,
                                const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  assert(root != Node::NullPtr);
 
  while (true)
    if (const auto &root_key = KEY(root); cmp(key, root_key))
      {
        if (LLINK(root) == Node::NullPtr)
          return root;
 
        root = LLINK(root);
      }
    else if (cmp(root_key, key))
      {
        if (RLINK(root) == Node::NullPtr)
          return root;
 
        root = RLINK(root);
      }
    else
      return root;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *insert_in_bst(Node *&r, Node *p, const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(r);
  if (r == Node::NullPtr) [[unlikely]]
    return r = p;
 
  const auto &pk = KEY(p);
  const auto &rk = KEY(r);
 
  if (cmp(pk, rk))
    return insert_in_bst<Node, Compare>(LLINK(r), p, cmp);
  if (cmp(rk, pk))
    return insert_in_bst<Node, Compare>(RLINK(r), p, cmp);
 
  [[unlikely]] return Node::NullPtr;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *insert_dup_in_bst(Node *&root, Node *p, const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr) [[unlikely]]
    return root = p;
 
  const auto &pk = KEY(p);
  const auto &rk = KEY(root);
 
  if (cmp(pk, rk))
    return insert_dup_in_bst(LLINK(root), p, cmp);
 
  return insert_dup_in_bst(RLINK(root), p, cmp);
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *search_or_insert_in_bst(Node *&r, Node *p, const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(r);
  if (r == Node::NullPtr) [[unlikely]]
    return r = p;
 
  const auto &pk = KEY(p);
  const auto &rk = KEY(r);
 
  if (cmp(pk, rk))
    return search_or_insert_in_bst<Node, Compare>(LLINK(r), p, cmp);
  if (cmp(rk, pk))
    return search_or_insert_in_bst<Node, Compare>(RLINK(r), p, cmp);
 
  [[unlikely]] return r;
}
 
template <BinNodeLike Node, class Compare>
inline bool split_key_rec_helper(Node *root, const typename Node::key_type &key, Node *&ts,
                                        Node *&tg, Compare &cmp) noexcept
{
  if (root == Node::NullPtr)
    {  // key is not in the tree ==> split will succeed
      ts = tg = Node::NullPtr;
      return true;
    }
 
  if (cmp(key, KEY(root)))
    {
      if (split_key_rec_helper(LLINK(root), key, ts, LLINK(root), cmp))
        {
          tg = root;
          return true;
        }
      return false;
    }
 
  if (cmp(KEY(root), key))
    if (split_key_rec_helper(RLINK(root), key, RLINK(root), tg, cmp))
      {
        ts = root;
        return true;
      }
 
  return false;  // key exists in the tree
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline bool split_key_rec(Node *&root, const typename Node::key_type &key, Node *&ts, Node *&tg,
                          const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  const bool ret = split_key_rec_helper(root, key, ts, tg, cmp);
  if (ret)
    root = Node::NullPtr;
  return ret;
}
 
template <BinNodeLike Node, class Compare>
inline void split_key_dup_rec_helper(Node *root, const typename Node::key_type &key,
                                            Node *&ts, Node *&tg, Compare &cmp) noexcept
{
  if (root == Node::NullPtr)
    {
      ts = tg = Node::NullPtr;
      return;
    }
 
  if (cmp(KEY(root), key))
    {
      split_key_dup_rec_helper(RLINK(root), key, RLINK(root), tg, cmp);
      ts = root;
    }
  else
    {
      split_key_dup_rec_helper(LLINK(root), key, ts, LLINK(root), cmp);
      tg = root;
    }
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline void split_key_dup_rec(Node *&root, const typename Node::key_type &key, Node *&ts, Node *&tg,
                              const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  split_key_dup_rec_helper(root, key, ts, tg, cmp);
  root = Node::NullPtr;
}
 
template <BinNodeLike Node>
inline Node *join_exclusive(Node *&ts, Node *&tg) noexcept
{
  if (ts == Node::NullPtr)
    return tg;
 
  if (tg == Node::NullPtr)
    return ts;
 
  LLINK(tg) = join_exclusive(RLINK(ts), LLINK(tg));
 
  RLINK(ts) = tg;
  Node *ret_val = ts;
  ts = tg = Node::NullPtr;  // empty the trees
 
  return ret_val;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *remove_from_bst(Node *&root, const typename Node::key_type &key,
                             const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return Node::NullPtr;
 
  if (cmp(key, KEY(root)))
    return remove_from_bst(LLINK(root), key, cmp);
  if (cmp(KEY(root), key))
    return remove_from_bst(RLINK(root), key, cmp);
 
  Node *ret_val = root;  // save root that is going to be removed
  root = join_exclusive(LLINK(root), RLINK(root));
 
  ret_val->reset();
 
  return ret_val;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *insert_root(Node *&root, Node *p, const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  Node *l = Node::NullPtr, *r = Node::NullPtr;
 
  if (not split_key_rec(root, KEY(p), l, r, cmp))
    return Node::NullPtr;
 
  LLINK(p) = l;
  RLINK(p) = r;
  root = p;
 
  return root;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *insert_dup_root(Node *&root, Node *p, const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  split_key_dup_rec(root, KEY(p), LLINK(p), RLINK(p), cmp);
  return root = p;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *join_preorder(Node *t1, Node *t2, Node *&dup, const Compare &cmp = Compare()) noexcept
{
  if (t2 == Node::NullPtr)
    return t1;
 
  Node *l = LLINK(t2);
  Node *r = RLINK(t2);
 
  t2->reset();
 
  if (insert_in_bst(t1, t2, cmp) == Node::NullPtr)
    insert_in_bst(dup, t2, cmp);  // insertion has failed
 
  join_preorder(t1, l, dup, cmp);
  join_preorder(t1, r, dup, cmp);
 
  return t1;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node *join(Node *t1, Node *t2, Node *&dup, const Compare &cmp = Compare()) noexcept
{
  if (t1 == Node::NullPtr)
    return t2;
 
  if (t2 == Node::NullPtr)
    return t1;
 
  Node *l = LLINK(t1);
  Node *r = RLINK(t1);
 
  t1->reset();
 
  while (t1 != Node::NullPtr and insert_root(t2, t1, cmp) == Node::NullPtr)
    {
      Node *p = remove_from_bst(t1, KEY(t1), cmp);
 
      assert(p != Node::NullPtr);
 
      insert_in_bst(dup, p, cmp);
    }
 
  LLINK(t2) = join(l, LLINK(t2), dup, cmp);
  RLINK(t2) = join(r, RLINK(t2), dup, cmp);
 
  return t2;
}
 
template <BinNodeLike Node>
inline Node *rotate_to_right(Node *p) noexcept
{
  assert(p != Node::NullPtr);
 
  Node *q = LLINK(p);
  LLINK(p) = RLINK(q);
  RLINK(q) = p;
 
  return q;
}
 
template <BinNodeLike Node>
inline Node *rotate_to_right(Node *p, Node *pp) noexcept
{
  assert(p != Node::NullPtr);
  assert(pp != Node::NullPtr);
  assert(LLINK(pp) == p or RLINK(pp) == p);
 
  Node *q = LLINK(p);
  LLINK(p) = RLINK(q);
  RLINK(q) = p;
 
  if (LLINK(pp) == p)  // update the parent
    LLINK(pp) = q;
  else
    RLINK(pp) = q;
 
  return q;
}
 
template <BinNodeLike Node>
inline Node *rotate_to_left(Node *p) noexcept
{
  assert(p != Node::NullPtr);
 
  Node *q = RLINK(p);
  RLINK(p) = LLINK(q);
  LLINK(q) = p;
 
  return q;
}
 
template <BinNodeLike Node>
inline Node *rotate_to_left(Node *p, Node *pp) noexcept
{
  assert(p != Node::NullPtr);
  assert(pp != Node::NullPtr);
  assert(LLINK(pp) == p or RLINK(pp) == p);
 
  Node *q = RLINK(p);
  RLINK(p) = LLINK(q);
  LLINK(q) = p;
 
  // update the parent
  if (LLINK(pp) == p)
    LLINK(pp) = q;
  else
    RLINK(pp) = q;
 
  return q;
}
 
template <BinNodeLike Node, class Key, class Compare = Aleph::less<typename Node::key_type>>
inline void split_key(Node *&root, const Key &key, Node *&l, Node *&r,
                      const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  assert(l == Node::NullPtr and r == Node::NullPtr);
  if (root == Node::NullPtr)
    {
      l = r = Node::NullPtr;
      return;
    }
 
  Node **current_parent = nullptr;
  Node **pending_child = nullptr;
  bool current_is_right = true;
  if (cmp(key, KEY(root)))
    {
      r = root;
      pending_child = &l;
    }
  else
    {
      l = root;
      pending_child = &r;
      current_is_right = false;
    }
 
  Node *current = root;
  while (current != Node::NullPtr)
    {
      if (cmp(key, KEY(current)))
        { /* current must be in right side */
          if (not current_is_right)
            {
              current_is_right = not current_is_right;
              *pending_child = *current_parent; /* change of side */
              pending_child = current_parent;
            }
          current_parent = &LLINK(current);
        }
      else
        { /* current must be in left side */
          if (current_is_right)
            {
              current_is_right = not current_is_right;
              *pending_child = *current_parent; /* change of side */
              pending_child = current_parent;
            }
          current_parent = &RLINK(current);
        }
      current = *current_parent;
    }
  *pending_child = Node::NullPtr;
  root = Node::NullPtr;
}
 
template <BinNodeLike Node>
inline void swap_node_with_successor(Node *p,    // Node for swapping
                                     Node *&pp,  // parent of p
                                     Node *q,    // Successor inorder of p
                                     Node *&pq)  // parent of q
  noexcept
{
  assert(p != Node::NullPtr and q != Node::NullPtr and pp != Node::NullPtr and pq != Node::NullPtr);
  assert(LLINK(pp) == p or RLINK(pp) == p);
  assert(LLINK(pq) == q or RLINK(pq) == q);
  assert(LLINK(q) == Node::NullPtr);
 
  /* Set of pp to its new son q */
  if (LLINK(pp) == p)
    LLINK(pp) = q;
  else
    RLINK(pp) = q;
 
  LLINK(q) = LLINK(p);
  LLINK(p) = Node::NullPtr;
 
  /* Checks if successor is right child of p. In this case, p will
     become q's son. This situation happens when p's son does not have
     a left branch */
  if (RLINK(p) == q)
    {
      RLINK(p) = RLINK(q);
      RLINK(q) = p;
      pq = pp;
      pp = q;
      return;
    }
 
  /* In this case, successor is the leftmost node descending from
     right son of p */
  Node *qr = RLINK(q);
  RLINK(q) = RLINK(p);
  LLINK(pq) = p;
  RLINK(p) = qr;
 
  std::swap(pp, pq);
}
 
template <BinNodeLike Node>
inline void swap_node_with_predecessor(Node *p,    // Node for swapping
                                       Node *&pp,  // p's parent
                                       Node *q,    // Predecessor inorder of p
                                       Node *&pq)  // q's parent
  noexcept
{
  assert((p != Node::NullPtr) and (q != Node::NullPtr) and (pp != Node::NullPtr) and
         (pq != Node::NullPtr));
  assert((RLINK(pp) == p) or (LLINK(pp) == p));
  assert((RLINK(pq) == q) or (LLINK(pq) == q));
  assert(RLINK(q) == Node::NullPtr);
 
  /* Set of pp to its new son q */
  if (RLINK(pp) == p)
    RLINK(pp) = q;
  else
    LLINK(pp) = q;
 
  RLINK(q) = RLINK(p);
  RLINK(p) = Node::NullPtr;
 
  /* Checks if predecessor is left child of p. In this case, p will
     become q's son. This situation happens when p's son does not have
     a right branch */
  if (LLINK(p) == q)
    {
      LLINK(p) = LLINK(q);
      LLINK(q) = p;
      pq = pp;
      pp = q;
      return;
    }
 
  /* In this case, predecessor is the rightmost node descending from
     right son of p */
  Node *ql = LLINK(q);
  LLINK(q) = LLINK(p);
  RLINK(pq) = p;
  LLINK(p) = ql;
  std::swap(pp, pq);
}
 
template <BinNodeLike Node, class Key = typename Node::key_type,
          class Compare = Aleph::less<typename Node::key_type>>
inline Node *insert_root_rec(Node *root, Node *p, const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return p; /* insertion in an empty tree */
 
  if (cmp(KEY(p), KEY(root)))
    { /* insert in the left subtree */
      Node *left_branch = insert_root_rec(LLINK(root), p, cmp);
      if (left_branch == Node::NullPtr)
        return Node::NullPtr;
 
      LLINK(root) = left_branch;
      root = rotate_to_right(root);
    }
  else if (cmp(KEY(root), KEY(p)))
    { /* insert in the right subtree */
      Node *right_branch = insert_root_rec(RLINK(root), p, cmp);
      if (right_branch == Node::NullPtr)
        return Node::NullPtr;
 
      RLINK(root) = right_branch;
      root = rotate_to_left(root);
    }
  else
    return Node::NullPtr; /* duplicated key */
 
  return root;
}
 
template <BinNodeLike Node, class Key = typename Node::key_type,
          class Compare = Aleph::less<typename Node::key_type>>
inline Node *search_or_insert_root_rec(Node *root, Node *p, const Compare &cmp = Compare()) noexcept
{
  assert_valid_tree_root(root);
  if (root == Node::NullPtr)
    return p;  // insertion in empty tree
 
  if (cmp(KEY(p), KEY(root)))
    {  // insert in left subtree
      Node *left_branch = search_or_insert_root_rec(LLINK(root), p, cmp);
      if (left_branch == p)
        {
          LLINK(root) = left_branch;
          root = rotate_to_right(root);
          return p;
        }
 
      return left_branch;
    }
  if (cmp(KEY(root), KEY(p)))
    {  // insert in right subtree
      Node *right_branch = search_or_insert_root_rec(RLINK(root), p, cmp);
      if (right_branch == p)
        {
          RLINK(root) = right_branch;
          root = rotate_to_left(root);
          return p;
        }
 
      return right_branch;
    }
 
  return root;
}
 
template <class Node>
class BinNodePrefixIterator
{
  Node *root = nullptr;
  Node *curr = Node::NullPtr;
  ArrayStack<Node *> s;
 
public:
  void swap(BinNodePrefixIterator &it) noexcept
  {
    std::swap(root, it.root);
    std::swap(curr, it.curr);
    s.swap(it.s);
  }
 
  BinNodePrefixIterator() = default;
 
  BinNodePrefixIterator(Node *r) noexcept : root(r), curr(root), s(Node::MaxHeight)
  {
    // empty
  }
 
  BinNodePrefixIterator(const BinNodePrefixIterator &it) : root(it.root), curr(it.curr), s(it.s)
  {
    // empty
  }
 
  BinNodePrefixIterator(BinNodePrefixIterator &&it) noexcept
  {
    swap(it);
  }
 
  void reset_first() noexcept
  {
    curr = root;
    s.empty();
  }
 
private:
  // Helper function for finding last node
  static Node *last(Node *p) noexcept
  {
    if (RLINK(p) != Node::NullPtr)
      return last(RLINK(p));
 
    if (LLINK(p) != Node::NullPtr)
      return last(LLINK(p));
 
    return p;
  }
 
public:
  void reset_last() noexcept
  {
    s.empty();
    if (root == Node::NullPtr)
      {
        curr = Node::NullPtr;
        return;
      }
 
    curr = last(root);
  }
 
  void end() noexcept
  {
    curr = Node::NullPtr;
    s.empty();
  }
 
  BinNodePrefixIterator &operator = (const BinNodePrefixIterator &it)
  {
    if (this == &it)
      return *this;
 
    root = it.root;
    curr = it.curr;
    s = it.s;
    return *this;
  }
 
  BinNodePrefixIterator &operator = (BinNodePrefixIterator &&it) noexcept
  {
    swap(it);
    return *this;
  }
 
  [[nodiscard]] bool has_curr() const noexcept
  {
    return curr != Node::NullPtr;
  }
 
  Node *get_curr_ne() const noexcept
  {
    return curr;
  }
 
  Node *get_curr() const
  {
    ah_overflow_error_if(not has_curr()) << "Iterator overflow";
    return get_curr_ne();
  }
 
  void next_ne() noexcept
  {
    auto l = LLINK(curr), r = RLINK(curr);
    if (l != Node::NullPtr)
      {
        curr = l;
        if (r != Node::NullPtr)
          s.push(r);
        return;
      }
 
    if (r != Node::NullPtr)
      {
        curr = r;
        return;
      }
 
    if (s.is_empty())
      curr = Node::NullPtr;
    else
      curr = s.pop();
  }
 
  void next()
  {
    ah_overflow_error_if(not has_curr()) << "Iterator overflow";
    next_ne();
  }
};
 
template <BinNodeLike Node, class Op>
bool prefix_traverse(Node *root, Op op)
{
  for (BinNodePrefixIterator<Node> it(root); it.has_curr(); it.next_ne())
    if (not op(it.get_curr()))
      return false;
  return true;
}
 
template <BinNodeLike Node, class Op>
void prefix_for_each(Node *root, Op op)
{
  for (BinNodePrefixIterator<Node> it(root); it.has_curr(); it.next_ne())
    op(it.get_curr());
}
 
template <class Node>
class BinNodeInfixIterator
{
  mutable Node *root = Node::NullPtr;
  Node *curr = Node::NullPtr;
  mutable long pos = 0;
  ArrayStack<Node *> s;
 
  Node *advance_to_min(Node *r) noexcept
  {
    while (LLINK(r) != Node::NullPtr)
      {
        s.push(r);
        r = LLINK(r);
      }
    return r;
  }
 
  static Node *advance_to_max(Node *r) noexcept
  {
    while (RLINK(r) != Node::NullPtr)
      r = RLINK(r);
 
    return r;
  }
 
  void init() noexcept
  {
    if (root != Node::NullPtr)
      curr = advance_to_min(root);
    pos = 0;
  }
 
public:
  bool is_in_first() const noexcept
  {
    return curr != Node::NullPtr and LLINK(curr) == Node::NullPtr and s.is_empty();
  }
 
  bool is_last() const noexcept
  {
    return curr != Node::NullPtr and RLINK(curr) == Node::NullPtr and s.is_empty();
  }
 
  void swap(BinNodeInfixIterator &it) noexcept
  {
    std::swap(root, it.root);
    std::swap(curr, it.curr);
    std::swap(pos, it.pos);
    s.swap(it.s);
  }
 
  BinNodeInfixIterator() = default;
 
  BinNodeInfixIterator(Node *r) noexcept : root(r), s(Node::MaxHeight)
  {
    init();
  }
 
  BinNodeInfixIterator(const BinNodeInfixIterator &it)
    : root(it.root), curr(it.curr), pos(it.pos), s(it.s)
  {
    // empty
  }
 
  BinNodeInfixIterator(BinNodeInfixIterator &&it) noexcept
  {
    swap(it);
  }
 
  void reset_first() noexcept
  {
    s.empty();
    init();
  }
 
  void reset_last() noexcept
  {
    s.empty();
    if (root == Node::NullPtr)
      {
        curr = Node::NullPtr;
        pos = 0;
        return;
      }
 
    curr = advance_to_max(root);
    pos = -1;  // pending: computed lazily by get_pos()
  }
 
  void end() noexcept
  {
    s.empty();
    curr = Node::NullPtr;
    pos = 0;
  }
 
  BinNodeInfixIterator &operator = (const BinNodeInfixIterator &it)
  {
    if (this == &it)
      return *this;
 
    root = it.root;
    curr = it.curr;
    pos = it.pos;
    s = it.s;
    return *this;
  }
 
  BinNodeInfixIterator &operator = (BinNodeInfixIterator &&it) noexcept
  {
    swap(it);
    return *this;
  }
 
  bool has_curr() const noexcept
  {
    return curr != Node::NullPtr;
  }
 
  Node *get_curr_ne() const noexcept
  {
    return curr;
  }
 
  Node *get_curr() const
  {
    ah_overflow_error_if(not has_curr()) << "Iterator overflow";
    return curr;
  }
 
  size_t get_pos() const
  {
    if (pos < 0)
      pos = static_cast<long>(size(root)) - 1;
    return pos;
  }
 
  void next_ne() noexcept
  {
    if (pos < 0)  // resolve the position left pending by reset_last()
      pos = static_cast<long>(size(root)) - 1;
 
    ++pos;
    curr = RLINK(curr);
    if (curr != Node::NullPtr)
      {
        curr = advance_to_min(curr);
        return;
      }
 
    if (s.is_empty())
      curr = Node::NullPtr;
    else
      curr = s.pop();
  }
 
  void next()
  {
    ah_overflow_error_if(not has_curr()) << "Iterator overflow";
    next_ne();
  }
};
 
template <BinNodeLike Node, class Op>
bool infix_traverse(Node *root, Op op)
{
  for (BinNodeInfixIterator<Node> it(root); it.has_curr(); it.next_ne())
    if (not op(it.get_curr()))
      return false;
  return true;
}
 
template <BinNodeLike Node, class Op>
bool traverse(Node *root, Op op)
{
  return infix_traverse(root, op);
}
 
template <BinNodeLike Node, class Op>
void infix_for_each(Node *root, Op op)
{
  for (BinNodeInfixIterator<Node> it(root); it.has_curr(); it.next_ne())
    op(it.get_curr());
}
}  // namespace Aleph
 
#endif  // TPL_BINNODEUTILS_H