Trait constriction::backends::BoundedReadWords

pub trait BoundedReadWords<Word, S: Semantics>: ReadWords<Word, S> {
    fn remaining(&self) -> usize;

    fn is_exhausted(&self) -> bool { ... }
}

A trait for data sources that know how much data is left.

Required Methods

fn remaining(&self) -> usize

Returns the number of Words that are left for reading.

If remaining() returns n then the next n calls to read must not return Ok(None), and any subsequent reads must not return Ok(Some(_)).

Provided Methods

fn is_exhausted(&self) -> bool

Whether or not there is no data left to read.

You’ll usually want to overwrite the default implementation of ReadWords::maybe_exhausted to call is_exhausted, although the only strict requirement is that maybe_exhausted must not return false if is_exhausted returns true.

Examples found in repository

src/backends.rs (line 820)

    fn is_exhausted(&self) -> bool {
        self.0.is_exhausted()
    }
}

impl<Word, B: BoundedReadWords<Word, Queue>> BoundedReadWords<Word, Stack> for Reverse<B> {
    #[inline(always)]
    fn remaining(&self) -> usize {
        self.0.remaining()
    }

    #[inline(always)]
    fn is_exhausted(&self) -> bool {
        self.0.is_exhausted()
    }
}

impl<B: PosSeek> PosSeek for Reverse<B> {
    type Position = B::Position;
}

impl<B: Pos> Pos for Reverse<B> {
    /// Delegates the call to the wrapped backend and returns its result without doing any
    /// conversion. This is consistent with the implementaiton of `Seek::sek` for
    /// `Reverse`.
    #[inline(always)]
    fn pos(&self) -> B::Position {
        self.0.pos()
    }
}

impl<B: Seek> Seek for Reverse<B> {
    /// Passes `pos` through to the wrapped backend, i.e., doesn't do any conversion. This
    /// is consistent with the implementation of `Pos::pos` for `Reverse`.
    #[inline(always)]
    fn seek(&mut self, pos: B::Position) -> Result<(), ()> {
        self.0.seek(pos)
    }
}

// ADAPTER FOR IN-MEMORY BUFFERS ==============================================

/// 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:
///
/// ```
/// # use constriction::{
/// #     stream::{model::DefaultLeakyQuantizer, stack::DefaultAnsCoder, Decode},
/// #     CoderError, UnwrapInfallible,
/// # };
/// #
/// 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()
/// }
/// #
/// # let quantizer = DefaultLeakyQuantizer::new(-100..=100);
/// # let model = quantizer.quantize(probability::distribution::Gaussian::new(25.0, 10.0));
/// # let mut coder = DefaultAnsCoder::new();
/// # coder.encode_iid_symbols_reverse(0..100, &model).unwrap();
/// # let compressed = coder.into_compressed().unwrap_infallible();
/// # assert!(decode_shared_data(100, &compressed).iter().cloned().eq(0..100));
/// ```
///
/// ## 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))
/// );
/// ```
///
/// [`RangeDecoder`]: crate::stream::queue::RangeDecoder
/// [`AnsCoder`]: crate::stream::stack::AnsCoder
#[derive(Clone, Debug)]
pub struct Cursor<Word, Buf> {
    buf: Buf,

    /// The index of the next word to be read with a `ReadWords<Word, Queue>` or written
    /// with a `WriteWords<Word>, and one plus the index of the next word to read with
    /// `ReadWords<Word, Stack>.
    ///
    /// Satisfies the invariant `pos <= buf.as_ref().len()` if `Buf: AsRef<[Word]>` (see
    /// unsafe trait `SafeBuf`).
    pos: usize,

    phantom: PhantomData<Word>,
}

/// Unsafe marker trait indicating sane implementation of `AsRef` (and possibly `AsMut`).
///
/// By implementing `SafeBuf<Word>` for a type `T`, you guarantee that
/// - calling `x.as_ref()` for some `x: T` several times in a row (with no other method
///   calls on `x` in-between) never returns slices of decreasing length; and
/// - if `T` implements `AsMut<[Word]>` then the above property must also hold for any
///   sequence of calls of `x.as_ref()` and `x.as_mut()`, and the lengths of slices returned
///   by either of these calls must not decrease.
///
/// This is very likely the behaviour you would expect anyway for `AsRef` and `AsMut`. This
/// guarantee allows the implementation of `ReadWords<Word, Stack>` for [`Cursor`] to elide
/// an additional pedantic bounds check by maintaining an in-bounds invariant on its index
/// into the buffer.
///
/// # Safety
///
/// If `SafeBuf` is implemented for a type `Buf` that violates the above contract then the
/// implementations of `ReadWords<Word, Stack>::read` for `Cursor<Word, Buf>` and of
/// `WriteWords<Word>` for `Reverse<Cursor<Word, Buf>>` may attempt to access the buffer out
/// of bounds without bounds checks.
pub unsafe trait SafeBuf<Word>: AsRef<[Word]> {}

unsafe impl<'a, Word> SafeBuf<Word> for &'a [Word] {}
unsafe impl<'a, Word> SafeBuf<Word> for &'a mut [Word] {}
unsafe impl<Word> SafeBuf<Word> for Vec<Word> {}
unsafe impl<Word> SafeBuf<Word> for Box<[Word]> {}

impl<Word, Buf> Cursor<Word, Buf> {
    /// 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.
    ///
    /// [`RangeDecoder::from_compressed`]:
    /// crate::stream::queue::RangeDecoder::from_compressed
    #[inline(always)]
    pub fn new_at_write_beginning(buf: Buf) -> Self {
        Self {
            buf,
            pos: 0,
            phantom: PhantomData,
        }
    }

    /// 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.
    ///
    /// [`AnsCoder::from_compressed_slice`]:
    /// crate::stream::stack::AnsCoder::from_compressed_slice
    #[inline(always)]
    pub fn new_at_write_end(buf: Buf) -> Self
    where
        Buf: AsRef<[Word]>,
    {
        let pos = buf.as_ref().len();
        Self {
            buf,
            pos,
            phantom: PhantomData,
        }
    }

    /// 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`.
    ///
    /// [`new_at_write_end`]: Self::new_at_write_end
    #[inline(always)]
    pub fn new_at_write_end_mut(mut buf: Buf) -> Self
    where
        Buf: AsMut<[Word]>,
    {
        let pos = buf.as_mut().len();
        Self {
            buf,
            pos,
            phantom: PhantomData,
        }
    }

    /// 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.
    ///
    /// [`new_at_write_beginning`]: Self::new_at_write_beginning
    /// [`new_at_write_end`]: Self::new_at_write_end
    #[allow(clippy::result_unit_err)]
    pub fn new_at_pos(buf: Buf, pos: usize) -> Result<Self, ()>
    where
        Buf: AsRef<[Word]>,
    {
        if pos > buf.as_ref().len() {
            Err(())
        } else {
            Ok(Self {
                buf,
                pos,
                phantom: PhantomData,
            })
        }
    }

    /// 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`.
    ///
    /// [`new_at_pos`]: Self::new_at_pos
    #[allow(clippy::result_unit_err)]
    pub fn new_at_pos_mut(mut buf: Buf, pos: usize) -> Result<Self, ()>
    where
        Buf: AsMut<[Word]>,
    {
        if pos > buf.as_mut().len() {
            Err(())
        } else {
            Ok(Self {
                buf,
                pos,
                phantom: PhantomData,
            })
        }
    }

    /// 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:
    ///
    /// ```compile_fail
    /// 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
    /// ```
    ///
    /// [`cloned`]: Self::cloned
    pub fn as_view(&self) -> Cursor<Word, &[Word]>
    where
        Buf: AsRef<[Word]>,
    {
        Cursor {
            buf: self.buf.as_ref(),
            pos: self.pos,
            phantom: PhantomData,
        }
    }

    /// Same as [`as_view`] except that the returned view also implements [`WriteWords`].
    ///
    /// [`as_view`]: Self::as_view
    pub fn as_mut_view(&mut self) -> Cursor<Word, &mut [Word]>
    where
        Buf: AsMut<[Word]>,
    {
        Cursor {
            buf: self.buf.as_mut(),
            pos: self.pos,
            phantom: PhantomData,
        }
    }

    /// 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.
    ///
    /// [`as_view`]: Self::as_view
    pub fn cloned(&self) -> Cursor<Word, Vec<Word>>
    where
        Word: Clone,
        Buf: AsRef<[Word]>,
    {
        Cursor {
            buf: self.buf.as_ref().to_vec(),
            pos: self.pos,
            phantom: PhantomData,
        }
    }

    /// 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()`.
    pub fn buf(&self) -> &Buf {
        &self.buf
    }

    /// Returns a mutable reference to the generic buffer that the `Cursor` reads from or
    /// writes to.
    ///
    /// Same as [`buf`](Self::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`).
    pub fn buf_mut(&mut self) -> &mut Buf {
        &mut self.buf
    }

    /// Consumes the `Cursor` and returns the buffer and the current position.
    ///
    /// If you don't want to consume the `Cursor` then call [`buf`](Self::buf) or
    /// [`buf_mut`](Self::buf_mut) and [`pos`](Pos::pos) instead. You'll have to bring the
    /// [`Pos`] trait into scope for the last one to work (`use constriction::Pos;`).
    pub fn into_buf_and_pos(self) -> (Buf, usize) {
        (self.buf, self.pos)
    }

    /// 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.
    pub fn into_reversed(mut self) -> Reverse<Self>
    where
        Buf: AsMut<[Word]>,
    {
        self.buf.as_mut().reverse();
        self.pos = self.buf.as_mut().len() - self.pos;
        Reverse(self)
    }
}

impl<Word, Buf> Reverse<Cursor<Word, Buf>> {
    /// Reverses both the data and the reading direction.
    ///
    /// This is essentially the same as [`Cursor::into_reversed`], except that, rather than
    /// wrapping yet another `Reverse` around the `Cursor`, the last step of this method
    /// just removes the existing `Reverse` wrapper, which has the same effect.
    ///
    /// See documentation of [`Reverse`] for more information and a usage example.
    #[inline(always)]
    pub fn into_reversed(self) -> Cursor<Word, Buf>
    where
        Buf: AsMut<[Word]>,
    {
        // Accessing `.0` twice removes *two* `Reverse`, resulting in no semantic change.
        self.0.into_reversed().0
    }
}

impl<Word, Buf: AsMut<[Word]>> WriteWords<Word> for Cursor<Word, Buf> {
    type WriteError = BoundedWriteError;

    #[inline(always)]
    fn write(&mut self, word: Word) -> Result<(), Self::WriteError> {
        if let Some(target) = self.buf.as_mut().get_mut(self.pos) {
            *target = word;
            self.pos += 1;
            Ok(())
        } else {
            Err(BoundedWriteError::OutOfSpace)
        }
    }
}

impl<Word, Buf: AsMut<[Word]> + AsRef<[Word]>> BoundedWriteWords<Word> for Cursor<Word, Buf> {
    #[inline(always)]
    fn space_left(&self) -> usize {
        self.buf.as_ref().len() - self.pos
    }
}

impl<Word, Buf: SafeBuf<Word> + AsMut<[Word]>> WriteWords<Word> for Reverse<Cursor<Word, Buf>> {
    type WriteError = BoundedWriteError;

    #[inline(always)]
    fn write(&mut self, word: Word) -> Result<(), Self::WriteError> {
        if self.0.pos == 0 {
            Err(BoundedWriteError::OutOfSpace)
        } else {
            self.0.pos -= 1;
            unsafe {
                // SAFETY: We maintain the invariant `self.0.pos <= self.0.buf.as_mut().len()`
                // and we just decreased `self.0.pos` (and made sure that didn't wrap around),
                // so we now have `self.0.pos < self.0.buf.as_mut().len()`.
                *self.0.buf.as_mut().get_unchecked_mut(self.0.pos) = word;
                Ok(())
            }
        }
    }
}

impl<Word, Buf: SafeBuf<Word> + AsMut<[Word]>> BoundedWriteWords<Word>
    for Reverse<Cursor<Word, Buf>>
{
    #[inline(always)]
    fn space_left(&self) -> usize {
        self.0.buf.as_ref().len()
    }
}

/// Error type for data sinks with a finite capacity.
///
/// This is currently used as the `WriteError` in the [implementation of `WriteWords` for
/// `Cursor`](struct.Cursor.html#impl-WriteWords<Word>) but it should also be used in the
/// implementation of [`WriteWords`] for custom types where appropriate.
///
/// If you use this error type for a data sink then you may also want to implement
/// [`BoundedWriteWords`] for it (if the capacity is known upfront).
#[derive(Debug, Clone, Eq, PartialEq)]
pub enum BoundedWriteError {
    /// Attempting to write compressed data failed because it would exceeded the finite
    /// capacity of the data sink.
    OutOfSpace,
}

impl Display for BoundedWriteError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            Self::OutOfSpace => write!(f, "Out of space."),
        }
    }
}

#[cfg(feature = "std")]
impl std::error::Error for BoundedWriteError {}

impl<Word: Clone, Buf: SafeBuf<Word>> ReadWords<Word, Stack> for Cursor<Word, Buf> {
    type ReadError = Infallible;

    #[inline(always)]
    fn read(&mut self) -> Result<Option<Word>, Self::ReadError> {
        if self.pos == 0 {
            Ok(None)
        } else {
            self.pos -= 1;
            unsafe {
                // SAFETY: We maintain the invariant `self.pos <= self.buf.as_ref().len()`
                // and we just decreased `self.pos` (and made sure that didn't wrap around),
                // so we now have `self.pos < self.buf.as_ref().len()`.
                Ok(Some(self.buf.as_ref().get_unchecked(self.pos).clone()))
            }
        }
    }

    #[inline(always)]
    fn maybe_exhausted(&self) -> bool {
        BoundedReadWords::<Word, Stack>::is_exhausted(self)
    }
}

impl<Word: Clone, Buf: AsRef<[Word]>> ReadWords<Word, Queue> for Cursor<Word, Buf> {
    type ReadError = Infallible;

    #[inline(always)]
    fn read(&mut self) -> Result<Option<Word>, Self::ReadError> {
        let maybe_word = self.buf.as_ref().get(self.pos).cloned();
        if maybe_word.is_some() {
            self.pos += 1;
        }
        Ok(maybe_word)
    }

    #[inline(always)]
    fn maybe_exhausted(&self) -> bool {
        BoundedReadWords::<Word, Queue>::is_exhausted(self)
    }

src/symbol/mod.rs (line 227)

    pub fn is_empty(&self) -> bool
    where
        B: BoundedReadWords<Word, Stack>,
    {
        self.mask_last_written == Word::zero() && self.backend.is_exhausted()
    }
}

// SPECIAL IMPLEMENTATIONS FOR VEC ============================================

impl<Word: BitArray> StackCoder<Word, Vec<Word>> {
    pub fn with_bit_capacity(bit_capacity: usize) -> Self {
        Self {
            // Reserve capacity for one additional bit for sealing.
            backend: Vec::with_capacity(bit_capacity / Word::BITS + 1),
            ..Default::default()
        }
    }

    pub fn get_compressed(&mut self) -> StackCoderGuard<'_, Word> {
        StackCoderGuard::new(self)
    }
}

impl<Word: BitArray> QueueEncoder<Word, Vec<Word>> {
    pub fn with_bit_capacity(bit_capacity: usize) -> Self {
        Self {
            backend: Vec::with_capacity((bit_capacity + Word::BITS - 1) / Word::BITS),
            ..Default::default()
        }
    }

    pub fn get_compressed(&mut self) -> QueueEncoderGuard<'_, Word> {
        QueueEncoderGuard::new(self)
    }
}

#[derive(Debug)]
pub struct StackCoderGuard<'a, Word: BitArray> {
    inner: &'a mut StackCoder<Word, Vec<Word>>,
}

impl<'a, Word: BitArray> StackCoderGuard<'a, Word> {
    fn new(stack_coder: &'a mut StackCoder<Word, Vec<Word>>) -> Self {
        // Stacks need to be sealed by one additional bit so that the end can be discovered.
        stack_coder.write_bit(true).unwrap_infallible();
        if stack_coder.mask_last_written != Word::zero() {
            stack_coder.backend.push(stack_coder.current_word);
        }
        Self { inner: stack_coder }
    }
}

impl<'a, Word: BitArray> Drop for StackCoderGuard<'a, Word> {
    fn drop(&mut self) {
        if self.inner.mask_last_written != Word::zero() {
            self.inner.backend.pop();
        }
        self.inner.read_bit().expect("The constructor wrote a bit.");
    }
}

impl<'a, Word: BitArray> Deref for StackCoderGuard<'a, Word> {
    type Target = [Word];

    fn deref(&self) -> &Self::Target {
        &self.inner.backend
    }
}

#[derive(Debug)]
pub struct QueueEncoderGuard<'a, Word: BitArray> {
    inner: &'a mut QueueEncoder<Word, Vec<Word>>,
}

impl<'a, Word: BitArray> QueueEncoderGuard<'a, Word> {
    fn new(queue_encoder: &'a mut QueueEncoder<Word, Vec<Word>>) -> Self {
        // Queues don't need to be sealed, so just flush the remaining word if any.
        if queue_encoder.mask_last_written != Word::zero() {
            queue_encoder.backend.push(queue_encoder.current_word);
        }
        Self {
            inner: queue_encoder,
        }
    }
}

impl<'a, Word: BitArray> Drop for QueueEncoderGuard<'a, Word> {
    fn drop(&mut self) {
        if self.inner.mask_last_written != Word::zero() {
            self.inner.backend.pop();
        }
    }
}

impl<'a, Word: BitArray> Deref for QueueEncoderGuard<'a, Word> {
    type Target = [Word];

    fn deref(&self) -> &Self::Target {
        &self.inner.backend
    }
}

// IMPLEMENTATIONS FOR A QUEUE ================================================

impl<Word: BitArray, B> QueueEncoder<Word, B> {
    pub fn from_compressed(compressed: B) -> Self
    where
        B: Default,
    {
        Self {
            backend: compressed,
            ..Default::default()
        }
    }

    pub fn into_decoder(self) -> Result<QueueDecoder<Word, B::IntoReadWords>, B::WriteError>
    where
        B: WriteWords<Word> + IntoReadWords<Word, Queue>,
    {
        Ok(QueueDecoder::from_compressed(
            self.into_compressed()?.into_read_words(),
        ))
    }

    pub fn into_compressed(mut self) -> Result<B, B::WriteError>
    where
        B: WriteWords<Word>,
    {
        // Queues don't need to be sealed, so just flush the remaining word if any.
        if self.mask_last_written != Word::zero() {
            self.backend.write(self.current_word)?;
        }
        Ok(self.backend)
    }

    pub fn into_overshooting_iter(
        self,
    ) -> Result<
        impl Iterator<Item = Result<bool, <B::IntoReadWords as ReadWords<Word, Queue>>::ReadError>>,
        B::WriteError,
    >
    where
        B: WriteWords<Word> + IntoReadWords<Word, Queue>,
    {
        // TODO: return `impl ExactSizeIterator` for `B: BoundedReadWords` once
        // specialization is stable
        self.into_decoder()
    }
}

impl<Word: BitArray, B: WriteWords<Word>> WriteBitStream<Queue> for QueueEncoder<Word, B> {
    type WriteError = B::WriteError;

    fn write_bit(&mut self, bit: bool) -> Result<(), Self::WriteError> {
        let write_mask = self.mask_last_written << 1;
        self.mask_last_written = if write_mask != Word::zero() {
            let new_bit = if bit { write_mask } else { Word::zero() };
            self.current_word = self.current_word | new_bit;
            write_mask
        } else {
            if self.mask_last_written != Word::zero() {
                self.backend.write(self.current_word)?;
            }
            self.current_word = if bit { Word::one() } else { Word::zero() };
            Word::one()
        };

        Ok(())
    }

    #[inline(always)]
    fn encode_symbol<Symbol, C>(
        &mut self,
        symbol: Symbol,
        codebook: C,
    ) -> Result<(), DefaultEncoderError<Self::WriteError>>
    where
        C: EncoderCodebook,
        Symbol: Borrow<C::Symbol>,
    {
        codebook.encode_symbol_prefix(symbol, |bit| self.write_bit(bit))
    }
}

impl<Word: BitArray, B> QueueDecoder<Word, B> {
    pub fn from_compressed(compressed: B) -> Self {
        Self {
            backend: compressed,
            current_word: Word::zero(),
            mask_next_to_read: Word::zero(),
        }
    }

    /// We don't keep track of the exact length of a queue, so we can only say with
    /// certainty if we can detect that there's something left.
    pub fn maybe_exhausted(&self) -> bool
    where
        B: BoundedReadWords<Word, Queue>,
    {
        let mask_remaining_bits = !self.mask_next_to_read.wrapping_sub(&Word::one());
        self.current_word & mask_remaining_bits == Word::zero() && self.backend.is_exhausted()
    }

src/stream/queue.rs (line 267)

    pub fn is_empty<'a>(&'a self) -> bool
    where
        Backend: AsReadWords<'a, Word, Queue>,
        Backend::AsReadWords: BoundedReadWords<Word, Queue>,
    {
        self.state.range.get() == State::max_value() && self.bulk.as_read_words().is_exhausted()
    }

Implementations on Foreign Types

impl<Word> BoundedReadWords<Word, Stack> for Vec<Word>

fn remaining(&self) -> usize

impl<Array> BoundedReadWords<<Array as Array>::Item, Stack> for SmallVec<Array>where
    Array: Array,

fn remaining(&self) -> usize

Implementors

impl<Iter, S, Word> BoundedReadWords<Word, S> for FallibleIteratorReadWords<Iter>where
    Self: ReadWords<Word, S>,
    Iter: ExactSizeIterator,
    S: Semantics,

impl<Iter, S, Word> BoundedReadWords<Word, S> for InfallibleIteratorReadWords<Iter>where
    Self: ReadWords<Word, S>,
    Iter: ExactSizeIterator,
    S: Semantics,

impl<Word, B: BoundedReadWords<Word, Queue>> BoundedReadWords<Word, Stack> for Reverse<B>

impl<Word, B: BoundedReadWords<Word, Stack>> BoundedReadWords<Word, Queue> for Reverse<B>

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

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