Struct appendlist::AppendList

pub struct AppendList<T> { /* fields omitted */ }

A list that can be appended to while elements are borrowed

This looks like a fairly bare-bones list API, except that it has a push method that works on non-mut lists. It is safe to hold references to values inside this list and push a new value onto the end.

Additionally, the list has O(1) index and O(1) push (not amortized!).

For example, this would be illegal with a Vec:

use appendlist::AppendList;

let list = AppendList::new();

list.push(1);
let first_item = &list[0];
list.push(2);
let second_item = &list[1];

assert_eq!(*first_item, list[0]);
assert_eq!(*second_item, list[1]);

Implementation details

This section is not necessary to use the API, it just describes the underlying allocation and indexing strategies.

The list is a Vec of chunks. Each chunk is itself a Vec<T>. The list will fill up a chunk, then allocate a new chunk with its full capacity. Because the capacity of a given chunk never changes, the underlying Vec<T> never reallocates, so references to that chunk are never invalidated. Each chunk is twice the size of the previous chunk, so there will never be more than O(log(n)) chunks.

Constant-time indexing is achieved because the chunk ID of a particular index can be quickly calculated: if the first chunk has size c, index i will be located in chunk floor(log2(i + c) - log2(c)). If c is a power of 2, this is equivalent to floor(log2(i + c)) - floor(log2(c)), and a very fast floor log2 algorithm can be derived from usize::leading_zeros().

Methods

impl<T> AppendList<T>

pub fn new() -> Self

Create a new AppendList

pub fn push(&self, item: T)

Append an item to the end

Note that this does not require mut.

pub fn len(&self) -> usize

Get the length of the list

pub fn get(&self, index: usize) -> Option<&T>

Get an item from the list, if it is in bounds

Returns None if the index is out-of-bounds. Note that you can also index with [], which will panic on out-of-bounds.

Important traits for Iter<'l, T>

impl<'l, T> Iterator for Iter<'l, T> type Item = &'l T;

pub fn iter(&self) -> Iter<T>

Get an iterator over the list

Trait Implementations

impl<T: PartialEq> PartialEq<AppendList<T>> for AppendList<T>

fn eq(&self, other: &AppendList<T>) -> 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<'l, T> IntoIterator for &'l AppendList<T>

type Item = &'l T

The type of the elements being iterated over.

type IntoIter = Iter<'l, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Default for AppendList<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T> Index<usize> for AppendList<T>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T: Debug> Debug for AppendList<T>

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

Formats the value using the given formatter.

impl<T> FromIterator<T> for AppendList<T>

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

Creates a value from an iterator.