tpl_rand_tree.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_RAND_TREE_H
# define TPL_RAND_TREE_H
 
# include <ctime>
# include <climits>
# include <gsl/gsl_rng.h>
# include <ahUtils.H>
# include <ahFunction.H>
# include <tpl_randNode.H>
# include <tpl_binTreeOps.H>
# include <ah-errors.H>
# include <ah-concepts.H>
 
using namespace Aleph;
 
namespace Aleph
{
  template <template <typename> class NodeType, typename Key, class Compare>
    requires StrictWeakOrder<Compare, Key>
  class Gen_Rand_Tree
  {
  public:
    using Node = NodeType<Key>; 
 
  private:
    Node *tree_root;
    gsl_rng *r;
    Compare cmp;
 
    Node * random_insert(Node *root, Node *p) noexcept
    {
      if (root == Node::NullPtr)
        return p;
 
      // Prefetch children to reduce memory latency
      __builtin_prefetch(LLINK(root));
      __builtin_prefetch(RLINK(root));
 
      const long n = COUNT(root);
      if (const size_t rn = gsl_rng_uniform_int(r, n + 1); rn == n) [[unlikely]]
          return BinTreeXt_Operation<Node, Compare>(cmp).insert_root(root, p);
 
      Node *result;
      const Key & pk = KEY(p);
      const Key & rk = KEY(root);
      if (cmp(pk, rk)) // KEY(p) < KEY(root)
        {
          result = random_insert(LLINK(root), p);
          if (result != Node::NullPtr) // p was inserted
            {
              LLINK(root) = result;
              ++COUNT(root);
              return root;
            }
        }
      else if (cmp(rk, pk)) // KEY(p) > KEY(root)
        {
          result = random_insert(RLINK(root), p);
          if (result != Node::NullPtr) // p was inserted
            {
              RLINK(root) = result;
              ++COUNT(root);
              return root;
            }
        }
 
      return Node::NullPtr; // duplicated key ==> no insertion
    }
 
    Node * random_insert_dup(Node *root, Node *p) noexcept
    {
      if (root == Node::NullPtr)
        return p;
 
      // Prefetch children to reduce memory latency
      __builtin_prefetch(LLINK(root));
      __builtin_prefetch(RLINK(root));
 
      const long n = COUNT(root);
      if (const size_t rn = gsl_rng_uniform_int(r, n + 1); rn == n) [[unlikely]]
          return BinTreeXt_Operation<Node, Compare>(cmp).insert_dup_root(root, p);
 
      const Key & pk = KEY(p);
      const Key & rk = KEY(root);
      if (cmp(pk, rk)) // KEY(p) < KEY(root)
        LLINK(root) = random_insert_dup(LLINK(root), p);
      else
        RLINK(root) = random_insert_dup(RLINK(root), p);
 
      ++COUNT(root);
 
      return root;
    }
 
    Node * random_search_or_insert(Node *& root, Node *p) noexcept
    {
      if (root == Node::NullPtr)
        return root = p;
 
      // Prefetch children to reduce memory latency
      if (LLINK(root) != Node::NullPtr)
        __builtin_prefetch(LLINK(root));
      if (RLINK(root) != Node::NullPtr)
        __builtin_prefetch(RLINK(root));
 
      const long n = COUNT(root);
      if (const size_t rn = gsl_rng_uniform_int(r, n + 1); rn == n) [[unlikely]]
        {
          if (BinTreeXt_Operation<Node, Compare>(cmp).insert_root(root, p) != Node::NullPtr)
            return p;
 
          return searchInBinTree<Node, Compare>(root, KEY(p), cmp);
        }
 
      const Key & pk = KEY(p);
      const Key & rk = KEY(root);
      if (cmp(pk, rk))
        {
          Node *ret = random_search_or_insert(LLINK(root), p);
          if (ret == p)
            ++COUNT(root);
 
          return ret;
        }
      if (cmp(rk, pk))
        {
          Node *ret = random_search_or_insert(RLINK(root), p);
          if (ret == p)
            ++COUNT(root);
 
          return ret;
        }
 
      return root; // key == root: found existing
    }
 
  public:
    Gen_Rand_Tree(const Gen_Rand_Tree &) = delete;
 
    Gen_Rand_Tree &operator =(const Gen_Rand_Tree &) = delete;
 
  private:
    void init(const unsigned long seed)
    {
      r = gsl_rng_alloc(gsl_rng_mt19937);
 
      ah_bad_alloc_if(r == nullptr);
 
      gsl_rng_set(r, seed % gsl_rng_max(r));
    }
 
  public:
    Compare &key_comp() noexcept { return cmp; }
 
    const Compare &key_comp() const noexcept { return cmp; }
 
    Compare &get_compare() noexcept { return key_comp(); }
 
    const Compare &get_compare() const noexcept { return cmp; }
 
    gsl_rng * gsl_rng_object() noexcept { return r; }
 
    void set_seed(const unsigned long seed) noexcept
    {
      gsl_rng_set(r, seed % gsl_rng_max(r));
    }
 
    Gen_Rand_Tree(const unsigned int seed, const Compare & __cmp = Compare())
      : tree_root(Node::NullPtr), r(nullptr), cmp(__cmp)
    {
      init(seed);
    }
 
    Gen_Rand_Tree(const Compare & cmp = Compare()) noexcept
      : Gen_Rand_Tree(time(nullptr), cmp)
    { /* empty */
    }
 
    void swap(Gen_Rand_Tree & tree) noexcept
    {
      std::swap(tree_root, tree.tree_root);
      std::swap(r, tree.r);
      std::swap(cmp, tree.cmp);
    }
 
    Gen_Rand_Tree(Gen_Rand_Tree && other) noexcept
      : tree_root(other.tree_root), r(other.r), cmp(std::move(other.cmp))
    {
      other.tree_root = Node::NullPtr;
      other.r = nullptr;
    }
 
    Gen_Rand_Tree &operator =(Gen_Rand_Tree && other) noexcept
    {
      if (this != &other)
        {
          // Clean up current resources
          if (r != nullptr)
            gsl_rng_free(r);
          destroyRec(tree_root);
 
          // Transfer ownership
          tree_root = other.tree_root;
          r = other.r;
          cmp = std::move(other.cmp);
 
          // Reset other
          other.tree_root = Node::NullPtr;
          other.r = nullptr;
        }
      return *this;
    }
 
    virtual ~Gen_Rand_Tree() noexcept
    {
      if (r != nullptr)
        gsl_rng_free(r);
      // Note: nodes are NOT freed here. DynSetTree::empty() handles node deletion.
      // The underlying tree only manages the tree structure, not node memory.
    }
 
    Node * insert(Node *p) noexcept
    {
      assert(p != Node::NullPtr);
      assert((LLINK(p) == Node::NullPtr) and (RLINK(p) == Node::NullPtr));
      assert(COUNT(p) == 1);
 
      Node *result = random_insert(tree_root, p);
      if (result == Node::NullPtr)
        return nullptr;
 
      return tree_root = result;
    }
 
    Node * insert_dup(Node *p) noexcept
    {
      assert(p != Node::NullPtr);
      assert((LLINK(p) == Node::NullPtr) and (RLINK(p) == Node::NullPtr));
      assert(COUNT(p) == 1);
 
      return tree_root = random_insert_dup(tree_root, p);
    }
 
  private:
    Node * random_join_exclusive(Node *tl, Node *tr) noexcept
    {
      if (tl == Node::NullPtr)
        return tr;
 
      if (tr == Node::NullPtr)
        return tl;
 
      const size_t & m = COUNT(tl);
      const size_t & n = COUNT(tr);
      if (const size_t rn = 1 + gsl_rng_uniform_int(r, m + n); rn <= m)
        { // left subtree wins
          COUNT(tl) += COUNT(tr);
          RLINK(tl) = random_join_exclusive(RLINK(tl), tr);
          return tl;
        }
      COUNT(tr) += COUNT(tl);
      LLINK(tr) = random_join_exclusive(tl, LLINK(tr));
      return tr;
    }
 
    Node * random_remove(Node *& root, const Key & key) noexcept
    {
      if (root == Node::NullPtr)
        return Node::NullPtr;
 
      Node *ret_val;
      const Key & rk = KEY(root);
      if (cmp(key, rk))
        {
          ret_val = random_remove(LLINK(root), key);
          if (ret_val != Node::NullPtr)
            --COUNT(root);
 
          return ret_val;
        }
      if (cmp(rk, key))
        {
          ret_val = random_remove(RLINK(root), key);
          if (ret_val != Node::NullPtr)
            --COUNT(root);
 
          return ret_val;
        }
 
      // key was found
      ret_val = root;
      root = random_join_exclusive(LLINK(root), RLINK(root));
      ret_val->reset();
 
      return ret_val;
    }
 
  public:
    Node * remove(const Key & key) noexcept
    {
      Node *ret_val = random_remove(tree_root, key);
 
      return ret_val != Node::NullPtr ? ret_val : nullptr;
    }
 
    Node * search(const Key & key) const noexcept
    {
      Node *retVal = searchInBinTree<Node, Compare>(tree_root, key, cmp);
      return retVal == Node::NullPtr ? nullptr : retVal;
    }
 
    Node * search_or_insert(Node *p) noexcept
    {
      assert(p != Node::NullPtr);
      assert(COUNT(p) == 1);
 
      return random_search_or_insert(tree_root, p);
    }
 
    [[nodiscard]] bool verify() const
    {
      return check_rank_tree(tree_root);
    }
 
    Node *&getRoot() noexcept { return tree_root; }
 
    Node * select(const size_t i) const
    {
      return Aleph::select(tree_root, i);
    }
 
    [[nodiscard]] size_t size() const noexcept { return COUNT(tree_root); }
 
    [[nodiscard]] bool is_empty() const noexcept { return tree_root == Node::NullPtr; }
 
    std::pair<long, Node *> position(const Key & key) const noexcept
    {
      std::pair<long, Node *> ret_val;
      ret_val.first = BinTreeXt_Operation<Node, Compare>(cmp).
          inorder_position(tree_root, key, ret_val.second);
 
      return ret_val;
    }
 
    std::pair<long, Node *> find_position(const Key & key) const noexcept
    {
      std::pair<long, Node *> r(-2, nullptr);
 
      r.first = BinTreeXt_Operation<Node, Compare>(cmp).
          find_position(tree_root, key, r.second);
 
      return r;
    }
 
  private:
    Node * remove_pos(Node *& root, const size_t pos) noexcept
    {
      if (pos == COUNT(LLINK(root)))
        {
          Node *ret_val = root;
          root = random_join_exclusive(LLINK(ret_val), RLINK(ret_val));
          return ret_val;
        }
 
      --COUNT(root);
      if (pos < COUNT(LLINK(root)))
        return remove_pos(LLINK(root), pos);
      else
        return remove_pos(RLINK(root), pos - COUNT(LLINK(root)) - 1);
    }
 
  public:
    Node * remove_pos(const size_t i)
    {
      ah_out_of_range_error_if(i >= COUNT(tree_root)) << "infix position out of range";
 
      return remove_pos(tree_root, i);
    }
 
    bool split_key(const Key & key, Gen_Rand_Tree & t1, Gen_Rand_Tree & t2)
      noexcept
    {
      return split_key_rec_xt(tree_root, key, t1.getRoot(), t2.getRoot());
    }
 
    void split_key_dup(const Key & key, Gen_Rand_Tree & t1, Gen_Rand_Tree & t2)
      noexcept
    {
      split_key_dup_rec_xt(tree_root, key, t1.getRoot(), t2.getRoot());
    }
 
    void split_pos(size_t pos, Gen_Rand_Tree & t1, Gen_Rand_Tree & t2) noexcept
    {
      split_pos_rec(tree_root, pos, t1.getRoot(), t2.getRoot());
    }
 
  private:
    Node * random_join(Node *t1, Node *t2, Node *& dup)
    {
      if (t1 == Node::NullPtr)
        return t2;
 
      if (t2 == Node::NullPtr)
        return t1;
 
      Node *ret = Node::NullPtr;
      const size_t m = COUNT(t1);
      const size_t n = COUNT(t2);
      if (const size_t rn = 1 + gsl_rng_uniform_int(r, m + n); rn <= m)
        { // root of t1 wins
          Node *l = LLINK(t1), *r = RLINK(t1);
          t1->reset();
        t1_wins:
          ret = insert_root_xt(t2, t1, cmp);
          if (ret != Node::NullPtr)
            {
              LLINK(ret) = random_join(LLINK(ret), l, dup);
              RLINK(ret) = random_join(RLINK(ret), r, dup);
              COUNT(ret) = COUNT(LLINK(ret)) + 1 + COUNT(RLINK(ret));
            }
          else
            {
              dup = random_insert_dup(dup, random_remove(t2, KEY(t1)));
              goto t1_wins;
            }
        }
      else
        { // root of t2 wins
          Node *l = LLINK(t2), *r = RLINK(t2);
          t2->reset();
        t2_wins:
          ret = insert_root_xt(t1, t2, cmp);
          if (ret != Node::NullPtr)
            {
              LLINK(ret) = random_join(l, LLINK(ret), dup);
              RLINK(ret) = random_join(r, RLINK(ret), dup);
              COUNT(ret) = COUNT(LLINK(ret)) + 1 + COUNT(RLINK(ret));
            }
          else
            {
              dup = random_insert_dup(dup, random_remove(t1, KEY(t2)));
              goto t2_wins;
            }
        }
 
      return ret;
    }
 
    Node * random_join(Node *t1, Node *t2)
    {
      if (t1 == Node::NullPtr)
        return t2;
 
      if (t2 == Node::NullPtr)
        return t1;
 
      Node *ret = Node::NullPtr;
      const size_t & m = COUNT(t1);
      const size_t & n = COUNT(t2);
      const size_t total = m + n;
      if (const size_t rn = 1 + gsl_rng_uniform_int(r, total); rn <= m)
        { // root of t1 wins
          Node *l = LLINK(t1), *r = RLINK(t1);
          t1->reset();
          ret = insert_dup_root_xt(t2, t1, cmp);
          LLINK(ret) = random_join(LLINK(ret), l);
          RLINK(ret) = random_join(RLINK(ret), r);
        }
      else
        { // root of t2 wins
          Node *l = LLINK(t2), *r = RLINK(t2);
          t2->reset();
          ret = insert_dup_root_xt(t1, t2, cmp);
          LLINK(ret) = random_join(l, LLINK(ret));
          RLINK(ret) = random_join(r, RLINK(ret));
        }
 
      COUNT(ret) = total;
      return ret;
    }
 
  public:
    void join(Gen_Rand_Tree & t, Gen_Rand_Tree & dup) noexcept
    {
      tree_root = random_join(tree_root, t.tree_root, dup.tree_root);
      t.tree_root = Node::NullPtr;
    }
 
    void join_dup(Gen_Rand_Tree & t) noexcept
    {
      tree_root = random_join(tree_root, t.tree_root);
      t.tree_root = Node::NullPtr;
    }
 
    void join_exclusive(Gen_Rand_Tree & t) noexcept
    {
      tree_root = random_join_exclusive(tree_root, t.tree_root);
      t.tree_root = Node::NullPtr;
    }
 
    struct Iterator : public BinNodeInfixIterator<Node>
    {
      Iterator(Gen_Rand_Tree & t) : BinNodeInfixIterator<Node>(t.getRoot()) {}
    };
  };
 
  template <typename Key, class Compare = Aleph::less<Key>>
    requires StrictWeakOrder<Compare, Key>
  struct Rand_Tree : public Gen_Rand_Tree<RandNode, Key, Compare>
  {
    using Base = Gen_Rand_Tree<RandNode, Key, Compare>;
    using Base::Base;
  };
 
 
  template <typename Key, class Compare = Aleph::less<Key>>
    requires StrictWeakOrder<Compare, Key>
  struct Rand_Tree_Vtl : public Gen_Rand_Tree<RandNodeVtl, Key, Compare>
  {
    using Base = Gen_Rand_Tree<RandNodeVtl, Key, Compare>;
    using Base::Base;
  };
} // end namespace Aleph
 
# endif // TPL_RAND_TREE_H