Program Listing for File RankSelect.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File RankSelect.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <atomic>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <mutex>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS BasicRankSelect --------------------------*/
/*--------------------------------------------------------------------------*/

struct RankSelectOptions {
 enum class Selects { NONE , ONES , ZEROS , BOTH };
 };

template< bool Lazy >
class BasicRankSelect : public RankSelectOptions {

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

 BasicRankSelect( void );

 explicit BasicRankSelect( BitVector b , Selects s = Selects::BOTH );

 BasicRankSelect( std::span< const Word > w , std::size_t n ,
                  Selects s = Selects::BOTH );

 BasicRankSelect( const BasicRankSelect & o );

 BasicRankSelect( BasicRankSelect && o ) noexcept;

 BasicRankSelect & operator=( const BasicRankSelect & o );

 BasicRankSelect & operator=( BasicRankSelect && o ) noexcept;

 ~BasicRankSelect( void ) = default;

 [[nodiscard]] const BitVector & bits( void ) const;

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

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

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

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

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

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

 [[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< BasicRankSelect , 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 kBlock = 256;
 static constexpr int kRel = 8;
 static constexpr std::size_t kQuarter = kBlock / 4;
 static constexpr std::uint64_t kRelMask = ( std::uint64_t( 1 ) << kRel ) - 1;
#ifndef ADS_RANKSELECT_TOP
 static constexpr int kTop = 64 - 3 * kRel;
#else
 static constexpr int kTop = ADS_RANKSELECT_TOP;   // a test of the top level
#endif
#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

 static constexpr std::size_t kGroup = 4096;
 static constexpr std::size_t kSparse = std::size_t( 1 ) << 16;

 struct Inventory {
  int l = 0 , g = 0 , s = 0;
  std::vector< std::uint64_t > pos;
  std::vector< std::uint16_t , detail::LineAllocator< std::uint16_t > > off;
  };

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

 void directory( Selects s , const Word * w );

 void shape( bool b , Inventory & I , std::size_t & groups ) const;

 const Inventory & inventory( bool b ) const;

 void build( bool b ) const;

 void first( bool b ) const;

 void adopt( const BasicRankSelect & o , bool move );

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

 [[nodiscard]] std::size_t selectSparse( std::size_t k , bool b ,
                                         std::size_t p ,
                                         std::size_t q ) const;

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

 BitVector f_b;
 std::vector< std::uint64_t , detail::LineAllocator< std::uint64_t > >
                                                                     f_dir;
 std::vector< std::uint64_t > f_top;
 bool f_big = false;
 mutable Inventory f_inv[ 2 ];
 bool f_has[ 2 ] = { true , true };
 std::size_t f_ones = 0;
 struct Once {
  mutable std::once_flag flag[ 2 ];
  mutable std::atomic< bool > ready[ 2 ] = { false , false };
  };
 struct None {};
 [[no_unique_address]] std::conditional_t< Lazy , Once , None > f_once;

 };  // end( class BasicRankSelect )

using RankSelect = BasicRankSelect< false >;

using LazyRankSelect = BasicRankSelect< true >;

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

}  // end( namespace ADS )

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

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

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

#endif  /* RankSelect.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File RankSelect.h --------------------------*/
/*--------------------------------------------------------------------------*/