Struct HashedArrayTree

Source

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

Expand description

Hashed Array Tree (HAT) described by Edward Sitarski.

Implementations§

Source §

impl<T> HashedArrayTree<T>

Source

pub fn new() -> Self

Returns a hashed array tree with zero capacity.

Source

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).

Source

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).

Source

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

Retrieve a reference to the element at the given offset.

§Time complexity

Constant time.

Source

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

Returns a mutable reference to an element.

§Time complexity

Constant time.

Source

pub fn raw_pop(&mut self) -> T

Like Self::pop() but without the Option wrapper.

Will panic if the array is empty.

Source

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).

Source

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).

Source

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.

§Panics

Panics if the index is out of bounds.

§Time complexity

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

Source

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

Source

pub fn len(&self) -> usize

Return the number of elements in the array.

§Time complexity

Constant time.

Source

pub fn capacity(&self) -> usize

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

§Time complexity

Constant time.

Source

pub fn is_empty(&self) -> bool

Returns true if the array has a length of 0.

§Time complexity

Constant time.

Source

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)

Source

pub fn swap(&mut self, a: usize, b: usize)

Swap two elements in the array.

§Panics

Panics if either index is out of bounds.

Source

pub fn sort_unstable_by<F>(&mut self, compare: F)
where F: FnMut(&T, &T) -> Ordering,

Sorts the slice in ascending order with a comparison function, without preserving the initial order of equal elements.

This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not allocate), and O(n * log(n)) worst-case.

Implements the standard heapsort algorithm.

Source

pub fn dedup_by<F>(&mut self, same_bucket: F)
where F: FnMut(&T, &T) -> bool,

Removes all but the first of consecutive elements in the array satisfying a given equality relation.

The same_bucket function is passed references to two elements from the array and must determine if the elements compare equal. The elements are passed in reverse order from their order in the array, so if same_bucket(a, b) returns true, a is removed.

If the array is sorted, this removes all duplicates.

Source

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

Moves all the elements of other into self, leaving other empty.

Source

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

Splits the collection into two at the given index.

Returns a newly allocated array containing the elements in the range [at, len). After the call, the original array will be left containing the elements [0, at).