Program Listing for File PrefixSearch.h

↰ Return to documentation for file (ADS/string/PrefixSearch.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File PrefixSearch.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/search/BinarySearch.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

[[nodiscard]] inline std::size_t lexicographicPosition(
                                       const std::vector< std::string > & A ,
                                       std::string_view Q );

[[nodiscard]] inline std::size_t prefixEnd(
                                       const std::vector< std::string > & A ,
                                       std::string_view P );

[[nodiscard]] inline std::pair< std::size_t , std::size_t > prefixRange(
                                       const std::vector< std::string > & A ,
                                       std::string_view P );

[[nodiscard]] inline std::size_t commonPrefixLength( std::string_view a ,
                                                     std::string_view b );

namespace detail {

[[nodiscard]] inline bool precedes( std::string_view s , std::string_view P ,
                                    bool upper );

[[nodiscard]] inline std::uint64_t prefixKey( std::string_view s );

}  // end( namespace detail )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS BinnedSearch ----------------------------*/
/*--------------------------------------------------------------------------*/

class BinnedSearch {
 public:
 explicit BinnedSearch( std::vector< std::uint64_t > X );

 [[nodiscard]] std::size_t position( std::uint64_t y ) const;

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

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

 [[nodiscard]] std::uint64_t width( void ) const;

 [[nodiscard]] std::pair< std::size_t , std::size_t > bin(
                                                      std::size_t j ) const;

 [[nodiscard]] std::optional< std::size_t > binOf( std::uint64_t y ) const;

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

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

 [[nodiscard]] const std::vector< std::uint64_t > & items( void ) const;

 private:
 std::vector< std::uint64_t > f_X;
 std::uint64_t f_b = 1;
 std::vector< std::size_t > f_start;
 };

/*--------------------------------------------------------------------------*/
/*----------------------- CLASS BinnedStringSearch -------------------------*/
/*--------------------------------------------------------------------------*/

class BinnedStringSearch {
 public:
 explicit BinnedStringSearch( std::vector< std::string > A );

 [[nodiscard]] std::size_t lexicographicPosition( std::string_view Q ) const;

 [[nodiscard]] std::size_t prefixEnd( std::string_view P ) const;

 [[nodiscard]] std::pair< std::size_t , std::size_t > prefixRange(
                                                   std::string_view P ) const;

 [[nodiscard]] const BinnedSearch & keys( void ) const;

 private:
 [[nodiscard]] std::size_t rank( std::string_view P , bool upper ,
                                 std::uint64_t k ) const;

 std::vector< std::string > f_A;
 BinnedSearch f_K;
 };

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

}  // end( namespace ADS )

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

#include "ADS/string/impl/PrefixSearch.tpp"

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

#endif  /* PrefixSearch.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File PrefixSearch.h ------------------------*/
/*--------------------------------------------------------------------------*/