Struct interval_heap::IntervalHeap

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

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.

Methods

impl<T: Ord> IntervalHeap<T>

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());

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>

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

Returns an empty heap ordered according to the given comparator.

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.

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.

fn iter(&self) -> Iter<T>

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

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

Returns a reference to the smallest item in the heap.

Returns None if the heap is empty.

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

Returns a reference to the greatest item in the heap.

Returns None if the heap is empty.

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.

fn capacity(&self) -> usize

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

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.

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.

fn shrink_to_fit(&mut self)

Discards as much additional capacity from the heap as possible.

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

Removes the smallest item from the heap and returns it.

Returns None if the heap was empty.

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

Removes the greatest item from the heap and returns it.

Returns None if the heap was empty.

fn push(&mut self, item: T)

Pushes an item onto the heap.

fn into_vec(self) -> Vec<T>

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

fn into_sorted_vec(self) -> Vec<T>

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

fn len(&self) -> usize

Returns the number of items in the heap.

fn is_empty(&self) -> bool

Returns true if the heap contains no items.

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

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

Returns the "default value" for a type.

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

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.

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.

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.