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 /// # use priority_queue::DoublePriorityQueue;
473 /// let mut pq = DoublePriorityQueue::new();
474 ///
475 /// pq.push("Apples", 5);
476 /// pq.push("Bananas", 10);
477 ///
478 /// assert_eq!(pq.extract_if(|i, p| {
479 /// *p = 15;
480 /// i == &"Apples"
481 /// }).collect::<Vec<_>>(), vec![("Apples", 15)]);
482 ///
483 /// assert_eq!(pq.peek_min(), Some((&"Bananas", &15)));
484 /// assert_eq!(pq.into_vec(), vec!["Bananas"]);
485 /// ```
486 pub fn extract_if<F>(&mut self, predicate: F) -> ExtractIf<I, P, F, H>
487 where
488 F: FnMut(&mut I, &mut P) -> bool,
489 {
490 ExtractIf::new(self, predicate)
491 }
492
493 /// Removes the item with the lowest priority from
494 /// the priority queue if the predicate returns `true`.
495 ///
496 /// Returns the pair (item, priority), or None if the
497 /// queue is empty or the predicate returns `false`.
498 ///
499 /// The predicate receives mutable references to both the item and
500 /// the priority.
501 ///
502 /// It's a logical error to change the item in a way
503 /// that changes the result of `Hash` or `EQ`.
504 ///
505 /// The predicate can change the priority. If it returns true, the
506 /// returned couple will have the updated priority, otherwise, the
507 /// heap structural property will be restored.
508 ///
509 /// # Example
510 /// ```
511 /// # use priority_queue::DoublePriorityQueue;
512 /// let mut pq = DoublePriorityQueue::new();
513 ///
514 /// pq.push("Apples", 5);
515 /// pq.push("Bananas", 10);
516 ///
517 /// assert_eq!(pq.pop_min_if(|i, p| {
518 /// *p = 15;
519 /// false
520 /// }), None);
521 ///
522 /// assert_eq!(pq.pop_min(), Some(("Bananas", 10)));
523 /// ```
524 pub fn pop_min_if<F>(&mut self, f: F) -> Option<(I, P)>
525 where
526 F: FnOnce(&mut I, &mut P) -> bool,
527 {
528 self.find_min().and_then(|i| {
529 let r = self.store.swap_remove_if(i, f);
530 self.heapify(i);
531 r
532 })
533 }
534
535 /// Removes the item with the greatest priority from
536 /// the priority queue if the predicate returns `true`.
537 ///
538 /// Returns the pair (item, priority), or None if the
539 /// queue is empty or the predicate returns `false`.
540 ///
541 /// The predicate receives mutable references to both the item and
542 /// the priority.
543 ///
544 /// It's a logical error to change the item in a way
545 /// that changes the result of `Hash` or `EQ`.
546 ///
547 /// The predicate can change the priority. If it returns true, the
548 /// returned couple will have the updated priority, otherwise, the
549 /// heap structural property will be restored.
550 ///
551 /// # Example
552 /// ```
553 /// # use priority_queue::DoublePriorityQueue;
554 /// let mut pq = DoublePriorityQueue::new();
555 /// pq.push("Apples", 5);
556 /// pq.push("Bananas", 10);
557 /// assert_eq!(pq.pop_max_if(|i, p| {
558 /// *p = 3;
559 /// false
560 /// }), None);
561 /// assert_eq!(pq.pop_max(), Some(("Apples", 5)));
562 /// ```
563 pub fn pop_max_if<F>(&mut self, f: F) -> Option<(I, P)>
564 where
565 F: FnOnce(&mut I, &mut P) -> bool,
566 {
567 self.find_max().and_then(|i| {
568 let r = self.store.swap_remove_if(i, f);
569 self.up_heapify(i);
570 r
571 })
572 }
573
574 /// Insert the item-priority pair into the queue.
575 ///
576 /// If an element equal to `item` is already in the queue, its priority
577 /// is updated and the old priority is returned in `Some`; otherwise,
578 /// `item` is inserted with `priority` and `None` is returned.
579 ///
580 /// # Example
581 /// ```
582 /// # use priority_queue::DoublePriorityQueue;
583 /// let mut pq = DoublePriorityQueue::new();
584 /// assert_eq!(pq.push("Apples", 5), None);
585 /// assert_eq!(pq.get_priority("Apples"), Some(&5));
586 /// assert_eq!(pq.push("Apples", 6), Some(5));
587 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
588 /// assert_eq!(pq.push("Apples", 4), Some(6));
589 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
590 /// ```
591 ///
592 /// Computes in **O(log(N))** time.
593 pub fn push(&mut self, item: I, priority: P) -> Option<P> {
594 use indexmap::map::Entry::*;
595 let mut pos = Position(0);
596 let mut oldp = None;
597
598 match self.store.map.entry(item) {
599 Occupied(mut e) => {
600 oldp = Some(replace(e.get_mut(), priority));
601 pos = unsafe { *self.store.qp.get_unchecked(e.index()) };
602 }
603 Vacant(e) => {
604 e.insert(priority);
605 }
606 }
607
608 if oldp.is_some() {
609 self.up_heapify(pos);
610 return oldp;
611 }
612 // get a reference to the priority
613 // copy the current size of the heap
614 let i = self.len();
615 // add the new element in the qp vector as the last in the heap
616 self.store.qp.push(Position(i));
617 self.store.heap.push(Index(i));
618 self.bubble_up(Position(i), Index(i));
619 self.store.size += 1;
620 None
621 }
622
623 /// Increase the priority of an existing item in the queue, or
624 /// insert it if not present.
625 ///
626 /// If an element equal to `item` is already in the queue with a
627 /// lower priority, its priority is increased to the new one
628 /// without replacing the element and the old priority is returned
629 /// in `Some`.
630 ///
631 /// If an element equal to `item` is already in the queue with an
632 /// equal or higher priority, its priority is not changed and the
633 /// `priority` argument is returned in `Some`.
634 ///
635 /// If no element equal to `item` is already in the queue, the new
636 /// element is inserted and `None` is returned.
637 ///
638 /// # Example
639 /// ```
640 /// # use priority_queue::DoublePriorityQueue;
641 /// let mut pq = DoublePriorityQueue::new();
642 /// assert_eq!(pq.push_increase("Apples", 5), None);
643 /// assert_eq!(pq.get_priority("Apples"), Some(&5));
644 /// assert_eq!(pq.push_increase("Apples", 6), Some(5));
645 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
646 /// // Already present with higher priority, so requested (lower)
647 /// // priority is returned.
648 /// assert_eq!(pq.push_increase("Apples", 4), Some(4));
649 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
650 /// ```
651 ///
652 /// Computes in **O(log(N))** time.
653 pub fn push_increase(&mut self, item: I, priority: P) -> Option<P> {
654 if self.get_priority(&item).map_or(true, |p| priority > *p) {
655 self.push(item, priority)
656 } else {
657 Some(priority)
658 }
659 }
660
661 /// Decrease the priority of an existing item in the queue, or
662 /// insert it if not present.
663 ///
664 /// If an element equal to `item` is already in the queue with a
665 /// higher priority, its priority is decreased to the new one
666 /// without replacing the element and the old priority is returned
667 /// in `Some`.
668 ///
669 /// If an element equal to `item` is already in the queue with an
670 /// equal or lower priority, its priority is not changed and the
671 /// `priority` argument is returned in `Some`.
672 ///
673 /// If no element equal to `item` is already in the queue, the new
674 /// element is inserted and `None` is returned.
675 ///
676 /// # Example
677 /// ```
678 /// # use priority_queue::DoublePriorityQueue;
679 /// let mut pq = DoublePriorityQueue::new();
680 /// assert_eq!(pq.push_decrease("Apples", 5), None);
681 /// assert_eq!(pq.get_priority("Apples"), Some(&5));
682 /// assert_eq!(pq.push_decrease("Apples", 4), Some(5));
683 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
684 /// // Already present with lower priority, so requested (higher)
685 /// // priority is returned.
686 /// assert_eq!(pq.push_decrease("Apples", 6), Some(6));
687 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
688 /// ```
689 ///
690 /// Computes in **O(log(N))** time.
691 pub fn push_decrease(&mut self, item: I, priority: P) -> Option<P> {
692 if self.get_priority(&item).map_or(true, |p| priority < *p) {
693 self.push(item, priority)
694 } else {
695 Some(priority)
696 }
697 }
698
699 /// Change the priority of an Item returning the old value of priority,
700 /// or `None` if the item wasn't in the queue.
701 ///
702 /// The argument `item` is only used for lookup, and is not used to overwrite the item's data
703 /// in the priority queue.
704 ///
705 /// # Example
706 /// ```
707 /// # use priority_queue::DoublePriorityQueue;
708 /// let mut pq = DoublePriorityQueue::new();
709 /// assert_eq!(pq.change_priority("Apples", 5), None);
710 /// assert_eq!(pq.get_priority("Apples"), None);
711 /// assert_eq!(pq.push("Apples", 6), None);
712 /// assert_eq!(pq.get_priority("Apples"), Some(&6));
713 /// assert_eq!(pq.change_priority("Apples", 4), Some(6));
714 /// assert_eq!(pq.get_priority("Apples"), Some(&4));
715 /// ```
716 ///
717 /// The item is found in **O(1)** thanks to the hash table.
718 /// The operation is performed in **O(log(N))** time.
719 pub fn change_priority<Q>(&mut self, item: &Q, new_priority: P) -> Option<P>
720 where
721 I: Borrow<Q>,
722 Q: Eq + Hash + ?Sized,
723 {
724 self.store
725 .change_priority(item, new_priority)
726 .map(|(r, pos)| {
727 self.up_heapify(pos);
728 r
729 })
730 }
731
732 /// Change the priority of an Item using the provided function.
733 /// Return a boolean value where `true` means the item was in the queue and update was successful
734 ///
735 /// The argument `item` is only used for lookup, and is not used to overwrite the item's data
736 /// in the priority queue.
737 ///
738 /// The item is found in **O(1)** thanks to the hash table.
739 /// The operation is performed in **O(log(N))** time (worst case).
740 pub fn change_priority_by<Q, F>(&mut self, item: &Q, priority_setter: F) -> bool
741 where
742 I: Borrow<Q>,
743 Q: Eq + Hash + ?Sized,
744 F: FnOnce(&mut P),
745 {
746 self.store
747 .change_priority_by(item, priority_setter)
748 .map(|pos| {
749 self.up_heapify(pos);
750 })
751 .is_some()
752 }
753
754 /// Get the priority of an item, or `None`, if the item is not in the queue
755 pub fn get_priority<Q>(&self, item: &Q) -> Option<&P>
756 where
757 I: Borrow<Q>,
758 Q: Eq + Hash + ?Sized,
759 {
760 self.store.get_priority(item)
761 }
762
763 /// Get the couple (item, priority) of an arbitrary element, as reference
764 /// or `None` if the item is not in the queue.
765 pub fn get<Q>(&self, item: &Q) -> Option<(&I, &P)>
766 where
767 I: Borrow<Q>,
768 Q: Eq + Hash + ?Sized,
769 {
770 self.store.get(item)
771 }
772
773 /// Get the couple (item, priority) of an arbitrary element, or `None`
774 /// if the item was not in the queue.
775 ///
776 /// The item is a mutable reference, but it's a logic error to modify it
777 /// in a way that change the result of `Hash` or `Eq`.
778 ///
779 /// The priority cannot be modified with a call to this function.
780 /// To modify the priority use use [`push`](DoublePriorityQueue::push),
781 /// [`change_priority`](DoublePriorityQueue::change_priority) or
782 /// [`change_priority_by`](DoublePriorityQueue::change_priority_by).
783 pub fn get_mut<Q>(&mut self, item: &Q) -> Option<(&mut I, &P)>
784 where
785 I: Borrow<Q>,
786 Q: Eq + Hash + ?Sized,
787 {
788 self.store.get_mut(item)
789 }
790
791 /// Remove an arbitrary element from the priority queue.
792 /// Returns the (item, priority) couple or None if the item
793 /// is not found in the queue.
794 ///
795 /// The operation is performed in **O(log(N))** time (worst case).
796 pub fn remove<Q>(&mut self, item: &Q) -> Option<(I, P)>
797 where
798 I: Borrow<Q>,
799 Q: Eq + Hash + ?Sized,
800 {
801 self.store.remove(item).map(|(item, priority, pos)| {
802 if pos.0 < self.len() {
803 self.up_heapify(pos);
804 }
805
806 (item, priority)
807 })
808 }
809
810 /// Returns the items not ordered
811 pub fn into_vec(self) -> Vec<I> {
812 self.store.into_vec()
813 }
814
815 /// Drops all items from the priority queue
816 pub fn clear(&mut self) {
817 self.store.clear();
818 }
819
820 /// Move all items of the `other` queue to `self`
821 /// ignoring the items Eq to elements already in `self`
822 /// At the end, `other` will be empty.
823 ///
824 /// **Note** that at the end, the priority of the duplicated elements
825 /// inside `self` may be the one of the elements in `other`,
826 /// if `other` is longer than `self`
827 pub fn append(&mut self, other: &mut Self) {
828 self.store.append(&mut other.store);
829 self.heap_build();
830 }
831}
832
833impl<I, P, H> DoublePriorityQueue<I, P, H> {
834 /// Returns the index of the min element
835 fn find_min(&self) -> Option<Position> {
836 match self.len() {
837 0 => None,
838 _ => Some(Position(0)),
839 }
840 }
841}
842
843impl<I, P, H> DoublePriorityQueue<I, P, H>
844where
845 P: Ord,
846{
847 /**************************************************************************/
848 /* internal functions */
849
850 fn heapify(&mut self, i: Position) {
851 if self.len() <= 1 {
852 return;
853 }
854 if level(i) % 2 == 0 {
855 self.heapify_min(i)
856 } else {
857 self.heapify_max(i)
858 }
859 }
860
861 fn heapify_min(&mut self, mut i: Position) {
862 while i <= parent(Position(self.len() - 1)) {
863 let m = i;
864
865 let l = left(i);
866 let r = right(i);
867 // Minimum of childs and grandchilds
868 i = *[l, r, left(l), right(l), left(r), right(r)]
869 .iter()
870 .map_while(|i| self.store.heap.get(i.0).map(|index| (i, index)))
871 .min_by_key(|(_, index)| {
872 self.store
873 .map
874 .get_index(index.0)
875 .map(|(_, priority)| priority)
876 .unwrap()
877 })
878 .unwrap()
879 .0;
880
881 if unsafe {
882 self.store.get_priority_from_position(i) < self.store.get_priority_from_position(m)
883 } {
884 self.store.swap(i, m);
885 if i > r {
886 // i is a grandchild of m
887 let p = parent(i);
888 if unsafe {
889 self.store.get_priority_from_position(i)
890 > self.store.get_priority_from_position(p)
891 } {
892 self.store.swap(i, p);
893 }
894 } else {
895 break;
896 }
897 } else {
898 break;
899 }
900 }
901 }
902
903 fn heapify_max(&mut self, mut i: Position) {
904 while i <= parent(Position(self.len() - 1)) {
905 let m = i;
906
907 let l = left(i);
908 let r = right(i);
909 // Minimum of childs and grandchilds
910 i = *[l, r, left(l), right(l), left(r), right(r)]
911 .iter()
912 .map_while(|i| self.store.heap.get(i.0).map(|index| (i, index)))
913 .max_by_key(|(_, index)| {
914 self.store
915 .map
916 .get_index(index.0)
917 .map(|(_, priority)| priority)
918 .unwrap()
919 })
920 .unwrap()
921 .0;
922
923 if unsafe {
924 self.store.get_priority_from_position(i) > self.store.get_priority_from_position(m)
925 } {
926 self.store.swap(i, m);
927 if i > r {
928 // i is a grandchild of m
929 let p = parent(i);
930 if unsafe {
931 self.store.get_priority_from_position(i)
932 < self.store.get_priority_from_position(p)
933 } {
934 self.store.swap(i, p);
935 }
936 } else {
937 break;
938 }
939 } else {
940 break;
941 }
942 }
943 }
944
945 fn bubble_up(&mut self, mut position: Position, map_position: Index) -> Position {
946 let priority = self.store.map.get_index(map_position.0).unwrap().1;
947 if position.0 > 0 {
948 let parent = parent(position);
949 let parent_priority = unsafe { self.store.get_priority_from_position(parent) };
950 let parent_index = unsafe { *self.store.heap.get_unchecked(parent.0) };
951 position = match (level(position) % 2 == 0, parent_priority < priority) {
952 // on a min level and greater then parent
953 (true, true) => {
954 unsafe {
955 *self.store.heap.get_unchecked_mut(position.0) = parent_index;
956 *self.store.qp.get_unchecked_mut(parent_index.0) = position;
957 }
958 self.bubble_up_max(parent, map_position)
959 }
960 // on a min level and less then parent
961 (true, false) => self.bubble_up_min(position, map_position),
962 // on a max level and greater then parent
963 (false, true) => self.bubble_up_max(position, map_position),
964 // on a max level and less then parent
965 (false, false) => {
966 unsafe {
967 *self.store.heap.get_unchecked_mut(position.0) = parent_index;
968 *self.store.qp.get_unchecked_mut(parent_index.0) = position;
969 }
970 self.bubble_up_min(parent, map_position)
971 }
972 }
973 }
974
975 unsafe {
976 // put the new element into the heap and
977 // update the qp translation table and the size
978 *self.store.heap.get_unchecked_mut(position.0) = map_position;
979 *self.store.qp.get_unchecked_mut(map_position.0) = position;
980 }
981 position
982 }
983
984 fn bubble_up_min(&mut self, mut position: Position, map_position: Index) -> Position {
985 let priority = self.store.map.get_index(map_position.0).unwrap().1;
986 let mut grand_parent = Position(0);
987 while if position.0 > 0 && parent(position).0 > 0 {
988 grand_parent = parent(parent(position));
989 (unsafe { self.store.get_priority_from_position(grand_parent) }) > priority
990 } else {
991 false
992 } {
993 unsafe {
994 let grand_parent_index = *self.store.heap.get_unchecked(grand_parent.0);
995 *self.store.heap.get_unchecked_mut(position.0) = grand_parent_index;
996 *self.store.qp.get_unchecked_mut(grand_parent_index.0) = position;
997 }
998 position = grand_parent;
999 }
1000 position
1001 }
1002
1003 fn bubble_up_max(&mut self, mut position: Position, map_position: Index) -> Position {
1004 let priority = self.store.map.get_index(map_position.0).unwrap().1;
1005 let mut grand_parent = Position(0);
1006 while if position.0 > 0 && parent(position).0 > 0 {
1007 grand_parent = parent(parent(position));
1008 (unsafe { self.store.get_priority_from_position(grand_parent) }) < priority
1009 } else {
1010 false
1011 } {
1012 unsafe {
1013 let grand_parent_index = *self.store.heap.get_unchecked(grand_parent.0);
1014 *self.store.heap.get_unchecked_mut(position.0) = grand_parent_index;
1015 *self.store.qp.get_unchecked_mut(grand_parent_index.0) = position;
1016 }
1017 position = grand_parent;
1018 }
1019 position
1020 }
1021
1022 fn up_heapify(&mut self, i: Position) {
1023 if let Some(&tmp) = self.store.heap.get(i.0) {
1024 let pos = self.bubble_up(i, tmp);
1025 if i != pos {
1026 self.heapify(i)
1027 }
1028 self.heapify(pos);
1029 }
1030 }
1031
1032 /// Internal function that transform the `heap`
1033 /// vector in a heap with its properties
1034 ///
1035 /// Computes in **O(N)**
1036 pub(crate) fn heap_build(&mut self) {
1037 if self.is_empty() {
1038 return;
1039 }
1040 for i in (0..=parent(Position(self.len())).0).rev() {
1041 self.heapify(Position(i));
1042 }
1043 }
1044
1045 /// Returns the index of the max element
1046 fn find_max(&self) -> Option<Position> {
1047 match self.len() {
1048 0 => None,
1049 1 => Some(Position(0)),
1050 2 => Some(Position(1)),
1051 _ => Some(
1052 *[Position(1), Position(2)]
1053 .iter()
1054 .max_by_key(|i| unsafe { self.store.get_priority_from_position(**i) })
1055 .unwrap(),
1056 ),
1057 }
1058 }
1059}
1060
1061//FIXME: fails when the vector contains repeated items
1062// FIXED: repeated items ignored
1063impl<I, P, H> From<Vec<(I, P)>> for DoublePriorityQueue<I, P, H>
1064where
1065 I: Hash + Eq,
1066 P: Ord,
1067 H: BuildHasher + Default,
1068{
1069 fn from(vec: Vec<(I, P)>) -> Self {
1070 let store = Store::from(vec);
1071 let mut pq = DoublePriorityQueue { store };
1072 pq.heap_build();
1073 pq
1074 }
1075}
1076
1077use crate::PriorityQueue;
1078
1079impl<I, P, H> From<PriorityQueue<I, P, H>> for DoublePriorityQueue<I, P, H>
1080where
1081 I: Hash + Eq,
1082 P: Ord,
1083 H: BuildHasher,
1084{
1085 fn from(pq: PriorityQueue<I, P, H>) -> Self {
1086 let store = pq.store;
1087 let mut this = Self { store };
1088 this.heap_build();
1089 this
1090 }
1091}
1092
1093//FIXME: fails when the iterator contains repeated items
1094// FIXED: the item inside the pq is updated
1095// so there are two functions with different behaviours.
1096impl<I, P, H> FromIterator<(I, P)> for DoublePriorityQueue<I, P, H>
1097where
1098 I: Hash + Eq,
1099 P: Ord,
1100 H: BuildHasher + Default,
1101{
1102 fn from_iter<IT>(iter: IT) -> Self
1103 where
1104 IT: IntoIterator<Item = (I, P)>,
1105 {
1106 let store = Store::from_iter(iter);
1107 let mut pq = DoublePriorityQueue { store };
1108 pq.heap_build();
1109 pq
1110 }
1111}
1112
1113impl<I, P, H> IntoIterator for DoublePriorityQueue<I, P, H>
1114where
1115 I: Hash + Eq,
1116 P: Ord,
1117 H: BuildHasher,
1118{
1119 type Item = (I, P);
1120 type IntoIter = IntoIter<I, P>;
1121 fn into_iter(self) -> IntoIter<I, P> {
1122 self.store.into_iter()
1123 }
1124}
1125
1126impl<'a, I, P, H> IntoIterator for &'a DoublePriorityQueue<I, P, H>
1127where
1128 I: Hash + Eq,
1129 P: Ord,
1130 H: BuildHasher,
1131{
1132 type Item = (&'a I, &'a P);
1133 type IntoIter = Iter<'a, I, P>;
1134 fn into_iter(self) -> Iter<'a, I, P> {
1135 self.store.iter()
1136 }
1137}
1138
1139impl<'a, I, P, H> IntoIterator for &'a mut DoublePriorityQueue<I, P, H>
1140where
1141 I: Hash + Eq,
1142 P: Ord,
1143 H: BuildHasher,
1144{
1145 type Item = (&'a mut I, &'a mut P);
1146 type IntoIter = IterMut<'a, I, P, H>;
1147 fn into_iter(self) -> IterMut<'a, I, P, H> {
1148 IterMut::new(self)
1149 }
1150}
1151
1152impl<I, P, H> Extend<(I, P)> for DoublePriorityQueue<I, P, H>
1153where
1154 I: Hash + Eq,
1155 P: Ord,
1156 H: BuildHasher,
1157{
1158 fn extend<T: IntoIterator<Item = (I, P)>>(&mut self, iter: T) {
1159 let iter = iter.into_iter();
1160 let (min, max) = iter.size_hint();
1161 let rebuild = if let Some(max) = max {
1162 self.reserve(max);
1163 better_to_rebuild(self.len(), max)
1164 } else if min != 0 {
1165 self.reserve(min);
1166 better_to_rebuild(self.len(), min)
1167 } else {
1168 false
1169 };
1170 if rebuild {
1171 self.store.extend(iter);
1172 self.heap_build();
1173 } else {
1174 for (item, priority) in iter {
1175 self.push(item, priority);
1176 }
1177 }
1178 }
1179}
1180
1181use std::fmt;
1182
1183impl<I, P, H> fmt::Debug for DoublePriorityQueue<I, P, H>
1184where
1185 I: Hash + Eq + fmt::Debug,
1186 P: Ord + fmt::Debug,
1187{
1188 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
1189 self.store.fmt(f)
1190 }
1191}
1192
1193use std::cmp::PartialEq;
1194
1195impl<I, P1, H1, P2, H2> PartialEq<DoublePriorityQueue<I, P2, H2>> for DoublePriorityQueue<I, P1, H1>
1196where
1197 I: Hash + Eq,
1198 P1: Ord,
1199 P1: PartialEq<P2>,
1200 Option<P1>: PartialEq<Option<P2>>,
1201 P2: Ord,
1202 H1: BuildHasher,
1203 H2: BuildHasher,
1204{
1205 fn eq(&self, other: &DoublePriorityQueue<I, P2, H2>) -> bool {
1206 self.store == other.store
1207 }
1208}
1209
1210/// Compute the index of the left child of an item from its index
1211#[inline(always)]
1212const fn left(i: Position) -> Position {
1213 Position((i.0 * 2) + 1)
1214}
1215/// Compute the index of the right child of an item from its index
1216#[inline(always)]
1217const fn right(i: Position) -> Position {
1218 Position((i.0 * 2) + 2)
1219}
1220/// Compute the index of the parent element in the heap from its index
1221#[inline(always)]
1222const fn parent(i: Position) -> Position {
1223 Position((i.0 - 1) / 2)
1224}
1225
1226// Compute the level of a node from its index
1227#[inline(always)]
1228const fn level(i: Position) -> usize {
1229 log2_fast(i.0 + 1)
1230}
1231
1232#[inline(always)]
1233const fn log2_fast(x: usize) -> usize {
1234 (usize::BITS - x.leading_zeros() - 1) as usize
1235}
1236
1237// `rebuild` takes O(len1 + len2) operations
1238// and about 2 * (len1 + len2) comparisons in the worst case
1239// while `extend` takes O(len2 * log_2(len1)) operations
1240// and about 1 * len2 * log_2(len1) comparisons in the worst case,
1241// assuming len1 >= len2.
1242fn better_to_rebuild(len1: usize, len2: usize) -> bool {
1243 // log(1) == 0, so the inequation always falsy
1244 // log(0) is inapplicable and produces panic
1245 if len1 <= 1 {
1246 return false;
1247 }
1248
1249 2 * (len1 + len2) < len2 * log2_fast(len1)
1250}
1251
1252#[cfg(feature = "serde")]
1253#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1254mod serde {
1255 use std::cmp::{Eq, Ord};
1256 use std::hash::{BuildHasher, Hash};
1257
1258 use serde::de::{Deserialize, Deserializer};
1259 use serde::ser::{Serialize, Serializer};
1260
1261 use super::DoublePriorityQueue;
1262 use crate::store::Store;
1263
1264 impl<I, P, H> Serialize for DoublePriorityQueue<I, P, H>
1265 where
1266 I: Hash + Eq + Serialize,
1267 P: Ord + Serialize,
1268 H: BuildHasher,
1269 {
1270 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1271 where
1272 S: Serializer,
1273 {
1274 self.store.serialize(serializer)
1275 }
1276 }
1277
1278 impl<'de, I, P, H> Deserialize<'de> for DoublePriorityQueue<I, P, H>
1279 where
1280 I: Hash + Eq + Deserialize<'de>,
1281 P: Ord + Deserialize<'de>,
1282 H: BuildHasher + Default,
1283 {
1284 fn deserialize<D>(deserializer: D) -> Result<DoublePriorityQueue<I, P, H>, D::Error>
1285 where
1286 D: Deserializer<'de>,
1287 {
1288 Store::deserialize(deserializer).map(|store| {
1289 let mut pq = DoublePriorityQueue { store };
1290 pq.heap_build();
1291 pq
1292 })
1293 }
1294 }
1295}