Class BinnedSearch

Defined in File PrefixSearch.h

Class Documentation

class BinnedSearch

the search by interpolation of a sorted array of integers by bins

Public Functions

explicit BinnedSearch(std::vector<std::uint64_t> X)

the bins of X

Pre:: X is sorted (an audit)

std::size_t position(std::uint64_t y) const

the number of items smaller than y

Post:: X[ r - 1 ] < y <= X[ r ]

bool contains(std::uint64_t y) const

std::size_t bins(void) const: the number of bins

std::uint64_t width(void) const: the width b of a bin

std::pair<std::size_t, std::size_t> bin(std::size_t j) const

the places [ first , last ) of X in the bin j

Pre:: j < bins()

std::optional<std::size_t> binOf(std::uint64_t y) const: the bin of y, or none if y is out of [ x_1 , x_m ]

std::size_t largestBin(void) const: the items of the largest bin

std::size_t size(void) const

const std::vector<std::uint64_t> &items(void) const