Program Listing for File Treap.h

↰ Return to documentation for file (ADS/tree/Treap.h)

/*--------------------------------------------------------------------------*/
/*------------------------------ File Treap.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <optional>
#include <utility>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------------ CLASS Treap -------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 using Key = K;
 using Value = V;

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

 [[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 height( void ) const;

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

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

 struct Node {
  K key;
  V value;
  std::uint64_t priority;
  std::unique_ptr< Node > left , right;
  };

 public:

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

 // a constant view of the pairs ( key , value ) by increasing key,
 // bidirectional, along the path from the root (the nodes have no parent)

 struct Shape {
  static auto root( const auto & o ) { return( o.f_root.get() ); }
  static auto left( const auto * n ) { return( n->left.get() ); }
  static auto right( const auto * n ) { return( n->right.get() ); }
  static auto read( const auto * n ) {
   return( std::pair< const K & , const V & >( n->key , n->value ) );
   }
  };

 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 const_iterator = PathIterator< Treap , Shape >;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , true ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , false ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 private:
 using Ptr = std::unique_ptr< Node >;

 static void rotateRight( Ptr & t );
 static void rotateLeft( Ptr & t );
 bool insert( Ptr & t , const K & k , const V & v );
 static bool remove( Ptr & t , const K & k );
 static int height( const Ptr & t );
 template< class F >
 static void visit( const Ptr & t , F & f );
 static bool valid( const Ptr & t , const K * lo , const K * hi );

 Ptr f_root;
 std::size_t f_size = 0;
 SplitMix64 f_g;

 };  // end( class Treap )

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

}  // end( namespace ADS )

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

#include "ADS/tree/impl/Treap.tpp"

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

#endif  /* Treap.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File Treap.h ----------------------------*/
/*--------------------------------------------------------------------------*/