Program Listing for File BitVector.h

↰ Return to documentation for file (ADS/succinct/BitVector.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File BitVector.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/combinatorial/Bitwise.h"
#include "ADS/memory/HugePageAllocator.h"

#include <algorithm>
#include <bit>
#include <compare>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <span>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

#ifdef __BMI2__
 #include <immintrin.h>
#endif

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

namespace ADS {

namespace detail {

template< class T >
class LineAllocator {
 public:
 using value_type = T;
 static constexpr std::size_t LINE = 64;

 LineAllocator( void ) = default;
 template< class U >
 LineAllocator( const LineAllocator< U > & ) noexcept {}

 [[nodiscard]] T * allocate( std::size_t n ) {
  if( n * sizeof( T ) >= HugePageAllocator< T >::PAGE )
   return( HugePageAllocator< T >().allocate( n ) );
  return( static_cast< T * >( ::operator new( n * sizeof( T ) ,
                                              std::align_val_t( LINE ) ) ) );
  }

 template< class U >
 void construct( U * p ) noexcept {
  ::new( static_cast< void * >( p ) ) U;
  }
 template< class U , class... A >
 void construct( U * p , A &&... a ) {
  ::new( static_cast< void * >( p ) ) U( std::forward< A >( a )... );
  }

 void deallocate( T * p , std::size_t n ) noexcept {
  if( n * sizeof( T ) >= HugePageAllocator< T >::PAGE )
   HugePageAllocator< T >().deallocate( p , n );
  else ::operator delete( p , std::align_val_t( LINE ) );
  }

 template< class U >
 bool operator==( const LineAllocator< U > & ) const noexcept {
  return( true );
  }
 };

}  // end( namespace detail )

using Words = std::vector< Word , detail::LineAllocator< Word > >;

[[nodiscard]] constexpr int selectInWord( Word x , int k );

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS SubscriptIterator -------------------------*/
/*--------------------------------------------------------------------------*/

template< class O , class T >
class SubscriptIterator {
 public:
 using value_type = T;
 using reference = T;
 using difference_type = std::ptrdiff_t;
 using iterator_concept = std::random_access_iterator_tag;
 using iterator_category = std::input_iterator_tag;

 SubscriptIterator( void ) = default;
 SubscriptIterator( const O * o , std::size_t i )
  : f_o( o ) , f_i( difference_type( i ) ) {}

 reference operator*( void ) const { return( ( *this )[ 0 ] ); }
 reference operator[]( difference_type k ) const {
  return( ( *f_o )[ std::size_t( f_i + k ) ] );
  }

 SubscriptIterator & operator++( void ) { ++f_i; return( *this ); }
 SubscriptIterator & operator--( void ) { --f_i; return( *this ); }
 SubscriptIterator operator++( int ) { auto t = *this; ++f_i; return( t ); }
 SubscriptIterator operator--( int ) { auto t = *this; --f_i; return( t ); }
 SubscriptIterator & operator+=( difference_type k ) {
  f_i += k;
  return( *this );
  }
 SubscriptIterator & operator-=( difference_type k ) {
  f_i -= k;
  return( *this );
  }

 friend SubscriptIterator operator+( SubscriptIterator a ,
                                     difference_type k ) {
  return( a += k );
  }
 friend SubscriptIterator operator+( difference_type k ,
                                     SubscriptIterator a ) {
  return( a += k );
  }
 friend SubscriptIterator operator-( SubscriptIterator a ,
                                     difference_type k ) {
  return( a -= k );
  }
 friend difference_type operator-( const SubscriptIterator & a ,
                                   const SubscriptIterator & b ) {
  return( a.f_i - b.f_i );
  }

 bool operator==( const SubscriptIterator & o ) const {
  return( f_i == o.f_i );
  }
 std::strong_ordering operator<=>( const SubscriptIterator & o ) const {
  return( f_i <=> o.f_i );
  }

 [[nodiscard]] std::size_t index( void ) const {
  return( std::size_t( f_i ) );
  }

 private:
 const O * f_o = nullptr;
 difference_type f_i = 0;

 };  // end( class SubscriptIterator )

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS BitVector -----------------------------*/
/*--------------------------------------------------------------------------*/

class BitVector {

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

 BitVector( void ) = default;

 explicit BitVector( std::size_t n , bool b = false );

 explicit BitVector( std::string_view s );

 BitVector( std::span< const Word > w , std::size_t n );

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

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

 [[nodiscard]] bool operator[]( std::size_t i ) const;

 void set( std::size_t i , bool b = true );

 void push_back( bool b );

 void append( Word v , int len );

 [[nodiscard]] Word get( std::size_t i , int len ) const;

 void put( std::size_t i , Word v , int len );

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

 [[nodiscard]] const Words & words( void ) const;

 [[nodiscard]] std::string toString( void ) const;

 void reserve( std::size_t n );

 void clear( void );

 friend bool operator==( const BitVector & a , const BitVector & b ) =
                                                                     default;

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

 using value_type = bool;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = bool;
 using const_reference = bool;
 using const_iterator = SubscriptIterator< BitVector , bool >;
 using iterator = const_iterator;

 [[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:

 template< bool > friend class BasicRankSelect;   // which copy the words
 friend class CompactRankSelect;                  // as they count them

 [[nodiscard]] static std::size_t wordsFor( std::size_t n ) {
  return( ( n / 64 + 9 ) & ~std::size_t( 7 ) );
  }

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

 Words f_w = Words( 8 , 0 );
 std::size_t f_n = 0;

 };  // end( class BitVector )

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

}  // end( namespace ADS )

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

#include "ADS/succinct/impl/BitVector.tpp"

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

#endif  /* BitVector.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File BitVector.h --------------------------*/
/*--------------------------------------------------------------------------*/