Struct FixedHeap

Source

pub struct FixedHeap<T, const N: usize> { /* private fields */ }

Expand description

A fixed-size heap structure with manually provided stateful comparison function.

Implementations§

Source §

impl<T, const N: usize> FixedHeap<T, N>

Source

pub fn new() -> Self

Creates a new empty FixedHeap.

Passing in a comparer and state is deferred so as to not hold a reference preventing mutation of other parts of state that do not affect the heap order.

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();

Source

pub fn copy_from_slice(&mut self, slice: &[T])
where T: Copy,

Copies slice into the backing storage, ignoring heap properties.

Caution: this will not preserve the heap property of the structure

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
let array = [4; 12];
heap.copy_from_slice(&array[2..8]);
assert_eq!(heap.len(), 6);

Source

pub fn peek(&self) -> Option<&T>

Returns a reference to the highest priority element.

§Returns

None if there are no elements in the heap.

Some(elem) if there was an element. elem is higher priority than all other elements.

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
assert_eq!(heap.add_last(1), None);
assert_eq!(heap.peek(), Some(&1));

Source

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

Returns a reference to the element at index.

§Returns

None if there is no element at index.

Some(elem) if there was an element.

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
assert_eq!(heap.add_last(1), None);
assert_eq!(heap.add_last(2), None);
assert_eq!(heap.peek_at(1), Some(&2));

Source

pub fn add_last(&mut self, value: T) -> Option<T>

Tries to add value to the end, ignoring heap properties.

Caution: this will not preserve the heap property of the structure

§Returns

None if there was spare capacity to accommodate value

Some(value) if there was no spare capacity

§Time Complexity

O(1)

§Examples

let mut heap: FixedHeap<i32, 1> = FixedHeap::new();
assert_eq!(heap.add_last(1), None);
assert_eq!(heap.add_last(2), Some(2));

Source

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

Removes and returns the element at index, ignoring heap properties. Use pop_at instead to preserve heap properties.

Caution: this will not preserve the heap property of the structure

§Returns

None if there’s no element at index.

Some(elem) if there was an element at index.

§Time Complexity

O(1)

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
assert_eq!(heap.swap_remove(0), None); // []
assert_eq!(heap.add_last(1), None); // [1]
assert_eq!(heap.swap_remove(1), None); // [1]
assert_eq!(heap.add_last(2), None); // [1, 2]
assert_eq!(heap.swap_remove(0), Some(1)); // [2]
assert_eq!(heap.swap_remove(0), Some(2)); // []

Source

pub fn push<S, F>(&mut self, value: T, comparer: &F, state: &S) -> Option<T>
where F: Fn(&T, &T, &S) -> bool,

Tries to push value onto the heap, calling comparer with state to determine ordering.

comparer should return true if its first argument is strictly higher priority than the second. It is technically permitted to return true when given elements of equal priority, although it is recommended to return false in those cases to avoid swaps for performance reasons. A possible use case for returning true when equal is to have newly added elements take priority over older ones.

Use state to pass in another datastructure in order to sort keys by associated values.

The same comparer should always be used for push and pop, and state should be stable.

If comparer judges that a particular element is higher priority than another one, it is expected that that remains true for as long as those elements are in this heap.

§Returns

None if there was spare capacity to accommodate value

Some(elem) if the lowest priority element elem had to be evicted to accommodate value. elem may be value if all the elements already present were higher priority than value.

§Time Complexity

If there was spare capacity, average time complexity O(1) and worst case O(log N)

If the heap was full, average time complexity O(log N) and worst case O(N) It is recommended to avoid letting the heap reach capacity.

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
let comparer = |a: &i32, b: &i32, _: &()| a > b;
heap.push(1, &comparer, &());

With keys into another struct:

let mut heap: FixedHeap<usize, 16> = FixedHeap::new();
let comparer = |a: &usize, b: &usize, state: &[i32; 4]| state[*a] > state[*b];
let state = [1, 3, 1, 2];
heap.push(0, &comparer, &state);

Source

pub fn pop<S, F>(&mut self, comparer: &F, state: &S) -> Option<T>
where F: Fn(&T, &T, &S) -> bool,

Removes and returns the highest priority element, calling comparer with state to determine ordering.

comparer should return true if its first argument is strictly higher priority than the second. It is technically permitted to return true when given elements of equal priority, although it is recommended to return false in those cases to avoid swaps for performance reasons. A possible use case for returning true when equal is to have newly added elements take priority over older ones.

Use state to pass in another datastructure in order to sort keys by associated values.

The same comparer should always be used for push and pop, and state should be stable.

If comparer judges that a particular element is higher priority than another one, it is expected that that remains true for as long as those elements are in this heap.

§Returns

None if there are no elements in the heap.

Some(elem) if there was an element. elem is higher priority than all remaining elements.

§Time Complexity

Average time complexity O(1) and worst case O(log N)

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
let comparer = |a: &i32, b: &i32, _: &()| a > b;
heap.push(1, &comparer, &());
assert_eq!(heap.pop(&comparer, &()), Some(1));

With keys into another struct:

let mut heap: FixedHeap<usize, 16> = FixedHeap::new();
let comparer = |a: &usize, b: &usize, state: &[i32; 4]| state[*a] > state[*b];
let state = [1, 3, 1, 2];
heap.push(1, &comparer, &state);
assert_eq!(heap.pop(&comparer, &state), Some(1));

Source

pub fn pop_at<S, F>( &mut self, index: usize, comparer: &F, state: &S, ) -> Option<T>
where F: Fn(&T, &T, &S) -> bool,

Removes and returns the element at index, preserving the heap property by calling comparer with state to determine ordering.

comparer should return true if its first argument is strictly higher priority than the second. It is technically permitted to return true when given elements of equal priority, although it is recommended to return false in those cases to avoid swaps for performance reasons. A possible use case for returning true when equal is to have newly added elements take priority over older ones.

Use state to pass in another datastructure in order to sort keys by associated values.

The same comparer should always be used for push and pop, and state should be stable.

If comparer judges that a particular element is higher priority than another one, it is expected that that remains true for as long as those elements are in this heap.

§Returns

None if there is no element at index.

Some(elem) if there was an element.

§Time Complexity

Average time complexity O(1) and worst case O(log N)

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
let comparer = |a: &i32, b: &i32, _: &()| a > b;
heap.push(1, &comparer, &());
heap.push(2, &comparer, &());
assert_eq!(heap.pop_at(1, &comparer, &()), Some(1));

With keys into another struct:

let mut heap: FixedHeap<usize, 16> = FixedHeap::new();
let comparer = |a: &usize, b: &usize, state: &[i32; 4]| state[*a] > state[*b];
let state = [1, 3, 1, 2];
heap.push(1, &comparer, &state);
heap.push(2, &comparer, &state);
assert_eq!(heap.pop_at(1, &comparer, &state), Some(2));

Source

pub fn as_slice(&self) -> &[T]

Provides immutable access to the backing array of the heap.

Source

pub fn as_slice_mut(&mut self) -> &mut [T]

Provides mutable access to the backing array of the heap. Caution: you must preserve the heap property of the structure

Source

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

Provides mutable iteration of the heap’s elements. NOTE: The elements are NOT in the order they’d be popped in!

Source

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Provides mutable iteration of the heap’s elements. NOTE: The elements are NOT in the order they’d be popped in! Caution: you must preserve the heap property of the structure

Source

pub fn len(&self) -> usize

Returns the number of elements.

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
let comparer = |a: &i32, b: &i32, _: &()| a > b;
heap.push(1, &comparer, &());
assert_eq!(heap.len(), 1);

Source

pub fn is_empty(&self) -> bool

Returns true if there are no elements.

§Examples

let mut heap: FixedHeap<i32, 16> = FixedHeap::new();
let comparer = |a: &i32, b: &i32, _: &()| a > b;
assert!(heap.is_empty());
heap.push(1, &comparer, &());
assert!(!heap.is_empty());

Source

pub fn is_full(&self) -> bool

Returns true if there is no free space left.

§Examples

let mut heap: FixedHeap<i32, 1> = FixedHeap::new();
let comparer = |a: &i32, b: &i32, _: &()| a > b;
assert!(!heap.is_full());
heap.push(1, &comparer, &());
assert!(heap.is_full());