Forward/random‐access reader over an Elias‐Fano‐encoded, non‐decreasing sequence of integers produced by EliasFanoEncoder.

Synopsis

Declared in <folly/compression/elias_fano/EliasFanoCoding.h>

template<
    class Encoder,
    class Instructions = instructions::Default,
    bool kUnchecked = false,
    class SizeT = Encoder::SkipValueType>
class EliasFanoReader;

Description

The reader maintains a current position. It starts positioned before the first element; advance it with next()/skip()/skipTo() or jump to an absolute position or value with jump()/jumpTo(). While valid(), value() returns the current element. Sequential and skip‐based access are sub‐linear thanks to the encoded skip/forward pointers.

Type Aliases

Name

Description

EncoderType

The encoder type whose output this reader consumes.

SizeType

The type used for positions and sizes.

ValueType

The element value type.

Member Functions

Name

Description

EliasFanoReader [constructor]

Constructs a reader over the given compressed list. The reader starts positioned before the first element, so call next() (or skipTo()/jump()) before reading value().

jump

Jumps to the element at position n. The reader can be in any state. Returns false if n >= size().

jumpTo

Jumps to the first element >= value. The reader can be in any state. Returns false if no such element exists.

next

Advances to the next element. Returns false if the end of the list has been reached.

position

Returns the zero‐based index of the current element. Before the first advance the position is kBeforeFirstPos.

prepareSkipTo

Prepare to skip to value by prefetching appropriate memory in both the upper and lower bits.

previous

Moves to the previous element. Returns false and resets to before the first element if there is no previous element.

previousValue

Returns the value immediately preceding the current one without moving the reader. Requires 0 < position() < size().

reset

Repositions the reader before the first element.

size

Returns the number of elements in the list.

skip

Advances by n elements. n = 0 is allowed and has no effect. Returns false if the end of the list is reached. position() + n must be representable by SizeType.

skipTo

Skips to the first element >= value whose position is greater or equal to the current position. Requires that value >= value() (or that the reader is positioned before the first element). Returns false if no such element exists. If kCanBeAtValue is false, the requirement above becomes value > value().

valid

Whether the reader is positioned on a valid element, i.e. not before the first element and not past the last one.

value

Returns the value of the current element. Requires valid().

Created with MrDocs