[−][src]Struct keyed_priority_queue::KeyedPriorityQueue
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.
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); }
Implementations
impl<TKey: Hash + Eq, TPriority: Ord> KeyedPriorityQueue<TKey, TPriority>
[src]
pub fn new() -> Self
[src]
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
[src]
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)
[src]
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>
[src]
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)>
[src]
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)>
[src]
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>
[src]
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: ?Sized>(&self, key: &Q) -> Option<&TPriority> where
TKey: Borrow<Q>,
Q: Hash + Eq,
[src]
TKey: Borrow<Q>,
Q: Hash + Eq,
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: ?Sized>(
&mut self,
key: &Q,
priority: TPriority
) -> Result<TPriority, SetPriorityNotFoundError> where
TKey: Borrow<Q>,
Q: Hash + Eq,
[src]
&mut self,
key: &Q,
priority: TPriority
) -> Result<TPriority, SetPriorityNotFoundError> where
TKey: Borrow<Q>,
Q: Hash + Eq,
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: ?Sized>(&mut self, key: &Q) -> Option<TPriority> where
TKey: Borrow<Q>,
Q: Hash + Eq,
[src]
TKey: Borrow<Q>,
Q: Hash + Eq,
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: ?Sized>(&mut self, key: &Q) -> Option<(TKey, TPriority)> where
TKey: Borrow<Q>,
Q: Hash + Eq,
[src]
TKey: Borrow<Q>,
Q: Hash + Eq,
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
[src]
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
[src]
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)
[src]
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>ⓘNotable traits for KeyedPriorityQueueBorrowIter<'a, TKey, TPriority>
impl<'a, TKey: 'a + Hash + Eq, TPriority: 'a> Iterator for KeyedPriorityQueueBorrowIter<'a, TKey, TPriority> type Item = (&'a TKey, &'a TPriority);
[src]
Notable traits for KeyedPriorityQueueBorrowIter<'a, TKey, TPriority>
impl<'a, TKey: 'a + Hash + Eq, TPriority: 'a> Iterator for KeyedPriorityQueueBorrowIter<'a, TKey, TPriority> type Item = (&'a TKey, &'a TPriority);
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: Clone, TPriority: Clone> Clone for KeyedPriorityQueue<TKey, TPriority> where
TKey: Hash + Eq,
TPriority: Ord,
[src]
TKey: Hash + Eq,
TPriority: Ord,
fn clone(&self) -> KeyedPriorityQueue<TKey, TPriority>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<TKey: Hash + Eq + Debug, TPriority: Ord + Debug> Debug for KeyedPriorityQueue<TKey, TPriority>
[src]
impl<TKey: Hash + Eq, TPriority: Ord> Default for KeyedPriorityQueue<TKey, TPriority>
[src]
impl<TKey: Hash + Eq, TPriority: Ord> FromIterator<(TKey, TPriority)> for KeyedPriorityQueue<TKey, TPriority>
[src]
fn from_iter<T: IntoIterator<Item = (TKey, TPriority)>>(iter: T) -> Self
[src]
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>
[src]
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
[src]
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.
Auto Trait Implementations
impl<TKey, TPriority> RefUnwindSafe for KeyedPriorityQueue<TKey, TPriority> where
TKey: RefUnwindSafe,
TPriority: RefUnwindSafe,
TKey: RefUnwindSafe,
TPriority: RefUnwindSafe,
impl<TKey, TPriority> Send for KeyedPriorityQueue<TKey, TPriority> where
TKey: Send,
TPriority: Send,
TKey: Send,
TPriority: Send,
impl<TKey, TPriority> Sync for KeyedPriorityQueue<TKey, TPriority> where
TKey: Sync,
TPriority: Sync,
TKey: Sync,
TPriority: Sync,
impl<TKey, TPriority> Unpin for KeyedPriorityQueue<TKey, TPriority> where
TKey: Unpin,
TPriority: Unpin,
TKey: Unpin,
TPriority: Unpin,
impl<TKey, TPriority> UnwindSafe for KeyedPriorityQueue<TKey, TPriority> where
TKey: UnwindSafe,
TPriority: UnwindSafe,
TKey: UnwindSafe,
TPriority: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<I> IntoIterator for I where
I: Iterator,
[src]
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,