Program Listing for File BTree.h

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

/*--------------------------------------------------------------------------*/
/*------------------------------ File BTree.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <iterator>
#include <memory>
#include <optional>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS BTree --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 using Key = K;
 using Value = V;

 explicit BTree( int t = 3 );

 [[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]] bool empty( void ) const;

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

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

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

 struct Node {
  std::vector< K > k;
  std::vector< V > v;
  std::vector< std::unique_ptr< Node > > c;
  [[nodiscard]] bool leaf( void ) const { return( c.empty() ); }
  };

 public:

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

 // a constant view of the pairs ( key , value ) by increasing key,
 // forward, with the path of ( node , index ) from the root: in a node
 // above the last, the index is the child the path went into, and the key
 // of that index comes once the child is done

 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 ) {
   if( x && ! x->k.empty() ) leftmost( x );
   }

  reference operator*( void ) const {
   const auto & [ x , i ] = f_path.back();
   return( reference( x->k[ i ] , x->v[ i ] ) );
   }

  const_iterator & operator++( void ) {
   auto & [ x , i ] = f_path.back();
   if( ! x->c.empty() ) {                   // into the child after the key
    ++i;
    leftmost( x->c[ i ].get() );
    return( *this );
    }
   if( ++i < x->k.size() ) return( *this );
   f_path.pop_back();                       // up to the first ancestor
   while( ! f_path.empty() &&               // with a key left
          ( f_path.back().second >= f_path.back().first->k.size() ) )
    f_path.pop_back();
   return( *this );
   }

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

  bool operator==( const const_iterator & o ) const {
   return( f_path.empty() ? o.f_path.empty()
                          : ( ! o.f_path.empty() &&
                              ( f_path.back() == o.f_path.back() ) ) );
   }

  private:
  void leftmost( const Node * x ) {
   for( ; ! x->c.empty() ; x = x->c[ 0 ].get() ) f_path.emplace_back( x , 0 );
   f_path.emplace_back( x , 0 );
   }

  std::vector< std::pair< const Node * , std::size_t > > f_path;
  };

 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_root.get() ) );
  }
 [[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:

 static std::size_t place( const Node * x , const K & key );

 void split( Node * x , std::size_t i );

 static void merge( Node * x , std::size_t j );

 std::size_t fill( Node * x , std::size_t i );

 bool remove( Node * x , const K & key );

 template< class F >
 static void visit( const Node * x , F & f );

 bool valid( const Node * x , const K * lo , const K * hi , int d ,
             int & leafDepth , bool root ) const;

 int f_t;
 std::unique_ptr< Node > f_root;
 std::size_t f_size = 0;

 };  // end( class BTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BTree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File BTree.h ----------------------------*/
/*--------------------------------------------------------------------------*/