tpl_splay_treeRk.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_SPLAY_TREE_RK_H
# define TPL_SPLAY_TREE_RK_H
 
# include <tpl_binNodeXt.H>
# include <ah-errors.H>
 
using namespace Aleph;
 
 
template <template <class> class NodeType, typename Key, class Compare>
class GenTdSplayTreeRk
{
public:
  typedef NodeType<Key> Node;
 
private:
  Node *root;
  Compare cmp;
  static constexpr signed char CmpLess = -1;
  static constexpr signed char CmpEqual = 0;
  static constexpr signed char CmpGreater = 1;
 
  signed char splay_impl(const Key & key) noexcept
  {
    assert(root != Node::NullPtr); // splay requires non-empty tree
    Node header(sentinelCtor);
    Node * head_ptr = &header;
    Node * l = head_ptr;
    Node * r = head_ptr;
    Node * t = root;
 
    size_t l_size = 0;
    size_t r_size = 0;
    signed char cmp_result = CmpEqual;
 
    while (true)
      {
        if (const Key & tk = KEY(t); cmp(key, tk))  // key < tk: go left
          {
            cmp_result = CmpLess;
            if (LLINK(t) == Node::NullPtr) [[unlikely]]
              break;
 
            if (cmp(key, KEY(LLINK(t))))  // zig-zig case
              {
                t = rotate_to_right_xt(t);
                if (LLINK(t) == Node::NullPtr) [[unlikely]]
                  break;
              }
 
            LLINK(r) = t;
            r = t;
            t = LLINK(t);
            r_size += 1 + COUNT(RLINK(r));
          }
        else if (cmp(tk, key))  // tk < key: go right
          {
            cmp_result = CmpGreater;
            if (RLINK(t) == Node::NullPtr) [[unlikely]]
              break;
 
            if (cmp(KEY(RLINK(t)), key))  // zig-zig case
              {
                t = rotate_to_left_xt(t);
                if (RLINK(t) == Node::NullPtr) [[unlikely]]
                  break;
              }
 
            RLINK(l) = t;
            l = t;
            t = RLINK(t);
            l_size += 1 + COUNT(LLINK(l));
          }
        else [[unlikely]]  // key == tk: found
          {
            cmp_result = CmpEqual;
            break;
          }
      }
 
    l_size += COUNT(LLINK(t));
    r_size += COUNT(RLINK(t));
    COUNT(t) = l_size + r_size + 1;
 
    /* reassembling of subtrees in one with t as root */
    RLINK(l) = LLINK(t);
    LLINK(r) = RLINK(t);
 
    LLINK(t) = RLINK(head_ptr);
    RLINK(t) = LLINK(head_ptr);
 
    for (Node * y = LLINK(t); y != Node::NullPtr; y = RLINK(y))
      {
        COUNT(y) = l_size;
        l_size -= 1 + COUNT(LLINK(y));
      }
 
    for (Node * y = RLINK(t); y != Node::NullPtr; y = LLINK(y))
      {
        COUNT(y) = r_size;
        r_size -= 1 + COUNT(RLINK(y));
      }
 
    root = t;
 
    return cmp_result;
  }
 
public:
  typedef Key key_type;
 
  Compare &key_comp() { return cmp; }
 
  Compare &get_compare() { return key_comp(); }
 
  void splay(const Key & key) noexcept
  {
    (void) splay_impl(key);
  }
 
  GenTdSplayTreeRk(Compare __cmp = Compare())
    : root(Node::NullPtr), cmp(__cmp)
  {
    // Empty
  }
 
  void swap(GenTdSplayTreeRk & tree)
  {
    std::swap(root, tree.root);
    std::swap(cmp, tree.cmp);
  }
 
  virtual ~GenTdSplayTreeRk()
  { /* empty */
  }
 
private:
  Node * __insert(Node *p)
  {
    COUNT(p) = COUNT(root) + 1;
    const Key & pk = KEY(p);
    const Key & rk = KEY(root);
    if (cmp(pk, rk))
      {
        COUNT(root) -= COUNT(LLINK(root));
        LLINK(p) = LLINK(root);
        RLINK(p) = root;
        LLINK(root) = Node::NullPtr;
      }
    else
      {
        COUNT(root) -= COUNT(RLINK(root));
        RLINK(p) = RLINK(root);
        LLINK(p) = root;
        RLINK(root) = Node::NullPtr;
      }
 
    return root = p; // inserted node become root
  }
 
public:
  Node * insert(Node *p)
  {
    assert(p != Node::NullPtr);
    assert(COUNT(p) == 1);
    assert(LLINK(p) == Node::NullPtr and RLINK(p) == Node::NullPtr);
 
    /* test insertion in empty tree */
    if (root == Node::NullPtr)
      return root = p;
 
    const Key & key = KEY(p);
 
    const signed char cmp_result = splay_impl(key);
    if (cmp_result == CmpEqual)
      return nullptr; // item is already in tree
 
    return __insert(p);
  }
 
  Node * insert_dup(Node *p)
  {
    assert(p != Node::NullPtr);
    assert(LLINK(p) == Node::NullPtr and RLINK(p) == Node::NullPtr);
 
    /* test insertion in empty tree */
    if (root == Node::NullPtr)
      return root = p;
 
    splay_impl(KEY(p));
 
    return __insert(p);
  }
 
  Node * search(const Key & key)
  {
    if (root == Node::NullPtr)
      return nullptr;
 
    const signed char cmp_result = splay_impl(key);
 
    return cmp_result == CmpEqual ? root : nullptr;
  }
 
  Node * search_or_insert(Node *p)
  {
    if (root == Node::NullPtr)
      return root = p;
 
    const Key & key = KEY(p);
    const signed char cmp_result = splay_impl(key);
    if (cmp_result == CmpEqual)
      return root;
 
    return __insert(p);
  }
 
private:
  Node * splay_max(Node * r) noexcept
  {
    if (r == Node::NullPtr || RLINK(r) == Node::NullPtr)
      return r;
 
    Node header(sentinelCtor);
    Node * head_ptr = &header;
    Node * l = head_ptr;
    Node * t = r;
 
    size_t l_size = 0;
 
    // Always go right to find maximum
    while (RLINK(t) != Node::NullPtr)
      {
        // Zig-zig: if grandchild exists on the right, rotate twice
        if (RLINK(RLINK(t)) != Node::NullPtr)
          {
            t = rotate_to_left_xt(t);
            if (RLINK(t) == Node::NullPtr)
              break;
          }
 
        // Link left: attach t to l's right
        RLINK(l) = t;
        l = t;
        t = RLINK(t);
        l_size += 1 + COUNT(LLINK(l));
      }
 
    // Reassemble
    l_size += COUNT(LLINK(t));
    COUNT(t) = l_size + 1;
 
    RLINK(l) = LLINK(t);
    LLINK(t) = RLINK(head_ptr);
 
    // Recompute counts along the left spine
    for (Node * y = LLINK(t); y != Node::NullPtr; y = RLINK(y))
      {
        COUNT(y) = l_size;
        l_size -= 1 + COUNT(LLINK(y));
      }
 
    return t;
  }
 
public:
  Node * remove(const Key & key)
  {
    if (root == Node::NullPtr)
      return nullptr;
 
    const signed char cmp_result = splay_impl(key);
    if (cmp_result != CmpEqual)
      return nullptr; /* key not found */
 
    Node *ret_val = root; /* store node to delete */
 
    if (LLINK(root) == Node::NullPtr)
      root = RLINK(root);
    else if (RLINK(root) == Node::NullPtr)
      root = LLINK(root);
    else
      {
        Node *right_subtree = RLINK(root);
 
        // Splay the maximum of left subtree to become root.
        // We use splay_max() instead of splay(key) because splay(key) can
        // bring a duplicate that is not the actual maximum, corrupting counts.
        // splay_max() uses proper zig-zig rotations to maintain O(log n) amortized.
        root = splay_max(LLINK(root));
 
        // The new root has no right child (it was the maximum)
        // Connect the right subtree
        RLINK(root) = right_subtree;
        COUNT(root) = COUNT(LLINK(root)) + 1 + COUNT(right_subtree);
      }
 
    ret_val->reset();
 
    return ret_val;
  }
 
  Node *&getRoot()
  {
    return root;
  }
 
  bool verify() const { return check_rank_tree(root) and check_bst(root, cmp); }
 
  size_t size() const
  {
    return COUNT(root);
  }
 
  bool is_empty() const
  {
    return root == Node::NullPtr;
  }
 
  std::pair<long, Node *> position(const Key & key)
  {
    if (root == Node::NullPtr)
      return {-1, nullptr};
 
    const signed char cmp_result = splay_impl(key);
    if (cmp_result == CmpEqual)
      return {static_cast<long>(COUNT(LLINK(root))), root};
 
    return {-1, nullptr};
  }
 
  std::pair<long, Node *> find_position(const Key & key)
  {
    if (root == Node::NullPtr)
      return {-1, nullptr};
 
    const signed char cmp_result = splay_impl(key);
    if (cmp_result == CmpEqual)
      return {static_cast<long>(COUNT(LLINK(root))), root};
 
    // key not found - determine position it would have
    if (cmp_result == CmpLess)
      return {static_cast<long>(COUNT(LLINK(root))) - 1, root}; // less than root
    return {static_cast<long>(COUNT(LLINK(root))) + 1, root};
    // greater than root
  }
 
  Node * select(const size_t & i)
  {
    return Aleph::select(root, i);
  }
 
  class Iterator
  {
    GenTdSplayTreeRk *tree_ptr = nullptr;
    Node *curr = Node::NullPtr;
    size_t pos = 0;
 
  public:
    Iterator() = default;
 
    Iterator(GenTdSplayTreeRk & tree) noexcept
      : tree_ptr(&tree), curr(Node::NullPtr), pos(0)
    {
      if (tree_ptr->root != Node::NullPtr)
        curr = find_min(tree_ptr->root);
    }
 
    bool has_curr() const noexcept { return curr != Node::NullPtr; }
 
    Node * get_curr() const
    {
      ah_overflow_error_if(curr == Node::NullPtr)
          << "Iterator is at end";
      return curr;
    }
 
    Node * get_curr_ne() const noexcept { return curr; }
 
    void next()
    {
      ah_overflow_error_if(curr == Node::NullPtr)
          << "Iterator is at end";
      curr = inorder_successor(tree_ptr->root, KEY(curr));
      ++pos;
    }
 
    void next_ne() noexcept
    {
      curr = inorder_successor(tree_ptr->root, KEY(curr));
      ++pos;
    }
 
    size_t get_pos() const noexcept { return pos; }
 
    void reset_first() noexcept
    {
      pos = 0;
      if (tree_ptr != nullptr && tree_ptr->root != Node::NullPtr)
        curr = find_min(tree_ptr->root);
      else
        curr = Node::NullPtr;
    }
 
  private:
    static Node * find_min(Node *r) noexcept
    {
      while (LLINK(r) != Node::NullPtr)
        r = LLINK(r);
      return r;
    }
 
    static Node * inorder_successor(Node *root, const Key & key) noexcept
    {
      Node *successor = Node::NullPtr;
      Node *curr = root;
 
      while (curr != Node::NullPtr)
        {
          if (key < KEY(curr))
            {
              successor = curr;
              curr = LLINK(curr);
            }
          else
            curr = RLINK(curr);
        }
 
      return successor;
    }
  };
};
 
 
template <typename Key, class Compare = Aleph::less<Key>>
struct Splay_Tree_Rk : public GenTdSplayTreeRk<BinNodeXt, Key, Compare>
{
  using Base = GenTdSplayTreeRk<BinNodeXt, Key, Compare>;
  using Base::Base;
};
 
 
template <typename Key, class Compare = Aleph::less<Key>>
struct Splay_Tree_Rk_Vtl : public GenTdSplayTreeRk<BinNodeXtVtl, Key, Compare>
{
  using Base = GenTdSplayTreeRk<BinNodeXtVtl, Key, Compare>;
  using Base::Base;
};
 
 
#endif /* TPL_SPLAY_TREE_RK_H */