Program Listing for File RRRBitVector.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File RRRBitVector.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS RRRBitVector ---------------------------*/
/*--------------------------------------------------------------------------*/

class RRRBitVector {

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

 RRRBitVector( void ) : RRRBitVector( BitVector() ) {}

 explicit RRRBitVector( const BitVector & b );

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

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

 [[nodiscard]] std::size_t zeros( void ) const { return( f_m - 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 sizeInBits( void ) const;

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

 static constexpr int kB = 63;
 static constexpr std::size_t kSuper = 32;

 struct Tables {
  std::array< std::array< std::uint64_t , 64 > , 64 > C{};
  std::array< std::uint8_t , 64 > len{};
  };
 static const Tables & tables( void );

 static std::uint64_t offset( std::uint64_t x , int c );

 static int below( std::uint64_t o , int c , int q );

 [[nodiscard]] std::uint64_t locate( std::size_t j , int & c ,
                                     std::size_t & ones ) const;

 [[nodiscard]] int cls( std::size_t j ) const {
  return( int( f_cls.get( 6 * j , 6 ) ) );
  }

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

 std::size_t f_m = 0 , f_ones = 0;
 BitVector f_cls;
 BitVector f_off;
 BitVector f_rank;
 BitVector f_ptr;
 int f_wr = 1 , f_wp = 1;

 };  // end( class RRRBitVector )

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

}  // end( namespace ADS )

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

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

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

#endif  /* RRRBitVector.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File RRRBitVector.h -------------------------*/
/*--------------------------------------------------------------------------*/