#iterator #infinite #sequence #lazy-evaluation #invariants

yanked inf_vec

A lazily-populated infinite Vec-like data structure

1 unstable release

0.1.0 Feb 24, 2024

#17 in #infinite

MIT license

26KB
483 lines

inf_vec

This is a Rust crate that provides the InfVec type, a lazily-populated infinite Vec-like data structure.

See the documentation for usage info.


lib.rs:

This crate provides InfVec, A lazily-populated infinite Vec-like data structure.

An InfVec<T, I> contains infinitely many values of type T. It can be iterated over and indexed into similarly to a Vec. Elements are produced on-demand by a iterator with type I which is specified upon creation of the InfVec. The elements can be later accessed by index, and can be modified.

If the iterator is not infinite, operations on the InfVec might panic.

InfVec is currently invariant, as opposed to covariant, if that matters to you.

InfVec is thread-safe, so you can put it in static variables.

Despite the name, InfVec doesn't actually store elements continuously like a Vec. Instead, it stores elements in 64-element chunks. This is so that we can hand out references to elements, and not have them be invalidated as more elements are added to the cache.

If you don't want to specify an iterator type as a type parameter, you can use the InfVecBoxed or InfVecOwned type aliases.

Examples

Mutation of an InfVec:

use inf_vec::InfVec;

let mut inf_vec = InfVec::new(0..);
assert_eq!(
    inf_vec.iter().take(10).copied().collect::<Vec<_>>(),
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
);
inf_vec[3] = 100;
assert_eq!(
    inf_vec.iter().take(10).copied().collect::<Vec<_>>(),
    [0, 1, 2, 100, 4, 5, 6, 7, 8, 9]
);

Reusing a static InfVec:

use inf_vec::{InfVec, InfVecOwned, IteratorInfExt};
use once_cell::sync::Lazy;

// Note that each element will only ever be produced once.
static EVENS: Lazy<InfVecOwned<i32>> =
    Lazy::new(|| (0..).map(|x| x * 2).collect_inf().boxed());

fn evens_with_property(mut predicate: impl FnMut(i32) -> bool) -> impl Iterator<Item = i32> {
    EVENS.iter().copied().filter(move |&x| predicate(x))
}

assert_eq!(
    evens_with_property(|x| x % 3 == 0)
        .take(5)
        .collect::<Vec<_>>(),
    [0, 6, 12, 18, 24]
);
assert_eq!(
    evens_with_property(|x| x % 5 == 0)
        .take(5)
        .collect::<Vec<_>>(),
    [0, 10, 20, 30, 40]
);

Recursive InfVec:

use inf_vec::{InfVec, InfVecBoxed};
use std::sync::Arc;

let fibonacci: Arc<InfVecBoxed<i32>> = InfVec::recursive(|fibonacci_ref, i| {
    if i < 2 {
        1
    } else {
        fibonacci_ref[i - 1] + fibonacci_ref[i - 2]
    }
});
assert_eq!(
    fibonacci.iter().take(10).copied().collect::<Vec<_>>(),
    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
);

No runtime deps