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 <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>
 
namespace Aleph
{
  template <class Node>
  inline static
  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 <class Node>
  inline
  int inOrderRec(Node *root, void (*visitFct)(Node *, int, int))
  {
    int position = 0;
    inorder_rec_helper(root, 0, position, visitFct);
    return position;
  }
 
  template <class Node>
  inline static
  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 <class Node>
  inline
  int preOrderRec(Node *root, void (*visitFct)(Node *, int, int))
  {
    int position = 0;
    preorder_rec_helper(root, 0, position, visitFct);
    return position;
  }
 
  template <class Node>
  inline static
  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 <class Node>
  inline
  int postOrderRec(Node *root, void (*visitFct)(Node *, int, int))
  {
    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 <class 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 <class 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 <class Node, class Op>
  void for_each_postorder(Node *root, Op && op)
  {
    For_Each_Postorder<Node>().traverse(root, std::forward<Op>(op));
  }
 
 
  template <class 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 <class 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 <class 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 <class Node>
  DynList<Node *> prefix(Node *root)
  {
    DynList<Node *> ret_val;
    prefix(root, ret_val);
    return ret_val;
  }
 
  template <class Node>
  DynList<Node *> infix(Node *root)
  {
    DynList<Node *> ret_val;
    infix(root, ret_val);
    return ret_val;
  }
 
  template <class Node>
  DynList<Node *> suffix(Node *root)
  {
    DynList<Node *> ret_val;
    suffix(root, ret_val);
    return ret_val;
  }
 
 
  template <class Node>
  inline
  size_t compute_cardinality_rec(Node *root) noexcept
  {
    if (root == Node::NullPtr)
      return 0;
 
    return compute_cardinality_rec(LLINK(root)) + 1 +
           compute_cardinality_rec(RLINK(root));
  }
 
  template <class Node>
  inline
  size_t size(Node *root) noexcept
  {
    return compute_cardinality_rec(root);
  }
 
  template <class Node>
  inline size_t computeHeightRec(Node *root) noexcept
  {
    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 <class Node>
  inline
  void destroyRec(Node *& root) noexcept
  {
    if (root == Node::NullPtr)
      return;
 
    destroyRec(LLINK(root));
    destroyRec(RLINK(root));
    delete root;
    root = Node::NullPtr;
  }
 
  template <class Node>
  inline
  void callKeyDestructorsRec(Node *& root) noexcept
  {
    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 <class Node>
  [[nodiscard]] inline
  Node * copyRec(Node *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 <class 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 <class 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 <class 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 <class Node>
  inline
  void levelOrder(Node *root, void (*visitFct)(Node *, int, bool))
  {
    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 <class 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 <class 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 <class Node>
  inline static 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 <class 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 <class 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 <class 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 <class Node>
  inline static
  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 <class Node>
  inline
  size_t internal_path_length(Node *p) noexcept
  {
    return internal_path_length_helper(p, 0);
  }
 
  template <class 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 <class Node>
  inline
  BitArray tree_to_bits(Node *root)
  {
    BitArray ret_val;
    tree_to_bits(root, ret_val);
    return ret_val;
  }
 
  template <class 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 <class Node>
  static 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 <class Node>
  inline
  Node * bits_to_tree(const BitArray & array, int idx = 0)
  {
    return bits_to_tree_helper<Node>(array, idx);
  }
 
  template <class 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 <class 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 <class 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 <class 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 <class 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 <class 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 <class 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 <class 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 <class Node, class Compare>
  static 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 <class Node,
            class Compare = Aleph::less<typename Node::key_type>>
  inline
  bool check_bst(Node *p, const Compare & cmp = Compare())
  {
    return check_bst_range<Node, Compare>(p, nullptr, nullptr, cmp);
  }
 
 
  template <class 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 <class 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
  {
    Node *candidate = nullptr; // Tracks potential match when going right
 
    while (root != Node::NullPtr)
      {
        const bool go_left = cmp(key, KEY(root)); // key < root ?
 
        Node *next = go_left ? LLINK(root) : RLINK(root);
 
        // Prefetch only the branch that follows (best for caching)
        if (next != Node::NullPtr)
          __builtin_prefetch(next, 0, 3);
 
        if (not go_left)
          candidate = root;
        root = next;
      }
 
    // 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 <class Node>
  [[nodiscard]] inline
  Node * find_min(Node *root) noexcept
  {
    assert(root != Node::NullPtr && "find_min called on empty tree");
    while (LLINK(root) != Node::NullPtr)
      root = LLINK(root);
 
    return root;
  }
 
  template <class Node>
  [[nodiscard]] inline
  Node * find_max(Node *root) noexcept
  {
    assert(root != Node::NullPtr && "find_max called on empty tree");
    while (RLINK(root) != Node::NullPtr)
      root = RLINK(root);
 
    return root;
  }
 
  template <class 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 <class 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 <class 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((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 <class 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(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 <class Node,
            class Compare = Aleph::less<typename Node::key_type>>
  inline
  Node * insert_in_bst(Node *& r, Node *p, const Compare & cmp = Compare()) noexcept
  {
    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 <class Node,
            class Compare = Aleph::less<typename Node::key_type>>
  inline
  Node * insert_dup_in_bst(Node *& root, Node *p, const Compare & cmp = Compare())
    noexcept
  {
    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 <class 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
  {
    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 <class Node, class Compare>
  static 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 <class 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
  {
    const bool ret = split_key_rec_helper(root, key, ts, tg, cmp);
    if (ret)
      root = Node::NullPtr;
    return ret;
  }
 
 
  template <class Node, class Compare>
  static 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 <class 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
  {
    split_key_dup_rec_helper(root, key, ts, tg, cmp);
    root = Node::NullPtr;
  }
 
 
  template <class 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 <class 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
  {
    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 <class Node,
            class Compare = Aleph::less<typename Node::key_type>>
  inline
  Node * insert_root(Node *& root, Node *p, const Compare & cmp = Compare()) noexcept
  {
    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 <class Node,
            class Compare = Aleph::less<typename Node::key_type>>
  inline
  Node * insert_dup_root(Node *& root, Node *p, const Compare & cmp = Compare()) noexcept
  {
    split_key_dup_rec(root, KEY(p), LLINK(p), RLINK(p), cmp);
    return root = p;
  }
 
 
  template <class 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 <class 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 <class 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 <class 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 <class 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 <class 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 <class 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(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 <class 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 <class 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 <class 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
  {
    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 <class 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
  {
    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 <class 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 <class 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;
    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 = static_cast<long>(size(root)) - 1;
    }
 
    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 { return pos; }
 
    void next_ne() noexcept
    {
      ++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 <class 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 <class Node, class Op>
  bool traverse(Node *root, Op op)
  {
    return infix_traverse(root, op);
  }
 
  template <class 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());
  }
} // end Aleph
 
# endif // TPL_BINNODEUTILS_H