Program Listing for File PGMIndex.h

↰ Return to documentation for file (ADS/search/PGMIndex.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File PGMIndex.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Portable.h"
#include "ADS/memory/HugePageAllocator.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS PGMIndex ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class K , std::size_t E = 64 , std::size_t R = 4 >
 requires std::is_arithmetic_v< K >
class PGMIndex {

 static_assert( ( E >= 1 ) && ( R >= 1 ) , "the errors are at least 1" );

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

 using Item = K;

 PGMIndex( void ) = default;

 explicit PGMIndex( std::vector< K > A );

 [[nodiscard]] std::size_t lowerBound( const K & v ) const;

 [[nodiscard]] bool contains( const K & v ) const;

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

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

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

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

 [[nodiscard]] int height( void ) const;

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

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

 struct Line {
  double icpt;
  double slope;
  };

 struct Level {
  std::vector< std::uint64_t > key;
  std::vector< Line > line;
  std::vector< std::uint32_t > start;
  };

 [[nodiscard]] static std::uint64_t ord( const K & k );

 static Level approximate( const std::vector< std::uint64_t > & x ,
                           const std::vector< std::uint32_t > & y ,
                           std::int64_t e , std::size_t total );

 [[nodiscard]] static std::size_t predict( const Level & l , std::size_t s ,
                                           std::uint64_t x );

 std::vector< K , HugePageAllocator< K > > f_A;
 std::vector< Level > f_L;

 };  // end( class PGMIndex )

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

}  // end( namespace ADS )

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

#include "ADS/search/impl/PGMIndex.tpp"

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

#endif  /* PGMIndex.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File PGMIndex.h ---------------------------*/
/*--------------------------------------------------------------------------*/