tpl_skipList.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_SKIPLIST_H
# define TPL_SKIPLIST_H
 
# include <climits>
# include <ctime>
# include <gsl/gsl_rng.h>
# include <aleph.H>
# include <ah-errors.H>
 
namespace Aleph
{
  template <class Key, class Type>
  class SkipList
  {
  public:
    static const int maxLevel = 32;
 
    static const double defaultProbability;
 
    class Node
    {
    protected:
      int level;
 
      static Node nodeSentinel;
 
      /*
         Public methods work in function of nullptr pointer in order to indicate
         unsuccessful conditions. We put NullPtr as private in order to avoid
         that to accidentally put NullPtr instead of nullptr
      */
      static Node *NullPtr;
 
      private:
        Key key;
        Type data = Type();
 
        Node ** forward_ptr() noexcept
        {
          return reinterpret_cast<Node **>(reinterpret_cast<char *>(this) + sizeof(*this));
        }
 
        Node * const * forward_ptr() const noexcept
        {
          return reinterpret_cast<Node * const *>(
              reinterpret_cast<const char *>(this) + sizeof(*this));
        }
 
        void fillForwardnullptr()
        {
          for (int i = 0; i < level; i++)
            forward_ptr()[i] = const_cast<Node *>(&nodeSentinel);
        }
 
    public:
      friend class SkipList<Key, Type>;
 
      Node(const Key & _key, const Type & _data, int n)
        : level(n),
          key(_key),
          data(_data)
      {
        /* EMPTY */
      }
 
      Node(const Key & _key, int n)
        : level(n),
          key(_key)
      {
        /* EMPTY */
      }
 
      Node(const int n)
        : level(n)
      {
        /* EMPTY */
      }
 
      Node()
        : level(0),
          key(computeMaxKey())
      {
        /* EMPTY */
      }
 
      ~Node() = default;
 
        [[nodiscard]] Node * get_next() const noexcept
        {
          auto *next = forward_ptr()[0];
          return (next == NullPtr) ? nullptr : next;
        }
 
        Node *&getForward(int i)
        {
          assert(i < level);
          return forward_ptr()[i];
        }
 
        Node ** getForward()
        {
          return forward_ptr();
        }
 
      [[nodiscard]] const Key &get_key() const noexcept { return key; }
 
      Key &get_key() noexcept { return key; }
 
      [[nodiscard]] const Type &get_data() const noexcept { return data; }
 
      Type &get_data() noexcept { return data; }
 
      [[nodiscard]] int getLevel() const noexcept { return level; }
 
      static Key computeMaxKey() noexcept;
 
      protected:
        Node *forward[0];
      };
 
  private:
    /*
      Headenode : it's used for header node,
      it's an static array with maxLevel elements
    */
    class HeaderNode : public SkipList<Key, Type>::Node
    {
    private:
      typename SkipList<Key, Type>::Node *forward[maxLevel];
 
      friend class SkipList<Key, Type>;
 
    public:
      HeaderNode()
      {
        this->level = maxLevel;
 
        for (int i = 0; i < maxLevel; i++)
          HeaderNode::forward[i] = Node::NullPtr;
      }
 
      Node *&getForward(int i)
      {
        assert(i < this->getLevel());
        assert(this->getLevel() <= maxLevel);
 
        return HeaderNode::forward[i];
      }
    };
 
    /*
      Node*& getForward(Node* p, int i)
      {
      if ( p == headerPtr )
      return  ((HeaderNode*) p)->HeaderNode::forward[ i ];
      else
      return p->Node::forward[ i ];
      }
    */
 
    HeaderNode header; // SkipList's header
    HeaderNode *headerPtr; // Pointer to header
    gsl_rng *r;  // GSL random number generator
    double probability; // probability for randomLevel
    int level; // Current Maximum level of list linked
 
 
    void init(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:
    void set_seed(unsigned long seed) noexcept { gsl_rng_set(r, seed); }
 
    gsl_rng * gsl_rng_object() noexcept { return r; }
 
    SkipList(unsigned long seed, double p = defaultProbability)
      : headerPtr(&header),
        r(nullptr),
        probability(p),
        level(0)
    {
      assert(probability >= 0 and probability <= 1);
      init(seed);
    }
 
    explicit SkipList(double p = defaultProbability)
      : SkipList(time(nullptr), p)
    {
      // Empty
    }
 
    ~SkipList()
    {
      if (r != nullptr)
        gsl_rng_free(r);
    }
 
    // Disable copy (owns GSL resource)
    SkipList(const SkipList &) = delete;
    SkipList & operator=(const SkipList &) = delete;
 
    // Move constructor
    SkipList(SkipList && other) noexcept
      : header(std::move(other.header)),
        headerPtr(&header),
        r(other.r),
        probability(other.probability),
        level(other.level)
    {
      other.r = nullptr;
      other.level = 0;
    }
 
    // Move assignment
    SkipList & operator=(SkipList && other) noexcept
    {
      if (this != &other)
        {
          if (r != nullptr)
            gsl_rng_free(r);
          header = std::move(other.header);
          headerPtr = &header;
          r = other.r;
          probability = other.probability;
          level = other.level;
          other.r = nullptr;
          other.level = 0;
        }
      return *this;
    }
 
    [[nodiscard]] Node * search(const Key & searchKey) noexcept
    {
      Node *x = headerPtr;
 
      for (int i = level - 1; i >= 0; i--)
        while (x->getForward(i)->get_key() < searchKey)
          x = x->getForward(i);
 
      x = x->getForward(0);
 
      // Return nullptr if not found (either sentinel or different key)
      if (x == Node::NullPtr || x->get_key() != searchKey)
        return nullptr;
 
      return x;
    }
 
    Node * insert(Node *p) noexcept
    {
      int i;
      Node *update[maxLevel];
      Node *x = headerPtr;
 
      assert(p->getLevel() > 0 and p->getLevel() <= maxLevel);
 
      p->fillForwardnullptr();
 
      for (i = level - 1; i >= 0; i--)
        {
          while (x->getForward(i)->get_key() < p->get_key())
            x = x->getForward(i);
 
          update[i] = x;
        }
 
      x = x->getForward(0); // go to next node
 
      if (p->getLevel() > level)
        {
          for (i = level; i < p->getLevel(); i++)
            update[i] = headerPtr;
          level = p->getLevel();
        }
 
 
      for (i = 0; i < p->getLevel(); i++)
        {
          p->getForward(i) = update[i]->getForward(i);
          update[i]->getForward(i) = p;
        }
 
      assert(checkSkipList() == true);
      return p;
    }
 
    [[nodiscard]] Node * get_first() noexcept
    {
      return headerPtr->HeaderNode::forward[0];
    }
 
    [[nodiscard]] Node * remove(const Key & searchKey) noexcept
    {
      Node *update[maxLevel];
      Node *x = headerPtr;
      int i;
 
      for (i = level - 1; i >= 0; i--)
        {
          while (x->getForward(i)->get_key() < searchKey)
            x = x->getForward(i);
          update[i] = x;
        }
 
      x = x->getForward(0);
 
      if (x->get_key() == searchKey)
        {
          for (i = 0; i < level; i++)
            {
              if (update[i]->getForward(i) != x)
                break;
              update[i]->getForward(i) = x->getForward(i);
            }
 
          while (level > 0 and headerPtr->getForward(level) == nullptr)
            level--;
        }
      else
        return nullptr;
 
      assert(checkSkipList() == true);
 
      return x;
    }
 
    [[nodiscard]] int generateRandomLevel() noexcept
    {
      int l = 1;
      assert(probability > 0 and probability < 1);
      while (gsl_rng_uniform(r) < probability and l < maxLevel)
        ++l;
      return l;
    }
 
    [[nodiscard]] bool checkSkipList() const noexcept
    {
      Node *node = header.get_next();
      while (node != nullptr)
        {
          if (node->get_next() == nullptr)
            break;
 
          if (node->get_key() > node->get_next()->get_key())
            return false;
          node = node->get_next();
        }
      return true;
    }
 
    [[nodiscard]] Node * new_node() noexcept { return nullptr; }
 
    class Iterator
    {
      const SkipList *list_ptr = nullptr;
      Node *curr = nullptr;
 
      public:
        using Set_Type = SkipList;
 
        Iterator() noexcept = default;
 
        Iterator(const Iterator &) noexcept = default;
 
        Iterator(const SkipList & list) noexcept
          : list_ptr(&list), curr(list.headerPtr->HeaderNode::forward[0])
      {
        // Skip sentinel if we landed on it
        if (curr == Node::NullPtr)
          curr = nullptr;
      }
 
      [[nodiscard]] bool has_curr() const noexcept { return curr != nullptr; }
 
      [[nodiscard]] bool is_last() const noexcept
      {
        if (curr == nullptr)
          return false;
        Node *next = curr->get_next();
        return next == nullptr;
      }
 
      [[nodiscard]] Node * get_curr() const
      {
        ah_overflow_error_if(curr == nullptr) << "SkipList::Iterator::get_curr(): no current";
 
        return curr;
      }
 
      [[nodiscard]] Node * get_curr_ne() const noexcept { return curr; }
 
      [[nodiscard]] const Key &get_key() const { return get_curr()->get_key(); }
 
      [[nodiscard]] const Type &get_data() const { return get_curr()->get_data(); }
 
      void next()
      {
        ah_overflow_error_if(curr == nullptr) << "SkipList::Iterator::next(): no current";
        next_ne();
      }
 
      void next_ne() noexcept
      {
        if (curr != nullptr)
          {
            curr = curr->get_next();
            // get_next() returns nullptr for sentinel, so we're done
          }
      }
 
      void reset_first() noexcept
      {
        if (list_ptr != nullptr)
          {
            curr = list_ptr->headerPtr->HeaderNode::forward[0];
            if (curr == Node::NullPtr)
              curr = nullptr;
          }
      }
 
      void reset() noexcept { reset_first(); }
 
      Iterator &operator=(const Iterator & it) noexcept
      {
        list_ptr = it.list_ptr;
        curr = it.curr;
        return *this;
      }
 
      [[nodiscard]] bool operator==(const Iterator & it) const noexcept
      {
        return curr == it.curr;
      }
 
      [[nodiscard]] bool operator!=(const Iterator & it) const noexcept
      {
        return curr != it.curr;
      }
 
      Iterator &operator++() noexcept
      {
        next_ne();
        return *this;
      }
 
      Iterator operator++(int) noexcept
      {
        Iterator ret = *this;
        next_ne();
        return ret;
      }
 
      [[nodiscard]] Node * operator*() const { return get_curr(); }
 
      [[nodiscard]] Node * operator->() const { return get_curr(); }
    };
 
    [[nodiscard]] Iterator begin() const noexcept { return Iterator(*this); }
 
    [[nodiscard]] Iterator end() const noexcept { return Iterator(); }
  };
 
  /*
    BEWARE: Ensure that this instantiation to be unique
  */
  template <class Key, class Type>
  typename SkipList<Key, Type>::Node SkipList<Key, Type>::Node::nodeSentinel;
 
  template <class Key, class Type>
  typename SkipList<Key, Type>::Node *SkipList<Key, Type>::Node::NullPtr =
      &SkipList<Key, Type>::Node::nodeSentinel;
 
 
  template <class Key, class Type>
  const double SkipList<Key, Type>::defaultProbability = 0.5;
} // end namespace Aleph
 
# endif // TPL_SKIPLIST_H