Struct priority_queue::PriorityQueue

pub struct PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord,  { /* fields omitted */ }

A priority queue with efficient change function to change the priority of an element.

The priority is of type P, that must implement std::cmp::Ord.

The item is of type I, that must implement Hash and Eq.

Implemented as a heap of indexes, stores the items inside an OrderMap to be able to retrieve them quickly.

Methods

impl<I, P> PriorityQueue<I, P> where
    P: Ord,
    I: Hash + Eq, 

fn new() -> PriorityQueue<I, P>

Creates an empty PriorityQueue

fn with_capacity(capacity: usize) -> PriorityQueue<I, P>

Creates an empty PriorityQueue with the specified capacity.

The internal collections will be able to hold at least capacity elements without reallocating. If capacity is 0, there will be no allocation.

fn iter<'a>(&'a self) -> Iter<'a, I, P>

Returns an iterator in arbitrary order over the (item, priority) elements in the queue

fn peek(&self) -> Option<(&I, &P)>

Returns the couple (item, priority) with the greatest priority in the queue, or None if it is empty.

Computes in O(1) time

fn peek_mut(&mut self) -> Option<(&mut I, &P)>

Returns the couple (item, priority) with the greatest priority in the queue, or None if it is empty.

The item is a mutable reference, but it's a logic error to modify it in a way that change the result of Hash or Eq.

The priority cannot be modified with a call to this function. To modify the priority use push, change_priority or change_priority_by.

Computes in O(1) time

fn capacity(&self) -> usize

Returns the number of elements the internal map can hold without reallocating.

This number is a lower bound; the map might be able to hold more, but is guaranteed to be able to hold at least this many.

fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the given PriorityQueue. The collection may reserve more space to avoid frequent reallocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

Panics

Panics if the new capacity overflows usize.

fn shrink_to_fit(&mut self)

Shrinks the capacity of the internal data structures that support this operation as much as possible.

fn pop(&mut self) -> Option<(I, P)>

Removes the item with the greatest priority from the priority queue and returns the pair (item, priority), or None if the queue is empty.

fn push(&mut self, item: I, priority: P) -> Option<P>

Insert the item-priority pair into the queue.

If an element equals to item was already into the queue, it is updated and the old value of its priority returned in Some; otherwise, return None.

Computes in O(log(N)) time.

fn change_priority<Q: ?Sized>(&mut self, item: &Q, new_priority: P) -> Option<P> where
    I: Borrow<Q>,
    Q: Eq + Hash, 

Change the priority of an Item returning the old value of priority, or None if the item wasn't in the queue.

The item is found in O(1) thanks to the hash table. The operation is performed in O(log(N)) time.

fn change_priority_by<Q: ?Sized, F>(&mut self, item: &Q, priority_setter: F) where
    I: Borrow<Q>,
    Q: Eq + Hash,
    F: FnOnce(P) -> P, 

Change the priority of an Item using the provided function. The item is found in O(1) thanks to the hash table. The operation is performed in O(log(N)) time (worst case).

fn get_priority<Q: ?Sized>(&self, item: &Q) -> Option<&P> where
    I: Borrow<Q>,
    Q: Eq + Hash, 

Get the priority of an item, or None, if the item is not in the queue

fn get<Q>(&self, item: &Q) -> Option<(&I, &P)> where
    I: Borrow<Q>,
    Q: Eq + Hash, 

Get the couple (item, priority) of an arbitrary element, as reference or None if the item is not in the queue.

fn get_mut<Q>(&mut self, item: &Q) -> Option<(&mut I, &P)> where
    I: Borrow<Q>,
    Q: Eq + Hash, 

Get the couple (item, priority) of an arbitrary element, or None if the item was not in the queue.

The item is a mutable reference, but it's a logic error to modify it in a way that change the result of Hash or Eq.

The priority cannot be modified with a call to this function. To modify the priority use push, change_priority or change_priority_by.

fn into_vec(self) -> Vec<I>

Returns the items not ordered

fn into_sorted_vec(self) -> Vec<I>

Implements an HeapSort

fn len(&self) -> usize

Returns the number of elements in the priority queue.

fn is_empty(&self) -> bool

Returns true if the priority queue contains no elements.

fn clear(&mut self)

Drops all items from the priority queue

fn append(&mut self, other: &mut Self)

Move all items of the other queue to self ignoring the items Eq to elements already in self At the end, other will be empty.

Note that at the end, the priority of the duplicated elements inside self may be the one of the elements in other, if other is longer than self

fn into_sorted_iter(self) -> IntoSortedIter<I, P>

Generates a new iterator from self that will extract the elements from the one with the highest priority to the lowest one.

Trait Implementations

impl<I: Clone, P: Clone> Clone for PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord, 

fn clone(&self) -> PriorityQueue<I, P>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<I: Default, P: Default> Default for PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord, 

fn default() -> PriorityQueue<I, P>

Returns the "default value" for a type.

impl<I: Eq, P: Eq> Eq for PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord, 

impl<I, P> From<Vec<(I, P)>> for PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord, 

fn from(vec: Vec<(I, P)>) -> PriorityQueue<I, P>

Performs the conversion.

impl<I, P> FromIterator<(I, P)> for PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord, 

fn from_iter<IT>(iter: IT) -> PriorityQueue<I, P> where
    IT: IntoIterator<Item = (I, P)>, 

Creates a value from an iterator.

impl<I, P> IntoIterator for PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord, 

type Item = (I, P)

The type of the elements being iterated over.

type IntoIter = IntoIter<I, P>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<I, P>

Creates an iterator from a value.

impl<I, P> Extend<(I, P)> for PriorityQueue<I, P> where
    I: Hash + Eq,
    P: Ord, 

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

Extends a collection with the contents of an iterator.

impl<I, P> Debug for PriorityQueue<I, P> where
    I: Debug + Hash + Eq,
    P: Debug + Ord, 

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

Formats the value using the given formatter.

impl<I, P1, P2> PartialEq<PriorityQueue<I, P2>> for PriorityQueue<I, P1> where
    I: Hash + Eq,
    P1: Ord,
    P1: PartialEq<P2>,
    Option<P1>: PartialEq<Option<P2>>,
    P2: Ord, 

fn eq(&self, other: &PriorityQueue<I, P2>) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.