Struct KeyedPriorityQueue

pub struct KeyedPriorityQueue<TKey, TPriority, S = RandomState>
where
    TKey: Hash + Eq,
    TPriority: Ord,
    S: BuildHasher,
{ /* private fields */ }

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.

If you feel KeyedPriorityQueue slow, it can be because it uses RandomState (relatably slow but strong against HashDoS attack) hasher by default. You can try fnv or fxhash crates hashers.

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 })
    }
}

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);

Implementations

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

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);

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

pub fn with_hasher(hasher: S) -> Self

Creates an empty queue with specific Hasher

Examples

use keyed_priority_queue::KeyedPriorityQueue;
use std::collections::hash_map::RandomState;
let mut queue = KeyedPriorityQueue::with_hasher(RandomState::default());
queue.push("Key", 4);

pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self

Creates an empty queue with allocated memory enough to keep capacity elements without reallocation. Also useful when Hasher cannot be defaulted.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
use std::collections::hash_map::RandomState;
let mut queue = KeyedPriorityQueue::with_capacity_and_hasher(10, RandomState::default());
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) -> Option<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 entry(&mut self, key: TKey) -> Entry<'_, TKey, TPriority, S>

Gets the given key’s corresponding entry in the map for in-place manipulation.

Time complexity

Amortized O(1), uses only one hash lookup

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

where TKey: Borrow<Q>, Q: Hash + Eq + ?Sized,

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 hash map key lookup).

pub fn set_priority<Q>( &mut self, key: &Q, priority: TPriority, ) -> Result<TPriority, SetPriorityNotFoundError>

where TKey: Borrow<Q>, Q: Hash + Eq + ?Sized,

Set new priority for existing key and reorder the queue. Returns old priority if succeeds or SetPriorityNotFoundError.

Examples

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

Time complexity

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

pub fn remove<Q>(&mut self, key: &Q) -> Option<TPriority>

where TKey: Borrow<Q>, Q: Hash + Eq + ?Sized,

Allow removing item by key. Returns priority if succeeds.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert_eq!(queue.remove(&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(&10), None);

Time complexity

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

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

where TKey: Borrow<Q>, Q: Hash + Eq + ?Sized,

Allow removing item by key. Returns key and priority if succeeds.

Examples

use keyed_priority_queue::KeyedPriorityQueue;
let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert_eq!(queue.remove_entry(&2), Some((2, 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_entry(&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)

pub fn iter(&self) -> KeyedPriorityQueueBorrowIter<'_, TKey, TPriority, S>

Create readonly borrowing iterator over heap

use keyed_priority_queue::KeyedPriorityQueue;
use std::collections::HashMap;
let queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
let mut entries = HashMap::new();
for (&key, &priority) in queue.iter(){
    entries.insert(key, priority);
}
let second_map: HashMap<i32, i32> = (0..5).map(|x|(x,x)).collect();
assert_eq!(entries, second_map);

Time complexity

Iterating over whole queue is O(n)

Trait Implementations

impl<TKey, TPriority, S> Clone for KeyedPriorityQueue<TKey, TPriority, S>

where TKey: Hash + Eq + Clone, TPriority: Ord + Clone, S: BuildHasher + Clone,

fn clone(&self) -> KeyedPriorityQueue<TKey, TPriority, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

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

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.

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

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.

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?