Enum VecChunk

pub enum VecChunk<A> {
    Empty,
    Single(A),
    Concat(Rc<VecChunk<A>>, Rc<VecChunk<A>>),
    Collect(Rc<RefCell<Vec<A>>>),
    TransformFlatten(Rc<VecChunk<A>>, Rc<dyn Fn(A) -> VecChunk<A>>),
}

Available on crate feature alloc only.

A persistent data structure that provides efficient append and concatenation operations.

Overview

VecChunk<A> is an immutable data structure that allows O(1) complexity for append and concatenation operations through structural sharing. It uses Rc (Reference Counting) for efficient memory management.

Performance

• Append operation: O(1)
• Concatenation operation: O(1)
• Converting to Vec: O(n)

Implementation Details

The data structure is implemented as an enum with three variants:

• Empty: Represents an empty chunk
• Append: Represents a single element appended to another chunk
• Concat: Represents the concatenation of two chunks

Example

let mut chunk = VecChunk::default();
chunk = chunk.append(1);
chunk = chunk.append(2);

let other_chunk = VecChunk::default().append(3).append(4);
let combined = chunk.concat(other_chunk);

assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);

References

• Persistent Data Structures
• Structural Sharing

Derived Work

This is derived work from the tailcall-chunk crate, including the following modifications:

• add must_use attribute.
• make it no_std compatible.
• rename the structure to VecChunk.
• misc. refactoring.

Variants

Empty

Represents an empty chunk with no elements

Single(A)

Represents a chunk containing exactly one element

Concat(Rc<VecChunk<A>>, Rc<VecChunk<A>>)

Represents the concatenation of two chunks, enabling O(1) concatenation

Collect(Rc<RefCell<Vec<A>>>)

Represents a collection of elements

TransformFlatten(Rc<VecChunk<A>>, Rc<dyn Fn(A) -> VecChunk<A>>)

Represents a lazy transformation that flattens elements

Implementations

impl<A> VecChunk<A>

pub fn new(a: A) -> Self

Creates a new chunk containing a single element.

Arguments

• a - The element to store in the chunk

Example

let chunk: VecChunk<i32> = VecChunk::new(100);
assert!(!chunk.is_null());

pub fn is_null(&self) -> bool

Returns true if the chunk is empty.

Example

let chunk: VecChunk<i32> = VecChunk::default();
assert!(chunk.is_null());

let non_empty = chunk.append(42);
assert!(!non_empty.is_null());

pub fn append(self, a: A) -> Self

Append a new element to the chunk.

This operation has O(1) complexity as it creates a new Append variant that references the existing chunk through an Rc.

Example

let chunk = VecChunk::default().append(1).append(2);
assert_eq!(chunk.as_vec(), vec![1, 2]);

pub fn prepend(self, a: A) -> Self

Prepend a new element to the beginning of the chunk.

This operation has O(1) complexity as it creates a new Concat variant that references the existing chunk through an Rc.

Example

let chunk = VecChunk::default().prepend(1).prepend(2);
assert_eq!(chunk.as_vec(), vec![2, 1]);

pub fn concat(self, other: VecChunk<A>) -> VecChunk<A>

Concatenates this chunk with another chunk.

This operation has O(1) complexity as it creates a new Concat variant that references both chunks through Rcs.

Performance Optimization

If either chunk is empty, returns the other chunk instead of creating a new Concat variant.

Example

let chunk1 = VecChunk::default().append(1).append(2);
let chunk2 = VecChunk::default().append(3).append(4);
let combined = chunk1.concat(chunk2);
assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);

pub fn transform(self, f: impl Fn(A) -> A + 'static) -> Self

Transforms each element in the chunk using the provided function.

This method creates a lazy representation of the transformation without actually performing it. The transformation is only executed when as_vec or as_vec_mut is called.

Performance

• Creating the transformation: O(1)
• Executing the transformation (during as_vec): O(n)

Arguments

• f - A function that takes a reference to an element of type A and returns a new element of type A

Example

let chunk = VecChunk::default().append(1).append(2).append(3);
// This operation is O(1) and doesn't actually transform the elements
let doubled = chunk.transform(|x| x * 2);
// The transformation happens here, when we call as_vec()
assert_eq!(doubled.as_vec(), vec![2, 4, 6]);

pub fn materialize(self) -> VecChunk<A>

where A: Clone,

Materializes a chunk by converting it into a collected form.

This method evaluates any lazy transformations and creates a new chunk containing all elements in a Collect variant. This can be useful for performance when you plan to reuse the chunk multiple times, as it prevents re-evaluation of transformations.

Performance

• Time complexity: O(n) where n is the number of elements
• Space complexity: O(n) as it creates a new vector containing all elements

Example

let chunk = VecChunk::default()
    .append(1)
    .append(2)
    .transform(|x| x * 2);  // Lazy transformation

// Materialize the chunk to evaluate the transformation once
let materialized = chunk.materialize();

assert_eq!(materialized.as_vec(), vec![2, 4]);

pub fn transform_flatten(self, f: impl Fn(A) -> VecChunk<A> + 'static) -> Self

Transforms each element in the chunk into a new chunk and flattens the result.

This method creates a lazy representation of the transformation without actually performing it. The transformation is only executed when as_vec or as_vec_mut is called.

Performance

• Creating the transformation: O(1)
• Executing the transformation (during as_vec): O(n)

Arguments

• f - A function that takes an element of type A and returns a new VecChunk<A>

Example

let chunk = VecChunk::default().append(1).append(2);
// Transform each number x into a chunk containing [x, x+1]
let expanded = chunk.transform_flatten(|x| {
    VecChunk::default().append(x).append(x + 1)
});
assert_eq!(expanded.as_vec(), vec![1, 2, 2, 3]);

pub fn as_vec(&self) -> Vec<A>

where A: Clone,

Converts the chunk into a vector of references to its elements.

This operation has O(n) complexity where n is the number of elements in the chunk.

Example

let chunk = VecChunk::default().append(1).append(2).append(3);
assert_eq!(chunk.as_vec(), vec![1, 2, 3]);

pub fn as_vec_mut(&self, buf: &mut Vec<A>)

where A: Clone,

Helper method that populates a vector with references to the chunk’s elements.

This method is used internally by as_vec to avoid allocating multiple vectors during the traversal.

Arguments

• buf - A mutable reference to a vector that will be populated with references to the chunk’s elements

Trait Implementations

impl<A: Clone> Clone for VecChunk<A>

fn clone(&self) -> VecChunk<A>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A> Default for VecChunk<A>

fn default() -> Self

Creates a new empty chunk.

This is equivalent to using VecChunk::Empty.

impl<A> FromIterator<A> for VecChunk<A>

fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self

Creates a chunk from an iterator.

Example

let vec = vec![1, 2, 3];
let chunk: VecChunk<_> = vec.into_iter().collect();
assert_eq!(chunk.as_vec(), vec![1, 2, 3]);