Struct constriction::backends::Cursor
source · pub struct Cursor<Word, Buf> { /* private fields */ }
Expand description
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 Word
s
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 Word
s, 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 Word
s 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());
Cursor
s 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 Cursor
s vs Vec
s
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§
source§impl<Word, Buf> Cursor<Word, Buf>
impl<Word, Buf> Cursor<Word, Buf>
sourcepub fn new_at_write_beginning(buf: Buf) -> Self
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 Word
s 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 Word
s 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.
sourcepub fn new_at_write_end(buf: Buf) -> Self
pub fn new_at_write_end(buf: Buf) -> Self
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.
sourcepub fn new_at_write_end_mut(buf: Buf) -> Self
pub fn new_at_write_end_mut(buf: Buf) -> Self
Same as new_at_write_end
but for Buf
s 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
.
sourcepub fn new_at_pos(buf: Buf, pos: usize) -> Result<Self, ()>
pub fn new_at_pos(buf: Buf, pos: usize) -> Result<Self, ()>
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.
sourcepub fn new_at_pos_mut(buf: Buf, pos: usize) -> Result<Self, ()>
pub fn new_at_pos_mut(buf: Buf, pos: usize) -> Result<Self, ()>
Same as new_at_pos
but for Buf
s 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
.
sourcepub fn as_view(&self) -> Cursor<Word, &[Word]>
pub fn as_view(&self) -> Cursor<Word, &[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
sourcepub fn as_mut_view(&mut self) -> Cursor<Word, &mut [Word]>
pub fn as_mut_view(&mut self) -> Cursor<Word, &mut [Word]>
Same as as_view
except that the returned view also implements WriteWords
.
sourcepub fn cloned(&self) -> Cursor<Word, Vec<Word>>
pub fn cloned(&self) -> Cursor<Word, Vec<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.
sourcepub fn buf(&self) -> &Buf
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 Word
s, call cursor.buf().as_ref()
.
sourcepub fn buf_mut(&mut self) -> &mut Buf
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 Word
s, call cursor.buf().as_mut()
(if Buf
implements AsMut
).
sourcepub fn into_buf_and_pos(self) -> (Buf, usize)
pub fn into_buf_and_pos(self) -> (Buf, usize)
sourcepub fn into_reversed(self) -> Reverse<Self>
pub fn into_reversed(self) -> Reverse<Self>
Reverses both the data and the reading direction.
This method consumes the original Cursor
, reverses the order of the Word
s
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§
source§impl<Word: Clone, Buf: AsRef<[Word]>> ReadWords<Word, Queue> for Cursor<Word, Buf>
impl<Word: Clone, Buf: AsRef<[Word]>> ReadWords<Word, Queue> for Cursor<Word, Buf>
§type ReadError = Infallible
type ReadError = Infallible
Infallible
. Read moresource§fn read(&mut self) -> Result<Option<Word>, Self::ReadError>
fn read(&mut self) -> Result<Option<Word>, Self::ReadError>
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). Read moresource§fn maybe_exhausted(&self) -> bool
fn maybe_exhausted(&self) -> bool
true
if the data source could be out of data. Read moresource§impl<Word: Clone, Buf: SafeBuf<Word>> ReadWords<Word, Stack> for Cursor<Word, Buf>
impl<Word: Clone, Buf: SafeBuf<Word>> ReadWords<Word, Stack> for Cursor<Word, Buf>
§type ReadError = Infallible
type ReadError = Infallible
Infallible
. Read moresource§fn read(&mut self) -> Result<Option<Word>, Self::ReadError>
fn read(&mut self) -> Result<Option<Word>, Self::ReadError>
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). Read moresource§fn maybe_exhausted(&self) -> bool
fn maybe_exhausted(&self) -> bool
true
if the data source could be out of data. Read moresource§impl<Word, Buf: AsMut<[Word]>> WriteWords<Word> for Cursor<Word, Buf>
impl<Word, Buf: AsMut<[Word]>> WriteWords<Word> for Cursor<Word, Buf>
§type WriteError = BoundedWriteError
type WriteError = BoundedWriteError
Infallible
. Read moresource§fn write(&mut self, word: Word) -> Result<(), Self::WriteError>
fn write(&mut self, word: Word) -> Result<(), Self::WriteError>
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
).source§fn extend_from_iter(
&mut self,
iter: impl Iterator<Item = Word>
) -> Result<(), Self::WriteError>
fn extend_from_iter( &mut self, iter: impl Iterator<Item = Word> ) -> Result<(), Self::WriteError>
Word
s to the data sink, short-circuiting on error. Read moresource§fn maybe_full(&self) -> bool
fn maybe_full(&self) -> bool
true
if the data sink could be full Read more