Struct RustyPriorityQueue

pub struct RustyPriorityQueue<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> { /* private fields */ }

A priority queue implementation based on Rust’s BinaryHeap. Templated with P for priority and T for data.

• P must be PartialOrd, PartialEq, and Eq.
• T must be PartialEq and Eq.

If Node A and Node B have the same priority, but Node A was added before Node B, then Node A will be prioritized over Node B. See PriorityQueue for more information.

Examples

let mut prio = RustyPriorityQueue::<usize, String>::default();
prio.enqueue(2, "hello".to_string());
prio.enqueue(3, "julia".to_string());
prio.enqueue(1, "world".to_string());
prio.enqueue(3, "naomi".to_string());

let mut new_prio: RustyPriorityQueue<usize, String> = prio
    .into_iter()
    .map(|(priority, data)| (priority, data.to_owned() + " wow"))
    .collect();

assert_eq!(new_prio.dequeue(), Some((3, "julia wow".to_string())));
assert_eq!(new_prio.dequeue(), Some((3, "naomi wow".to_string())));
assert_eq!(new_prio.dequeue(), Some((2, "hello wow".to_string())));
assert_eq!(new_prio.dequeue(), Some((1, "world wow".to_string())));

Implementations

impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> RustyPriorityQueue<P, T>

pub const fn iter(&self) -> RustyPriorityQueueIterator<'_, P, T>

Get an iterator over the priority queue

pub fn into_iter(self) -> RustyPriorityQueueIntoIterator<P, T>

Convert the priority queue into an iterator

pub fn update(self, old: P, new: P, data: &T) -> Self

Update the priority of an item in the queue.

This is a very slow operation!

• it uses unsafe std::mem::transmute_copy under the hhod to guarantee allocation of priority P on every possible scenario.

Examples

let mut prio = RustyPriorityQueue::<usize, String>::default();
prio.enqueue(5, "julia".to_string());
prio.enqueue(2, "hello".to_string());
prio.enqueue(3, "julia".to_string());
prio.enqueue(1, "world".to_string());
prio.enqueue(3, "naomi".to_string());
let ref_str = "julia".to_string();
let mut new = prio.update(3, 7,&ref_str);
assert_eq!(new.dequeue(), Some((7, "julia".to_string())));
assert_eq!(new.dequeue(), Some((5, "julia".to_string())));
assert_eq!(new.dequeue(), Some((3, "naomi".to_string())));
assert_eq!(new.dequeue(), Some((2, "hello".to_string())));
assert_eq!(new.dequeue(), Some((1, "world".to_string())));

pub fn update_as(&mut self, old: P, new: P, data: T)

Update the priority of an item in the queue with a reference to the data.

Trait Implementations

impl<P: Debug + PartialOrd + PartialEq + Eq, T: Debug + PartialEq + Eq> Debug for RustyPriorityQueue<P, T>

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

Formats the value using the given formatter.

impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> Default for RustyPriorityQueue<P, T>

fn default() -> Self

Returns the “default value” for a type.

impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> FromIterator<(P, T)> for RustyPriorityQueue<P, T>

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

Creates a value from an iterator.

impl<'b, P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> IntoIterator for &'b RustyPriorityQueue<P, T>

type IntoIter = RustyPriorityQueueIterator<'b, P, T>

Which kind of iterator are we turning this into?

type Item = (&'b P, &'b T)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> IntoIterator for RustyPriorityQueue<P, T>

type Item = (P, T)

The type of the elements being iterated over.

type IntoIter = RustyPriorityQueueIntoIterator<P, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> PriorityQueue<P, T> for RustyPriorityQueue<P, T>

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = (P, T)>,

Extend the priority queue with an iterator

Examples

let mut prio = RustyPriorityQueue::<usize, String>::default();
prio.extend(vec![(2, "world".to_string()), (3, "hello".to_string())]);
assert_eq!(prio.dequeue(), Some((3, "hello".to_string())));
assert_eq!(prio.dequeue(), Some((2, "world".to_string())));
assert_eq!(prio.dequeue(), None);

fn with_capacity(capacity: usize) -> Self

Create a new priority queue with a given capacity

fn enqueue(&mut self, priority: P, data: T)

Add an item to the queue

fn dequeue(&mut self) -> Option<(P, T)>

Remove an item from the queue

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

Peeks the next item in the queue

fn len(&self) -> usize

Queue length

fn is_empty(&self) -> bool

Boolean if the queue is empty

fn capacity(&self) -> usize

Queue capacity

fn append(&mut self, other: Self)

Append another priority queue into this one

fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional elements more than the current length. The allocator may reserve more space to speculatively avoid frequent allocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for at least additional elements more than the current length. Unlike reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations. After calling reserve_exact, capacity will be greater than or equal to self.len() + additional. Does nothing if the capacity is already sufficient.

fn shrink_to_fit(&mut self)

Discards as much additional capacity as possible.

fn shrink_to(&mut self, capacity: usize)

Discards capacity with a lower bound. The capacity will remain at least as large as both the length and the supplied value. If the current capacity is less than the lower limit, this is a no-op.

fn clear(&mut self)

Removes all items from the queue

fn drain(&mut self) -> impl Iterator<Item = (P, T)> + '_

Clears the binary heap, returning an iterator over the removed elements in arbitrary order. If the iterator is dropped before being fully consumed, it drops the remaining elements in arbitrary order.

fn contains(&self, data: &T) -> bool

Check if an item exists in the queue true if it exists, false if it does not

fn contains_at(&self, priority: &P, data: &T) -> bool

Check if an item exists in the queue at a certain priority true if it exists, false if it does not

fn remove(&mut self, data: &T) -> bool

Remove all existing items from the queue true if it was removed, false if it was not

fn remove_at(&mut self, priority: &P, data: &T) -> bool

Remove an item from the queue if exists at a certain priority true if it was removed, false if it was not

fn max_node(&self) -> Option<(&P, &T)>

Returns the node the the highest priority in the queue. If no nodes exist, None is returned.

fn min_node(&self) -> Option<(&P, &T)>

Returns the node the the lowest priority in the queue. If no nodes exist, None is returned.