Program Listing for File TieredVector.h

↰ Return to documentation for file (ADS/sequence/TieredVector.h)

/*--------------------------------------------------------------------------*/
/*--------------------------- File TieredVector.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <bit>
#include <cstddef>
#include <iterator>
#include <memory>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS TieredVector ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class TieredVector {

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

 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = T &;
 using const_reference = const T &;

 TieredVector( void ) = default;

 [[nodiscard]] bool empty( void ) const { return( f_n == 0 ); }
 [[nodiscard]] std::size_t size( void ) const { return( f_n ); }

 [[nodiscard]] std::size_t block( void ) const { return( f_b ); }

 [[nodiscard]] T & operator[]( std::size_t i ) {
  ADS_PRE( i < f_n );
  Block & k = f_blocks[ i >> f_lg ];
  return( k.a[ ( k.off + i ) & ( f_b - 1 ) ] );
  }
 [[nodiscard]] const T & operator[]( std::size_t i ) const {
  ADS_PRE( i < f_n );
  const Block & k = f_blocks[ i >> f_lg ];
  return( k.a[ ( k.off + i ) & ( f_b - 1 ) ] );
  }

 void insert( std::size_t i , const T & x );

 void erase( std::size_t i );

 void push_back( const T & x ) { insert( f_n , x ); }

 void pop_back( void ) { erase( f_n - 1 ); }

 void clear( void );

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

 template< bool Const >
 class Iterator {
  using Owner = std::conditional_t< Const , const TieredVector ,
                                    TieredVector >;

  public:
  using iterator_category = std::random_access_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using reference = std::conditional_t< Const , const T & , T & >;
  using pointer = std::conditional_t< Const , const T * , T * >;

  Iterator( void ) = default;
  Iterator( Owner * v , std::size_t i ) : f_v( v ) , f_i( i ) {}

  template< bool K > requires ( Const && ! K )
  Iterator( const Iterator< K > & o ) : f_v( o.f_v ) , f_i( o.f_i ) {}

  reference operator*( void ) const { return( ( *f_v )[ f_i ] ); }
  pointer operator->( void ) const { return( &**this ); }
  reference operator[]( difference_type k ) const {
   return( ( *f_v )[ std::size_t( difference_type( f_i ) + k ) ] );
   }
  Iterator & operator++( void ) { ++f_i; return( *this ); }
  Iterator & operator--( void ) { --f_i; return( *this ); }
  Iterator operator++( int ) { auto t = *this; ++f_i; return( t ); }
  Iterator operator--( int ) { auto t = *this; --f_i; return( t ); }
  Iterator & operator+=( difference_type k ) {
   f_i = std::size_t( difference_type( f_i ) + k );
   return( *this );
   }
  Iterator & operator-=( difference_type k ) { return( *this += -k ); }
  friend Iterator operator+( Iterator a , difference_type k ) {
   return( a += k );
   }
  friend Iterator operator+( difference_type k , Iterator a ) {
   return( a += k );
   }
  friend Iterator operator-( Iterator a , difference_type k ) {
   return( a -= k );
   }
  friend difference_type operator-( const Iterator & a ,
                                    const Iterator & b ) {
   return( difference_type( a.f_i ) - difference_type( b.f_i ) );
   }
  bool operator==( const Iterator & o ) const { return( f_i == o.f_i ); }
  auto operator<=>( const Iterator & o ) const { return( f_i <=> o.f_i ); }

  private:
  Owner * f_v = nullptr;
  std::size_t f_i = 0;

  template< bool > friend class Iterator;
  };

 using iterator = Iterator< false >;
 using const_iterator = Iterator< true >;

 [[nodiscard]] iterator begin( void ) { return( iterator( this , 0 ) ); }
 [[nodiscard]] iterator end( void ) { return( iterator( this , f_n ) ); }
 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , f_n ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 struct Block {
  std::unique_ptr< T[] > a;
  std::size_t off = 0;
  };

 void rebuild( std::size_t n );

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

 std::vector< Block > f_blocks;
 std::size_t f_n = 0;
 std::size_t f_b = 64;
 unsigned f_lg = 6;

 };  // end( class TieredVector )

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

}  // end( namespace ADS )

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

#include "ADS/sequence/impl/TieredVector.tpp"

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

#endif  /* TieredVector.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File TieredVector.h -------------------------*/
/*--------------------------------------------------------------------------*/