Program Listing for File BTreeMap.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File BTreeMap.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/memory/ObjectPool.h"
#include "ADS/search/CountLess.h"

#include <algorithm>
#include <array>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iterator>
#include <limits>
#include <new>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS BTreeMap ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class K , class V , class Less = std::less< K > ,
          std::size_t B = 512 , bool R = false >
 requires std::default_initializable< K > &&
          std::default_initializable< V >
class BTreeMap {

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

 using Key = K;
 using Value = V;

 static constexpr std::size_t L =
  std::clamp< std::size_t >( B / ( sizeof( K ) + sizeof( V ) ) , 4 , 255 );

 static constexpr std::size_t I =
  std::clamp< std::size_t >( B / ( sizeof( K ) + sizeof( void * ) ) , 4 ,
                             255 );

 explicit BTreeMap( Less less = Less() );

 BTreeMap( const BTreeMap & o );

 BTreeMap( BTreeMap && o ) noexcept;

 BTreeMap & operator=( BTreeMap o ) noexcept;

 ~BTreeMap();

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

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

 [[nodiscard]] const V * find( const K & k ) const;

 [[nodiscard]] V * find( const K & k );

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

 bool remove( const K & k );

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

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

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

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

 void clear( void );

 template< std::input_iterator It >
 void build( It first , It last );

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

 template< class F >
 void forRange( const K & lo , const K & hi , F && f ) const;

 void swap( BTreeMap & o ) noexcept;

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

 // a constant view of the pairs ( key , value ) by increasing keys,
 // bidirectional, a leaf and a place in it

 class const_iterator;

 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;
 [[nodiscard]] const_iterator end( void ) const;
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 [[nodiscard]] const_iterator lowerBound( const K & k ) const;

 [[nodiscard]] const_iterator upperBound( const K & k ) const;

 const_iterator erase( const_iterator it );

 [[nodiscard]] std::size_t rank( const K & k ) const requires R;

 [[nodiscard]] const_iterator select( std::size_t i ) const requires R;

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

 static constexpr bool FAST = std::is_arithmetic_v< K > &&
  ( std::is_same_v< Less , std::less< K > > ||
    std::is_same_v< Less , std::less<> > );

 [[nodiscard]] static constexpr K pad( void ) {
  if constexpr( std::numeric_limits< K >::has_infinity )
   return( std::numeric_limits< K >::infinity() );
  else
   return( std::numeric_limits< K >::max() );
  }

 struct alignas( 64 ) Leaf {
  K k[ L ];
  V v[ L ];
  Leaf * prev = nullptr;
  Leaf * next = nullptr;
  std::uint32_t n = 0;
  };

 struct None {};

 struct alignas( 64 ) Inner {
  K k[ I ];
  void * c[ I + 1 ];
  Inner * prev = nullptr;
  Inner * next = nullptr;
  std::uint32_t n = 0;
  [[no_unique_address]] std::conditional_t< R ,
                         std::array< std::size_t , I + 1 > , None > cnt;
  };

 [[nodiscard]] static std::size_t total( const void * x , int h );

 static void recount( Inner * u , int h );

 struct Step {
  Inner * u;
  std::uint32_t i;
  };

 static constexpr int DEPTH = 64;


 template< class N >
 [[nodiscard]] N * make( void );

 void free( Leaf * x ) noexcept;

 void free( Inner * x ) noexcept;

 static void clean( K * a , std::size_t from , std::size_t to );

 static void fetch( const void * x , std::size_t bytes );

 template< std::size_t C >
 [[nodiscard]] std::size_t place( const K * a , std::uint32_t n ,
                                  const K & x ) const;

 template< bool Values >
 [[nodiscard]] const Leaf * descend( const K & x ,
                                     const Inner * * up = nullptr ,
                                     std::uint32_t * at = nullptr ) const;

 [[nodiscard]] const Inner * edge( bool right ) const;

 [[nodiscard]] const Leaf * descend( const K & x , Step * path ) const;

 [[nodiscard]] bool equal( const K & a , const K & b ) const;

 void split( Leaf * x , std::uint32_t p , const K & k , const V & v ,
             Step * path , int d );

 void climb( K s , void * r , Step * path , int d , int edge );

 void shrink( Leaf * x , Step * path , int d );

 void shrink( Inner * x , Step * path , int d );

 void destroy( void * x , int h ) noexcept;

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

 [[nodiscard]] bool valid( const void * x , int h , const K * lo ,
                           const K * hi , const Leaf * & last ,
                           std::vector< const Inner * > & left ,
                           std::size_t & count ) const;

 void * f_root = nullptr;
 Leaf * f_first = nullptr;
 Leaf * f_last = nullptr;
 std::size_t f_size = 0;
 int f_height = 0;
 [[no_unique_address]] Less f_less;
 ObjectPool< Leaf > f_leaves;
 ObjectPool< Inner > f_inners;

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

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

  const_iterator( void ) = default;

  reference operator*( void ) const {
   return( reference( f_l->k[ f_i ] , f_l->v[ f_i ] ) );
   }

  const_iterator & operator++( void ) {
   if( ++f_i == f_n ) [[unlikely]]
    step();
   return( *this );
   }

  const_iterator & operator--( void ) {
   if( ! f_l ) {                            // from the end
    f_l = f_t->f_last;
    f_p = f_t->edge( true );
    f_c = f_p ? f_p->n : 0;
    f_i = f_n = f_l->n;
    }
   else if( f_i == 0 ) {
    if( f_p ) {
     if( f_c == 0 ) {
      f_p = f_p->prev;
      f_c = f_p->n;
      }
     else
      --f_c;
     f_l = static_cast< const Leaf * >( f_p->c[ f_c ] );
     }
    else
     f_l = f_l->prev;
    f_i = f_n = f_l->n;
    }
   --f_i;
   return( *this );
   }

  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }
  const_iterator operator--( int ) { auto t = *this; --*this; return( t ); }

  bool operator==( const const_iterator & o ) const {
   return( ( f_l == o.f_l ) && ( f_i == o.f_i ) );
   }

  private:
  friend class BTreeMap;

  static constexpr std::uint32_t AHEAD = 4;

  const_iterator( const BTreeMap * t , const Leaf * l , std::uint32_t i ,
                  const Inner * p , std::uint32_t c )
   : f_t( t ) , f_l( l ) , f_p( p ) , f_i( i ) , f_n( l ? l->n : 0 ) ,
     f_c( c ) {
   if( f_l && ( f_i == f_n ) )              // past a leaf: the next one
    step();
   }

  void step( void ) {
   f_i = 0;
   if( f_p ) {
    if( f_c == f_p->n ) {
     f_p = f_p->next;
     f_c = 0;
     if( f_p && f_p->next )
      fetch( f_p->next , sizeof( Inner ) );
     }
    else
     ++f_c;
    if( f_p ) {
     f_l = static_cast< const Leaf * >( f_p->c[ f_c ] );
     const Inner * q = f_p;
     std::uint32_t a = f_c + AHEAD;
     if( a > q->n ) {
      a -= q->n + 1;
      q = q->next;
      }
     if( q && ( a <= q->n ) )
      fetch( q->c[ a ] , sizeof( Leaf ) );
     }
    else
     f_l = nullptr;
    }
   else
    f_l = f_l->next;
   f_n = f_l ? f_l->n : 0;
   }

  const BTreeMap * f_t = nullptr;
  const Leaf * f_l = nullptr;
  const Inner * f_p = nullptr;
  std::uint32_t f_i = 0;
  std::uint32_t f_n = 0;
  std::uint32_t f_c = 0;

 };  // end( class const_iterator )

 };  // end( class BTreeMap )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BTreeMap.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File BTreeMap.h ----------------------------*/
/*--------------------------------------------------------------------------*/