Module seq 

A compressed vector of variable-length sequences with indexed access.

This module provides SeqVec, a data structure for storing multiple integer sequences in a single compressed bitstream. Each sequence is accessed by its index (rank), and all elements within a sequence are decoded together.

Core Concepts

Use Case

SeqVec is designed for scenarios where:

• Data is naturally organized as many variable-length sequences.
• Access patterns retrieve entire sequences rather than individual elements.
• Memory overhead of per-sequence pointers and padding must be minimized.

A common application is representing adjacency lists in a compressed graph, where each node’s neighbors form a sequence.

Differences from VarVec

Aspect	VarVec	SeqVec
Access unit	Single element	Entire sequence
Index meaning	Element position	Sequence rank
Sampling	Periodic (every k elements)	At sequence boundaries
Primary operation	get(i) → T	get(i) → Iterator<T>

Compression

Like VarVec, SeqVec uses instantaneous variable-length codes (Gamma, Delta, Zeta, etc.) from the dsi-bitstream crate. All sequences are concatenated into a single compressed bitstream, with a FixedVec index storing the bit offset of each sequence’s start.

Sequence Length

Sequence lengths are not stored by default. The iterator for a sequence terminates when the current bit position reaches the start of the next sequence. This means:

• Retrieving a sequence is O(length) for decoding — unavoidable.
• Computing sequence length requires full iteration unless lengths are stored.

You can opt-in to storing explicit lengths via SeqVecBuilder::store_lengths. When enabled, O(1) length queries become available via SeqVec::sequence_len, and decoding can avoid the end-bit check in hot loops.

Immutability

SeqVec is immutable after creation. Variable-length encoding makes in-place modification impractical, as changing one element could shift all subsequent data.

Main Components

• SeqVec: The core compressed sequence vector.
• SeqVecBuilder: Builder for constructing a SeqVec with custom codec.
• SeqIter: Zero-allocation iterator over elements of a single sequence.
• SeqVecIter: Iterator over all sequences, yielding SeqIter instances.

Examples

Basic Usage

use compressed_intvec::seq::{SeqVec, LESeqVec};

let sequences: &[&[u32]] = &[
    &[1, 2, 3],
    &[10, 20],
    &[100, 200, 300, 400],
    &[], // Empty sequences are supported
];

let vec: LESeqVec<u32> = SeqVec::from_slices(sequences)?;

assert_eq!(vec.num_sequences(), 4);

// Access a sequence by index
let seq1: Vec<u32> = vec.get(1).unwrap().collect();
assert_eq!(seq1, vec![10, 20]);

Custom Codec

use compressed_intvec::seq::{SeqVec, LESeqVec, Codec};

let sequences: Vec<Vec<u64>> = vec![
    vec![1, 1, 1, 2, 3],
    vec![100, 200, 300],
];

let vec: LESeqVec<u64> = SeqVec::builder()
    .codec(Codec::Zeta { k: Some(3) })
    .build(&sequences)?;

Re-exports

pub use crate::variable::codec::Codec;

pub use crate::variable::VariableCodecSpec;Deprecated

Structs

SeqIter

A zero-allocation iterator over the elements of a single sequence.

SeqVec

A compressed, indexed vector of integer sequences.

SeqVecBuilder

A builder for creating a SeqVec from a collection of sequences.

SeqVecFromIterBuilder

A builder for creating a SeqVec from an iterator of sequences.

SeqVecIntoIter

An owning iterator over all sequences in a SeqVec.

SeqVecIter

An iterator over all sequences in a SeqVec.

SeqVecReader

A stateful reader for a SeqVec that provides convenient random sequence access with optimized reader reuse.

SeqVecSlice

An immutable, zero-copy slice of a SeqVec.

Enums

SeqVecError

Errors that can occur when working with SeqVec.

Type Aliases

BESSeqVec

A SeqVec for signed integers with big-endian bit ordering.

BESeqVec

A SeqVec with big-endian bit ordering.

LESSeqVec

A SeqVec for signed integers with little-endian bit ordering.

LESeqVec

A SeqVec with little-endian bit ordering.

SSeqVec

A SeqVec for signed integers with little-endian bit ordering.

SeqVecSlicePair

Type alias for a tuple of two SeqVecSlice references.

USeqVec

A SeqVec for unsigned integers with little-endian bit ordering.