keyed_priority_queue/keyed_priority_queue.rs
1use std::borrow::Borrow;
2use std::collections::hash_map::RandomState;
3use std::fmt::{Debug, Display};
4use std::hash::{BuildHasher, Hash};
5use std::iter::FromIterator;
6
7use crate::editable_binary_heap::{BinaryHeap, BinaryHeapIterator};
8use crate::mediator::{
9 Mediator, MediatorEntry, MediatorIndex, OccupiedEntry as MediatorOccupiedEntry,
10 VacantEntry as MediatorVacantEntry,
11};
12
13/// A priority queue that support lookup by key.
14///
15/// Bigger `TPriority` values will have more priority.
16///
17/// It is logic error if priority values changes other way than by [`set_priority`] method.
18/// It is logic error if key values changes somehow while in queue.
19/// This changes normally possible only through `Cell`, `RefCell`, global state, IO, or unsafe code.
20///
21/// If you feel KeyedPriorityQueue slow, it can be because it uses RandomState (relatably slow but strong against HashDoS attack) hasher by default.
22/// You can try [fnv] or [fxhash] crates hashers.
23///
24/// [`set_priority`]: struct.KeyedPriorityQueue.html#method.set_priority
25/// [fnv]: https://crates.io/crates/fnv
26/// [fxhash]: https://crates.io/crates/fxhash
27///
28/// # Examples
29///
30/// ## Main example
31/// ```
32/// use keyed_priority_queue::KeyedPriorityQueue;
33///
34/// let mut queue = KeyedPriorityQueue::new();
35///
36/// // Currently queue is empty
37/// assert_eq!(queue.peek(), None);
38///
39/// queue.push("Second", 4);
40/// queue.push("Third", 3);
41/// queue.push("First", 5);
42/// queue.push("Fourth", 2);
43/// queue.push("Fifth", 1);
44///
45/// // Peek return references to most important pair.
46/// assert_eq!(queue.peek(), Some((&"First", &5)));
47///
48/// assert_eq!(queue.len(), 5);
49///
50/// // We can clone queue if both key and priority is clonable
51/// let mut queue_clone = queue.clone();
52///
53/// // We can run consuming iterator on queue,
54/// // and it will return items in decreasing order
55/// for (key, priority) in queue_clone{
56/// println!("Priority of key {} is {}", key, priority);
57/// }
58///
59/// // Popping always will return the biggest element
60/// assert_eq!(queue.pop(), Some(("First", 5)));
61/// // We can change priority of item by key:
62/// queue.set_priority(&"Fourth", 10);
63/// // And get it
64/// assert_eq!(queue.get_priority(&"Fourth"), Some(&10));
65/// // Now biggest element is Fourth
66/// assert_eq!(queue.pop(), Some(("Fourth", 10)));
67/// // We can also decrease priority!
68/// queue.set_priority(&"Second", -1);
69/// assert_eq!(queue.pop(), Some(("Third", 3)));
70/// assert_eq!(queue.pop(), Some(("Fifth", 1)));
71/// assert_eq!(queue.pop(), Some(("Second", -1)));
72/// // Now queue is empty
73/// assert_eq!(queue.pop(), None);
74///
75/// // We can clear queue
76/// queue.clear();
77/// assert!(queue.is_empty());
78/// ```
79///
80/// ## Partial ord queue
81///
82/// If you need to use float values (which don't implement Ord) as priority,
83/// you can use some wrapper that implement it:
84///
85/// ```
86/// use keyed_priority_queue::KeyedPriorityQueue;
87/// use std::cmp::{Ord, Ordering, Eq, PartialEq, PartialOrd};
88///
89/// #[derive(Debug)]
90/// struct OrdFloat(f32);
91///
92/// impl PartialOrd for OrdFloat {
93/// fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(&other)) }
94/// }
95///
96/// impl Eq for OrdFloat {}
97///
98/// impl PartialEq for OrdFloat {
99/// fn eq(&self, other: &Self) -> bool { self.cmp(&other) == Ordering::Equal }
100/// }
101///
102/// impl Ord for OrdFloat {
103/// fn cmp(&self, other: &Self) -> Ordering {
104/// self.0.partial_cmp(&other.0)
105/// .unwrap_or(if self.0.is_nan() && other.0.is_nan() {
106/// Ordering::Equal
107/// } else if self.0.is_nan() {
108/// Ordering::Less
109/// } else { Ordering::Greater })
110/// }
111/// }
112///
113/// let mut queue = KeyedPriorityQueue::new();
114/// queue.push(5, OrdFloat(5.0));
115/// queue.push(4, OrdFloat(4.0));
116/// assert_eq!(queue.pop(), Some((5, OrdFloat(5.0))));
117/// assert_eq!(queue.pop(), Some((4, OrdFloat(4.0))));
118/// assert_eq!(queue.pop(), None);
119/// ```
120#[derive(Clone)]
121pub struct KeyedPriorityQueue<TKey, TPriority, S = RandomState>
122where
123 TKey: Hash + Eq,
124 TPriority: Ord,
125 S: BuildHasher,
126{
127 heap: BinaryHeap<TPriority>,
128 key_to_pos: Mediator<TKey, S>,
129}
130
131impl<TKey: Hash + Eq, TPriority: Ord> KeyedPriorityQueue<TKey, TPriority, RandomState> {
132 /// Creates an empty queue
133 ///
134 /// ### Examples
135 ///
136 ///
137 /// ```
138 /// use keyed_priority_queue::KeyedPriorityQueue;
139 /// let mut queue = KeyedPriorityQueue::new();
140 /// queue.push("Key", 4);
141 /// ```
142 #[inline]
143 pub fn new() -> Self {
144 Self::with_capacity_and_hasher(0, RandomState::default())
145 }
146
147 /// Creates an empty queue with allocated memory enough
148 /// to keep `capacity` elements without reallocation.
149 ///
150 /// ### Examples
151 ///
152 ///
153 /// ```
154 /// use keyed_priority_queue::KeyedPriorityQueue;
155 /// let mut queue = KeyedPriorityQueue::with_capacity(10);
156 /// queue.push("Key", 4);
157 /// ```
158 #[inline]
159 pub fn with_capacity(capacity: usize) -> Self {
160 Self::with_capacity_and_hasher(capacity, RandomState::default())
161 }
162}
163
164impl<TKey: Hash + Eq, TPriority: Ord, S: BuildHasher> KeyedPriorityQueue<TKey, TPriority, S> {
165 /// Creates an empty queue with specific Hasher
166 ///
167 /// ### Examples
168 ///
169 ///
170 /// ```
171 /// use keyed_priority_queue::KeyedPriorityQueue;
172 /// use std::collections::hash_map::RandomState;
173 /// let mut queue = KeyedPriorityQueue::with_hasher(RandomState::default());
174 /// queue.push("Key", 4);
175 /// ```
176 #[inline]
177 pub fn with_hasher(hasher: S) -> Self {
178 Self::with_capacity_and_hasher(0, hasher)
179 }
180
181 /// Creates an empty queue with allocated memory enough
182 /// to keep `capacity` elements without reallocation.
183 /// Also useful when Hasher cannot be defaulted.
184 ///
185 /// ### Examples
186 ///
187 ///
188 /// ```
189 /// use keyed_priority_queue::KeyedPriorityQueue;
190 /// use std::collections::hash_map::RandomState;
191 /// let mut queue = KeyedPriorityQueue::with_capacity_and_hasher(10, RandomState::default());
192 /// queue.push("Key", 4);
193 /// ```
194 #[inline]
195 pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
196 Self {
197 heap: BinaryHeap::with_capacity(capacity),
198 key_to_pos: Mediator::with_capacity_and_hasher(capacity, hasher),
199 }
200 }
201
202 /// Reserves space for at least `additional` new elements.
203 ///
204 /// ### Panics
205 ///
206 /// Panics if the new capacity overflows `usize`.
207 ///
208 /// ### Examples
209 ///
210 /// Basic usage:
211 ///
212 /// ```
213 /// use keyed_priority_queue::KeyedPriorityQueue;
214 /// let mut queue = KeyedPriorityQueue::new();
215 /// queue.reserve(100);
216 /// queue.push(4, 4);
217 /// ```
218 #[inline]
219 pub fn reserve(&mut self, additional: usize) {
220 self.heap.reserve(additional);
221 self.key_to_pos.reserve(additional);
222 }
223
224 /// Adds new element to queue if missing key or replace its priority if key exists.
225 /// In second case doesn't replace key.
226 ///
227 /// ### Examples
228 ///
229 ///
230 /// ```
231 /// use keyed_priority_queue::KeyedPriorityQueue;
232 /// let mut queue = KeyedPriorityQueue::new();
233 /// queue.push("First", 5);
234 /// assert_eq!(queue.peek(), Some((&"First", &5)));
235 /// queue.push("First", 10);
236 /// assert_eq!(queue.peek(), Some((&"First", &10)));
237 /// ```
238 ///
239 /// ### Time complexity
240 ///
241 /// Average complexity is ***O(log n)***
242 /// If elements pushed in descending order, amortized complexity is ***O(1)***.
243 ///
244 /// The worst case is when reallocation appears.
245 /// In this case complexity of single call is ***O(n)***.
246 pub fn push(&mut self, key: TKey, priority: TPriority) -> Option<TPriority> {
247 match self.entry(key) {
248 Entry::Vacant(entry) => {
249 entry.set_priority(priority);
250 None
251 }
252 Entry::Occupied(entry) => Some(entry.set_priority(priority)),
253 }
254 }
255
256 /// Remove and return item with the maximal priority.
257 ///
258 /// ### Examples
259 ///
260 ///
261 /// ```
262 /// use keyed_priority_queue::KeyedPriorityQueue;
263 /// let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
264 /// assert_eq!(queue.pop(), Some((4,4)));
265 /// assert_eq!(queue.pop(), Some((3,3)));
266 /// assert_eq!(queue.pop(), Some((2,2)));
267 /// assert_eq!(queue.pop(), Some((1,1)));
268 /// assert_eq!(queue.pop(), Some((0,0)));
269 /// ```
270 ///
271 /// ### Time complexity
272 ///
273 /// Cost of pop is always ***O(log n)***
274 pub fn pop(&mut self) -> Option<(TKey, TPriority)> {
275 let (to_remove, _) = self.heap.most_prioritized_idx()?;
276 Some(self.remove_internal(to_remove))
277 }
278
279 /// Get reference to the pair with the maximal priority.
280 ///
281 /// ### Examples
282 ///
283 ///
284 /// ```
285 /// use keyed_priority_queue::KeyedPriorityQueue;
286 /// let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
287 /// assert_eq!(queue.peek(), Some((&4, &4)));
288 /// ```
289 ///
290 /// ### Time complexity
291 ///
292 /// Always ***O(1)***
293 pub fn peek(&self) -> Option<(&TKey, &TPriority)> {
294 let (first_idx, heap_idx) = self.heap.most_prioritized_idx()?;
295 let (key, _) = self.key_to_pos.get_index(first_idx);
296 let (_, priority) = self
297 .heap
298 .look_into(heap_idx)
299 .expect("Checked using key_to_pos");
300 Some((key, priority))
301 }
302
303 /// Gets the given key's corresponding entry in the map for in-place manipulation.
304 ///
305 /// ## Time complexity
306 /// Amortized ***O(1)***, uses only one hash lookup
307 pub fn entry(&mut self, key: TKey) -> Entry<TKey, TPriority, S> {
308 // Borrow checker treats borrowing a field as borrowing whole structure
309 // so we need to get references to fields to borrow them individually.
310 let key_to_pos = &mut self.key_to_pos;
311 let heap = &mut self.heap;
312
313 match key_to_pos.entry(key) {
314 MediatorEntry::Vacant(internal_entry) => Entry::Vacant(VacantEntry {
315 internal_entry,
316 heap,
317 }),
318 MediatorEntry::Occupied(internal_entry) => Entry::Occupied(OccupiedEntry {
319 internal_entry,
320 heap,
321 }),
322 }
323 }
324
325 /// Get reference to the priority by key.
326 ///
327 /// ### Examples
328 ///
329 ///
330 /// ```
331 /// use keyed_priority_queue::KeyedPriorityQueue;
332 /// let mut queue: KeyedPriorityQueue<&str, i32> = [("first", 0), ("second", 1), ("third", 2)]
333 /// .iter().cloned().collect();
334 /// assert_eq!(queue.get_priority(&"second"), Some(&1));
335 /// ```
336 ///
337 /// ### Time complexity
338 ///
339 /// ***O(1)*** in average (limited by hash map key lookup).
340 pub fn get_priority<Q>(&self, key: &Q) -> Option<&TPriority>
341 where
342 TKey: Borrow<Q>,
343 Q: Hash + Eq + ?Sized,
344 {
345 let heap_idx = self.key_to_pos.get(key)?;
346 Some(
347 self.heap
348 .look_into(heap_idx)
349 .expect("Must contain if key_to_pos contain")
350 .1,
351 )
352 }
353
354 /// Set new priority for existing key and reorder the queue.
355 /// Returns old priority if succeeds or [`SetPriorityNotFoundError`].
356 ///
357 /// ### Examples
358 ///
359 ///
360 /// ```
361 /// use keyed_priority_queue::{KeyedPriorityQueue, SetPriorityNotFoundError};
362 /// let mut queue: KeyedPriorityQueue<&str, i32> = [("first", 0), ("second", 1), ("third", 2)]
363 /// .iter().cloned().collect();
364 /// assert_eq!(queue.set_priority(&"second", 5), Ok(1));
365 /// assert_eq!(queue.get_priority(&"second"), Some(&5));
366 /// assert_eq!(queue.pop(), Some(("second", 5)));
367 /// assert_eq!(queue.set_priority(&"Missing", 5), Err(SetPriorityNotFoundError{}));
368 /// ```
369 ///
370 /// ### Time complexity
371 ///
372 /// In best case ***O(1)***, in average costs ***O(log n)***.
373 ///
374 /// [`SetPriorityNotFoundError`]: struct.SetPriorityNotFoundError.html
375 #[inline]
376 pub fn set_priority<Q>(
377 &mut self,
378 key: &Q,
379 priority: TPriority,
380 ) -> Result<TPriority, SetPriorityNotFoundError>
381 where
382 TKey: Borrow<Q>,
383 Q: Hash + Eq + ?Sized,
384 {
385 let map_pos = match self.key_to_pos.get_full(key) {
386 None => return Err(SetPriorityNotFoundError {}),
387 Some((idx, _, _)) => idx,
388 };
389
390 Ok(self.set_priority_internal(map_pos, priority))
391 }
392
393 /// Allow removing item by key.
394 /// Returns priority if succeeds.
395 ///
396 /// ### Examples
397 ///
398 ///
399 /// ```
400 /// use keyed_priority_queue::KeyedPriorityQueue;
401 /// let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
402 /// assert_eq!(queue.remove(&2), Some(2));
403 /// assert_eq!(queue.pop(), Some((4,4)));
404 /// assert_eq!(queue.pop(), Some((3,3)));
405 /// // There is no 2
406 /// assert_eq!(queue.pop(), Some((1,1)));
407 /// assert_eq!(queue.pop(), Some((0,0)));
408 /// assert_eq!(queue.remove(&10), None);
409 /// ```
410 ///
411 /// ### Time complexity
412 ///
413 /// On average the function will require ***O(log n)*** operations.
414 #[inline]
415 pub fn remove<Q>(&mut self, key: &Q) -> Option<TPriority>
416 where
417 TKey: Borrow<Q>,
418 Q: Hash + Eq + ?Sized,
419 {
420 let (_, priority) = self.remove_entry(key)?;
421 Some(priority)
422 }
423
424 /// Allow removing item by key.
425 /// Returns key and priority if succeeds.
426 ///
427 /// ### Examples
428 ///
429 ///
430 /// ```
431 /// use keyed_priority_queue::KeyedPriorityQueue;
432 /// let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
433 /// assert_eq!(queue.remove_entry(&2), Some((2, 2)));
434 /// assert_eq!(queue.pop(), Some((4,4)));
435 /// assert_eq!(queue.pop(), Some((3,3)));
436 /// // There is no 2
437 /// assert_eq!(queue.pop(), Some((1,1)));
438 /// assert_eq!(queue.pop(), Some((0,0)));
439 /// assert_eq!(queue.remove_entry(&10), None);
440 /// ```
441 ///
442 /// ### Time complexity
443 ///
444 /// On average the function will require ***O(log n)*** operations.
445 #[inline]
446 pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(TKey, TPriority)>
447 where
448 TKey: Borrow<Q>,
449 Q: Hash + Eq + ?Sized,
450 {
451 let (index, _, _) = self.key_to_pos.get_full(key)?;
452 Some(self.remove_internal(index))
453 }
454
455 /// Get the number of elements in queue.
456 ///
457 /// ### Examples
458 ///
459 ///
460 /// ```
461 /// use keyed_priority_queue::KeyedPriorityQueue;
462 /// let queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
463 /// assert_eq!(queue.len(), 5);
464 /// ```
465 ///
466 /// ### Time complexity
467 ///
468 /// Always ***O(1)***
469 #[inline]
470 pub fn len(&self) -> usize {
471 debug_assert_eq!(self.key_to_pos.len(), self.heap.usize_len());
472 self.key_to_pos.len()
473 }
474
475 /// Returns true if queue is empty.
476 ///
477 /// ```
478 /// let mut queue = keyed_priority_queue::KeyedPriorityQueue::new();
479 /// assert!(queue.is_empty());
480 /// queue.push(0,5);
481 /// assert!(!queue.is_empty());
482 /// ```
483 ///
484 /// ### Time complexity
485 ///
486 /// Always ***O(1)***
487 #[inline]
488 pub fn is_empty(&self) -> bool {
489 debug_assert_eq!(self.heap.is_empty(), self.key_to_pos.is_empty());
490 self.key_to_pos.is_empty()
491 }
492
493 /// Make the queue empty.
494 ///
495 /// ```
496 /// use keyed_priority_queue::KeyedPriorityQueue;
497 /// let mut queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
498 /// assert!(!queue.is_empty());
499 /// queue.clear();
500 /// assert!(queue.is_empty());
501 /// ```
502 ///
503 /// ### Time complexity
504 ///
505 /// Always ***O(n)***
506 #[inline]
507 pub fn clear(&mut self) {
508 self.heap.clear();
509 self.key_to_pos.clear();
510 }
511
512 /// Create readonly borrowing iterator over heap
513 ///
514 /// ```
515 /// use keyed_priority_queue::KeyedPriorityQueue;
516 /// use std::collections::HashMap;
517 /// let queue: KeyedPriorityQueue<i32, i32> = (0..5).map(|x|(x,x)).collect();
518 /// let mut entries = HashMap::new();
519 /// for (&key, &priority) in queue.iter(){
520 /// entries.insert(key, priority);
521 /// }
522 /// let second_map: HashMap<i32, i32> = (0..5).map(|x|(x,x)).collect();
523 /// assert_eq!(entries, second_map);
524 /// ```
525 ///
526 /// ### Time complexity
527 ///
528 /// Iterating over whole queue is ***O(n)***
529 pub fn iter(&self) -> KeyedPriorityQueueBorrowIter<TKey, TPriority, S> {
530 KeyedPriorityQueueBorrowIter {
531 key_to_pos: &self.key_to_pos,
532 heap_iterator: self.heap.iter(),
533 }
534 }
535
536 // Removes entry from by index of map
537 fn remove_internal(&mut self, position: MediatorIndex) -> (TKey, TPriority) {
538 // Borrow checker treats borrowing a field as borrowing whole structure
539 // so we need to get references to fields to borrow them individually.
540 let key_to_pos = &mut self.key_to_pos;
541 let heap = &mut self.heap;
542
543 let (_, heap_to_rem) = key_to_pos.get_index(position);
544
545 let (removed_idx, priority) = heap
546 .remove(heap_to_rem, |index, heap_idx| {
547 *key_to_pos.get_index_mut(index) = heap_idx
548 })
549 .expect("Checked by key_to_pos");
550 debug_assert_eq!(position, removed_idx);
551
552 let (removed_key, _) = key_to_pos.swap_remove_index(position);
553 if MediatorIndex(key_to_pos.len()) != removed_idx {
554 let (_, heap_idx_of_moved) = key_to_pos.get_index(removed_idx);
555 heap.change_outer_pos(removed_idx, heap_idx_of_moved);
556 }
557
558 (removed_key, priority)
559 }
560
561 // Do O(log n) heap updates and by-index map changes
562 fn set_priority_internal(&mut self, position: MediatorIndex, priority: TPriority) -> TPriority {
563 // Borrow checker treats borrowing a field as borrowing whole structure
564 // so we need to get references to fields to borrow them individually.
565 let heap = &mut self.heap;
566 let key_to_pos = &mut self.key_to_pos;
567
568 let (_, heap_idx) = key_to_pos.get_index(position);
569
570 heap.change_priority(heap_idx, priority, |index, heap_idx| {
571 *key_to_pos.get_index_mut(index) = heap_idx
572 })
573 }
574}
575
576/// A view into a single entry in a queue, which may either be vacant or occupied.
577///
578/// This `enum` is constructed from the [`entry`] method on [`KeyedPriorityQueue`].
579///
580/// [`KeyedPriorityQueue`]: struct.KeyedPriorityQueue.html
581/// [`entry`]: struct.KeyedPriorityQueue.html#method.entry
582pub enum Entry<'a, TKey: Eq + Hash, TPriority: Ord, S: BuildHasher> {
583 /// An occupied entry.
584 Occupied(OccupiedEntry<'a, TKey, TPriority, S>),
585
586 /// A vacant entry.
587 Vacant(VacantEntry<'a, TKey, TPriority, S>),
588}
589
590/// A view into an occupied entry in a [`KeyedPriorityQueue`].
591/// It is part of the [`Entry`] enum.
592///
593/// [`Entry`]: enum.Entry.html
594/// [`KeyedPriorityQueue`]: struct.KeyedPriorityQueue.html
595pub struct OccupiedEntry<'a, TKey, TPriority, S = RandomState>
596where
597 TKey: 'a + Eq + Hash,
598 TPriority: 'a + Ord,
599 S: BuildHasher,
600{
601 internal_entry: MediatorOccupiedEntry<'a, TKey, S>,
602 heap: &'a mut BinaryHeap<TPriority>,
603}
604
605impl<'a, TKey, TPriority, S> OccupiedEntry<'a, TKey, TPriority, S>
606where
607 TKey: 'a + Eq + Hash,
608 TPriority: 'a + Ord,
609 S: BuildHasher,
610{
611 /// Returns reference to the priority associated to entry
612 ///
613 /// ## Time complexity
614 /// ***O(1)*** instant access
615 #[inline]
616 pub fn get_priority(&self) -> &TPriority {
617 let heap_idx = self.internal_entry.get_heap_idx();
618 self.heap.look_into(heap_idx).expect("Must be in queue").1
619 }
620
621 /// Changes priority of key and returns old priority
622 ///
623 /// ## Time complexity
624 /// Up to ***O(log n)*** operations in worst case
625 /// ***O(1)*** in best case
626 #[inline]
627 pub fn set_priority(mut self, priority: TPriority) -> TPriority {
628 let heap_idx = self.internal_entry.get_heap_idx();
629
630 let heap = &mut self.heap;
631 let key_to_pos = unsafe {
632 // Safety: reference used only inside the method and never leaked away
633 // This method can be called only when Mediator field alive along with queue itself.
634 self.internal_entry.transform_to_map()
635 };
636
637 heap.change_priority(heap_idx, priority, |index, heap_idx| {
638 *key_to_pos.get_index_mut(index) = heap_idx;
639 })
640 }
641
642 /// Get the reference to actual key
643 ///
644 /// ## Time complexity
645 /// ***O(1)*** instant access
646 #[inline]
647 pub fn get_key(&self) -> &TKey {
648 self.internal_entry.get_key()
649 }
650
651 /// Remove entry from queue
652 ///
653 /// ## Time complexity
654 /// Up to ***O(log n)*** operations
655 pub fn remove(mut self) -> (TKey, TPriority) {
656 let heap_idx = self.internal_entry.get_heap_idx();
657 // Look `Mediator` `entry` method
658 let key_to_pos = unsafe {
659 // Safety: reference used only inside the method and never leaked away
660 // This method can be called only when Mediator field alive along with queue itself.
661 self.internal_entry.transform_to_map()
662 };
663 let heap = &mut self.heap;
664
665 let (removed_idx, priority) = heap
666 .remove(heap_idx, |index, heap_idx| {
667 *key_to_pos.get_index_mut(index) = heap_idx
668 })
669 .expect("Checked by key_to_pos");
670
671 let (removed_key, _) = key_to_pos.swap_remove_index(removed_idx);
672 if MediatorIndex(key_to_pos.len()) != removed_idx {
673 let (_, heap_idx_of_moved) = key_to_pos.get_index(removed_idx);
674 heap.change_outer_pos(removed_idx, heap_idx_of_moved);
675 }
676
677 (removed_key, priority)
678 }
679}
680
681/// A view into a vacant entry in a [`KeyedPriorityQueue`].
682/// It is part of the [`Entry`] enum.
683///
684/// [`Entry`]: enum.Entry.html
685/// [`KeyedPriorityQueue`]: struct.KeyedPriorityQueue.html
686pub struct VacantEntry<'a, TKey, TPriority, S = RandomState>
687where
688 TKey: 'a + Eq + Hash,
689 TPriority: 'a + Ord,
690 S: BuildHasher,
691{
692 internal_entry: MediatorVacantEntry<'a, TKey, S>,
693 heap: &'a mut BinaryHeap<TPriority>,
694}
695
696impl<'a, TKey, TPriority, S> VacantEntry<'a, TKey, TPriority, S>
697where
698 TKey: 'a + Eq + Hash,
699 TPriority: 'a + Ord,
700 S: BuildHasher,
701{
702 /// Insert priority of key to queue
703 ///
704 /// ## Time complexity
705 /// Up to ***O(log n)*** operations
706 #[inline]
707 pub fn set_priority(self, priority: TPriority) {
708 let heap = self.heap;
709 let internal_entry = self.internal_entry;
710 let (key_to_pos, mediator_index) = unsafe {
711 // Safety: reference used only inside the method and never leaked away
712 // This method can be called only when Mediator field alive along with queue itself.
713 internal_entry.insert(heap.len())
714 };
715 heap.push(mediator_index, priority, |index, val| {
716 *key_to_pos.get_index_mut(index) = val
717 });
718 }
719
720 /// Get the reference to actual key
721 ///
722 /// ## Time complexity
723 /// ***O(1)*** instant access
724 #[inline]
725 pub fn get_key(&self) -> &TKey {
726 self.internal_entry.get_key()
727 }
728}
729
730impl<TKey: Hash + Eq + Debug, TPriority: Ord + Debug, S: BuildHasher> Debug
731 for KeyedPriorityQueue<TKey, TPriority, S>
732{
733 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
734 write!(f, "[")?;
735 for entry in self.iter() {
736 write!(f, "{:?}", entry)?;
737 }
738 write!(f, "]")
739 }
740}
741
742impl<TKey: Hash + Eq, TPriority: Ord, S: BuildHasher + Default> Default
743 for KeyedPriorityQueue<TKey, TPriority, S>
744{
745 #[inline]
746 fn default() -> Self {
747 Self::with_capacity_and_hasher(0, S::default())
748 }
749}
750
751impl<TKey: Hash + Eq, TPriority: Ord, S: BuildHasher + Default> FromIterator<(TKey, TPriority)>
752 for KeyedPriorityQueue<TKey, TPriority, S>
753{
754 /// Allows building queue from iterator using `collect()`.
755 /// At result it will be valid queue with unique keys.
756 ///
757 /// ### Examples
758 ///
759 ///
760 /// ```
761 /// use keyed_priority_queue::KeyedPriorityQueue;
762 /// let mut queue: KeyedPriorityQueue<&str, i32> =
763 /// [("first", 0), ("second", 1), ("third", 2), ("first", -1)]
764 /// .iter().cloned().collect();
765 /// assert_eq!(queue.pop(), Some(("third", 2)));
766 /// assert_eq!(queue.pop(), Some(("second", 1)));
767 /// assert_eq!(queue.pop(), Some(("first", -1)));
768 /// assert_eq!(queue.pop(), None);
769 /// ```
770 ///
771 /// ### Time complexity
772 ///
773 /// ***O(n log n)*** in average.
774 fn from_iter<T: IntoIterator<Item = (TKey, TPriority)>>(iter: T) -> Self {
775 let (heap, key_to_pos) = BinaryHeap::produce_from_iter_hash(iter);
776 Self { heap, key_to_pos }
777 }
778}
779
780impl<TKey: Hash + Eq, TPriority: Ord> IntoIterator for KeyedPriorityQueue<TKey, TPriority> {
781 type Item = (TKey, TPriority);
782 type IntoIter = KeyedPriorityQueueIterator<TKey, TPriority>;
783
784 /// Make iterator that return items in descending order.
785 ///
786 /// ### Examples
787 ///
788 ///
789 /// ```
790 /// use keyed_priority_queue::KeyedPriorityQueue;
791 /// let mut queue: KeyedPriorityQueue<&str, i32> =
792 /// [("first", 0), ("second", 1), ("third", 2)]
793 /// .iter().cloned().collect();
794 /// let mut iterator = queue.into_iter();
795 /// assert_eq!(iterator.next(), Some(("third", 2)));
796 /// assert_eq!(iterator.next(), Some(("second", 1)));
797 /// assert_eq!(iterator.next(), Some(("first", 0)));
798 /// assert_eq!(iterator.next(), None);
799 /// ```
800 ///
801 /// ### Time complexity
802 ///
803 /// ***O(n log n)*** for iteration.
804 fn into_iter(self) -> Self::IntoIter {
805 Self::IntoIter { queue: self }
806 }
807}
808
809/// This is consuming iterator that returns elements in decreasing order
810///
811/// ### Time complexity
812/// Overall complexity of iteration is ***O(n log n)***
813pub struct KeyedPriorityQueueIterator<TKey, TPriority, S = RandomState>
814where
815 TKey: Hash + Eq,
816 TPriority: Ord,
817 S: BuildHasher,
818{
819 queue: KeyedPriorityQueue<TKey, TPriority, S>,
820}
821
822impl<TKey: Hash + Eq, TPriority: Ord, S: BuildHasher> Iterator
823 for KeyedPriorityQueueIterator<TKey, TPriority, S>
824{
825 type Item = (TKey, TPriority);
826
827 #[inline]
828 fn next(&mut self) -> Option<Self::Item> {
829 self.queue.pop()
830 }
831
832 #[inline]
833 fn size_hint(&self) -> (usize, Option<usize>) {
834 (self.queue.len(), Some(self.queue.len()))
835 }
836
837 #[inline]
838 fn count(self) -> usize
839 where
840 Self: Sized,
841 {
842 self.queue.len()
843 }
844}
845
846/// This is unordered borrowing iterator over queue.
847///
848/// ### Time complexity
849/// Overall complexity of iteration is ***O(n)***
850pub struct KeyedPriorityQueueBorrowIter<'a, TKey, TPriority, S = RandomState>
851where
852 TKey: 'a + Hash + Eq,
853 TPriority: 'a,
854 S: BuildHasher,
855{
856 heap_iterator: BinaryHeapIterator<'a, TPriority>,
857 key_to_pos: &'a Mediator<TKey, S>,
858}
859
860impl<'a, TKey: 'a + Hash + Eq, TPriority: 'a, S: BuildHasher> Iterator
861 for KeyedPriorityQueueBorrowIter<'a, TKey, TPriority, S>
862{
863 type Item = (&'a TKey, &'a TPriority);
864
865 #[inline]
866 fn next(&mut self) -> Option<Self::Item> {
867 let heap_iterator = &mut self.heap_iterator;
868 let key_to_pos = &self.key_to_pos;
869 heap_iterator.next().map(|(index, priority)| {
870 let (key, _) = key_to_pos.get_index(index);
871 (key, priority)
872 })
873 }
874
875 #[inline]
876 fn size_hint(&self) -> (usize, Option<usize>) {
877 self.heap_iterator.size_hint()
878 }
879
880 #[inline]
881 fn count(self) -> usize
882 where
883 Self: Sized,
884 {
885 self.heap_iterator.count()
886 }
887}
888
889/// This is error type for [`set_priority`] method of [`KeyedPriorityQueue`].
890/// It means that queue doesn't contain such key.
891///
892/// [`KeyedPriorityQueue`]: struct.KeyedPriorityQueue.html
893/// [`set_priority`]: struct.KeyedPriorityQueue.html#method.set_priority
894#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Copy, Clone, Default)]
895pub struct SetPriorityNotFoundError;
896
897impl Display for SetPriorityNotFoundError {
898 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
899 write!(f, "Key not found in KeyedPriorityQueue during set_priority")
900 }
901}
902
903impl std::error::Error for SetPriorityNotFoundError {}
904
905#[cfg(test)]
906mod tests {
907 use super::KeyedPriorityQueue;
908
909 #[test]
910 fn test_priority() {
911 let mut items = [1, 4, 5, 2, 3];
912 let mut queue = KeyedPriorityQueue::<i32, i32>::with_capacity(items.len());
913 for (i, &x) in items.iter().enumerate() {
914 queue.push(x, x);
915 assert_eq!(queue.len(), i + 1);
916 }
917 assert_eq!(queue.len(), items.len());
918 items.sort_unstable_by_key(|&x| -x);
919 for &x in items.iter() {
920 assert_eq!(queue.pop(), Some((x, x)));
921 }
922 assert_eq!(queue.pop(), None);
923 }
924
925 #[test]
926 fn test_peek() {
927 let items = [
928 ("first", 5),
929 ("second", 4),
930 ("third", 3),
931 ("fourth", 2),
932 ("fifth", 1),
933 ];
934
935 let mut queue: KeyedPriorityQueue<&str, i32> = items.iter().cloned().collect();
936
937 while queue.len() > 0 {
938 let (&key, &priority) = queue.peek().unwrap();
939 let (key1, priority1) = queue.pop().unwrap();
940 assert_eq!(key, key1);
941 assert_eq!(priority, priority1);
942 }
943 assert_eq!(queue.peek(), None);
944 }
945
946 #[test]
947 fn test_get_priority() {
948 let items = [
949 ("first", 5),
950 ("second", 4),
951 ("third", 3),
952 ("fourth", 2),
953 ("fifth", 1),
954 ];
955
956 let queue: KeyedPriorityQueue<&str, i32> = items.iter().cloned().collect();
957 for &(key, priority) in items.iter() {
958 let &real = queue.get_priority(&key).unwrap();
959 assert_eq!(real, priority);
960 }
961 let mut queue = queue;
962 while let Some(_) = queue.pop() {}
963 for &(key, _) in items.iter() {
964 assert_eq!(queue.get_priority(&key), None);
965 }
966 }
967
968 #[test]
969 fn test_change_priority() {
970 let items = [
971 ("first", 5),
972 ("second", 4),
973 ("third", 3),
974 ("fourth", 2),
975 ("fifth", 1),
976 ];
977
978 let mut queue: KeyedPriorityQueue<&str, i32> = items.iter().cloned().collect();
979 assert_eq!(
980 queue.set_priority(&"HELLO", 64),
981 Err(super::SetPriorityNotFoundError::default())
982 );
983 let old_priority = *queue.get_priority(&"fifth").unwrap();
984 assert_eq!(queue.set_priority(&"fifth", old_priority + 10), Ok(1));
985 assert_eq!(queue.get_priority(&"fifth"), Some(&11));
986 assert_eq!(queue.pop(), Some(("fifth", 11)));
987
988 let old_priority = *queue.get_priority(&"first").unwrap();
989 assert_eq!(queue.set_priority(&"first", old_priority - 10), Ok(5));
990 assert_eq!(queue.get_priority(&"first"), Some(&-5));
991 queue.pop();
992 queue.pop();
993 queue.pop();
994 assert_eq!(queue.pop(), Some(("first", -5)));
995 }
996
997 #[test]
998 fn test_remove_items() {
999 let mut items = [1, 4, 5, 2, 3];
1000 let mut queue: KeyedPriorityQueue<i32, i32> = items.iter().map(|&x| (x, x)).collect();
1001 assert_eq!(queue.remove_entry(&3), Some((3, 3)));
1002 assert_eq!(queue.remove_entry(&20), None);
1003 assert_eq!(queue.len(), items.len() - 1);
1004 assert_eq!(queue.get_priority(&3), None);
1005 items.sort_unstable_by_key(|&x| -x);
1006 for x in items.iter().cloned().filter(|&x| x != 3) {
1007 assert_eq!(queue.pop(), Some((x, x)));
1008 }
1009 assert_eq!(queue.pop(), None);
1010 }
1011
1012 #[test]
1013 fn test_iteration() {
1014 let items = [
1015 ("first", 5),
1016 ("second", 4),
1017 ("third", 3),
1018 ("fourth", 2),
1019 ("fifth", 1),
1020 ];
1021
1022 let queue: KeyedPriorityQueue<&str, i32> = items.iter().rev().cloned().collect();
1023 let mut iter = queue.into_iter();
1024 assert_eq!(iter.next(), Some(("first", 5)));
1025 assert_eq!(iter.next(), Some(("second", 4)));
1026 assert_eq!(iter.next(), Some(("third", 3)));
1027 assert_eq!(iter.next(), Some(("fourth", 2)));
1028 assert_eq!(iter.next(), Some(("fifth", 1)));
1029 assert_eq!(iter.next(), None);
1030 }
1031
1032 #[test]
1033 fn test_multiple_push() {
1034 let mut queue = KeyedPriorityQueue::new();
1035 queue.push(0, 1);
1036 assert_eq!(queue.peek(), Some((&0, &1)));
1037 queue.push(0, 5);
1038 assert_eq!(queue.peek(), Some((&0, &5)));
1039 queue.push(0, 7);
1040 assert_eq!(queue.peek(), Some((&0, &7)));
1041 queue.push(0, 9);
1042 assert_eq!(queue.peek(), Some((&0, &9)));
1043 }
1044
1045 #[test]
1046 fn test_borrow_keys() {
1047 let mut queue: KeyedPriorityQueue<String, i32> = KeyedPriorityQueue::new();
1048 queue.push("Hello".to_string(), 5);
1049 let string = "Hello".to_string();
1050 let string_ref: &String = &string;
1051 let str_ref: &str = &string;
1052 assert_eq!(queue.get_priority(string_ref), Some(&5));
1053 assert_eq!(queue.get_priority(str_ref), Some(&5));
1054 }
1055
1056 #[test]
1057 fn test_entry_vacant() {
1058 use super::Entry;
1059
1060 let items = [
1061 ("first", 5i32),
1062 ("second", 4),
1063 ("third", 3),
1064 ("fourth", 2),
1065 ("fifth", 1),
1066 ];
1067
1068 let mut queue = KeyedPriorityQueue::new();
1069
1070 for &(k, v) in items.iter() {
1071 queue.push(k, v);
1072 }
1073
1074 assert_eq!(queue.len(), 5);
1075 match queue.entry("Cotton") {
1076 Entry::Occupied(_) => unreachable!(),
1077 Entry::Vacant(entry) => {
1078 assert_eq!(entry.get_key(), &"Cotton");
1079 entry.set_priority(10);
1080 }
1081 };
1082 assert_eq!(queue.len(), 6);
1083 assert_eq!(queue.get_priority(&"Cotton"), Some(&10));
1084 match queue.entry("Cotton") {
1085 Entry::Occupied(entry) => {
1086 assert_eq!(entry.get_key(), &"Cotton");
1087 assert_eq!(entry.get_priority(), &10);
1088 }
1089 Entry::Vacant(_) => unreachable!(),
1090 };
1091 }
1092
1093 #[test]
1094 fn test_entry_occupied() {
1095 use super::Entry;
1096
1097 let items = [
1098 ("first", 5i32),
1099 ("second", 4),
1100 ("third", 3),
1101 ("fourth", 2),
1102 ("fifth", 1),
1103 ];
1104
1105 let mut queue = KeyedPriorityQueue::new();
1106
1107 for &(k, v) in items.iter() {
1108 queue.push(k, v);
1109 }
1110
1111 assert_eq!(queue.len(), 5);
1112 match queue.entry("third") {
1113 Entry::Occupied(entry) => {
1114 assert_eq!(entry.get_key(), &"third");
1115 assert_eq!(entry.get_priority(), &3);
1116 assert_eq!(entry.set_priority(5), 3);
1117 }
1118 Entry::Vacant(_) => unreachable!(),
1119 };
1120 assert_eq!(queue.len(), 5);
1121 assert_eq!(queue.get_priority(&"third"), Some(&5));
1122 match queue.entry("third") {
1123 Entry::Occupied(entry) => {
1124 assert_eq!(entry.remove(), ("third", 5));
1125 }
1126 Entry::Vacant(_) => unreachable!(),
1127 };
1128
1129 assert_eq!(queue.len(), 4);
1130 assert_eq!(queue.get_priority(&"third"), None);
1131 }
1132
1133 #[test]
1134 fn test_borrow_iter() {
1135 use std::collections::HashMap;
1136 let items = [
1137 ("first", 5i32),
1138 ("third", 3),
1139 ("second", 4),
1140 ("fifth", 1),
1141 ("fourth", 2),
1142 ];
1143
1144 let queue: KeyedPriorityQueue<String, i32> =
1145 items.iter().map(|&(k, p)| (k.to_owned(), p)).collect();
1146
1147 let mut map: HashMap<&str, i32> = HashMap::new();
1148
1149 let mut total_items = 0;
1150 for (key, &value) in queue.iter() {
1151 map.insert(key, value);
1152 total_items += 1;
1153 }
1154 assert_eq!(items.len(), total_items);
1155 assert_eq!(queue.len(), items.len());
1156 let other_map: HashMap<_, _> = items.iter().cloned().collect();
1157 assert_eq!(map, other_map);
1158 }
1159
1160 #[test]
1161 fn test_sync() {
1162 fn assert_sync<T: Sync>() {}
1163 assert_sync::<KeyedPriorityQueue<i32, i32>>();
1164 }
1165
1166 #[test]
1167 fn test_send() {
1168 fn assert_sync<T: Send>() {}
1169 assert_sync::<KeyedPriorityQueue<i32, i32>>();
1170 }
1171
1172 #[test]
1173 fn test_fmt() {
1174 let items = [
1175 ("first", 5i32),
1176 ("second", 4),
1177 ("third", 3),
1178 ("fourth", 2),
1179 ("fifth", 1),
1180 ];
1181
1182 let queue: KeyedPriorityQueue<&str, i32> = items.iter().cloned().collect();
1183
1184 assert_eq!(
1185 format!("{:?}", queue),
1186 "[(\"first\", 5)(\"second\", 4)(\"third\", 3)(\"fourth\", 2)(\"fifth\", 1)]"
1187 );
1188 }
1189
1190 #[test]
1191 fn test_not_clone_works() {
1192 use core::hash::Hash;
1193 #[derive(Hash, PartialEq, Eq)]
1194 struct Key(u32);
1195
1196 let vals = [0u32, 1, 1, 2, 4, 5];
1197 let mut queue: KeyedPriorityQueue<Key, u32> =
1198 vals.iter().copied().map(|v| (Key(v), v)).collect();
1199 queue.set_priority(&Key(1), 10).unwrap();
1200 let mut res = Vec::with_capacity(5);
1201 while let Some((Key(k), p)) = queue.pop() {
1202 res.push((k, p));
1203 }
1204 assert_eq!(&res, &[(1, 10), (5, 5), (4, 4), (2, 2), (0, 0)]);
1205 }
1206
1207 #[test]
1208 fn test_remove_change_tree() {
1209 use std::cmp::Reverse;
1210 let mut queue = KeyedPriorityQueue::new();
1211
1212 queue.push(0, Reverse(300));
1213 queue.push(1, Reverse(500));
1214 queue.push(2, Reverse(400));
1215 queue.push(3, Reverse(400));
1216 queue.push(4, Reverse(600));
1217 queue.push(5, Reverse(100));
1218 queue.push(6, Reverse(200));
1219 queue.remove(&1);
1220
1221 let mut list = Vec::new();
1222 while let Some((_, timestamp)) = queue.pop() {
1223 list.push(timestamp.0);
1224 }
1225
1226 assert_eq!(list, [100, 200, 300, 400, 400, 600])
1227 }
1228}