Class PermutedBuckets

Class Documentation

class PermutedBuckets

a set of values below 2^w, permuted by x -> a x + c mod 2^w and split by the top bits of the images into buckets of L items on average

Public Functions

PermutedBuckets(const std::vector<std::uint64_t> &A, unsigned w, std::size_t L, std::uint64_t a, std::uint64_t c)

the values of A, distinct, in any order

Pre:

1 <= w <= 63, a odd, L >= 1, the values of A distinct and below 2^w

std::size_t size(void) const

the items

std::size_t buckets(void) const

the buckets, 2^ell

std::vector<std::uint64_t> intersect(const PermutedBuckets &other, std::size_t *scanned = nullptr) const

the values common to the two sets, sorted; the items of the two sets looked at go to *scanned, if given

Pre:

the same w, a and c

Post:

the intersection of the two sets (an audit)

std::vector<std::uint64_t> values(void) const

the values of the set, sorted, by inverting the permutation