Struct keyed_priority_queue::KeyedPriorityQueue

pub struct KeyedPriorityQueue<TKey, TPriority> where
    TKey: Hash + Clone + Eq,
    TPriority: Ord,  { /* fields omitted */ }

A priority queue that support lookup by key.

Bigger TPriority values will have more priority.

It is logic error if priority values changes other way than by set_priority method. It is logic error if key values changes somehow while in queue. This changes normally possible only through Cell, RefCell, global state, IO, or unsafe code. Keys cloned and kept in queue in two instances. Priorities have one single instance in queue.

Examples

Main example

use keyed_priority_queue::KeyedPriorityQueue;

let mut queue = KeyedPriorityQueue::new();

// Currently queue is empty
assert_eq!(queue.peek(), None);

queue.push("Second", 4);
queue.push("Third", 3);
queue.push("First", 5);
queue.push("Fourth", 2);
queue.push("Fifth", 1);

// Peek return references to most important pair.
assert_eq!(queue.peek(), Some((&"First", &5)));

assert_eq!(queue.len(), 5);

// We can clone queue if both key and priority is clonable
let mut queue_clone = queue.clone();

// We can run consuming iterator on queue,
// and it will return items in decreasing order
for (key, priority) in queue_clone{
    println!("Priority of key {} is {}", key, priority);
}

// Popping always will return the biggest element
assert_eq!(queue.pop(), Some(("First", 5)));
// We can change priority of item by key:
queue.set_priority(&"Fourth", 10);
// And get it
assert_eq!(queue.get_priority(&"Fourth"), Some(&10));
// Now biggest element is Fourth
assert_eq!(queue.pop(), Some(("Fourth", 10)));
// We can also decrease priority!
queue.set_priority(&"Second", -1);
assert_eq!(queue.pop(), Some(("Third", 3)));
assert_eq!(queue.pop(), Some(("Fifth", 1)));
assert_eq!(queue.pop(), Some(("Second", -1)));
// Now queue is empty
assert_eq!(queue.pop(), None);

// We can clear queue
queue.clear();
assert!(queue.is_empty());

Partial ord queue

If you need to use float values (which don't implement Ord) as priority, you can use some wrapper that implement it:

use keyed_priority_queue::KeyedPriorityQueue;
use std::cmp::{Ord, Ordering, Eq, PartialEq, PartialOrd};

#[derive(Debug)]
struct OrdFloat(f32);

impl PartialOrd for OrdFloat {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(&other)) }
}

impl Eq for OrdFloat {}

impl PartialEq for OrdFloat {
    fn eq(&self, other: &Self) -> bool { self.cmp(&other) == Ordering::Equal }
}

impl Ord for OrdFloat {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.partial_cmp(&other.0)
            .unwrap_or(if self.0.is_nan() && other.0.is_nan() {
                Ordering::Equal
            } else if self.0.is_nan() {
                Ordering::Less
            } else { Ordering::Greater })
    }
}

fn main(){
    let mut queue = KeyedPriorityQueue::new();
    queue.push(5, OrdFloat(5.0));
    queue.push(4, OrdFloat(4.0));
    assert_eq!(queue.pop(), Some((5, OrdFloat(5.0))));
    assert_eq!(queue.pop(), Some((4, OrdFloat(4.0))));
    assert_eq!(queue.pop(), None);
}

Methods

impl<TKey: Hash + Clone + Eq, TPriority: Ord> KeyedPriorityQueue<TKey, TPriority>

pub fn new() -> Self

Creates an empty queue

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue = KeyedPriorityQueue::new();
queue.push("Key", 4);

pub fn with_capacity(capacity: usize) -> Self

Creates an empty queue with allocated memory enough to keep capacity elements without reallocation.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue = KeyedPriorityQueue::with_capacity(10);
queue.push("Key", 4);

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

Reserves space for at least additional new elements.

Panics

Panics if the new capacity overflows usize.

Examples

Basic usage:

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue = KeyedPriorityQueue::new();
queue.reserve(100);
queue.push(4, 4);

pub fn push(&mut self, key: TKey, priority: TPriority)

Adds new element to queue if missing key or replace its priority if key exists. In second case doesn't replace key.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue = KeyedPriorityQueue::new();
queue.push("First", 5);
assert_eq!(queue.peek(), Some((&"First", &5)));
queue.push("First", 10);
assert_eq!(queue.peek(), Some((&"First", &10)));

Time complexity

Average complexity is O(log n) If elements pushed in descending order, amortized complexity is O(1).

The worst case is when reallocation appears. In this case complexity of single call is O(n).

pub fn pop(&mut self) -> Option<(TKey, TPriority)>

Remove and return item with the maximal priority.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert_eq!(queue.pop(), Some((4,4)));
assert_eq!(queue.pop(), Some((3,3)));
assert_eq!(queue.pop(), Some((2,2)));
assert_eq!(queue.pop(), Some((1,1)));
assert_eq!(queue.pop(), Some((0,0)));

Time complexity

Cost of pop is always O(log n)

pub fn peek(&self) -> Option<(&TKey, &TPriority)>

Get reference to the pair with the maximal priority.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert_eq!(queue.peek(), Some((&4, &4)));

Time complexity

Always O(1)

pub fn get_priority(&self, key: &TKey) -> Option<&TPriority>

Get reference to the priority by key.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<&str, i32> = [("first", 0), ("second", 1), ("third", 2)]
                            .iter().cloned().collect();
assert_eq!(queue.get_priority(&"second"), Some(&1));

Time complexity

O(1) in average (limited by HashMap key lookup).

pub fn set_priority(&mut self, key: &TKey, priority: TPriority)

Set new priority by key and reorder the queue.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<&str, i32> = [("first", 0), ("second", 1), ("third", 2)]
                            .iter().cloned().collect();
queue.set_priority(&"second", 5);
assert_eq!(queue.get_priority(&"second"), Some(&5));
assert_eq!(queue.pop(), Some(("second", 5)));

Time complexity

In best case O(1), in average costs O(log n).

Panics

The function panics if key is missing.

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<&str, i32> = [("first", 0), ("second", 1), ("third", 2)]
                            .iter().cloned().collect();
queue.set_priority(&"Missing", 5);

pub fn remove_item(&mut self, key: &TKey) -> Option<TPriority>

Allow removing item by key.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert_eq!(queue.remove_item(&2), Some(2));
assert_eq!(queue.pop(), Some((4,4)));
assert_eq!(queue.pop(), Some((3,3)));
// There is no 2
assert_eq!(queue.pop(), Some((1,1)));
assert_eq!(queue.pop(), Some((0,0)));
assert_eq!(queue.remove_item(&10), None);

Time complexity

On average the function will require O(log n) operations.

pub fn len(&self) -> usize

Get the number of elements in queue.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert_eq!(queue.len(), 5);

Time complexity

Always O(1)

pub fn is_empty(&self) -> bool

Returns true if queue is empty.

let mut queue = keyed_priority_queue::KeyedPriorityQueue::new();
assert!(queue.is_empty());
queue.push(0,5);
assert!(!queue.is_empty());

Time complexity

Always O(1)

pub fn clear(&mut self)

Make the queue empty.

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert!(!queue.is_empty());
queue.clear();
assert!(queue.is_empty());

Time complexity

Always O(n)

Trait Implementations

impl<TKey: Hash + Clone + Eq + Send, TPriority: Ord + Send> Send for KeyedPriorityQueue<TKey, TPriority>

impl<TKey: Hash + Clone + Eq + Sync, TPriority: Ord + Sync> Sync for KeyedPriorityQueue<TKey, TPriority>

impl<TKey: Hash + Clone + Eq, TPriority: Ord> IntoIterator for KeyedPriorityQueue<TKey, TPriority>

type Item = (TKey, TPriority)

The type of the elements being iterated over.

type IntoIter = KeyedPriorityQueueIterator<TKey, TPriority>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Make iterator that return items in descending order.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<&str, i32> =
    [("first", 0), ("second", 1), ("third", 2)]
                            .iter().cloned().collect();
let mut iterator = queue.into_iter();
assert_eq!(iterator.next(), Some(("third", 2)));
assert_eq!(iterator.next(), Some(("second", 1)));
assert_eq!(iterator.next(), Some(("first", 0)));
assert_eq!(iterator.next(), None);

Time complexity

O(n log n) for iteration.

impl<TKey: Hash + Clone + Eq, TPriority: Ord + Clone> Clone for KeyedPriorityQueue<TKey, TPriority>

fn clone(&self) -> Self

Allow cloning the queue if keys and priorities are clonable.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
let mut cloned = queue.clone();
assert_eq!(queue.pop(), cloned.pop());
assert_eq!(queue.pop(), cloned.pop());
assert_eq!(queue.pop(), cloned.pop());
assert_eq!(queue.pop(), cloned.pop());
assert_eq!(queue.pop(), cloned.pop());
assert_eq!(queue.pop(), cloned.pop());

Time complexity

Always O(n)

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

Performs copy-assignment from source.

impl<TKey: Hash + Clone + Eq, TPriority: Ord> Default for KeyedPriorityQueue<TKey, TPriority>

fn default() -> Self

Returns the "default value" for a type.

impl<TKey: Hash + Clone + Eq + Debug, TPriority: Ord + Debug> Debug for KeyedPriorityQueue<TKey, TPriority>

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

Formats the value using the given formatter.

impl<TKey: Hash + Clone + Eq, TPriority: Ord> FromIterator<(TKey, TPriority)> for KeyedPriorityQueue<TKey, TPriority>

fn from_iter<T: IntoIterator<Item = (TKey, TPriority)>>(iter: T) -> Self

Allows building queue from iterator using collect(). At result it will be valid queue with unique keys.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<&str, i32> =
[("first", 0), ("second", 1), ("third", 2), ("first", -1)]
                            .iter().cloned().collect();
assert_eq!(queue.pop(), Some(("third", 2)));
assert_eq!(queue.pop(), Some(("second", 1)));
assert_eq!(queue.pop(), Some(("first", -1)));
assert_eq!(queue.pop(), None);

Time complexity

O(n log n) in average.