Program Listing for File BPlusTree.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File BPlusTree.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <iterator>
#include <optional>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS BPlusTree -------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 using Key = K;
 using Value = V;

 explicit BPlusTree( int m );

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

 ~BPlusTree();

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

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

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

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

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

 [[nodiscard]] std::vector< std::pair< K , V > > range( const K & A ,
                                                       const K & B ) const;

 [[nodiscard]] std::vector< std::vector< std::vector< K > > > levels( void )
  const;

 void check( void ) const;

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

 struct Node {
  explicit Node( bool l ) : is_leaf( l ) {}
  bool is_leaf;
  std::vector< K > k;
  std::vector< Node * > p;
  std::vector< V > v;
  Node * parent = nullptr;
  Node * prev = nullptr;
  Node * next = nullptr;
  };

 public:

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

 // a constant view of the pairs ( key , value ) by increasing key,
 // bidirectional along the chain of the leaves

 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::bidirectional_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;
  const_iterator( const BPlusTree * t , const Node * f , std::size_t i )
   : f_t( t ) , f_f( f ) , f_i( i ) {}

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

  const_iterator & operator++( void ) {
   if( ++f_i < f_f->k.size() ) return( *this );
   f_f = f_f->next;
   f_i = 0;
   while( f_f && f_f->k.empty() ) f_f = f_f->next;
   return( *this );
   }

  const_iterator & operator--( void ) {
   if( f_f && ( f_i > 0 ) ) {
    --f_i;
    return( *this );
    }
   f_f = f_f ? f_f->prev : f_t->lastLeaf();   // from the end, the last
   while( f_f->k.empty() ) f_f = f_f->prev;
   f_i = f_f->k.size() - 1;
   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_f == o.f_f ) && ( f_i == o.f_i ) );
   }

  private:
  const BPlusTree * f_t = nullptr;
  const Node * f_f = nullptr;
  std::size_t f_i = 0;
  };

 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 {
  const Node * f = firstLeaf();
  while( f && f->k.empty() ) f = f->next;
  return( const_iterator( this , f , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , nullptr , 0 ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 private:

 [[nodiscard]] const Node * firstLeaf( void ) const {
  const Node * x = f_root;
  while( x && ! x->is_leaf ) x = x->p.front();
  return( x );
  }
 [[nodiscard]] const Node * lastLeaf( void ) const {
  const Node * x = f_root;
  while( x && ! x->is_leaf ) x = x->p.back();
  return( x );
  }

 Node * leaf( const K & x ) const;

 void up( Node * f , Node * g , const K & s );

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

 [[nodiscard]] bool shaped( const Node * u , const K * lo , const K * hi ,
                            int d , int & depth ,
                            const Node * & last ) const;

 static void destroy( Node * u );

 int f_m;
 Node * f_root;
 std::size_t f_size = 0;

 };  // end( class BPlusTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BPlusTree.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File BPlusTree.h --------------------------*/
/*--------------------------------------------------------------------------*/