Program Listing for File CompactRankSelect.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File CompactRankSelect.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/succinct/BitVector.h"

#include <algorithm>
#include <array>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <span>
#include <vector>

#if defined( __AVX2__ )
 #include <immintrin.h>
#endif

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS CompactRankSelect ------------------------*/
/*--------------------------------------------------------------------------*/

class CompactRankSelect {

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

 CompactRankSelect( void ) : CompactRankSelect( BitVector() ) {}

 explicit CompactRankSelect( BitVector b );

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

 [[nodiscard]] const BitVector & bits( void ) const { return( f_b ); }

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

 [[nodiscard]] bool operator[]( std::size_t i ) const { return( f_b[ i ] ); }

 [[nodiscard]] std::size_t ones( void ) const { return( f_ones ); }

 [[nodiscard]] std::size_t zeros( void ) const {
  return( f_b.size() - f_ones );
  }

 [[nodiscard]] std::size_t rank1( std::size_t i ) const;

 [[nodiscard]] std::size_t rank0( std::size_t i ) const {
  return( i - rank1( i ) );
  }

 [[nodiscard]] std::size_t select1( std::size_t k ) const;

 [[nodiscard]] std::size_t select0( std::size_t k ) const;

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

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

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

 static constexpr std::size_t kSuper = 4096;
 static constexpr std::size_t kBlock = 512;
 static constexpr std::size_t kSample = 4096;
#ifndef ADS_COMPACT_TOP
 static constexpr int kTop = 32;
#else
 static constexpr int kTop = ADS_COMPACT_TOP;  // a test of the top level
#endif

 struct Entry {
  std::uint64_t lo = 0 , hi = 0;
  };

 [[nodiscard]] static std::size_t inSuper( const Entry & e , std::size_t k ) {
  const std::size_t s = 32 + 12 * k;        // 32 , 44 , ... , 116
  const std::uint64_t v = s < 64 ? ( e.lo >> s ) | ( e.hi << ( 64 - s ) )
                                 : e.hi >> ( s - 64 );
  return( std::size_t( v & 0xFFF ) );
  }

#ifndef ADS_RANKSELECT_FUSE
 static constexpr std::size_t kFuse = std::size_t( 1 ) << 23;
#else
 static constexpr std::size_t kFuse = ADS_RANKSELECT_FUSE;   // a test
#endif

 void directory( const Word * w );

 [[nodiscard]] std::size_t before( std::size_t s , bool b ) const;

 [[nodiscard]] std::size_t select( std::size_t k , bool b ) const;

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

 BitVector f_b;
 std::vector< Entry > f_e;
 std::vector< std::uint64_t > f_top;
 std::vector< std::uint32_t > f_s[ 2 ];
 std::size_t f_ones = 0;

 };  // end( class CompactRankSelect )

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

}  // end( namespace ADS )

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

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

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

#endif  /* CompactRankSelect.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File CompactRankSelect.h ----------------------*/
/*--------------------------------------------------------------------------*/