Struct sized_chunks::sized_chunk::Chunk

pub struct Chunk<A, N = U64> where
    N: ChunkLength<A>,  { /* fields omitted */ }

A fixed capacity smart array.

An inline array of items with a variable length but a fixed, preallocated capacity given by the N type, which must be an Unsigned type level numeral.

It's 'smart' because it's able to reorganise its contents based on expected behaviour. If you construct one using push_back, it will be laid out like a Vec with space at the end. If you push_front it will start filling in values from the back instead of the front, so that you still get linear time push as long as you don't reverse direction. If you do, and there's no room at the end you're pushing to, it'll shift its contents over to the other side, creating more space to push into. This technique is tuned for Chunk's expected use case in im::Vector: usually, chunks always see either push_front or push_back, but not both unless they move around inside the tree, in which case they're able to reorganise themselves with reasonable efficiency to suit their new usage patterns.

It maintains a left index and a right index instead of a simple length counter in order to accomplish this, much like a ring buffer would, except that the Chunk keeps all its items sequentially in memory so that you can always get a &[A] slice for them, at the price of the occasional reordering operation. The allocated size of a Chunk is thus usize * 2 + A * N.

This technique also lets us choose to shift the shortest side to account for the inserted or removed element when performing insert and remove operations, unlike Vec where you always need to shift the right hand side.

Unlike a Vec, the Chunk has a fixed capacity and cannot grow beyond it. Being intended for low level use, it expects you to know or test whether you're pushing to a full array, and has an API more geared towards panics than returning Options, on the assumption that you know what you're doing. Of course, if you don't, you can expect it to panic immediately rather than do something undefined and usually bad.

Isn't this just a less efficient ring buffer?

You might be wondering why you would want to use this data structure rather than a RingBuffer, which is similar but doesn't need to shift its content around when it hits the sides of the allocated buffer. The answer is that Chunk can be dereferenced into a slice, while a ring buffer can not. You'll also save a few cycles on index lookups, as a Chunk's data is guaranteed to be contiguous in memory, so there's no need to remap logical indices to a ring buffer's physical layout.

Examples

// Construct a chunk with a 64 item capacity
let mut chunk = Chunk::<i32, U64>::new();
// Fill it with descending numbers
chunk.extend((0..64).rev());
// It derefs to a slice so we can use standard slice methods
chunk.sort();
// It's got all the amenities like `FromIterator` and `Eq`
let expected: Chunk<i32, U64> = (0..64).collect();
assert_eq!(expected, chunk);

Methods

impl<A, N> Chunk<A, N> where
    N: ChunkLength<A>, 

pub const CAPACITY: usize

The maximum number of elements this Chunk can contain.

pub fn new() -> Self

Construct a new empty chunk.

pub fn unit(value: A) -> Self

Construct a new chunk with one item.

pub fn pair(left: A, right: A) -> Self

Construct a new chunk with two items.

pub fn drain_from(other: &mut Self) -> Self

Construct a new chunk and move every item from other into the new chunk.

Time: O(n)

pub fn collect_from<I>(iter: &mut I, count: usize) -> Self where
    I: Iterator<Item = A>, 

Construct a new chunk and populate it by taking count items from the iterator iter.

Panics if the iterator contains less than count items.

Time: O(n)

pub fn from_front(other: &mut Self, count: usize) -> Self

Construct a new chunk and populate it by taking count items from the front of other.

Time: O(n) for the number of items moved

pub fn from_back(other: &mut Self, count: usize) -> Self

Construct a new chunk and populate it by taking count items from the back of other.

Time: O(n) for the number of items moved

pub fn len(&self) -> usize

Get the length of the chunk.

pub fn is_empty(&self) -> bool

Test if the chunk is empty.

pub fn is_full(&self) -> bool

Test if the chunk is at capacity.

pub fn push_front(&mut self, value: A)

Push an item to the front of the chunk.

Panics if the capacity of the chunk is exceeded.

Time: O(1) if there's room at the front, O(n) otherwise

pub fn push_back(&mut self, value: A)

Push an item to the back of the chunk.

Panics if the capacity of the chunk is exceeded.

Time: O(1) if there's room at the back, O(n) otherwise

pub fn pop_front(&mut self) -> A

Pop an item off the front of the chunk.

Panics if the chunk is empty.

Time: O(1)

pub fn pop_back(&mut self) -> A

Pop an item off the back of the chunk.

Panics if the chunk is empty.

Time: O(1)

pub fn drop_left(&mut self, index: usize)

Discard all items up to but not including index.

Panics if index is out of bounds.

Time: O(n) for the number of items dropped

pub fn drop_right(&mut self, index: usize)

Discard all items from index onward.

Panics if index is out of bounds.

Time: O(n) for the number of items dropped

pub fn split_off(&mut self, index: usize) -> Self

Split a chunk into two, the original chunk containing everything up to index and the returned chunk containing everything from index onwards.

Panics if index is out of bounds.

Time: O(n) for the number of items in the new chunk

pub fn append(&mut self, other: &mut Self)

Remove all items from other and append them to the back of self.

Panics if the capacity of the chunk is exceeded.

Time: O(n) for the number of items moved

pub fn drain_from_front(&mut self, other: &mut Self, count: usize)

Remove count items from the front of other and append them to the back of self.

Panics if self doesn't have count items left, or if other has fewer than count items.

Time: O(n) for the number of items moved

pub fn drain_from_back(&mut self, other: &mut Self, count: usize)

Remove count items from the back of other and append them to the front of self.

Panics if self doesn't have count items left, or if other has fewer than count items.

Time: O(n) for the number of items moved

pub fn set(&mut self, index: usize, value: A) -> A

Update the value at index index, returning the old value.

Panics if index is out of bounds.

Time: O(1)

pub fn insert(&mut self, index: usize, value: A)

Insert a new value at index index, shifting all the following values to the right.

Panics if the index is out of bounds or the chunk is full.

Time: O(n) for the number of elements shifted

pub fn insert_ordered(&mut self, value: A) where
    A: Ord, 

Insert a new value into the chunk in sorted order.

This assumes every element of the chunk is already in sorted order. If not, the value will still be inserted but the ordering is not guaranteed.

Time: O(log n) to find the insert position, then O(n) for the number of elements shifted.

Examples

let mut chunk = Chunk::<i32, U64>::from_iter(0..5);
chunk.insert_ordered(3);
assert_eq!(&[0, 1, 2, 3, 3, 4], chunk.as_slice());

pub fn insert_from<Iterable, I>(&mut self, index: usize, iter: Iterable) where
    Iterable: IntoIterator<Item = A, IntoIter = I>,
    I: ExactSizeIterator<Item = A>, 

Insert multiple values at index index, shifting all the following values to the right.

Panics if the index is out of bounds or the chunk doesn't have room for all the values.

Time: O(m+n) where m is the number of elements inserted and n is the number of elements following the insertion index. Calling insert repeatedly would be O(m*n).

pub fn remove(&mut self, index: usize) -> A

Remove the value at index index, shifting all the following values to the left.

Returns the removed value.

Panics if the index is out of bounds.

Time: O(n) for the number of items shifted

pub fn drain(&mut self) -> Drain<A, N>

Construct an iterator that drains values from the front of the chunk.

pub fn clear(&mut self)

Discard the contents of the chunk.

Time: O(n)

pub fn as_slice(&self) -> &[A]

Get a reference to the contents of the chunk as a slice.

pub fn as_mut_slice(&mut self) -> &mut [A]

Get a reference to the contents of the chunk as a mutable slice.

Trait Implementations

impl<A, N> Arbitrary for Chunk<A, N> where
    A: Arbitrary,
    N: ChunkLength<A> + 'static, 

fn arbitrary(u: &mut Unstructured) -> Result<Self>

Generate an arbitrary value of Self from the given unstructured data.

fn arbitrary_take_rest(u: Unstructured) -> Result<Self>

Generate an arbitrary value of Self from the entirety of the given unstructured data.

fn size_hint(depth: usize) -> (usize, Option<usize>)

Get a size hint for how many bytes out of an Unstructured this type needs to construct itself.

fn shrink(&self) -> Box<dyn Iterator<Item = Self>>

Generate an iterator of derived values which are "smaller" than the original self instance.

impl<A, N> AsMut<[A]> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn as_mut(&mut self) -> &mut [A]

Performs the conversion.

impl<A, N> AsRef<[A]> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn as_ref(&self) -> &[A]

Performs the conversion.

impl<A, N> Borrow<[A]> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn borrow(&self) -> &[A]

Immutably borrows from an owned value.

impl<A, N> BorrowMut<[A]> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn borrow_mut(&mut self) -> &mut [A]

Mutably borrows from an owned value.

impl<A, N> Clone for Chunk<A, N> where
    A: Clone,
    N: ChunkLength<A>, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A, N> Debug for Chunk<A, N> where
    A: Debug,
    N: ChunkLength<A>, 

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

Formats the value using the given formatter.

impl<A, N> Default for Chunk<A, N> where
    N: ChunkLength<A>, 

fn default() -> Self

Returns the "default value" for a type.

impl<A, N> Deref for Chunk<A, N> where
    N: ChunkLength<A>, 

type Target = [A]

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<A, N> DerefMut for Chunk<A, N> where
    N: ChunkLength<A>, 

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<A, N> Drop for Chunk<A, N> where
    N: ChunkLength<A>, 

fn drop(&mut self)

Executes the destructor for this type.

impl<A, N> Eq for Chunk<A, N> where
    A: Eq,
    N: ChunkLength<A>, 

impl<'a, A, N> Extend<&'a A> for Chunk<A, N> where
    A: 'a + Copy,
    N: ChunkLength<A>, 

fn extend<I>(&mut self, it: I) where
    I: IntoIterator<Item = &'a A>, 

Append the contents of the iterator to the back of the chunk.

Panics if the chunk exceeds its capacity.

Time: O(n) for the length of the iterator

impl<A, N> Extend<A> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn extend<I>(&mut self, it: I) where
    I: IntoIterator<Item = A>, 

Append the contents of the iterator to the back of the chunk.

Panics if the chunk exceeds its capacity.

Time: O(n) for the length of the iterator

impl<'a, A, N, T> From<&'a mut InlineArray<A, T>> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn from(array: &mut InlineArray<A, T>) -> Self

Performs the conversion.

impl<A, N, T> From<InlineArray<A, T>> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn from(array: InlineArray<A, T>) -> Self

Performs the conversion.

impl<A, N> FromIterator<A> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn from_iter<I>(it: I) -> Self where
    I: IntoIterator<Item = A>, 

Creates a value from an iterator.

impl<A, N> Hash for Chunk<A, N> where
    A: Hash,
    N: ChunkLength<A>, 

fn hash<H>(&self, hasher: &mut H) where
    H: Hasher, 

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<A, N, I> Index<I> for Chunk<A, N> where
    I: SliceIndex<[A]>,
    N: ChunkLength<A>, 

type Output = I::Output

The returned type after indexing.

fn index(&self, index: I) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<A, N, I> IndexMut<I> for Chunk<A, N> where
    I: SliceIndex<[A]>,
    N: ChunkLength<A>, 

fn index_mut(&mut self, index: I) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, A, N> IntoIterator for &'a Chunk<A, N> where
    N: ChunkLength<A>, 

type Item = &'a A

The type of the elements being iterated over.

type IntoIter = SliceIter<'a, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A, N> IntoIterator for &'a mut Chunk<A, N> where
    N: ChunkLength<A>, 

type Item = &'a mut A

The type of the elements being iterated over.

type IntoIter = SliceIterMut<'a, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A, N> IntoIterator for Chunk<A, N> where
    N: ChunkLength<A>, 

type Item = A

The type of the elements being iterated over.

type IntoIter = Iter<A, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A, N> Ord for Chunk<A, N> where
    A: Ord,
    N: ChunkLength<A>, 

fn cmp(&self, other: &Self) -> Ordering

This method returns an [Ordering] between self and other.

#[must_use] fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use] fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use] fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl<A, N, Slice> PartialEq<Slice> for Chunk<A, N> where
    Slice: Borrow<[A]>,
    A: PartialEq,
    N: ChunkLength<A>, 

fn eq(&self, other: &Slice) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A, N> PartialOrd<Chunk<A, N>> for Chunk<A, N> where
    A: PartialOrd,
    N: ChunkLength<A>, 

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use] fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use] fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use] fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use] fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<A, N> PoolClone for Chunk<A, N> where
    A: Clone,
    N: ChunkLength<A>, 

unsafe fn clone_uninit(&self, target: &mut MaybeUninit<Self>)

Clone an instance of Self into an uninitialised instance of Self.

impl<A, N> PoolDefault for Chunk<A, N> where
    N: ChunkLength<A>, 

unsafe fn default_uninit(target: &mut MaybeUninit<Self>)

Initialise an instance of Self to its default state.

impl<N: ChunkLength<u8>> Read for Chunk<u8, N>

fn read(&mut self, buf: &mut [u8]) -> Result<usize>

Pull some bytes from this source into the specified buffer, returning how many bytes were read.

fn read_vectored(&mut self, bufs: &mut [IoSliceMut]) -> Result<usize, Error>

Like read, except that it reads into a slice of buffers.

unsafe fn initializer(&self) -> Initializer

🔬 This is a nightly-only experimental API. (read_initializer)

Determines if this Reader can work with buffers of uninitialized memory.

fn read_to_end(&mut self, buf: &mut Vec<u8>) -> Result<usize, Error>

Read all bytes until EOF in this source, placing them into buf.

fn read_to_string(&mut self, buf: &mut String) -> Result<usize, Error>

Read all bytes until EOF in this source, appending them to buf.

fn read_exact(&mut self, buf: &mut [u8]) -> Result<(), Error>

Read the exact number of bytes required to fill buf.

fn by_ref(&mut self) -> &mut Self

Creates a "by reference" adaptor for this instance of Read.

fn bytes(self) -> Bytes<Self>

Transforms this Read instance to an [Iterator] over its bytes.

fn chain<R>(self, next: R) -> Chain<Self, R> where
    R: Read, 

Creates an adaptor which will chain this stream with another.

fn take(self, limit: u64) -> Take<Self>

Creates an adaptor which will read at most limit bytes from it.

impl<N> Write for Chunk<u8, N> where
    N: ChunkLength<u8>, 

fn write(&mut self, buf: &[u8]) -> Result<usize>

Write a buffer into this writer, returning how many bytes were written.

fn flush(&mut self) -> Result<()>

Flush this output stream, ensuring that all intermediately buffered contents reach their destination.

fn write_vectored(&mut self, bufs: &[IoSlice]) -> Result<usize, Error>

Like write, except that it writes from a slice of buffers.

fn write_all(&mut self, buf: &[u8]) -> Result<(), Error>

Attempts to write an entire buffer into this writer.

fn write_fmt(&mut self, fmt: Arguments) -> Result<(), Error>

Writes a formatted string into this writer, returning any error encountered.

fn by_ref(&mut self) -> &mut Self

Creates a "by reference" adaptor for this instance of Write.