Struct IntervalHeap

pub struct IntervalHeap<T, C: Compare<T> = Natural<T>> { /* private fields */ }

A double-ended priority queue implemented with an interval heap.

It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the heap’s comparator, changes while it is in the heap. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

Implementations

impl<T: Ord> IntervalHeap<T>

pub fn new() -> IntervalHeap<T>

Returns an empty heap ordered according to the natural order of its items.

Examples

use interval_heap::IntervalHeap;

let heap = IntervalHeap::<u32>::new();
assert!(heap.is_empty());

pub fn with_capacity(capacity: usize) -> IntervalHeap<T>

Returns an empty heap with the given capacity and ordered according to the natural order of its items.

The heap will be able to hold exactly capacity items without reallocating.

Examples

use interval_heap::IntervalHeap;

let heap = IntervalHeap::<u32>::with_capacity(5);
assert!(heap.is_empty());
assert!(heap.capacity() >= 5);

impl<T, C: Compare<T>> IntervalHeap<T, C>

pub fn with_comparator(cmp: C) -> IntervalHeap<T, C>

Returns an empty heap ordered according to the given comparator.

pub fn with_capacity_and_comparator( capacity: usize, cmp: C, ) -> IntervalHeap<T, C>

Returns an empty heap with the given capacity and ordered according to the given comparator.

pub fn from_vec_and_comparator(vec: Vec<T>, cmp: C) -> IntervalHeap<T, C>

Returns a heap containing all the items of the given vector and ordered according to the given comparator.

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

Returns an iterator visiting all items in the heap in arbitrary order.

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

Returns a reference to the smallest item in the heap.

Returns None if the heap is empty.

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

Returns a reference to the greatest item in the heap.

Returns None if the heap is empty.

pub fn min_max(&self) -> Option<(&T, &T)>

Returns references to the smallest and greatest items in the heap.

Returns None if the heap is empty.

pub fn capacity(&self) -> usize

Returns the number of items the heap can hold without reallocation.

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

Reserves the minimum capacity for exactly additional more items to be inserted into the heap.

Does nothing if the capacity is already sufficient.

Note that the allocator may give the heap more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

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

Reserves capacity for at least additional more items to be inserted into the heap.

The heap may reserve more space to avoid frequent reallocations.

pub fn shrink_to_fit(&mut self)

Discards as much additional capacity from the heap as possible.

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

Removes the smallest item from the heap and returns it.

Returns None if the heap was empty.

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

Removes the greatest item from the heap and returns it.

Returns None if the heap was empty.

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

Pushes an item onto the heap.

pub fn into_vec(self) -> Vec<T>

Consumes the heap and returns its items as a vector in arbitrary order.

pub fn into_sorted_vec(self) -> Vec<T>

Consumes the heap and returns its items as a vector in sorted (ascending) order.

pub fn len(&self) -> usize

Returns the number of items in the heap.

pub fn is_empty(&self) -> bool

Returns true if the heap contains no items.

pub fn clear(&mut self)

Removes all items from the heap.

Trait Implementations

impl<T: Clone, C: Clone + Compare<T>> Clone for IntervalHeap<T, C>

fn clone(&self) -> IntervalHeap<T, C>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug, C: Compare<T>> Debug for IntervalHeap<T, C>

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

Formats the value using the given formatter.

impl<T, C: Compare<T> + Default> Default for IntervalHeap<T, C>

fn default() -> IntervalHeap<T, C>

Returns the “default value” for a type.

impl<'a, T: 'a + Copy, C: Compare<T>> Extend<&'a T> for IntervalHeap<T, C>

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

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

Extends a collection with exactly one element.

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, C: Compare<T>> Extend<T> for IntervalHeap<T, C>

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

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

Extends a collection with exactly one element.

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: Ord> From<Vec<T>> for IntervalHeap<T>

fn from(vec: Vec<T>) -> IntervalHeap<T>

Returns a heap containing all the items of the given vector and ordered according to the natural order of its items.

Examples

use interval_heap::IntervalHeap;

let heap = IntervalHeap::from(vec![5, 1, 6, 4]);
assert_eq!(heap.len(), 4);
assert_eq!(heap.min_max(), Some((&1, &6)));

impl<T, C: Compare<T> + Default> FromIterator<T> for IntervalHeap<T, C>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> IntervalHeap<T, C>

Creates a value from an iterator.

impl<'a, T, C: Compare<T>> IntoIterator for &'a IntervalHeap<T, C>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<T, C: Compare<T>> IntoIterator for IntervalHeap<T, C>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.