Struct interval_heap::IntervalHeap

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

An IntervalHeap is an implementation of a double-ended priority queue. As such, it supports the following operations: push, min, max, pop_min, pop_max where insertion takes amortized O(log n) time, removal takes O(log n) time and accessing minimum and maximum can be done in constant time. Also, other convenient functions are provided that handle conversion from and into vectors and allow iteration etc.

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

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

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

Examples

use interval_heap::IntervalHeap;

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

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

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

Examples

use interval_heap::IntervalHeap;

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

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 elements of the given vector and ordered according to the given comparator.

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

An iterator visiting all values in underlying vector, in arbitrary order.

fn into_iter(self) -> IntoIter<T>

Returns a consuming iterator over the heap in arbitrary order.

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

Returns a reference to the smallest item or None (if empty).

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

Returns a reference to the greatest item or None (if empty).

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

Returns references to the smallest and greatest item or None (if empty).

fn capacity(&self) -> usize

Returns the number of items the interval heap could hold without reallocation.

fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more elements to be inserted in the given IntervalHeap. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection 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 elements to be inserted in the IntervalHeap. The collection may reserve more space to avoid frequent reallocations.

fn shrink_to_fit(&mut self)

Discards as much additional capacity as possible.

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

Removes the smallest item and returns it, or None if is empty.

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

Removes the greatest item and returns it, or None if is empty.

fn push(&mut self, x: T)

Pushes an item onto the queue.

fn into_vec(self) -> Vec<T>

Consumes the IntervalHeap and returns the underlying vector in arbitrary order.

fn into_sorted_vec(self) -> Vec<T>

Consumes the IntervalHeap and returns a vector in sorted (ascending) order.

fn len(&self) -> usize

Returns the number of items in the interval heap

fn is_empty(&self) -> bool

Returns true if the queue contains no items.

fn clear(&mut self)

Drops all items from the queue.

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 an empty heap ordered according to a default comparator.

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 an interval heap with all the items from an iterator

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

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

Extends the interval heap by a new chunk of items given by 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.