tpl_binNodeXt.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_BINNODEXT_H
# define TPL_BINNODEXT_H
 
# include <ah-concepts.H>
 
# include <tpl_binNode.H>
# include <tpl_binNodeUtils.H>
 
using namespace Aleph;
 
namespace Aleph {
 
class BinNodeXt_Data
{
  size_t count; // Cardinality of the tree
 
public:
 
  BinNodeXt_Data() noexcept : count(1) {}
  BinNodeXt_Data(SentinelCtor) noexcept : count(0) {}
 
  size_t & getCount() noexcept { return count; }
  size_t size() const noexcept { return count; }
 
  void reset() noexcept { count = 1; }
};
 
DECLARE_BINNODE_SENTINEL(BinNodeXt, 255, BinNodeXt_Data);
 
template <RankedBinNodeLike Node> inline auto & COUNT(Node * p) noexcept
{
  return p->getCount();
}
 
 
    template <RankedBinNodeLike Node> static inline
Node * __select_rec(Node * r, const size_t i) noexcept
{
  assert(r != Node::NullPtr);
  assert(COUNT(Node::NullPtr) == 0);
 
  if (i == COUNT(LLINK(r)))
    return r;
 
  if (i < COUNT(LLINK(r)))
    return __select_rec(LLINK(r), i);
 
  return __select_rec(RLINK(r), i - COUNT(LLINK(r)) - 1);
}
 
    template <RankedBinNodeLike Node> inline
Node * select_rec(Node * r, const size_t i)
{
  ah_out_of_range_error_if(i >= COUNT(r)) << "infix position out of range";
 
  return __select_rec(r, i);
}
 
    template <RankedBinNodeLike Node> inline
Node * select_ne(Node * r, const size_t pos) noexcept
{
  assert(COUNT(Node::NullPtr) == 0);
  for (size_t i = pos; i != COUNT(LLINK(r)); /* nothing */)
    {
      assert(i < COUNT(r) and
       COUNT(LLINK(r)) + COUNT(RLINK(r)) + 1 == COUNT(r));
 
      if (i < COUNT(LLINK(r)))
        r = LLINK(r);
      else
        {
          i -= COUNT(LLINK(r)) + 1;
          r = RLINK(r);
        }
    }
 
  return r;
}
 
    template <RankedBinNodeLike Node> inline
Node * select(Node * r, const size_t pos)
{
  ah_out_of_range_error_if(pos >= COUNT(r)) << "infix position out of range";
 
  return select_ne(r, pos);
}
 
    template <RankedBinNodeLike Node> inline
Node * select(Node * root, const size_t pos, Node *& parent)
{
  ah_out_of_range_error_if(pos >= COUNT(root)) << "infix position out of range";
 
  parent = Node::NullPtr;
  for (size_t i = pos; i != COUNT(LLINK(root)); /* nada */)
    {
      assert(i < COUNT(root) and
       COUNT(LLINK(root)) + COUNT(RLINK(root)) + 1 == COUNT(root));
 
      parent = root;
      if (i < COUNT(LLINK(root)))
        root = LLINK(root);
      else
        {
          i -= COUNT(LLINK(root)) + 1;
          root = RLINK(root);
        }
    }
 
  return root;
}
 
    template <RankedBinNodeLike Node, class Compare> inline
long inorder_position(Node * r,
                      const typename Node::key_type & key,
                      Node *& p, Compare & cmp) noexcept
{
  assert(COUNT(Node::NullPtr) == 0);
 
  if (r == Node::NullPtr)
    return -1;
 
  if (cmp(key, KEY(r)))
    return inorder_position(LLINK(r), key, p, cmp);
  if (cmp(KEY(r), key))
    {
      long ret = inorder_position(RLINK(r), key, p, cmp);
      if (ret != -1)
        return ret + COUNT(LLINK(r)) + 1;
      return ret;
    }
  p = r;
  return COUNT(LLINK(r));
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
      inline long inorder_position(Node * r,
                                   const typename Node::key_type & key,
                                   Node *& p, Compare && cmp = Compare())
  noexcept
{
  return inorder_position(r, key, p, cmp);
}
 
    template <BinNodeLike Node, class Compare> inline
long inorder_position(Node * r, const typename Node::key_type & key,
                      Compare & cmp) noexcept
{
  Node * p = nullptr;
  return inorder_position(r, key, p, cmp);
}
 
    template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline long inorder_position(Node * r, const typename Node::key_type & key,
           Compare && cmp = Compare()) noexcept
{
  return inorder_position(r, key, cmp);
}
 
    template <RankedBinNodeLike Node,
              class Compare = Aleph::less<typename Node::key_type>> inline
long find_position(Node * r, const typename Node::key_type & key,
                   Node *& p, Compare & cmp) noexcept
{
  assert(COUNT(Node::NullPtr) == 0);
 
  long offset = 0;
  Node * candidate = Node::NullPtr;
 
  while (r != Node::NullPtr)
      if (cmp(key, KEY(r)))
        {
          candidate = r;
          r = LLINK(r);
        }
      else if (cmp(KEY(r), key))
        {
          offset += static_cast<long>(COUNT(LLINK(r)) + 1);
          r = RLINK(r);
        }
      else
        {
          p = r;
          return offset + static_cast<long>(COUNT(LLINK(r)));
        }
 
  if (candidate != Node::NullPtr)
    {
      p = candidate;
      return offset + static_cast<long>(COUNT(LLINK(candidate))) - 1;
    }
 
  p = Node::NullPtr;
  return offset - 1;
}
 
template <BinNodeLike Node,
    class Compare = Aleph::less<typename Node::key_type>> inline
long find_position(Node * r, const typename Node::key_type & key,
                   Node *& p, Compare && cmp = Compare()) noexcept
{
  return find_position(r, key, p, cmp);
}
 
    template <RankedBinNodeLike Node, class Compare> inline
Node * insert_by_key_xt(Node *& r, Node * p, Compare & cmp) noexcept
{
  assert(COUNT(Node::NullPtr) == 0);
 
  if (r == Node::NullPtr)
    return r = p;
 
  Node * q = Node::NullPtr;
  if (cmp(KEY(p), KEY(r)))
    {
      q = insert_by_key_xt(LLINK(r), p, cmp);
      if (q != Node::NullPtr)
        ++COUNT(r);
    }
  else if (cmp(KEY(r), KEY(p)))
    {
      q = insert_by_key_xt(RLINK(r), p, cmp);
      if (q != Node::NullPtr)
        ++COUNT(r);
    }
  // else return Node::NullPtr; is not needed
 
  return q;
}
 
  template <BinNodeLike Node,
            class Compare = Aleph::less<typename Node::key_type>> inline
Node * insert_by_key_xt(Node *& r, Node * p, Compare && cmp = Compare())
    noexcept
{
  return insert_by_key_xt(r, p, cmp);
}
 
    template <RankedBinNodeLike Node, class Compare> inline
Node * insert_dup_by_key_xt(Node *& r, Node * p, Compare & cmp) noexcept
{
  assert(COUNT(Node::NullPtr) == 0);
 
  if (r == Node::NullPtr)
    return r = p;
 
  Node * q;
  if (cmp(KEY(p), KEY(r)))
    q = insert_dup_by_key_xt(LLINK(r), p, cmp);
  else
    q = insert_dup_by_key_xt(RLINK(r), p, cmp);
 
  ++COUNT(r);
 
  return q;
}
 
    template <BinNodeLike Node,
              class Compare = Aleph::less<typename Node::key_type>> inline
Node * insert_dup_by_key_xt(Node *& r, Node * p, Compare && cmp = Compare())
      noexcept
{
  return insert_dup_by_key_xt(r, p, cmp);
}
 
    template <RankedBinNodeLike Node, class Compare> inline
Node * search_or_insert_by_key_xt(Node *& r, Node * p, Compare & cmp) noexcept
{
  assert(COUNT(Node::NullPtr) == 0);
 
  if (r == Node::NullPtr)
    return r = p;
 
  Node * q;
  if (cmp(KEY(p), KEY(r)))
    {
      q = search_or_insert_by_key_xt(LLINK(r), p, cmp);
      if (q == p)
        ++COUNT(r);
    }
  else if (cmp(KEY(r), KEY(p)))
    {
      q = search_or_insert_by_key_xt(RLINK(r), p, cmp);
      if (q == p)
        ++COUNT(r);
    }
  else
    return r;
 
  return q;
}
 
template <BinNodeLike Node,
    class Compare = Aleph::less<typename Node::key_type>> inline
Node * search_or_insert_by_key_xt(Node *& r, Node * p,
                                  Compare && cmp = Compare()) noexcept
{
  return search_or_insert_by_key_xt(r, p, cmp);
}
 
 
    template <RankedBinNodeLike Node, class Compare> static inline
bool __split_key_rec_xt(Node * root, const typename Node::key_type & key,
                        Node *& l, Node *& r, Compare & cmp) noexcept
{
  if (root == Node::NullPtr)
    {
      l = r = Node::NullPtr;
      return true;
    }
 
  if (cmp(key, KEY(root)))
    {
      if (not __split_key_rec_xt(LLINK(root), key, l, LLINK(root), cmp))
        return false;
 
      r = root;
      COUNT(r) -= COUNT(l);
    }
  else if (cmp(KEY(root), key))
    {
      if (not __split_key_rec_xt(RLINK(root), key, RLINK(root), r, cmp))
        return false;
 
      l = root;
      COUNT(l) -= COUNT(r);
    }
  else
    return false;
 
  return true;
}
 
template <BinNodeLike Node, class Compare> inline
bool split_key_rec_xt(Node *& root, const typename Node::key_type & key,
                      Node *& l, Node *& r, Compare & cmp) noexcept
{
  const bool ret = __split_key_rec_xt(root, key, l, r, cmp);
  if (ret)
    root = Node::NullPtr;
  return ret;
}
 
template <BinNodeLike Node,
              class Compare = Aleph::less<typename Node::key_type>> inline
bool split_key_rec_xt(Node *& root, const typename Node::key_type & key,
                      Node *& l, Node *& r, Compare && cmp = Compare())
  noexcept
{
  return split_key_rec_xt(root, key, l, r, cmp);
}
 
 
    template <RankedBinNodeLike Node, class Compare> static inline
void __split_key_dup_rec_xt(Node * root, const typename Node::key_type & key,
                            Node *& l, Node *& r, Compare & cmp) noexcept
{
  if (root == Node::NullPtr)
    {
      l = r = Node::NullPtr;
      return;
    }
 
  if (cmp(key, KEY(root)))
    {
      __split_key_dup_rec_xt(LLINK(root), key, l, LLINK(root), cmp);
      r = root;
      COUNT(r) -= COUNT(l);
    }
  else
    {
      __split_key_dup_rec_xt(RLINK(root), key, RLINK(root), r, cmp);
      l = root;
      COUNT(l) -= COUNT(r);
    }
}
 
 
 template <BinNodeLike Node, class Compare> inline
void split_key_dup_rec_xt(Node *& root, const typename Node::key_type & key,
                          Node *& l, Node *& r, Compare & cmp) noexcept
{
  __split_key_dup_rec_xt<Node, Compare>(root, key, l, r, cmp);
  root = Node::NullPtr;
}
 
 template <BinNodeLike Node,
              class Compare = Aleph::less<typename Node::key_type>> inline
void split_key_dup_rec_xt(Node *& root, const typename Node::key_type & key,
                          Node *& l, Node *& r, Compare && cmp = Compare())
   noexcept
{
  return split_key_dup_rec_xt(root, key, l, r, cmp);
}
 
    template <RankedBinNodeLike Node, class Compare> inline
Node * insert_root_xt(Node *& root, Node * p, Compare & cmp) noexcept
{
  if (root == Node::NullPtr)
    {
      root = p;
      return p;
    }
 
  if (not split_key_rec_xt(root, KEY(p), LLINK(p), RLINK(p), cmp))
    return Node::NullPtr;
 
  COUNT(p) = COUNT(LLINK(p)) + COUNT(RLINK(p)) + 1;
  root = p;
 
  return p;
}
 
    template <BinNodeLike Node,
              class Compare = Aleph::less<typename Node::key_type>> inline
Node * insert_root_xt(Node *& root, Node * p, Compare && cmp = Compare()) 
      noexcept
{
  return insert_root_xt(root, p, cmp);
}
 
    template <RankedBinNodeLike Node, class Compare> inline
Node * insert_dup_root_xt(Node *& root, Node * p, Compare & cmp) noexcept
{
  if (root == Node::NullPtr)
    {
      COUNT(p) = 1;
      LLINK(p) = RLINK(p) = Node::NullPtr;
      return root = p;
    }
 
  split_key_dup_rec_xt(root, KEY(p), LLINK(p), RLINK(p), cmp);
  COUNT(p) = COUNT(LLINK(p)) + COUNT(RLINK(p)) + 1;
 
  return root = p;
}
 
template <BinNodeLike Node,
    class Compare = Aleph::less<typename Node::key_type>> inline
Node * insert_dup_root_xt(Node *& root, Node * p, Compare && cmp = Compare())
   noexcept
{
  return insert_dup_root_xt(root, p, cmp);
}
 
 
    template <RankedBinNodeLike Node> static inline
void __split_pos_rec(Node * r, size_t i, Node *& ts, Node *& tg) noexcept
{
  if (i == COUNT(LLINK(r)))
    {
      ts = LLINK(r);
      tg = r;
      LLINK(tg) = Node::NullPtr;
      COUNT(tg) -= COUNT(ts);
      return;
    }
 
  if (i < COUNT(LLINK(r)))
    {
      __split_pos_rec(LLINK(r), i, ts, LLINK(r));
      tg = r;
      COUNT(r) -= COUNT(ts);
    }
  else
    {
      __split_pos_rec(RLINK(r), i - (COUNT(LLINK(r)) + 1), RLINK(r), tg);
      ts = r;
      COUNT(r) -= COUNT(tg);
    }
}
 
 
template <RankedBinNodeLike Node> inline
void split_pos_rec(Node *& r, const size_t i, Node *& ts, Node *& tg)
{
  ah_out_of_range_error_if(i > COUNT(r)) << "infix position out of range";
 
  if (i == COUNT(r)) // Is it the last position?
    {
      ts = r;
      r = tg = Node::NullPtr;
      return;
    }
 
  __split_pos_rec<Node>(r, i, ts, tg);
 
  r = Node::NullPtr;
}
 
    template <RankedBinNodeLike Node>  inline
void insert_by_pos_xt(Node *& r, Node * p, size_t pos)
{
  assert(COUNT(Node::NullPtr) == 0);
 
  split_pos_rec(r, pos, LLINK(p), RLINK(p));
  COUNT(p) = COUNT(LLINK(p)) + 1 + COUNT(RLINK(p));
  r = p;
}
 
    template <RankedBinNodeLike Node> inline
Node * join_exclusive_xt(Node *& ts, Node *& tg) noexcept
{
  if (ts == Node::NullPtr)
    return tg;
 
  if (tg == Node::NullPtr)
    return ts;
 
  LLINK(tg) = join_exclusive_xt(RLINK(ts), LLINK(tg));
  RLINK(ts) = tg;
 
      // Update Counters
  COUNT(tg) = COUNT(LLINK(tg)) + 1 + COUNT(RLINK(tg));
  COUNT(ts) = COUNT(LLINK(ts)) + 1 + COUNT(RLINK(ts));
 
  Node * ret_val = ts;
  ts = tg = Node::NullPtr; // should be empty after joining
 
  return ret_val;
}
 
 
    template <RankedBinNodeLike Node,
              class Compare = Aleph::less<typename Node::key_type>> inline
Node * remove_by_key_xt(Node *& root, const typename Node::key_type & key,
      Compare & cmp) noexcept
{
  if (root == Node::NullPtr)
    return Node::NullPtr;
 
  Node * ret_val = Node::NullPtr;
  if (cmp(key, KEY(root)))
    {
      ret_val = remove_by_key_xt(LLINK(root), key, cmp);
      if (ret_val != Node::NullPtr)
        --COUNT(root);
 
      return ret_val;
    }
  if (cmp(KEY(root), key))
    {
      ret_val = remove_by_key_xt(RLINK(root), key, cmp);
      if (ret_val != Node::NullPtr)
        --COUNT(root);
 
      return ret_val;
    }
 
  ret_val = root;
  root = join_exclusive_xt(LLINK(root), RLINK(root));
 
  ret_val->reset();
 
  return ret_val;
}
 
template <BinNodeLike Node, class Compare = Aleph::less<typename Node::key_type>>
inline Node * remove_by_key_xt(Node *& root,
                               const typename Node::key_type & key,
                               Compare && cmp = Compare()) noexcept
{
  return remove_by_key_xt(root, key, cmp);
}
 
 
    template <RankedBinNodeLike Node> static inline
Node * __remove_by_pos_xt(Node *& root, size_t pos) noexcept
{
  if (COUNT(LLINK(root)) == pos) // found position?
    {
      Node * ret_val = root;
      root = join_exclusive_xt(LLINK(root), RLINK(root));
 
      ret_val->reset();
 
      return ret_val;
    }
 
  Node * ret_val;
  if (pos < COUNT(LLINK(root)))
    ret_val = __remove_by_pos_xt(LLINK(root), pos);
  else
    ret_val = __remove_by_pos_xt(RLINK(root), pos - (COUNT(LLINK(root)) + 1));
 
  if (ret_val != Node::NullPtr) // removal was done?
    --COUNT(root);
 
  return ret_val;
}
 
    template <RankedBinNodeLike Node> inline
Node * remove_by_pos_xt(Node *& root, size_t pos)
{
  ah_out_of_range_error_if(pos >= COUNT(root)) << "infix position out of range";
 
  return __remove_by_pos_xt(root, pos);
}
 
    template <RankedBinNodeLike Node> inline
bool check_rank_tree(Node * root) noexcept
{
  if (root == Node::NullPtr)
    return true;
 
  if (COUNT(LLINK(root)) + COUNT(RLINK(root)) + 1 != COUNT(root))
    return false;
 
  return check_rank_tree(LLINK(root)) and check_rank_tree(RLINK(root));
}
 
    template <RankedBinNodeLike Node> inline
Node * rotate_to_right_xt(Node* p) noexcept
{
  assert(p != Node::NullPtr);
  assert(COUNT(LLINK(p)) + 1 + COUNT(RLINK(p)) == COUNT(p));
 
  Node * q = LLINK(p);
  LLINK(p) = RLINK(q);
  RLINK(q) = p;
  COUNT(p) -= 1 + COUNT(LLINK(q));
  COUNT(q) += 1 + COUNT(RLINK(p));
  assert(COUNT(LLINK(q)) + 1 + COUNT(RLINK(q)) == COUNT(q));
  return q;
}
 
    template <RankedBinNodeLike Node> inline
Node * rotate_to_left_xt(Node* p) noexcept
{
  assert(p != Node::NullPtr);
  assert(COUNT(LLINK(p)) + 1 + COUNT(RLINK(p)) == COUNT(p));
 
  Node * q = RLINK(p);
  RLINK(p) = LLINK(q);
  LLINK(q) = p;
  COUNT(p) -= 1 + COUNT(RLINK(q));
  COUNT(q) += 1 + COUNT(LLINK(p));
  assert(COUNT(LLINK(q)) + 1 + COUNT(RLINK(q)) == COUNT(q));
  return q;
}
 
 
    template <RankedBinNodeLike Node, class Key, class Compare> inline
Node * search_or_insert_root_rec_xt(Node * root, Node * p, Compare & cmp)
      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_xt<Node, Key>(LLINK(root), p, cmp);
      if (left_branch == p) // p was inserted?
        {
          ++COUNT(root);
          LLINK(root) = left_branch;
          root        = rotate_to_right_xt(root);
          return p;
        }
 
        return left_branch;
    }
  if (cmp(KEY(root), KEY(p)))
    { // insert in right subtree
      Node * right_branch = search_or_insert_root_rec_xt<Node, Key>(RLINK(root), p, cmp);
      if (right_branch == p) // p was inserted?
        {
          ++COUNT(root);
          RLINK(root) = right_branch;
          root        = rotate_to_left_xt(root);
          return p;
        }
 
      return right_branch;
    }
 
  return root;
}
 
template <BinNodeLike Node, class Key,
              class Compare = Aleph::less<typename Node::key_type>> inline
Node * search_or_insert_root_rec_xt(Node * root, Node * p,
                                    Compare && cmp = Compare()) noexcept
{
  return search_or_insert_root_rec_xt<Node, Key>(root, p, cmp);
}
 
 
template <class TreeType, class Node, typename Key, class Compare>
class BinTreeXt_Iterator
{
protected:
 
  mutable TreeType * tree_ptr;
  mutable Node * curr;
  mutable int curr_pos;
 
  static constexpr int Pos_Not_Current = -1;
  static constexpr int Pos_Empty_Container = -2;
  static constexpr int Pos_Not_Updated = -3;
 
private:
 
  bool is_container_empty() const noexcept
  {
    return COUNT(tree_ptr->getRoot()) == 0;
  }
 
  bool pos_updated() const noexcept
  {
    return curr_pos != Pos_Not_Updated;
  }
 
  bool curr_updated() const noexcept
  {
    return curr != nullptr;
  }
 
  void update_pos() const noexcept
  {
    assert(curr != nullptr);
    curr_pos = BinTreeXt_Operation<Node, Compare>(tree_ptr->key_comp()).
      inorder_position(tree_ptr->getRoot(), KEY(curr), curr);
  }
 
  void update_curr() const noexcept
  {
    assert(curr_pos != Pos_Not_Updated);
 
    if (curr_pos == Pos_Empty_Container or curr_pos == Pos_Not_Current or
        curr_pos == static_cast<int>(COUNT(tree_ptr->getRoot())))
      return;
 
    curr = Aleph::select(tree_ptr->getRoot(), curr_pos);
  }
 
public:
 
  BinTreeXt_Iterator() noexcept
    : tree_ptr(nullptr), curr(nullptr), curr_pos(Pos_Not_Current)
  { /* empty */ }
 
  BinTreeXt_Iterator(const TreeType & __tree) noexcept
    : tree_ptr(&const_cast<TreeType&>(__tree)), curr(nullptr)
  {
    curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
  }
 
  BinTreeXt_Iterator(const TreeType & __tree, Node * __curr) noexcept
    : tree_ptr(&const_cast<TreeType&>(__tree)),
      curr(__curr), curr_pos(Pos_Not_Updated)
  { /* empty */ }
 
  BinTreeXt_Iterator(const TreeType & __tree, const size_t pos) noexcept
    : tree_ptr(&const_cast<TreeType&>(__tree)),
      curr(nullptr), curr_pos(pos)
  { /* empty */ }
 
  BinTreeXt_Iterator(const BinTreeXt_Iterator & itor) noexcept
    : tree_ptr(itor.tree_ptr), curr(itor.curr), curr_pos(itor.curr_pos)
  { /* empty */ }
 
  BinTreeXt_Iterator & operator = (const BinTreeXt_Iterator & itor) noexcept
  {
    if (this == &itor)
      return *this;
 
    tree_ptr = itor.tree_ptr;
    curr = itor.curr;
    curr_pos = itor.curr_pos;
 
    return *this;
  }
 
  void reset_first() noexcept
  {
    curr = nullptr;
    curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
  }
 
  void reset_last() noexcept
  {
    curr = nullptr;
    curr_pos = is_container_empty() ? Pos_Empty_Container :
      static_cast<int>(COUNT(tree_ptr->getRoot())) - 1;
  }
 
  void end() noexcept
  {
    put_itor_at_the_end(*this);
  }
 
  void reset_to_key(const Key & key) noexcept
  {
    std::pair<long, Node*> p = tree_ptr->find_position(key);
    curr_pos = p.first;
  }
 
  void reset_to_node(Node * node) noexcept
  {
    curr = node;
    curr_pos = Pos_Not_Updated;
  }
 
  void reset_to_pos(const size_t pos) noexcept
  {
    curr = nullptr;
    curr_pos = pos;
  }
 
  Node * get_curr_ne() const noexcept
  {
    if (not curr_updated())
      update_curr();
    return curr;
  }
 
  Node * get_curr() const noexcept
  {
    return get_curr_ne();
  }
 
  size_t get_current_position() const
  {
    if (not pos_updated())
      update_pos();
 
    ah_range_error_if(curr_pos < -1) << "Iterator has no current";
    ah_range_error_if(curr_pos > static_cast<int>(COUNT(tree_ptr->getRoot())))
      << "Iterator has no current";
 
    return curr_pos;
  }
 
  size_t get_pos() const { return get_current_position(); }
 
  bool has_curr() const noexcept
  {
    if (not pos_updated())
      update_pos();
 
    return curr_pos >= 0 and
      curr_pos < static_cast<int>(COUNT(tree_ptr->getRoot()));
  }
 
  void prev()
  {
    ah_underflow_error_if(not has_curr()) << "Iterator has no current";
    --curr_pos;
    curr = nullptr;
  }
 
  void next_ne() noexcept
  {
    ++curr_pos;
    curr = nullptr;
  }
 
  void next()
  {
    ah_overflow_error_if(not has_curr()) << "Iterator has no current";
    next_ne();
  }
 
  Node * del()
  {
    ah_underflow_error_if(not has_curr()) << "Iterator has no current";
 
    if (not curr_updated())
      update_curr();
 
    Node * ret_val = tree_ptr->remove(KEY(curr));
    curr = nullptr;
 
    return ret_val;
  }
 
  bool operator == (const BinTreeXt_Iterator & itor) const noexcept
  {
    if (is_container_empty() and itor.is_container_empty())
      return true;
 
    if (pos_updated() and itor.pos_updated())
      return curr_pos == itor.curr_pos;
 
    if (curr_updated() and itor.curr_updated())
      return curr == itor.curr;
 
    if (not pos_updated())
      {
        update_pos();
        return curr_pos == itor.curr_pos;
      }
 
    itor.update_pos();
    return curr_pos == itor.curr_pos;
  }
 
  bool operator != (const BinTreeXt_Iterator & itor) const
  {
    return not (*this == itor);
  }
}; // end class BinTreeXt_Iterator
 
 
} // end namespace Aleph
 
# endif // TPL_BINNODEXT_H