pub struct DoublePriorityQueue<I, P, H = RandomState>
where I: Hash + Eq, P: Ord,
{ /* private fields */ }
Expand description

A double 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 IndexMap to be able to retrieve them quickly.

With this data structure it is possible to efficiently extract both the maximum and minimum elements arbitrarily.

If your need is to always extract the minimum, use a PriorityQueue<I, Reverse<P>> wrapping your priorities in the standard wrapper Reverse<T>.

§Example

use priority_queue::DoublePriorityQueue;

let mut pq = DoublePriorityQueue::new();

assert!(pq.is_empty());
pq.push("Apples", 5);
pq.push("Bananas", 8);
pq.push("Strawberries", 23);

assert_eq!(pq.peek_max(), Some((&"Strawberries", &23)));
assert_eq!(pq.peek_min(), Some((&"Apples", &5)));

pq.change_priority("Bananas", 25);
assert_eq!(pq.peek_max(), Some((&"Bananas", &25)));

for (item, _) in pq.into_sorted_iter() {
    println!("{}", item);
}

Implementations§

source§

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

source

pub fn new() -> Self

Creates an empty DoublePriorityQueue

source

pub fn with_capacity(capacity: usize) -> Self

Creates an empty DoublePriorityQueue with the specified capacity.

source§

impl<I, P, H> DoublePriorityQueue<I, P, H>
where P: Ord, I: Hash + Eq, H: BuildHasher + Default,

source

pub fn with_default_hasher() -> Self

Creates an empty DoublePriorityQueue with the default hasher

source

pub fn with_capacity_and_default_hasher(capacity: usize) -> Self

Creates an empty DoublePriorityQueue with the specified capacity and default hasher

source§

impl<I, P, H> DoublePriorityQueue<I, P, H>
where P: Ord, I: Hash + Eq, H: BuildHasher,

source

pub fn with_hasher(hash_builder: H) -> Self

Creates an empty DoublePriorityQueue with the specified hasher

source

pub fn with_capacity_and_hasher(capacity: usize, hash_builder: H) -> Self

Creates an empty DoublePriorityQueue with the specified capacity and hasher

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

source

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

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

source

pub fn shrink_to_fit(&mut self)

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

source§

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

source

pub fn iter_mut(&mut self) -> IterMut<'_, I, P, H>

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

The item and the priority are mutable references, but it’s a logic error to modify the item in a way that change the result of Hash or Eq.

It’s not an error, instead, to modify the priorities, because the heap will be rebuilt once the IterMut goes out of scope. It would be rebuilt even if no priority value would have been modified, but the procedure will not move anything, but just compare the priorities.

source

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

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

Computes in O(1) time

source

pub fn peek_max(&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

source

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

Returns the couple (item, priority) with the lowest 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

source

pub fn peek_max_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

source

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

source

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

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

source

pub fn pop_max(&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.

source

pub fn into_ascending_sorted_vec(self) -> Vec<I>

Implements a HeapSort.

Consumes the PriorityQueue and returns a vector with all the items sorted from the one associated to the lowest priority to the highest.

source

pub fn into_descending_sorted_vec(self) -> Vec<I>

Implements a HeapSort

Consumes the PriorityQueue and returns a vector with all the items sorted from the one associated to the highest priority to the lowest.

source

pub fn len(&self) -> usize

Returns the number of elements in the priority queue.

source

pub fn is_empty(&self) -> bool

Returns true if the priority queue contains no elements.

source

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

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

source§

impl<I, P, H> DoublePriorityQueue<I, P, H>
where P: Ord, I: Hash + Eq, H: BuildHasher,

source

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

Reserves capacity for at least additional more elements to be inserted in the given DoublePriorityQueue. 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.

source

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

Insert the item-priority pair into the queue.

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

Computes in O(log(N)) time.

source

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

Increase the priority of an existing item in the queue, or insert it if not present.

If an element equal to item is already in the queue with a lower priority, its priority is increased to the new one without replacing the element and the old priority is returned. Otherwise, the new element is inserted into the queue.

Returns Some if an element equal to item is already in the queue. If its priority is higher then priority, the latter is returned back, otherwise, the old priority is contained in the Option. If the item is not in the queue, None is returned.

Computes in O(log(N)) time.

source

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

Decrease the priority of an existing item in the queue, or insert it if not present.

If an element equal to item is already in the queue with a higher priority, its priority is decreased to the new one without replacing the element and the old priority is returned. Otherwise, the new element is inserted into the queue.

Returns Some if an element equal to item is already in the queue. If its priority is lower then priority, the latter is returned back, otherwise, the old priority is contained in the Option. If the item is not in the queue, None is returned.

Computes in O(log(N)) time.

source

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

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

The argument item is only used for lookup, and is not used to overwrite the item’s data in the priority queue.

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

source

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

Change the priority of an Item using the provided function. Return a boolean value where true means the item was in the queue and update was successful

The argument item is only used for lookup, and is not used to overwrite the item’s data in the priority queue.

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

source

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

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

source

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

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

source

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

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.

source

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

Remove an arbitrary element from the priority queue. Returns the (item, priority) couple or None if the item is not found in the queue.

The operation is performed in O(log(N)) time (worst case).

source

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

Returns the items not ordered

source

pub fn clear(&mut self)

Drops all items from the priority queue

source

pub 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

Trait Implementations§

source§

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

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

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

Formats the value using the given formatter. Read more
source§

impl<I, P, H> Default for DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher + Default,

source§

fn default() -> Self

Returns the “default value” for a type. Read more
source§

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

source§

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

Extends a collection with the contents of an iterator. Read more
source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

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. Read more
source§

impl<I, P, H> From<DoublePriorityQueue<I, P, H>> for PriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher,

source§

fn from(pq: DoublePriorityQueue<I, P, H>) -> Self

Converts to this type from the input type.
source§

impl<I, P, H> From<PriorityQueue<I, P, H>> for DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher,

source§

fn from(pq: PriorityQueue<I, P, H>) -> Self

Converts to this type from the input type.
source§

impl<I, P, H> From<Vec<(I, P)>> for DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher + Default,

source§

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

Converts to this type from the input type.
source§

impl<I, P, H> FromIterator<(I, P)> for DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher + Default,

source§

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

Creates a value from an iterator. Read more
source§

impl<'a, I, P, H> IntoIterator for &'a DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher,

§

type Item = (&'a I, &'a P)

The type of the elements being iterated over.
§

type IntoIter = Iter<'a, I, P>

Which kind of iterator are we turning this into?
source§

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

Creates an iterator from a value. Read more
source§

impl<'a, I, P, H> IntoIterator for &'a mut DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord,

§

type Item = (&'a mut I, &'a mut P)

The type of the elements being iterated over.
§

type IntoIter = IterMut<'a, I, P, H>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> IterMut<'a, I, P, H>

Creates an iterator from a value. Read more
source§

impl<I, P, H> IntoIterator for DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher,

§

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?
source§

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

Creates an iterator from a value. Read more
source§

impl<I, P1, H1, P2, H2> PartialEq<DoublePriorityQueue<I, P2, H2>> for DoublePriorityQueue<I, P1, H1>
where I: Hash + Eq, P1: Ord + PartialEq<P2>, Option<P1>: PartialEq<Option<P2>>, P2: Ord, H1: BuildHasher, H2: BuildHasher,

source§

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

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

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

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl<I, P, H> Eq for DoublePriorityQueue<I, P, H>
where I: Hash + Eq, P: Ord, H: BuildHasher,

Auto Trait Implementations§

§

impl<I, P, H> RefUnwindSafe for DoublePriorityQueue<I, P, H>

§

impl<I, P, H> Send for DoublePriorityQueue<I, P, H>
where H: Send, I: Send, P: Send,

§

impl<I, P, H> Sync for DoublePriorityQueue<I, P, H>
where H: Sync, I: Sync, P: Sync,

§

impl<I, P, H> Unpin for DoublePriorityQueue<I, P, H>
where H: Unpin, I: Unpin, P: Unpin,

§

impl<I, P, H> UnwindSafe for DoublePriorityQueue<I, P, H>
where H: UnwindSafe, I: UnwindSafe, P: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.