Program Listing for File InterleavedRankSelect.h

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

/*--------------------------------------------------------------------------*/
/*---------------------- File InterleavedRankSelect.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------- CLASS InterleavedRankSelect ----------------------*/
/*--------------------------------------------------------------------------*/

class InterleavedRankSelect {

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

 InterleavedRankSelect( void ) : InterleavedRankSelect( BitVector() ) {}

 explicit InterleavedRankSelect( const BitVector & b );

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

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

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

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

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

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

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

 static constexpr std::size_t kData = 496;
 static constexpr std::size_t kLines = 128;
 static constexpr std::size_t kSample = 8192;

 void build( const Word * w , std::size_t n );

 [[nodiscard]] std::size_t before( std::size_t l ) const {
  return( std::size_t( f_S[ l / kLines ] ) +
          std::size_t( f_L[ 8 * l ] & 0xFFFF ) );
  }

 [[nodiscard]] std::size_t inLine( std::size_t l , unsigned p ) const;

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

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

 std::size_t f_n = 0 , f_ones = 0;
 std::vector< Word , detail::LineAllocator< Word > > f_L;
 std::vector< std::uint64_t > f_S;
 std::vector< std::uint32_t > f_sl[ 2 ];
 std::vector< std::uint64_t > f_sc[ 2 ];

 };  // end( class InterleavedRankSelect )

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

}  // end( namespace ADS )

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

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

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

#endif  /* InterleavedRankSelect.h included */

/*--------------------------------------------------------------------------*/
/*-------------------- End File InterleavedRankSelect.h --------------------*/
/*--------------------------------------------------------------------------*/