priority_queue/double_priority_queue/mod.rs
1/*
2 * Copyright 2017 Gianmarco Garrisi
3 *
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Lesser General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version, or (at your option) under the terms
9 * of the Mozilla Public License version 2.0.
10 *
11 * ----
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this program. If not, see <http://www.gnu.org/licenses/>.
20 *
21 * ----
22 *
23 * This Source Code Form is subject to the terms of the Mozilla Public License,
24 * v. 2.0. If a copy of the MPL was not distributed with this file, You can
25 * obtain one at http://mozilla.org/MPL/2.0/.
26 *
27 */
28//! This module contains the [`DoublePriorityQueue`] type and the related iterators.
29//!
30//! See the type level documentation for more details and examples.
31
32pub mod iterators;
33
34#[cfg(not(feature = "std"))]
35use std::vec::Vec;
36
37use crate::core_iterators::*;
38use crate::store::{Index, Position, Store};
39use crate::TryReserveError;
40use iterators::*;
41
42use std::borrow::Borrow;
43use std::cmp::{Eq, Ord};
44#[cfg(feature = "std")]
45use std::collections::hash_map::RandomState;
46use std::hash::{BuildHasher, Hash};
47use std::iter::{Extend, FromIterator, IntoIterator, Iterator};
48use std::mem::replace;
49
50/// A double priority queue with efficient change function to change the priority of an
51/// element.
52///
53/// The priority is of type P, that must implement `std::cmp::Ord`.
54///
55/// The item is of type I, that must implement `Hash` and `Eq`.
56///
57/// Implemented as a heap of indexes, stores the items inside an `IndexMap`
58/// to be able to retrieve them quickly.
59///
60/// With this data structure it is possible to efficiently extract both
61/// the maximum and minimum elements arbitrarily.
62///
63/// If your need is to always extract the minimum, use a
64/// `PriorityQueue<I, Reverse<P>>` wrapping
65/// your priorities in the standard wrapper
66/// [`Reverse<T>`](https://doc.rust-lang.org/std/cmp/struct.Reverse.html).
67///
68///
69/// # Example
70/// ```rust
71/// use priority_queue::DoublePriorityQueue;
72///
73/// let mut pq = DoublePriorityQueue::new();
74///
75/// assert!(pq.is_empty());
76/// pq.push("Apples", 5);
77/// pq.push("Bananas", 8);
78/// pq.push("Strawberries", 23);
79///
80/// assert_eq!(pq.peek_max(), Some((&"Strawberries", &23)));
81/// assert_eq!(pq.peek_min(), Some((&"Apples", &5)));
82///
83/// pq.change_priority("Bananas", 25);
84/// assert_eq!(pq.peek_max(), Some((&"Bananas", &25)));
85///
86/// for (item, _) in pq.into_sorted_iter() {
87/// println!("{}", item);
88/// }
89/// ```
90#[derive(Clone)]
91#[cfg(feature = "std")]
92pub struct DoublePriorityQueue<I, P, H = RandomState> {
93 pub(crate) store: Store<I, P, H>,
94}
95
96#[derive(Clone)]
97#[cfg(not(feature = "std"))]
98pub struct DoublePriorityQueue<I, P, H> {
99 pub(crate) store: Store<I, P, H>,
100}
101
102// do not [derive(Eq)] to loosen up trait requirements for other types and impls
103impl<I, P, H> Eq for DoublePriorityQueue<I, P, H>
104where
105 I: Hash + Eq,
106 P: Ord,
107 H: BuildHasher,
108{
109}
110
111impl<I, P, H> Default for DoublePriorityQueue<I, P, H>
112where
113 I: Hash + Eq,
114 P: Ord,
115 H: BuildHasher + Default,
116{
117 fn default() -> Self {
118 Self::with_default_hasher()
119 }
120}
121
122#[cfg(feature = "std")]
123impl<I, P> DoublePriorityQueue<I, P>
124where
125 P: Ord,
126 I: Hash + Eq,
127{
128 /// Creates an empty `DoublePriorityQueue`
129 pub fn new() -> Self {
130 Self::with_capacity(0)
131 }
132
133 /// Creates an empty `DoublePriorityQueue` with the specified capacity.
134 pub fn with_capacity(capacity: usize) -> Self {
135 Self::with_capacity_and_default_hasher(capacity)
136 }
137}
138
139impl<I, P, H> DoublePriorityQueue<I, P, H>
140where
141 P: Ord,
142 I: Hash + Eq,
143 H: BuildHasher + Default,
144{
145 /// Creates an empty `DoublePriorityQueue` with the default hasher
146 pub fn with_default_hasher() -> Self {
147 Self::with_capacity_and_default_hasher(0)
148 }
149
150 /// Creates an empty `DoublePriorityQueue` with the specified capacity and default hasher
151 pub fn with_capacity_and_default_hasher(capacity: usize) -> Self {
152 Self::with_capacity_and_hasher(capacity, H::default())
153 }
154}
155
156impl<I, P, H> DoublePriorityQueue<I, P, H>
157where
158 P: Ord,
159 I: Hash + Eq,
160 H: BuildHasher,
161{
162 /// Creates an empty `DoublePriorityQueue` with the specified hasher
163 pub fn with_hasher(hash_builder: H) -> Self {
164 Self::with_capacity_and_hasher(0, hash_builder)
165 }
166
167 /// Creates an empty `DoublePriorityQueue` with the specified capacity and hasher
168 ///
169 /// The internal collections will be able to hold at least `capacity`
170 /// elements without reallocating.
171 /// If `capacity` is 0, there will be no allocation.
172 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: H) -> Self {
173 Self {
174 store: Store::with_capacity_and_hasher(capacity, hash_builder),
175 }
176 }
177}
178
179impl<I, P, H> DoublePriorityQueue<I, P, H> {
180 /// Returns the number of elements the internal map can hold without
181 /// reallocating.
182 ///
183 /// This number is a lower bound; the map might be able to hold more,
184 /// but is guaranteed to be able to hold at least this many.
185 pub fn capacity(&self) -> usize {
186 self.store.capacity()
187 }
188
189 /// Returns an iterator in arbitrary order over the
190 /// (item, priority) elements in the queue
191 pub fn iter(&self) -> Iter<I, P> {
192 self.store.iter()
193 }
194
195 /// Clears the PriorityQueue, returning an iterator over the removed elements in arbitrary order.
196 /// If the iterator is dropped before being fully consumed, it drops the remaining elements in arbitrary order.
197 pub fn drain(&mut self) -> Drain<I, P> {
198 self.store.drain()
199 }
200
201 /// Shrinks the capacity of the internal data structures
202 /// that support this operation as much as possible.
203 pub fn shrink_to_fit(&mut self) {
204 self.store.shrink_to_fit();
205 }
206
207 /// Returns the number of elements in the priority queue.
208 #[inline]
209 pub fn len(&self) -> usize {
210 self.store.len()
211 }
212
213 /// Returns true if the priority queue contains no elements.
214 pub fn is_empty(&self) -> bool {
215 self.store.is_empty()
216 }
217
218 /// Returns the couple (item, priority) with the lowest
219 /// priority in the queue, or None if it is empty.
220 ///
221 /// Computes in **O(1)** time
222 pub fn peek_min(&self) -> Option<(&I, &P)> {
223 self.find_min().and_then(|i| {
224 self.store
225 .map
226 .get_index(unsafe { *self.store.heap.get_unchecked(i.0) }.0)
227 })
228 }
229
230 /// Reserves capacity for at least `additional` more elements to be inserted
231 /// in the given `DoublePriorityQueue`. The collection may reserve more space to avoid
232 /// frequent reallocations. After calling `reserve`, capacity will be
233 /// greater than or equal to `self.len() + additional`. Does nothing if
234 /// capacity is already sufficient.
235 ///
236 /// # Panics
237 ///
238 /// Panics if the new capacity overflows `usize`.
239 pub fn reserve(&mut self, additional: usize) {
240 self.store.reserve(additional);
241 }
242
243 /// Reserve capacity for `additional` more elements, without over-allocating.
244 ///
245 /// Unlike `reserve`, this does not deliberately over-allocate the entry capacity to avoid
246 /// frequent re-allocations. However, the underlying data structures may still have internal
247 /// capacity requirements, and the allocator itself may give more space than requested, so this
248 /// cannot be relied upon to be precisely minimal.
249 ///
250 /// Computes in **O(n)** time.
251 pub fn reserve_exact(&mut self, additional: usize) {
252 self.store.reserve_exact(additional);
253 }
254
255 /// Try to reserve capacity for at least `additional` more elements.
256 ///
257 /// Computes in O(n) time.
258 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
259 self.store.try_reserve(additional)
260 }
261
262 /// Try to reserve capacity for `additional` more elements, without over-allocating.
263 ///
264 /// Unlike `reserve`, this does not deliberately over-allocate the entry capacity to avoid
265 /// frequent re-allocations. However, the underlying data structures may still have internal
266 /// capacity requirements, and the allocator itself may give more space than requested, so this
267 /// cannot be relied upon to be precisely minimal.
268 ///
269 /// Computes in **O(n)** time.
270 pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
271 self.store.try_reserve_exact(additional)
272 }
273}
274impl<I, P, H> DoublePriorityQueue<I, P, H>
275where
276 P: Ord,
277{
278 /// Return an iterator in arbitrary order over the
279 /// (item, priority) elements in the queue.
280 ///
281 /// The item and the priority are mutable references, but it's a logic error
282 /// to modify the item in a way that change the result of `Hash` or `Eq`.
283 ///
284 /// It's *not* an error, instead, to modify the priorities, because the heap
285 /// will be rebuilt once the `IterMut` goes out of scope. It would be
286 /// rebuilt even if no priority value would have been modified, but the
287 /// procedure will not move anything, but just compare the priorities.
288 pub fn iter_mut(&mut self) -> IterMut<I, P, H> {
289 IterMut::new(self)
290 }
291
292 /// Returns the couple (item, priority) with the greatest
293 /// priority in the queue, or None if it is empty.
294 ///
295 /// Computes in **O(1)** time
296 pub fn peek_max(&self) -> Option<(&I, &P)> {
297 self.find_max().and_then(|i| {
298 self.store
299 .map
300 .get_index(unsafe { *self.store.heap.get_unchecked(i.0) }.0)
301 })
302 }
303
304 /// Removes the item with the lowest priority from
305 /// the priority queue and returns the pair (item, priority),
306 /// or None if the queue is empty.
307 pub fn pop_min(&mut self) -> Option<(I, P)> {
308 self.find_min().and_then(|i| {
309 let r = self.store.swap_remove(i);
310 self.heapify(i);
311 r
312 })
313 }
314
315 /// Removes the item with the greatest priority from
316 /// the priority queue and returns the pair (item, priority),
317 /// or None if the queue is empty.
318 pub fn pop_max(&mut self) -> Option<(I, P)> {
319 self.find_max().and_then(|i| {
320 let r = self.store.swap_remove(i);
321 self.heapify(i);
322 r
323 })
324 }
325
326 /// Implements a HeapSort.
327 ///
328 /// Consumes the PriorityQueue and returns a vector
329 /// with all the items sorted from the one associated to
330 /// the lowest priority to the highest.
331 pub fn into_ascending_sorted_vec(mut self) -> Vec<I> {
332 let mut res = Vec::with_capacity(self.store.size);
333 while let Some((i, _)) = self.pop_min() {
334 res.push(i);
335 }
336 res
337 }
338
339 /// Implements a HeapSort
340 ///
341 /// Consumes the PriorityQueue and returns a vector
342 /// with all the items sorted from the one associated to
343 /// the highest priority to the lowest.
344 pub fn into_descending_sorted_vec(mut self) -> Vec<I> {
345 let mut res = Vec::with_capacity(self.store.size);
346 while let Some((i, _)) = self.pop_max() {
347 res.push(i);
348 }
349 res
350 }
351
352 /// Generates a new double ended iterator from self that
353 /// will extract the elements from the one with the lowest priority
354 /// to the highest one.
355 pub fn into_sorted_iter(self) -> IntoSortedIter<I, P, H> {
356 IntoSortedIter { pq: self }
357 }
358}
359
360impl<I, P, H> DoublePriorityQueue<I, P, H>
361where
362 H: BuildHasher,
363{
364 /// Returns the couple (item, priority) with the lowest
365 /// priority in the queue, or None if it is empty.
366 ///
367 /// The item is a mutable reference, but it's a logic error to modify it
368 /// in a way that change the result of `Hash` or `Eq`.
369 ///
370 /// The priority cannot be modified with a call to this function.
371 /// To modify the priority use [`push`](DoublePriorityQueue::push),
372 /// [`change_priority`](DoublePriorityQueue::change_priority) or
373 /// [`change_priority_by`](DoublePriorityQueue::change_priority_by).
374 ///
375 /// Computes in **O(1)** time
376 pub fn peek_min_mut(&mut self) -> Option<(&mut I, &P)> {
377 use indexmap::map::MutableKeys;
378
379 self.find_min()
380 .and_then(move |i| {
381 self.store
382 .map
383 .get_index_mut2(unsafe { *self.store.heap.get_unchecked(i.0) }.0)
384 })
385 .map(|(k, v)| (k, &*v))
386 }
387}
388
389impl<I, P, H> DoublePriorityQueue<I, P, H>
390where
391 P: Ord,
392 H: BuildHasher,
393{
394 /// Returns the couple (item, priority) with the greatest
395 /// priority in the queue, or None if it is empty.
396 ///
397 /// The item is a mutable reference, but it's a logic error to modify it
398 /// in a way that change the result of `Hash` or `Eq`.
399 ///
400 /// The priority cannot be modified with a call to this function.
401 /// To modify the priority use [`push`](DoublePriorityQueue::push),
402 /// [`change_priority`](DoublePriorityQueue::change_priority) or
403 /// [`change_priority_by`](DoublePriorityQueue::change_priority_by).
404 ///
405 /// Computes in **O(1)** time
406 pub fn peek_max_mut(&mut self) -> Option<(&mut I, &P)> {
407 use indexmap::map::MutableKeys;
408 self.find_max()
409 .and_then(move |i| {
410 self.store
411 .map
412 .get_index_mut2(unsafe { *self.store.heap.get_unchecked(i.0) }.0)
413 })
414 .map(|(k, v)| (k, &*v))
415 }
416}
417
418impl<I, P, H> DoublePriorityQueue<I, P, H>
419where
420 P: Ord,
421 I: Hash + Eq,
422 H: BuildHasher,
423{
424 /// Retains only the elements specified by the `predicate`.
425 ///
426 /// In other words, remove all elements e for which `predicate(&i, &p)` returns `false`.
427 /// The elements are visited in arbitrary order.
428 pub fn retain<F>(&mut self, predicate: F)
429 where
430 F: FnMut(&I, &P) -> bool,
431 {
432 self.store.retain(predicate);
433 self.heap_build();
434 }
435
436 /// Retains only the elements specified by the `predicate`.
437 ///
438 /// In other words, remove all elements e for which `predicate(&mut i, &mut p)` returns `false`.
439 /// The elements are visited in arbitrary order.
440 ///
441 /// The `predicate` receives mutable references to both the item and
442 /// the priority.
443 ///
444 /// It's a logical error to change the item in a way
445 /// that changes the result of `Hash` or `Eq`.
446 ///
447 /// The `predicate` can change the priority. If the element is retained,
448 /// it will have the updated one.
449 pub fn retain_mut<F>(&mut self, predicate: F)
450 where
451 F: FnMut(&mut I, &mut P) -> bool,
452 {
453 self.store.retain_mut(predicate);
454 self.heap_build();
455 }
456
457 /// Returns an `Iterator` removing from the queue the `(item, priority)`
458 /// pairs for which the `predicate` returns `true`, in arbitraty order.
459 ///
460 /// The `predicate` receives mutable references to both the item and
461 /// the priority.
462 ///
463 /// It's a logical error to change the item in a way
464 /// that changes the result of `Hash` or `Eq`.
465 ///
466 /// The `predicate` can change the priority. If it returns `true`, the
467 /// extracted pair will have the updated priority, otherwise, the
468 /// heap structural property will be restored once the iterator is `Drop`ped.
469 ///
470 /// # Example
471 /// ```
472 /// ```
473 pub fn extract_if<F>(&mut self, predicate: F) -> ExtractIf<I, P, F, H>
474 where
475 F: FnMut(&mut I, &mut P) -> bool,
476 {
477 ExtractIf::new(self, predicate)
478 }
479
480 /// Removes the item with the lowest priority from
481 /// the priority queue if the predicate returns `true`.
482 ///
483 /// Returns the pair (item, priority), or None if the
484 /// queue is empty or the predicate returns `false`.
485 ///
486 /// The predicate receives mutable references to both the item and
487 /// the priority.
488 ///
489 /// It's a logical error to change the item in a way
490 /// that changes the result of `Hash` or `EQ`.
491 ///
492 /// The predicate can change the priority. If it returns true, the
493 /// returned couple will have the updated priority, otherwise, the
494 /// heap structural property will be restored.
495 ///
496 /// # Example
497 /// ```
498 /// # use priority_queue::DoublePriorityQueue;
499 /// let mut pq = DoublePriorityQueue::new();
500 /// pq.push("Apples", 5);
501 /// pq.push("Bananas", 10);
502 /// assert_eq!(pq.pop_min_if(|i, p| {
503 /// *p = 15;
504 /// false
505 /// }), None);
506 /// assert_eq!(pq.pop_min(), Some(("Bananas", 10)));
507 /// ```
508 pub fn pop_min_if<F>(&mut self, f: F) -> Option<(I, P)>
509 where
510 F: FnOnce(&mut I, &mut P) -> bool,
511 {
512 self.find_min().and_then(|i| {
513 let r = self.store.swap_remove_if(i, f);
514 self.heapify(i);
515 r
516 })
517 }
518
519 /// Removes the item with the greatest priority from
520 /// the priority queue if the predicate returns `true`.
521 ///
522 /// Returns the pair (item, priority), or None if the
523 /// queue is empty or the predicate returns `false`.
524 ///
525 /// The predicate receives mutable references to both the item and
526 /// the priority.
527 ///
528 /// It's a logical error to change the item in a way
529 /// that changes the result of `Hash` or `EQ`.
530 ///
531 /// The predicate can change the priority. If it returns true, the
532 /// returned couple will have the updated priority, otherwise, the
533 /// heap structural property will be restored.
534 ///
535 /// # Example
536 /// ```
537 /// # use priority_queue::DoublePriorityQueue;
538 /// let mut pq = DoublePriorityQueue::new();
539 /// pq.push("Apples", 5);
540 /// pq.push("Bananas", 10);
541 /// assert_eq!(pq.pop_max_if(|i, p| {
542 /// *p = 3;
543 /// false
544 /// }), None);
545 /// assert_eq!(pq.pop_max(), Some(("Apples", 5)));
546 /// ```
547 pub fn pop_max_if<F>(&mut self, f: F) -> Option<(I, P)>
548 where
549 F: FnOnce(&mut I, &mut P) -> bool,
550 {
551 self.find_max().and_then(|i| {
552 let r = self.store.swap_remove_if(i, f);
553 self.up_heapify(i);
554 r
555 })
556 }
557
558 /// Insert the item-priority pair into the queue.
559 ///
560 /// If an element equal to `item` is already in the queue, its priority
561 /// is updated and the old priority is returned in `Some`; otherwise,
562 /// `item` is inserted with `priority` and `None` is returned.
563 ///
564 /// # Example
565 /// ```
566 /// # use priority_queue::DoublePriorityQueue;
567 /// let mut pq = DoublePriorityQueue::new();
568 /// assert_eq!(pq.push("Apples", 5), None);
569 /// assert_eq!(pq.get_priority("Apples"), Some(&5));
570 /// assert_eq!(pq.push("Apples", 6), Some(5));
571 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
572 /// assert_eq!(pq.push("Apples", 4), Some(6));
573 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
574 /// ```
575 ///
576 /// Computes in **O(log(N))** time.
577 pub fn push(&mut self, item: I, priority: P) -> Option<P> {
578 use indexmap::map::Entry::*;
579 let mut pos = Position(0);
580 let mut oldp = None;
581
582 match self.store.map.entry(item) {
583 Occupied(mut e) => {
584 oldp = Some(replace(e.get_mut(), priority));
585 pos = unsafe { *self.store.qp.get_unchecked(e.index()) };
586 }
587 Vacant(e) => {
588 e.insert(priority);
589 }
590 }
591
592 if oldp.is_some() {
593 self.up_heapify(pos);
594 return oldp;
595 }
596 // get a reference to the priority
597 // copy the current size of the heap
598 let i = self.len();
599 // add the new element in the qp vector as the last in the heap
600 self.store.qp.push(Position(i));
601 self.store.heap.push(Index(i));
602 self.bubble_up(Position(i), Index(i));
603 self.store.size += 1;
604 None
605 }
606
607 /// Increase the priority of an existing item in the queue, or
608 /// insert it if not present.
609 ///
610 /// If an element equal to `item` is already in the queue with a
611 /// lower priority, its priority is increased to the new one
612 /// without replacing the element and the old priority is returned
613 /// in `Some`.
614 ///
615 /// If an element equal to `item` is already in the queue with an
616 /// equal or higher priority, its priority is not changed and the
617 /// `priority` argument is returned in `Some`.
618 ///
619 /// If no element equal to `item` is already in the queue, the new
620 /// element is inserted and `None` is returned.
621 ///
622 /// # Example
623 /// ```
624 /// # use priority_queue::DoublePriorityQueue;
625 /// let mut pq = DoublePriorityQueue::new();
626 /// assert_eq!(pq.push_increase("Apples", 5), None);
627 /// assert_eq!(pq.get_priority("Apples"), Some(&5));
628 /// assert_eq!(pq.push_increase("Apples", 6), Some(5));
629 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
630 /// // Already present with higher priority, so requested (lower)
631 /// // priority is returned.
632 /// assert_eq!(pq.push_increase("Apples", 4), Some(4));
633 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
634 /// ```
635 ///
636 /// Computes in **O(log(N))** time.
637 pub fn push_increase(&mut self, item: I, priority: P) -> Option<P> {
638 if self.get_priority(&item).map_or(true, |p| priority > *p) {
639 self.push(item, priority)
640 } else {
641 Some(priority)
642 }
643 }
644
645 /// Decrease the priority of an existing item in the queue, or
646 /// insert it if not present.
647 ///
648 /// If an element equal to `item` is already in the queue with a
649 /// higher priority, its priority is decreased to the new one
650 /// without replacing the element and the old priority is returned
651 /// in `Some`.
652 ///
653 /// If an element equal to `item` is already in the queue with an
654 /// equal or lower priority, its priority is not changed and the
655 /// `priority` argument is returned in `Some`.
656 ///
657 /// If no element equal to `item` is already in the queue, the new
658 /// element is inserted and `None` is returned.
659 ///
660 /// # Example
661 /// ```
662 /// # use priority_queue::DoublePriorityQueue;
663 /// let mut pq = DoublePriorityQueue::new();
664 /// assert_eq!(pq.push_decrease("Apples", 5), None);
665 /// assert_eq!(pq.get_priority("Apples"), Some(&5));
666 /// assert_eq!(pq.push_decrease("Apples", 4), Some(5));
667 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
668 /// // Already present with lower priority, so requested (higher)
669 /// // priority is returned.
670 /// assert_eq!(pq.push_decrease("Apples", 6), Some(6));
671 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
672 /// ```
673 ///
674 /// Computes in **O(log(N))** time.
675 pub fn push_decrease(&mut self, item: I, priority: P) -> Option<P> {
676 if self.get_priority(&item).map_or(true, |p| priority < *p) {
677 self.push(item, priority)
678 } else {
679 Some(priority)
680 }
681 }
682
683 /// Change the priority of an Item returning the old value of priority,
684 /// or `None` if the item wasn't in the queue.
685 ///
686 /// The argument `item` is only used for lookup, and is not used to overwrite the item's data
687 /// in the priority queue.
688 ///
689 /// # Example
690 /// ```
691 /// # use priority_queue::DoublePriorityQueue;
692 /// let mut pq = DoublePriorityQueue::new();
693 /// assert_eq!(pq.change_priority("Apples", 5), None);
694 /// assert_eq!(pq.get_priority("Apples"), None);
695 /// assert_eq!(pq.push("Apples", 6), None);
696 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
697 /// assert_eq!(pq.change_priority("Apples", 4), Some(6));
698 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
699 /// ```
700 ///
701 /// The item is found in **O(1)** thanks to the hash table.
702 /// The operation is performed in **O(log(N))** time.
703 pub fn change_priority<Q>(&mut self, item: &Q, new_priority: P) -> Option<P>
704 where
705 I: Borrow<Q>,
706 Q: Eq + Hash + ?Sized,
707 {
708 self.store
709 .change_priority(item, new_priority)
710 .map(|(r, pos)| {
711 self.up_heapify(pos);
712 r
713 })
714 }
715
716 /// Change the priority of an Item using the provided function.
717 /// Return a boolean value where `true` means the item was in the queue and update was successful
718 ///
719 /// The argument `item` is only used for lookup, and is not used to overwrite the item's data
720 /// in the priority queue.
721 ///
722 /// The item is found in **O(1)** thanks to the hash table.
723 /// The operation is performed in **O(log(N))** time (worst case).
724 pub fn change_priority_by<Q, F>(&mut self, item: &Q, priority_setter: F) -> bool
725 where
726 I: Borrow<Q>,
727 Q: Eq + Hash + ?Sized,
728 F: FnOnce(&mut P),
729 {
730 self.store
731 .change_priority_by(item, priority_setter)
732 .map(|pos| {
733 self.up_heapify(pos);
734 })
735 .is_some()
736 }
737
738 /// Get the priority of an item, or `None`, if the item is not in the queue
739 pub fn get_priority<Q>(&self, item: &Q) -> Option<&P>
740 where
741 I: Borrow<Q>,
742 Q: Eq + Hash + ?Sized,
743 {
744 self.store.get_priority(item)
745 }
746
747 /// Get the couple (item, priority) of an arbitrary element, as reference
748 /// or `None` if the item is not in the queue.
749 pub fn get<Q>(&self, item: &Q) -> Option<(&I, &P)>
750 where
751 I: Borrow<Q>,
752 Q: Eq + Hash + ?Sized,
753 {
754 self.store.get(item)
755 }
756
757 /// Get the couple (item, priority) of an arbitrary element, or `None`
758 /// if the item was not in the queue.
759 ///
760 /// The item is a mutable reference, but it's a logic error to modify it
761 /// in a way that change the result of `Hash` or `Eq`.
762 ///
763 /// The priority cannot be modified with a call to this function.
764 /// To modify the priority use use [`push`](DoublePriorityQueue::push),
765 /// [`change_priority`](DoublePriorityQueue::change_priority) or
766 /// [`change_priority_by`](DoublePriorityQueue::change_priority_by).
767 pub fn get_mut<Q>(&mut self, item: &Q) -> Option<(&mut I, &P)>
768 where
769 I: Borrow<Q>,
770 Q: Eq + Hash + ?Sized,
771 {
772 self.store.get_mut(item)
773 }
774
775 /// Remove an arbitrary element from the priority queue.
776 /// Returns the (item, priority) couple or None if the item
777 /// is not found in the queue.
778 ///
779 /// The operation is performed in **O(log(N))** time (worst case).
780 pub fn remove<Q>(&mut self, item: &Q) -> Option<(I, P)>
781 where
782 I: Borrow<Q>,
783 Q: Eq + Hash + ?Sized,
784 {
785 self.store.remove(item).map(|(item, priority, pos)| {
786 if pos.0 < self.len() {
787 self.up_heapify(pos);
788 }
789
790 (item, priority)
791 })
792 }
793
794 /// Returns the items not ordered
795 pub fn into_vec(self) -> Vec<I> {
796 self.store.into_vec()
797 }
798
799 /// Drops all items from the priority queue
800 pub fn clear(&mut self) {
801 self.store.clear();
802 }
803
804 /// Move all items of the `other` queue to `self`
805 /// ignoring the items Eq to elements already in `self`
806 /// At the end, `other` will be empty.
807 ///
808 /// **Note** that at the end, the priority of the duplicated elements
809 /// inside `self` may be the one of the elements in `other`,
810 /// if `other` is longer than `self`
811 pub fn append(&mut self, other: &mut Self) {
812 self.store.append(&mut other.store);
813 self.heap_build();
814 }
815}
816
817impl<I, P, H> DoublePriorityQueue<I, P, H> {
818 /// Returns the index of the min element
819 fn find_min(&self) -> Option<Position> {
820 match self.len() {
821 0 => None,
822 _ => Some(Position(0)),
823 }
824 }
825}
826
827impl<I, P, H> DoublePriorityQueue<I, P, H>
828where
829 P: Ord,
830{
831 /**************************************************************************/
832 /* internal functions */
833
834 fn heapify(&mut self, i: Position) {
835 if self.len() <= 1 {
836 return;
837 }
838 if level(i) % 2 == 0 {
839 self.heapify_min(i)
840 } else {
841 self.heapify_max(i)
842 }
843 }
844
845 fn heapify_min(&mut self, mut i: Position) {
846 while i <= parent(Position(self.len() - 1)) {
847 let m = i;
848
849 let l = left(i);
850 let r = right(i);
851 // Minimum of childs and grandchilds
852 i = *[l, r, left(l), right(l), left(r), right(r)]
853 .iter()
854 .map_while(|i| self.store.heap.get(i.0).map(|index| (i, index)))
855 .min_by_key(|(_, index)| {
856 self.store
857 .map
858 .get_index(index.0)
859 .map(|(_, priority)| priority)
860 .unwrap()
861 })
862 .unwrap()
863 .0;
864
865 if unsafe {
866 self.store.get_priority_from_position(i) < self.store.get_priority_from_position(m)
867 } {
868 self.store.swap(i, m);
869 if i > r {
870 // i is a grandchild of m
871 let p = parent(i);
872 if unsafe {
873 self.store.get_priority_from_position(i)
874 > self.store.get_priority_from_position(p)
875 } {
876 self.store.swap(i, p);
877 }
878 } else {
879 break;
880 }
881 } else {
882 break;
883 }
884 }
885 }
886
887 fn heapify_max(&mut self, mut i: Position) {
888 while i <= parent(Position(self.len() - 1)) {
889 let m = i;
890
891 let l = left(i);
892 let r = right(i);
893 // Minimum of childs and grandchilds
894 i = *[l, r, left(l), right(l), left(r), right(r)]
895 .iter()
896 .map_while(|i| self.store.heap.get(i.0).map(|index| (i, index)))
897 .max_by_key(|(_, index)| {
898 self.store
899 .map
900 .get_index(index.0)
901 .map(|(_, priority)| priority)
902 .unwrap()
903 })
904 .unwrap()
905 .0;
906
907 if unsafe {
908 self.store.get_priority_from_position(i) > self.store.get_priority_from_position(m)
909 } {
910 self.store.swap(i, m);
911 if i > r {
912 // i is a grandchild of m
913 let p = parent(i);
914 if unsafe {
915 self.store.get_priority_from_position(i)
916 < self.store.get_priority_from_position(p)
917 } {
918 self.store.swap(i, p);
919 }
920 } else {
921 break;
922 }
923 } else {
924 break;
925 }
926 }
927 }
928
929 fn bubble_up(&mut self, mut position: Position, map_position: Index) -> Position {
930 let priority = self.store.map.get_index(map_position.0).unwrap().1;
931 if position.0 > 0 {
932 let parent = parent(position);
933 let parent_priority = unsafe { self.store.get_priority_from_position(parent) };
934 let parent_index = unsafe { *self.store.heap.get_unchecked(parent.0) };
935 position = match (level(position) % 2 == 0, parent_priority < priority) {
936 // on a min level and greater then parent
937 (true, true) => {
938 unsafe {
939 *self.store.heap.get_unchecked_mut(position.0) = parent_index;
940 *self.store.qp.get_unchecked_mut(parent_index.0) = position;
941 }
942 self.bubble_up_max(parent, map_position)
943 }
944 // on a min level and less then parent
945 (true, false) => self.bubble_up_min(position, map_position),
946 // on a max level and greater then parent
947 (false, true) => self.bubble_up_max(position, map_position),
948 // on a max level and less then parent
949 (false, false) => {
950 unsafe {
951 *self.store.heap.get_unchecked_mut(position.0) = parent_index;
952 *self.store.qp.get_unchecked_mut(parent_index.0) = position;
953 }
954 self.bubble_up_min(parent, map_position)
955 }
956 }
957 }
958
959 unsafe {
960 // put the new element into the heap and
961 // update the qp translation table and the size
962 *self.store.heap.get_unchecked_mut(position.0) = map_position;
963 *self.store.qp.get_unchecked_mut(map_position.0) = position;
964 }
965 position
966 }
967
968 fn bubble_up_min(&mut self, mut position: Position, map_position: Index) -> Position {
969 let priority = self.store.map.get_index(map_position.0).unwrap().1;
970 let mut grand_parent = Position(0);
971 while if position.0 > 0 && parent(position).0 > 0 {
972 grand_parent = parent(parent(position));
973 (unsafe { self.store.get_priority_from_position(grand_parent) }) > priority
974 } else {
975 false
976 } {
977 unsafe {
978 let grand_parent_index = *self.store.heap.get_unchecked(grand_parent.0);
979 *self.store.heap.get_unchecked_mut(position.0) = grand_parent_index;
980 *self.store.qp.get_unchecked_mut(grand_parent_index.0) = position;
981 }
982 position = grand_parent;
983 }
984 position
985 }
986
987 fn bubble_up_max(&mut self, mut position: Position, map_position: Index) -> Position {
988 let priority = self.store.map.get_index(map_position.0).unwrap().1;
989 let mut grand_parent = Position(0);
990 while if position.0 > 0 && parent(position).0 > 0 {
991 grand_parent = parent(parent(position));
992 (unsafe { self.store.get_priority_from_position(grand_parent) }) < priority
993 } else {
994 false
995 } {
996 unsafe {
997 let grand_parent_index = *self.store.heap.get_unchecked(grand_parent.0);
998 *self.store.heap.get_unchecked_mut(position.0) = grand_parent_index;
999 *self.store.qp.get_unchecked_mut(grand_parent_index.0) = position;
1000 }
1001 position = grand_parent;
1002 }
1003 position
1004 }
1005
1006 fn up_heapify(&mut self, i: Position) {
1007 if let Some(&tmp) = self.store.heap.get(i.0) {
1008 let pos = self.bubble_up(i, tmp);
1009 if i != pos {
1010 self.heapify(i)
1011 }
1012 self.heapify(pos);
1013 }
1014 }
1015
1016 /// Internal function that transform the `heap`
1017 /// vector in a heap with its properties
1018 ///
1019 /// Computes in **O(N)**
1020 pub(crate) fn heap_build(&mut self) {
1021 if self.is_empty() {
1022 return;
1023 }
1024 for i in (0..=parent(Position(self.len())).0).rev() {
1025 self.heapify(Position(i));
1026 }
1027 }
1028
1029 /// Returns the index of the max element
1030 fn find_max(&self) -> Option<Position> {
1031 match self.len() {
1032 0 => None,
1033 1 => Some(Position(0)),
1034 2 => Some(Position(1)),
1035 _ => Some(
1036 *[Position(1), Position(2)]
1037 .iter()
1038 .max_by_key(|i| unsafe { self.store.get_priority_from_position(**i) })
1039 .unwrap(),
1040 ),
1041 }
1042 }
1043}
1044
1045//FIXME: fails when the vector contains repeated items
1046// FIXED: repeated items ignored
1047impl<I, P, H> From<Vec<(I, P)>> for DoublePriorityQueue<I, P, H>
1048where
1049 I: Hash + Eq,
1050 P: Ord,
1051 H: BuildHasher + Default,
1052{
1053 fn from(vec: Vec<(I, P)>) -> Self {
1054 let store = Store::from(vec);
1055 let mut pq = DoublePriorityQueue { store };
1056 pq.heap_build();
1057 pq
1058 }
1059}
1060
1061use crate::PriorityQueue;
1062
1063impl<I, P, H> From<PriorityQueue<I, P, H>> for DoublePriorityQueue<I, P, H>
1064where
1065 I: Hash + Eq,
1066 P: Ord,
1067 H: BuildHasher,
1068{
1069 fn from(pq: PriorityQueue<I, P, H>) -> Self {
1070 let store = pq.store;
1071 let mut this = Self { store };
1072 this.heap_build();
1073 this
1074 }
1075}
1076
1077//FIXME: fails when the iterator contains repeated items
1078// FIXED: the item inside the pq is updated
1079// so there are two functions with different behaviours.
1080impl<I, P, H> FromIterator<(I, P)> for DoublePriorityQueue<I, P, H>
1081where
1082 I: Hash + Eq,
1083 P: Ord,
1084 H: BuildHasher + Default,
1085{
1086 fn from_iter<IT>(iter: IT) -> Self
1087 where
1088 IT: IntoIterator<Item = (I, P)>,
1089 {
1090 let store = Store::from_iter(iter);
1091 let mut pq = DoublePriorityQueue { store };
1092 pq.heap_build();
1093 pq
1094 }
1095}
1096
1097impl<I, P, H> IntoIterator for DoublePriorityQueue<I, P, H>
1098where
1099 I: Hash + Eq,
1100 P: Ord,
1101 H: BuildHasher,
1102{
1103 type Item = (I, P);
1104 type IntoIter = IntoIter<I, P>;
1105 fn into_iter(self) -> IntoIter<I, P> {
1106 self.store.into_iter()
1107 }
1108}
1109
1110impl<'a, I, P, H> IntoIterator for &'a DoublePriorityQueue<I, P, H>
1111where
1112 I: Hash + Eq,
1113 P: Ord,
1114 H: BuildHasher,
1115{
1116 type Item = (&'a I, &'a P);
1117 type IntoIter = Iter<'a, I, P>;
1118 fn into_iter(self) -> Iter<'a, I, P> {
1119 self.store.iter()
1120 }
1121}
1122
1123impl<'a, I, P, H> IntoIterator for &'a mut DoublePriorityQueue<I, P, H>
1124where
1125 I: Hash + Eq,
1126 P: Ord,
1127 H: BuildHasher,
1128{
1129 type Item = (&'a mut I, &'a mut P);
1130 type IntoIter = IterMut<'a, I, P, H>;
1131 fn into_iter(self) -> IterMut<'a, I, P, H> {
1132 IterMut::new(self)
1133 }
1134}
1135
1136impl<I, P, H> Extend<(I, P)> for DoublePriorityQueue<I, P, H>
1137where
1138 I: Hash + Eq,
1139 P: Ord,
1140 H: BuildHasher,
1141{
1142 fn extend<T: IntoIterator<Item = (I, P)>>(&mut self, iter: T) {
1143 let iter = iter.into_iter();
1144 let (min, max) = iter.size_hint();
1145 let rebuild = if let Some(max) = max {
1146 self.reserve(max);
1147 better_to_rebuild(self.len(), max)
1148 } else if min != 0 {
1149 self.reserve(min);
1150 better_to_rebuild(self.len(), min)
1151 } else {
1152 false
1153 };
1154 if rebuild {
1155 self.store.extend(iter);
1156 self.heap_build();
1157 } else {
1158 for (item, priority) in iter {
1159 self.push(item, priority);
1160 }
1161 }
1162 }
1163}
1164
1165use std::fmt;
1166
1167impl<I, P, H> fmt::Debug for DoublePriorityQueue<I, P, H>
1168where
1169 I: Hash + Eq + fmt::Debug,
1170 P: Ord + fmt::Debug,
1171{
1172 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
1173 self.store.fmt(f)
1174 }
1175}
1176
1177use std::cmp::PartialEq;
1178
1179impl<I, P1, H1, P2, H2> PartialEq<DoublePriorityQueue<I, P2, H2>> for DoublePriorityQueue<I, P1, H1>
1180where
1181 I: Hash + Eq,
1182 P1: Ord,
1183 P1: PartialEq<P2>,
1184 Option<P1>: PartialEq<Option<P2>>,
1185 P2: Ord,
1186 H1: BuildHasher,
1187 H2: BuildHasher,
1188{
1189 fn eq(&self, other: &DoublePriorityQueue<I, P2, H2>) -> bool {
1190 self.store == other.store
1191 }
1192}
1193
1194/// Compute the index of the left child of an item from its index
1195#[inline(always)]
1196const fn left(i: Position) -> Position {
1197 Position((i.0 * 2) + 1)
1198}
1199/// Compute the index of the right child of an item from its index
1200#[inline(always)]
1201const fn right(i: Position) -> Position {
1202 Position((i.0 * 2) + 2)
1203}
1204/// Compute the index of the parent element in the heap from its index
1205#[inline(always)]
1206const fn parent(i: Position) -> Position {
1207 Position((i.0 - 1) / 2)
1208}
1209
1210// Compute the level of a node from its index
1211#[inline(always)]
1212const fn level(i: Position) -> usize {
1213 log2_fast(i.0 + 1)
1214}
1215
1216#[inline(always)]
1217const fn log2_fast(x: usize) -> usize {
1218 (usize::BITS - x.leading_zeros() - 1) as usize
1219}
1220
1221// `rebuild` takes O(len1 + len2) operations
1222// and about 2 * (len1 + len2) comparisons in the worst case
1223// while `extend` takes O(len2 * log_2(len1)) operations
1224// and about 1 * len2 * log_2(len1) comparisons in the worst case,
1225// assuming len1 >= len2.
1226fn better_to_rebuild(len1: usize, len2: usize) -> bool {
1227 // log(1) == 0, so the inequation always falsy
1228 // log(0) is inapplicable and produces panic
1229 if len1 <= 1 {
1230 return false;
1231 }
1232
1233 2 * (len1 + len2) < len2 * log2_fast(len1)
1234}
1235
1236#[cfg(feature = "serde")]
1237#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1238mod serde {
1239 use std::cmp::{Eq, Ord};
1240 use std::hash::{BuildHasher, Hash};
1241
1242 use serde::de::{Deserialize, Deserializer};
1243 use serde::ser::{Serialize, Serializer};
1244
1245 use super::DoublePriorityQueue;
1246 use crate::store::Store;
1247
1248 impl<I, P, H> Serialize for DoublePriorityQueue<I, P, H>
1249 where
1250 I: Hash + Eq + Serialize,
1251 P: Ord + Serialize,
1252 H: BuildHasher,
1253 {
1254 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1255 where
1256 S: Serializer,
1257 {
1258 self.store.serialize(serializer)
1259 }
1260 }
1261
1262 impl<'de, I, P, H> Deserialize<'de> for DoublePriorityQueue<I, P, H>
1263 where
1264 I: Hash + Eq + Deserialize<'de>,
1265 P: Ord + Deserialize<'de>,
1266 H: BuildHasher + Default,
1267 {
1268 fn deserialize<D>(deserializer: D) -> Result<DoublePriorityQueue<I, P, H>, D::Error>
1269 where
1270 D: Deserializer<'de>,
1271 {
1272 Store::deserialize(deserializer).map(|store| {
1273 let mut pq = DoublePriorityQueue { store };
1274 pq.heap_build();
1275 pq
1276 })
1277 }
1278 }
1279}