Struct constriction::backends::Cursor

pub struct Cursor<Word, Buf> { /* private fields */ }

Adapter that turns an in-memory buffer into an impl ReadWords and/or an impl WriteWords.

A Cursor<Word, Buf> allows you to use an in-memory buffer Buf of a slice of Words as a source and/or sink of compressed data in an entropy coder. The type Buf must implement AsRef<[Word]> to be used as a data source (i.e., an implementation of ReadWords) and it must implement AsMut<[Word]> to be used as a data sink (i.e., an implementation of WriteWords). In the most typical use cases, Buf is either a Vec<Word> (if the entropy coder should own the compressed data) or a reference to a slice of Words, i.e., &[Word] (if the entropy coder should only have shared access to the compressed data, e.g., because you want to keep the compressed data alive even after the entropy coder gets dropped).

A Cursor<Word, Buf> implements ReadWords for both Queue and Stack semantics. By convention, reading with Queue semantics incremenets the Cursor’s index into the slice returned by .as_ref() whereas reading with Stack semantics decrements the index. Whether Queue or Stack semantics will be used is usually decided by the implementation of the entropy coder that uses the Cursor as its backend. If you want to read in the opposite direction than what’s the convention for your use case (e.g., because you’ve already manually reversed the order of the Words in the buffer) then wrap the Cursor in a Reverse. The implementation of WriteWords<Word> (if Buf implements AsMut<[Word]>) always writes in the same direction in which ReadWords<Word, Queue> reads.

Examples

Sharing and Owning Cursors

The following example shows how a Cursor can be used to decode both shared and owned compressed data with a RangeDecoder:

use constriction::{
    stream::{
        model::DefaultLeakyQuantizer, queue::{DefaultRangeEncoder, DefaultRangeDecoder},
        Encode, Decode
    },
    UnwrapInfallible,
};

// Some simple entropy model, just for demonstration purpose.
let quantizer = DefaultLeakyQuantizer::new(-100..=100);
let model = quantizer.quantize(probability::distribution::Gaussian::new(25.0, 10.0));

// Encode the symbols `0..100` using a `RangeEncoder` (uses the default `Vec` backend because
// we don't know the size of the compressed data upfront).
let mut encoder = DefaultRangeEncoder::new();
encoder.encode_iid_symbols(0..100, &model);
let compressed = encoder.into_compressed().unwrap_infallible(); // `compressed` is a `Vec<u32>`.
dbg!(compressed.len()); // Prints "compressed.len() = 40".

// Create a `RangeDecoder` with shared access to the compressed data. This constructs a
// `Cursor<u32, &[u32]>` that points to the beginning of the data and loads it in the decoder.
let mut sharing_decoder
    = DefaultRangeDecoder::from_compressed(&compressed[..]).unwrap_infallible();
// `sharing_decoder` has type `RangeDecoder<u32, u64, Cursor<u32, &'a [u32]>`.

// Decode the data and verify correctness.
assert!(sharing_decoder.decode_iid_symbols(100, &model).map(Result::unwrap).eq(0..100));
assert!(sharing_decoder.maybe_exhausted());

// We can still use `compressed` because we gave the decoder only shared access to it. Thus,
// `sharing_decoder` contains a reference into `compressed`, so we couldn't return it from the
// current function. If we want to return a decoder, we have to give it ownership of the data:
let mut owning_decoder = DefaultRangeDecoder::from_compressed(compressed).unwrap_infallible();
// `owning_decoder` has type `RangeDecoder<u32, u64, Cursor<u32, Vec<u32>>`.

// Verify that we can decode the data again.
assert!(owning_decoder.decode_iid_symbols(100, &model).map(Result::unwrap).eq(0..100));
assert!(owning_decoder.maybe_exhausted());

Cursors automatically use the correct Semantics

You can use a Cursor also as a stack, e.g., for an AnsCoder. The Cursor will automatically read data in the correct (i.e., reverse) direction when it is invoked with Stack semantics. Note, however, that using a Cursor is not always necessary when you decode with an AnsCoder because the AnsCoder can also decode directly from a Vec (see last example below). However, you’ll need a Cursor if you don’t own the compressed data:

fn decode_shared_data(amt: usize, compressed: &[u32]) -> Vec<i32> {
    // Some simple entropy model, just for demonstration purpose.
    let quantizer = DefaultLeakyQuantizer::new(-100..=100);
    let model = quantizer.quantize(probability::distribution::Gaussian::new(25.0, 10.0));

    // `AnsCoder::from_compressed_slice` wraps the provided compressed data in a `Cursor` and
    // initializes the cursor position at the end (= top of the stack; see documentation of
    // `Reverse` if you want to read the data from the beginning instead).
    let mut decoder = DefaultAnsCoder::from_compressed_slice(compressed).unwrap();
    decoder.decode_iid_symbols(amt, &model).collect::<Result<Vec<_>, _>>().unwrap_infallible()
}

Owning Cursors vs Vecs

If you have ownership of the compressed data, then decoding it with an AnsCoder doesn’t always require a Cursor. An AnsCoder can also directly decode from a Vec<Word> backend. The difference between Vec<Word> and an owning cursor Cursor<Word, Vec<Word>> is that decoding from a Vec consumes the compressed data (so you can interleave multiple encoding/decoding steps arbitrarily) whereas a Cursor (whether it be sharing or owning) does not consume the compressed data that is read from it. You can still interleave multiple encoding/decoding steps with an AnsCoder that uses a Cursor instead of a Vec backend, but since a Cursor doesn’t grow or shrink the wrapped buffer you will typically either run out of buffer space at some point or the final buffer will be padded to its original size with some partially overwritten left-over compressed data (for older readers like myself: think of a Cursor as a cassette recorder).

use constriction::{
    backends::Cursor, stream::{model::DefaultLeakyQuantizer, stack::DefaultAnsCoder, Decode},
    CoderError, UnwrapInfallible,
};

// Some simple entropy model, just for demonstration purpose.
let quantizer = DefaultLeakyQuantizer::new(-100..=100);
let model = quantizer.quantize(probability::distribution::Gaussian::new(25.0, 10.0));

// Encode the symbols `0..50` using a stack entropy coder and get the compressed data.
let mut coder = DefaultAnsCoder::new();
coder.encode_iid_symbols_reverse(0..50, &model).unwrap();
let compressed = coder.into_compressed().unwrap_infallible(); // `compressed` is a `Vec<u32>`.
dbg!(compressed.len()); // Prints "compressed.len() = 11".

// We can either reconstruct (a clone of) the original `coder` with `Vec` backend and decode
// data and/or encode some more data, or even do both in any order.
let mut vec_coder = DefaultAnsCoder::from_compressed(compressed.clone()).unwrap();
// Decode the top half of the symbols off the stack and verify correctness.
assert!(
    vec_coder.decode_iid_symbols(25, &model)
        .map(UnwrapInfallible::unwrap_infallible)
        .eq(0..25)
);
// Then encode some more symbols onto it.
vec_coder.encode_iid_symbols_reverse(50..75, &model).unwrap();
let compressed2 = vec_coder.into_compressed().unwrap_infallible();
dbg!(compressed2.len()); // Prints "compressed2.len() = 17"
// `compressed2` is longer than `compressed1` because the symbols we poped off had lower
// information content under the `model` than the symbols we replaced them with.

// In principle, we could have done the same with an `AnsCoder` that uses a `Cursor` backend.
let cursor = Cursor::new_at_write_end(compressed); // Could also use `&mut compressed[..]`.
let mut cursor_coder = DefaultAnsCoder::from_compressed(cursor).unwrap();
// Decode the top half of the symbols off the stack and verify correctness.
assert!(
    cursor_coder.decode_iid_symbols(25, &model)
        .map(UnwrapInfallible::unwrap_infallible)
        .eq(0..25)
);
// Encoding *a few* more symbols works ...
cursor_coder.encode_iid_symbols_reverse(65..75, &model).unwrap();
// ... but at some point we'll run out of buffer space.
assert_eq!(
    cursor_coder.encode_iid_symbols_reverse(50..65, &model),
    Err(CoderError::Backend(constriction::backends::BoundedWriteError::OutOfSpace))
);

Implementations

impl<Word, Buf> Cursor<Word, Buf>

pub fn new_at_write_beginning(buf: Buf) -> Self

Creates a Cursor for the buffer buf and initializes the cursor position to point at the beginning (i.e., index zero) of the buffer.

You can use the resulting cursor, for decoding compressed data with Queue semantics (for example, calling RangeDecoder::from_compressed with a vector or slice of Words will result in a call to Cursor::new_at_write_beginning).

If you want to read from the resulting buffer with Stack semantics then you’ll have to wrap it in a Reverse, i.e., let reversed_cursor = Reverse(Cursor::new_at_write_beginning(buf)). This usually only makes sense if you’ve already manually reversed the order of Words in buf. See documentation of Reverse for an example.

This method is called new_at_write_beginning rather than simply new_at_beginning just to avoid confusion around the meaning of the word “beginning”. This doesn’t mean that you must (or even can, necessarily) use the resulting Cursor for writing. But the unqualified word “beginning” would be ambiguous since reading from a Cursor could start (i.e., “begin”) at either boundary of the buffer (depending on the Semantics). By contrast, writing to a Cursor always “begins” at index zero, so “write_beginning” is unambiguous.

pub fn new_at_write_end(buf: Buf) -> Self

where Buf: AsRef<[Word]>,

Creates a Cursor for the buffer buf and initializes the cursor position to point at the end of the buffer.

You can use the resulting cursor, for decoding compressed data with Stack semantics (for example, AnsCoder::from_compressed_slice calls Cursor::new_at_write_end internally).

This method is called new_at_write_end rather than simply new_at_end just to avoid confusion around the meaning of the word “end”. This doesn’t mean that you must (or even can, necessarily) use the resulting Cursor for writing. But the unqualified word “end” would be ambiguous since reading from a Cursor could terminate (i.e., “end”) at either boundary of the buffer (depending on the Semantics). By contrast, writing to a Cursor always “ends” at index .as_ref().len(), so “write_end” is unambiguous.

pub fn new_at_write_end_mut(buf: Buf) -> Self

where Buf: AsMut<[Word]>,

Same as new_at_write_end but for Bufs that implement AsMut but don’t implement AsRef.

You can usually just call new_at_write_end, it will still give you mutable access (i.e., implement WriteWords) if Buf implements AsMut.

pub fn new_at_pos(buf: Buf, pos: usize) -> Result<Self, ()>

where Buf: AsRef<[Word]>,

Creates a Cursor for the buffer buf and initializes the cursor position to point at the given index pos.

You can use the resulting cursor for reading compressed data with both Queue and Stack semantics, or for writing data (if Buf implements AsMut). Reading will automatically advance the cursor position in the correct direction depending on whether the read uses Queue or Stack semantics.

This method is only useful if you want to point the cursor somewhere in the middle of the buffer. If you want to initalize the cursor position at either end of the buffer then calling new_at_write_beginning or new_at_write_end expresses your intent more clearly.

pub fn new_at_pos_mut(buf: Buf, pos: usize) -> Result<Self, ()>

where Buf: AsMut<[Word]>,

Same as new_at_pos but for Bufs that implement AsMut but don’t implement AsRef.

You can usually just call new_at_pos, it will still give you mutable access (i.e., implement WriteWords) if Buf implements AsMut.

pub fn as_view(&self) -> Cursor<Word, &[Word]>

where Buf: AsRef<[Word]>,

Returns a new (read-only) Cursor that shares its buffer with the current Cursor.

The new Cursor is initialized to point at the same position where the current Cursor currently points to, but it can move around independently from the current Cursor. This is a cheaper variant of cloned since it doesn’t copy the data in the buffer.

Note that the lifetime of the new Cursor is tied to the liefetime of &self, so you won’t be able to mutably access the current Cursor while the new Cursor is alive. Unfortunately, this excludes both reading and writing from the current Cursor (since reading and writing mutates the Cursor as it advances its position). If you want to create multiple cursors with the same buffer without copying the buffer, then create a Cursor for a slice &[Word] (e.g., by calling .as_view() once) and then .clone() that Cursor (which won’t clone the contents of the buffer, only the pointer to it):

use constriction::{backends::{Cursor, ReadWords}, Queue};
let data = vec![1, 2, 3, 4];

// Either directly create a `Cursor` for a slice and clone that ...
let mut cursor = Cursor::new_at_write_beginning(&data[..]);
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut cursor), Ok(Some(1)));
let mut cursor_clone = cursor.clone(); // Doesn't clone the data, only the pointer to it.
// `cursor_clone` initially points to the same position as `cursor` but their positions
// advance independently from each other:
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut cursor), Ok(Some(2)));
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut cursor), Ok(Some(3)));
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut cursor_clone), Ok(Some(2)));
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut cursor_clone), Ok(Some(3)));

// ... or, if someone gave you a `Cursor` that owns its buffer, then you can call `.as_view()`
// on it once to get a `Cursor` to a slice, which you can then clone cheaply again.
let mut original = Cursor::new_at_write_beginning(data);
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut original), Ok(Some(1)));
// let mut clone = original.clone(); // <-- This would clone the data, which could be expensive.
let mut view = original.as_view();   // `view` is a `Cursor<u32, &[u32]>`
let mut view_clone = view.clone();   // Doesn't clone the data, only the pointer to it.
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut view), Ok(Some(2)));
assert_eq!(<_ as ReadWords<u32, Queue>>::read(&mut view_clone), Ok(Some(2)));

If we had instead used original while view was still alive then the borrow checker would have complained:

use constriction::{backends::{Cursor, ReadWords}, Queue};
let data = vec![1, 2, 3, 4];
let mut original = Cursor::new_at_write_beginning(data);
let mut view = original.as_view();

<_ as ReadWords<u32, Queue>>::read(&mut original); // Error: mutable borrow occurs here
<_ as ReadWords<u32, Queue>>::read(&mut view);     // immutable borrow later used here

pub fn as_mut_view(&mut self) -> Cursor<Word, &mut [Word]>

where Buf: AsMut<[Word]>,

Same as as_view except that the returned view also implements WriteWords.

pub fn cloned(&self) -> Cursor<Word, Vec<Word>>

where Word: Clone, Buf: AsRef<[Word]>,

Makes a deep copy of the Cursor, copying the data to a new, owned buffer.

If you don’t need ownership over the data then use as_view instead as it is cheaper.

This method is different from Clone::clone because the return type isn’t necessarily identical to Self. If you have a Cursor that doesn’t own its data (for example, a Cursor<Word, &[Word]>), then calling .clone() on it is cheap since it doesn’t copy the data (only the pointer to it), but calling .cloned() is expensive if the buffer is large.

pub fn buf(&self) -> &Buf

Returns a reference to the generic buffer that the Cursor reads from or writes to.

To get the actual slice of Words, call cursor.buf().as_ref().

pub fn buf_mut(&mut self) -> &mut Buf

Returns a mutable reference to the generic buffer that the Cursor reads from or writes to.

Same as buf except that it requires mutable access to self and returns a mutable reference.

To get the actual mutable slice of Words, call cursor.buf().as_mut() (if Buf implements AsMut).

pub fn into_buf_and_pos(self) -> (Buf, usize)

Consumes the Cursor and returns the buffer and the current position.

If you don’t want to consume the Cursor then call buf or buf_mut and pos instead. You’ll have to bring the Pos trait into scope for the last one to work (use constriction::Pos;).

pub fn into_reversed(self) -> Reverse<Self>

where Buf: AsMut<[Word]>,

Reverses both the data and the reading direction.

This method consumes the original Cursor, reverses the order of the Words in-place, updates the cursor position accordingly, and returns a Cursor-like backend that progresses in the opposite direction for reads and/or writes. Reading from and writing to the returned backend will have identical behavior as in the original Cursor backend, but the flipped directions will be observable through Pos::pos, Seek::seek, and Self::buf.

See documentation of Reverse for more information and a usage example.

Trait Implementations

impl<Word: Clone, Buf: AsRef<[Word]>> BoundedReadWords<Word, Queue> for Cursor<Word, Buf>

fn remaining(&self) -> usize

Returns the number of Words that are left for reading.

fn is_exhausted(&self) -> bool

Whether or not there is no data left to read.

impl<Word: Clone, Buf: SafeBuf<Word>> BoundedReadWords<Word, Stack> for Cursor<Word, Buf>

fn remaining(&self) -> usize

Returns the number of Words that are left for reading.

fn is_exhausted(&self) -> bool

Whether or not there is no data left to read.

impl<Word, Buf: AsMut<[Word]> + AsRef<[Word]>> BoundedWriteWords<Word> for Cursor<Word, Buf>

fn space_left(&self) -> usize

Returns the number of Words that one can expect to still be able to write to the data sink.

fn is_full(&self) -> bool

Whether or not there is expected to still be some space left to write.

impl<Word: Clone, Buf: Clone> Clone for Cursor<Word, Buf>

fn clone(&self) -> Cursor<Word, Buf>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Word: Debug, Buf: Debug> Debug for Cursor<Word, Buf>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Word, Buf: AsRef<[Word]>> Pos for Cursor<Word, Buf>

fn pos(&self) -> usize

Returns the position in the compressed data, in units of Words.

impl<Word, Buf> PosSeek for Cursor<Word, Buf>

type Position = usize

impl<Word: Clone, Buf: AsRef<[Word]>> ReadWords<Word, Queue> for Cursor<Word, Buf>

type ReadError = Infallible

The error type that can occur when reading from the data source, or Infallible.

fn read(&mut self) -> Result<Option<Word>, Self::ReadError>

Reads a single Word from the data source and advances the state of the data source accordingly (i.e., so that the next read won’t read the same Word again).

fn maybe_exhausted(&self) -> bool

Returns true if the data source could be out of data.

impl<Word: Clone, Buf: SafeBuf<Word>> ReadWords<Word, Stack> for Cursor<Word, Buf>

type ReadError = Infallible

The error type that can occur when reading from the data source, or Infallible.

fn read(&mut self) -> Result<Option<Word>, Self::ReadError>

Reads a single Word from the data source and advances the state of the data source accordingly (i.e., so that the next read won’t read the same Word again).

fn maybe_exhausted(&self) -> bool

Returns true if the data source could be out of data.

impl<Word, Buf: AsRef<[Word]>> Seek for Cursor<Word, Buf>

fn seek(&mut self, pos: usize) -> Result<(), ()>

Jumps to a given position in the compressed data.

impl<Word, Buf: AsMut<[Word]>> WriteWords<Word> for Cursor<Word, Buf>

type WriteError = BoundedWriteError

The error type that can occur when writing to the data sink, or Infallible.

fn write(&mut self, word: Word) -> Result<(), Self::WriteError>

Writes a single Word to the data sink and advances the state of the data sink accordingly (i.e., so that the next write won’t overwrite the current Word).

fn extend_from_iter( &mut self, iter: impl Iterator<Item = Word> ) -> Result<(), Self::WriteError>

Writes a sequence of Words to the data sink, short-circuiting on error.

fn maybe_full(&self) -> bool

Returns true if the data sink could be full