Struct ink_storage::collections::BinaryHeap

pub struct BinaryHeap<T> where
    T: PackedLayout + Ord,  { /* fields omitted */ }

A priority queue implemented with a binary heap.

Note

The heap is a max-heap by default, i.e. the first element is the largest. Either Reverse or a custom Ord implementation can be used to make BinaryHeap a min-heap. This makes heap.pop() return the smallest value instead of the largest one.

Implementations

impl<T> BinaryHeap<T> where
    T: PackedLayout + Ord, 

pub fn new() -> Self

Creates a new empty storage heap.

pub fn len(&self) -> u32

Returns the number of elements in the heap, also referred to as its ‘length’.

pub fn is_empty(&self) -> bool

Returns true if the heap contains no elements.

impl<T> BinaryHeap<T> where
    T: PackedLayout + Ord, 

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

Returns an iterator yielding shared references to all elements of the heap.

Note

Avoid unbounded iteration over large heaps. Prefer using methods like Iterator::take in order to limit the number of yielded elements.

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

Returns a shared reference to the greatest element of the heap

Returns None if the heap is empty

pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>>

Returns an exclusive reference to the greatest element of the heap

Returns None if the heap is empty

Note:

If the PeekMut value is leaked, the heap may be in an inconsistent state.

Example

use ink_storage::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
assert!(heap.peek_mut().is_none());

heap.push(1);
heap.push(5);
heap.push(2);
{
    let mut val = heap.peek_mut().unwrap();
    *val = 0;
}
assert_eq!(heap.peek(), Some(&2));

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

Pops greatest element from the heap and returns it

Returns None if the heap is empty

pub fn clear(&mut self)

Removes all elements from this heap.

Note

Use this method to clear the heap instead of e.g. iterative pop(). This method performs significantly better and does not actually read any of the elements (whereas pop() does).

impl<T> BinaryHeap<T> where
    T: PackedLayout + Ord, 

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

Pushes the given element to the binary heap.

Trait Implementations

impl<T: Debug> Debug for BinaryHeap<T> where
    T: PackedLayout + Ord, 

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

Formats the value using the given formatter.

impl<T: Default> Default for BinaryHeap<T> where
    T: PackedLayout + Ord, 

fn default() -> BinaryHeap<T>

Returns the “default value” for a type.

impl<T: Eq> Eq for BinaryHeap<T> where
    T: PackedLayout + Ord, 

impl<T> Extend<T> for BinaryHeap<T> where
    T: PackedLayout + Ord, 

fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = T>, 

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<T> for BinaryHeap<T> where
    T: PackedLayout + Ord, 

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

Creates a value from an iterator.

impl<T: PartialEq> PartialEq<BinaryHeap<T>> for BinaryHeap<T> where
    T: PackedLayout + Ord, 

fn eq(&self, other: &BinaryHeap<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &BinaryHeap<T>) -> bool

This method tests for !=.

impl<T> SpreadLayout for BinaryHeap<T> where
    T: PackedLayout + Ord, 

const FOOTPRINT: u64

The footprint of the type.

fn pull_spread(ptr: &mut KeyPtr) -> Self

Pulls an instance of Self from the contract storage.

fn push_spread(&self, ptr: &mut KeyPtr)

Pushes an instance of Self to the contract storage.

fn clear_spread(&self, ptr: &mut KeyPtr)

Clears an instance of Self from the contract storage.

const REQUIRES_DEEP_CLEAN_UP: bool

Indicates whether a type requires deep clean-up of its state meaning that a clean-up routine has to decode an entity into an instance in order to eventually recurse upon its tear-down. This is not required for the majority of primitive data types such as i32, however types such as storage::Box that might want to forward the clean-up procedure to their inner T require a deep clean-up.

impl<T> StorageLayout for BinaryHeap<T> where
    T: PackedLayout + Ord + TypeInfo + 'static, 

fn layout(key_ptr: &mut KeyPtr) -> Layout

Returns the static storage layout of Self.

impl<T> StructuralEq for BinaryHeap<T> where
    T: PackedLayout + Ord, 

impl<T> StructuralPartialEq for BinaryHeap<T> where
    T: PackedLayout + Ord,