Program Listing for File SkipList.h

↰ Return to documentation for file (ADS/dictionary/SkipList.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File SkipList.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_SkipList
 #define __ADS_SkipList
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/dictionary/RandomHashing.h"

#include <algorithm>
#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <optional>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS SkipList ------------------------------*/
/*--------------------------------------------------------------------------*/

template< std::totally_ordered K , class V >
class SkipList {

/*--------------------------------------------------------------------------*/
 public:

 using Key = K;
 using Value = V;

 explicit SkipList( std::uint64_t seed = 1 );

 SkipList( const SkipList & ) = delete;
 SkipList & operator=( const SkipList & ) = delete;

 SkipList( SkipList && other ) noexcept;

 ~SkipList();

 [[nodiscard]] std::optional< V > lookup( const K & k ) const;

 void insert( const K & k , const V & v );

 void remove( const K & k );

 [[nodiscard]] bool contains( const K & k ) const;

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] int levels( void ) const;

 template< class F >
 void forEach( F && f ) const;

/*--------------------------------------------------------------------------*/
 private:

 static constexpr int kMax = 32;

 struct Node {
  K key;
  V value;
  std::vector< Node * > next;
  };

 public:

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a constant view of the pairs ( key , value ) by increasing key, along
 // the bottom level, forward

 class const_iterator {
  public:
  using reference = std::pair< const K & , const V & >;
  using value_type = reference;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::forward_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;
  explicit const_iterator( const Node * x ) : f_x( x ) {}

  reference operator*( void ) const {
   return( reference( f_x->key , f_x->value ) );
   }
  const_iterator & operator++( void ) {
   f_x = f_x->next[ 0 ];
   return( *this );
   }
  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }
  bool operator==( const const_iterator & o ) const = default;

  private:
  const Node * f_x = nullptr;
  };

 using value_type = std::pair< const K & , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type;
 using const_reference = value_type;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( f_head.empty() ? nullptr : f_head[ 0 ] ) );
  }
 [[nodiscard]] const_iterator end( void ) const { return( const_iterator() ); }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 private:

 Node * before( const K & k , Node * update[ kMax ] ) const;

 [[nodiscard]] bool sorted( void ) const;

 std::vector< Node * > f_head;
 int f_levels = 0;
 std::size_t f_size = 0;
 SplitMix64 f_g;

 };  // end( class SkipList )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/dictionary/impl/SkipList.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* SkipList.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File SkipList.h ---------------------------*/
/*--------------------------------------------------------------------------*/