Struct HashedArrayTree 

pub struct HashedArrayTree<T> { /* private fields */ }

Hashed Array Tree (HAT) described by Edward Sitarski.

Implementations

impl<T> HashedArrayTree<T>

pub fn new() -> Self

Returns a hashed array tree with zero capacity.

pub fn push(&mut self, value: T)

Appends an element to the back of a collection.

Panics

Panics if a new block is allocated that would exceed isize::MAX bytes.

Time complexity

O(N) in the worst case (expand).

pub fn push_within_capacity(&mut self, value: T) -> Result<(), T>

Appends an element if there is sufficient spare capacity, otherwise an error is returned with the element.

Time complexity

O(N) in the worst case (expand).

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

Retrieve a reference to the element at the given offset.

Time complexity

Constant time.

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

Returns a mutable reference to an element.

Time complexity

Constant time.

pub fn pop(&mut self) -> Option<T>

Removes the last element from the array and returns it, or None if the array is empty.

Time complexity

O(N) in the worst case (shrink).

pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T>

Removes and returns the last element from an array if the predicate returns true, or None`` if the predicate returns false`` or the array is empty (the predicate will not be called in that case).

Time complexity

O(N) in the worst case (shrink).

pub fn swap_remove(&mut self, index: usize) -> T

Removes an element from the array and returns it.

The removed element is replaced by the last element of the array.

This does not preserve ordering of the remaining elements.

Time complexity

O(N) in the worst case (shrink).

pub fn iter(&self) -> ArrayIter<'_, T>

pub fn len(&self) -> usize

Return the number of elements in the array.

Time complexity

Constant time.

pub fn capacity(&self) -> usize

Returns the total number of elements the array can hold without reallocating.

Time complexity

Constant time.

pub fn is_empty(&self) -> bool

Returns true if the array has a length of 0.

Time complexity

Constant time.

pub fn clear(&mut self)

Clears the array, removing all values and deallocating all leaves.

Time complexity

O(N) if elements are droppable, otherwise O(√N)

Trait Implementations

impl<T> Default for HashedArrayTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Display for HashedArrayTree<T>

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

Formats the value using the given formatter.

impl<T> Drop for HashedArrayTree<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<A> FromIterator<A> for HashedArrayTree<A>

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

Creates a value from an iterator.

impl<T> Index<usize> for HashedArrayTree<T>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for HashedArrayTree<T>

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

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

impl<T> IntoIterator for HashedArrayTree<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = ArrayIntoIter<<HashedArrayTree<T> as IntoIterator>::Item>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.