Class MoveStructure

• Defined in File MoveStructure.h

Class Documentation

class MoveStructure

a permutation of [ 0 , n ) that shifts each of its intervals alike, with the image of a place and its interval in O( 1 ) time

Public Functions

MoveStructure(void) = default

MoveStructure(std::span<const std::uint64_t> p, std::span<const std::uint64_t> q, std::span<const std::uint32_t> tag, std::uint64_t n)

the permutation of the intervals that start at p (sorted, the first at 0) onto those that start at q, of [ 0 , n ), each with its tag

Pre:

p and q of the same size, the images a partition of [ 0 , n )

inline std::size_t intervals(void) const

the number of the intervals, after the balance

inline std::uint64_t size(void) const

inline std::uint64_t start(std::size_t i) const

the start of the interval i, n for i = intervals()

inline std::uint32_t tag(std::size_t i) const

the tag of the interval i

std::pair<std::uint64_t, std::size_t> move(std::uint64_t x, std::size_t i) const

the image of x, of the interval i, and its interval

Pre:

start( i ) <= x < start( i + 1 )

std::size_t interval(std::uint64_t x) const

the interval of x, by a binary search (for the first place of a walk)

std::size_t sizeInBits(void) const

the bits of the starts, of the images, of their intervals and of the tags