Program Listing for File PartitionedEliasFano.h

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

/*--------------------------------------------------------------------------*/
/*----------------------- File PartitionedEliasFano.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_PartitionedEliasFano
 #define __ADS_PartitionedEliasFano
                      /* 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>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------- CLASS PartitionedEliasFano -----------------------*/
/*--------------------------------------------------------------------------*/

class PartitionedEliasFano {

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

 PartitionedEliasFano( void ) = default;

 explicit PartitionedEliasFano( std::span< const std::uint64_t > x );

 PartitionedEliasFano( std::span< const std::uint64_t > x , std::uint64_t u );

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

 [[nodiscard]] bool empty( void ) const { return( f_n == 0 ); }

 [[nodiscard]] std::uint64_t universe( void ) const { return( f_u ); }

 [[nodiscard]] std::uint64_t access( std::size_t i ) const;

 [[nodiscard]] std::uint64_t operator[]( std::size_t i ) const {
  return( access( i ) );
  }

 [[nodiscard]] std::size_t nextGEQ( std::uint64_t x ) const;

 [[nodiscard]] bool contains( std::uint64_t x ) const;

 [[nodiscard]] std::array< std::size_t , 3 > kinds( void ) const;

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

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

 using value_type = std::uint64_t;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = std::uint64_t;
 using const_reference = std::uint64_t;
 using const_iterator = SubscriptIterator< PartitionedEliasFano ,
                                           std::uint64_t >;
 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:

 static constexpr std::size_t kB = 128;
 static constexpr std::size_t kApart = 8;

 enum Kind { FULL = 0 , VECTOR = 1 , ELIAS = 2 };

 struct Code {
  Kind kind;
  std::uint64_t bits;
  int ell;
  };
 [[nodiscard]] static Code code( std::uint64_t m , std::uint64_t u );

 [[nodiscard]] std::uint64_t last( std::size_t j ) const {
  return( f_rec.get( j * std::size_t( f_wr ) , f_wl ) );
  }
 [[nodiscard]] std::size_t where( std::size_t j ) const {
  return( std::size_t( f_rec.get( j * std::size_t( f_wr ) +
                                  std::size_t( f_wl ) , f_wo ) ) );
  }
 [[nodiscard]] unsigned form( std::size_t j ) const {
  return( unsigned( f_rec.get( j * std::size_t( f_wr ) +
                               std::size_t( f_wl + f_wo ) , 8 ) ) );
  }

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

 [[nodiscard]] std::size_t ones( std::size_t p , std::size_t q ) const;

 std::size_t f_n = 0;
 std::uint64_t f_u = 0;
 BitVector f_codes;
 BitVector f_rec;
 int f_wl = 1 , f_wo = 1 , f_wr = 10;
 std::vector< std::uint64_t > f_apart;
 std::vector< std::uint64_t > f_eyt;
 std::vector< std::uint32_t > f_rank;

 };  // end( class PartitionedEliasFano )

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

}  // end( namespace ADS )

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

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

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

#endif  /* PartitionedEliasFano.h included */

/*--------------------------------------------------------------------------*/
/*--------------------- End File PartitionedEliasFano.h --------------------*/
/*--------------------------------------------------------------------------*/