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 /// Check if the queue contains `item`.
764 ///
765 /// Returns `true` if `item` is in the queue, `false` if it is not.
766 pub fn contains<Q>(&self, item: &Q) -> bool
767 where
768 I: Borrow<Q>,
769 Q: Eq + Hash + ?Sized,
770 {
771 self.store.contains(item)
772 }
773
774 /// Get the couple (item, priority) of an arbitrary element, as reference
775 /// or `None` if the item is not in the queue.
776 pub fn get<Q>(&self, item: &Q) -> Option<(&I, &P)>
777 where
778 I: Borrow<Q>,
779 Q: Eq + Hash + ?Sized,
780 {
781 self.store.get(item)
782 }
783
784 /// Get the couple (item, priority) of an arbitrary element, or `None`
785 /// if the item was not in the queue.
786 ///
787 /// The item is a mutable reference, but it's a logic error to modify it
788 /// in a way that change the result of `Hash` or `Eq`.
789 ///
790 /// The priority cannot be modified with a call to this function.
791 /// To modify the priority use use [`push`](DoublePriorityQueue::push),
792 /// [`change_priority`](DoublePriorityQueue::change_priority) or
793 /// [`change_priority_by`](DoublePriorityQueue::change_priority_by).
794 pub fn get_mut<Q>(&mut self, item: &Q) -> Option<(&mut I, &P)>
795 where
796 I: Borrow<Q>,
797 Q: Eq + Hash + ?Sized,
798 {
799 self.store.get_mut(item)
800 }
801
802 /// Remove an arbitrary element from the priority queue.
803 /// Returns the (item, priority) couple or None if the item
804 /// is not found in the queue.
805 ///
806 /// The operation is performed in **O(log(N))** time (worst case).
807 pub fn remove<Q>(&mut self, item: &Q) -> Option<(I, P)>
808 where
809 I: Borrow<Q>,
810 Q: Eq + Hash + ?Sized,
811 {
812 self.store.remove(item).map(|(item, priority, pos)| {
813 if pos.0 < self.len() {
814 self.up_heapify(pos);
815 }
816
817 (item, priority)
818 })
819 }
820
821 /// Returns the items not ordered
822 pub fn into_vec(self) -> Vec<I> {
823 self.store.into_vec()
824 }
825
826 /// Drops all items from the priority queue
827 pub fn clear(&mut self) {
828 self.store.clear();
829 }
830
831 /// Move all items of the `other` queue to `self`
832 /// ignoring the items Eq to elements already in `self`
833 /// At the end, `other` will be empty.
834 ///
835 /// **Note** that at the end, the priority of the duplicated elements
836 /// inside `self` may be the one of the elements in `other`,
837 /// if `other` is longer than `self`
838 pub fn append(&mut self, other: &mut Self) {
839 self.store.append(&mut other.store);
840 self.heap_build();
841 }
842}
843
844impl<I, P, H> DoublePriorityQueue<I, P, H> {
845 /// Returns the index of the min element
846 fn find_min(&self) -> Option<Position> {
847 match self.len() {
848 0 => None,
849 _ => Some(Position(0)),
850 }
851 }
852}
853
854impl<I, P, H> DoublePriorityQueue<I, P, H>
855where
856 P: Ord,
857{
858 /**************************************************************************/
859 /* internal functions */
860
861 fn heapify(&mut self, i: Position) {
862 if self.len() <= 1 {
863 return;
864 }
865 if level(i) % 2 == 0 {
866 self.heapify_min(i)
867 } else {
868 self.heapify_max(i)
869 }
870 }
871
872 fn heapify_min(&mut self, mut i: Position) {
873 while i <= parent(Position(self.len() - 1)) {
874 let m = i;
875
876 let l = left(i);
877 let r = right(i);
878 // Minimum of childs and grandchilds
879 i = *[l, r, left(l), right(l), left(r), right(r)]
880 .iter()
881 .map_while(|i| self.store.heap.get(i.0).map(|index| (i, index)))
882 .min_by_key(|(_, index)| {
883 self.store
884 .map
885 .get_index(index.0)
886 .map(|(_, priority)| priority)
887 .unwrap()
888 })
889 .unwrap()
890 .0;
891
892 if unsafe {
893 self.store.get_priority_from_position(i) < self.store.get_priority_from_position(m)
894 } {
895 self.store.swap(i, m);
896 if i > r {
897 // i is a grandchild of m
898 let p = parent(i);
899 if unsafe {
900 self.store.get_priority_from_position(i)
901 > self.store.get_priority_from_position(p)
902 } {
903 self.store.swap(i, p);
904 }
905 } else {
906 break;
907 }
908 } else {
909 break;
910 }
911 }
912 }
913
914 fn heapify_max(&mut self, mut i: Position) {
915 while i <= parent(Position(self.len() - 1)) {
916 let m = i;
917
918 let l = left(i);
919 let r = right(i);
920 // Minimum of childs and grandchilds
921 i = *[l, r, left(l), right(l), left(r), right(r)]
922 .iter()
923 .map_while(|i| self.store.heap.get(i.0).map(|index| (i, index)))
924 .max_by_key(|(_, index)| {
925 self.store
926 .map
927 .get_index(index.0)
928 .map(|(_, priority)| priority)
929 .unwrap()
930 })
931 .unwrap()
932 .0;
933
934 if unsafe {
935 self.store.get_priority_from_position(i) > self.store.get_priority_from_position(m)
936 } {
937 self.store.swap(i, m);
938 if i > r {
939 // i is a grandchild of m
940 let p = parent(i);
941 if unsafe {
942 self.store.get_priority_from_position(i)
943 < self.store.get_priority_from_position(p)
944 } {
945 self.store.swap(i, p);
946 }
947 } else {
948 break;
949 }
950 } else {
951 break;
952 }
953 }
954 }
955
956 fn bubble_up(&mut self, mut position: Position, map_position: Index) -> Position {
957 let priority = self.store.map.get_index(map_position.0).unwrap().1;
958 if position.0 > 0 {
959 let parent = parent(position);
960 let parent_priority = unsafe { self.store.get_priority_from_position(parent) };
961 let parent_index = unsafe { *self.store.heap.get_unchecked(parent.0) };
962 position = match (level(position) % 2 == 0, parent_priority < priority) {
963 // on a min level and greater then parent
964 (true, true) => {
965 unsafe {
966 *self.store.heap.get_unchecked_mut(position.0) = parent_index;
967 *self.store.qp.get_unchecked_mut(parent_index.0) = position;
968 }
969 self.bubble_up_max(parent, map_position)
970 }
971 // on a min level and less then parent
972 (true, false) => self.bubble_up_min(position, map_position),
973 // on a max level and greater then parent
974 (false, true) => self.bubble_up_max(position, map_position),
975 // on a max level and less then parent
976 (false, false) => {
977 unsafe {
978 *self.store.heap.get_unchecked_mut(position.0) = parent_index;
979 *self.store.qp.get_unchecked_mut(parent_index.0) = position;
980 }
981 self.bubble_up_min(parent, map_position)
982 }
983 }
984 }
985
986 unsafe {
987 // put the new element into the heap and
988 // update the qp translation table and the size
989 *self.store.heap.get_unchecked_mut(position.0) = map_position;
990 *self.store.qp.get_unchecked_mut(map_position.0) = position;
991 }
992 position
993 }
994
995 fn bubble_up_min(&mut self, mut position: Position, map_position: Index) -> Position {
996 let priority = self.store.map.get_index(map_position.0).unwrap().1;
997 let mut grand_parent = Position(0);
998 while if position.0 > 0 && parent(position).0 > 0 {
999 grand_parent = parent(parent(position));
1000 (unsafe { self.store.get_priority_from_position(grand_parent) }) > priority
1001 } else {
1002 false
1003 } {
1004 unsafe {
1005 let grand_parent_index = *self.store.heap.get_unchecked(grand_parent.0);
1006 *self.store.heap.get_unchecked_mut(position.0) = grand_parent_index;
1007 *self.store.qp.get_unchecked_mut(grand_parent_index.0) = position;
1008 }
1009 position = grand_parent;
1010 }
1011 position
1012 }
1013
1014 fn bubble_up_max(&mut self, mut position: Position, map_position: Index) -> Position {
1015 let priority = self.store.map.get_index(map_position.0).unwrap().1;
1016 let mut grand_parent = Position(0);
1017 while if position.0 > 0 && parent(position).0 > 0 {
1018 grand_parent = parent(parent(position));
1019 (unsafe { self.store.get_priority_from_position(grand_parent) }) < priority
1020 } else {
1021 false
1022 } {
1023 unsafe {
1024 let grand_parent_index = *self.store.heap.get_unchecked(grand_parent.0);
1025 *self.store.heap.get_unchecked_mut(position.0) = grand_parent_index;
1026 *self.store.qp.get_unchecked_mut(grand_parent_index.0) = position;
1027 }
1028 position = grand_parent;
1029 }
1030 position
1031 }
1032
1033 fn up_heapify(&mut self, i: Position) {
1034 if let Some(&tmp) = self.store.heap.get(i.0) {
1035 let pos = self.bubble_up(i, tmp);
1036 if i != pos {
1037 self.heapify(i)
1038 }
1039 self.heapify(pos);
1040 }
1041 }
1042
1043 /// Internal function that transform the `heap`
1044 /// vector in a heap with its properties
1045 ///
1046 /// Computes in **O(N)**
1047 pub(crate) fn heap_build(&mut self) {
1048 if self.is_empty() {
1049 return;
1050 }
1051 for i in (0..=parent(Position(self.len())).0).rev() {
1052 self.heapify(Position(i));
1053 }
1054 }
1055
1056 /// Returns the index of the max element
1057 fn find_max(&self) -> Option<Position> {
1058 match self.len() {
1059 0 => None,
1060 1 => Some(Position(0)),
1061 2 => Some(Position(1)),
1062 _ => Some(
1063 *[Position(1), Position(2)]
1064 .iter()
1065 .max_by_key(|i| unsafe { self.store.get_priority_from_position(**i) })
1066 .unwrap(),
1067 ),
1068 }
1069 }
1070}
1071
1072//FIXME: fails when the vector contains repeated items
1073// FIXED: repeated items ignored
1074impl<I, P, H> From<Vec<(I, P)>> for DoublePriorityQueue<I, P, H>
1075where
1076 I: Hash + Eq,
1077 P: Ord,
1078 H: BuildHasher + Default,
1079{
1080 fn from(vec: Vec<(I, P)>) -> Self {
1081 let store = Store::from(vec);
1082 let mut pq = DoublePriorityQueue { store };
1083 pq.heap_build();
1084 pq
1085 }
1086}
1087
1088use crate::PriorityQueue;
1089
1090impl<I, P, H> From<PriorityQueue<I, P, H>> for DoublePriorityQueue<I, P, H>
1091where
1092 I: Hash + Eq,
1093 P: Ord,
1094 H: BuildHasher,
1095{
1096 fn from(pq: PriorityQueue<I, P, H>) -> Self {
1097 let store = pq.store;
1098 let mut this = Self { store };
1099 this.heap_build();
1100 this
1101 }
1102}
1103
1104//FIXME: fails when the iterator contains repeated items
1105// FIXED: the item inside the pq is updated
1106// so there are two functions with different behaviours.
1107impl<I, P, H> FromIterator<(I, P)> for DoublePriorityQueue<I, P, H>
1108where
1109 I: Hash + Eq,
1110 P: Ord,
1111 H: BuildHasher + Default,
1112{
1113 fn from_iter<IT>(iter: IT) -> Self
1114 where
1115 IT: IntoIterator<Item = (I, P)>,
1116 {
1117 let store = Store::from_iter(iter);
1118 let mut pq = DoublePriorityQueue { store };
1119 pq.heap_build();
1120 pq
1121 }
1122}
1123
1124impl<I, P, H> IntoIterator for DoublePriorityQueue<I, P, H>
1125where
1126 I: Hash + Eq,
1127 P: Ord,
1128 H: BuildHasher,
1129{
1130 type Item = (I, P);
1131 type IntoIter = IntoIter<I, P>;
1132 fn into_iter(self) -> IntoIter<I, P> {
1133 self.store.into_iter()
1134 }
1135}
1136
1137impl<'a, I, P, H> IntoIterator for &'a DoublePriorityQueue<I, P, H>
1138where
1139 I: Hash + Eq,
1140 P: Ord,
1141 H: BuildHasher,
1142{
1143 type Item = (&'a I, &'a P);
1144 type IntoIter = Iter<'a, I, P>;
1145 fn into_iter(self) -> Iter<'a, I, P> {
1146 self.store.iter()
1147 }
1148}
1149
1150impl<'a, I, P, H> IntoIterator for &'a mut DoublePriorityQueue<I, P, H>
1151where
1152 I: Hash + Eq,
1153 P: Ord,
1154 H: BuildHasher,
1155{
1156 type Item = (&'a mut I, &'a mut P);
1157 type IntoIter = IterMut<'a, I, P, H>;
1158 fn into_iter(self) -> IterMut<'a, I, P, H> {
1159 IterMut::new(self)
1160 }
1161}
1162
1163impl<I, P, H> Extend<(I, P)> for DoublePriorityQueue<I, P, H>
1164where
1165 I: Hash + Eq,
1166 P: Ord,
1167 H: BuildHasher,
1168{
1169 fn extend<T: IntoIterator<Item = (I, P)>>(&mut self, iter: T) {
1170 let iter = iter.into_iter();
1171 let (min, max) = iter.size_hint();
1172 let rebuild = if let Some(max) = max {
1173 self.reserve(max);
1174 better_to_rebuild(self.len(), max)
1175 } else if min != 0 {
1176 self.reserve(min);
1177 better_to_rebuild(self.len(), min)
1178 } else {
1179 false
1180 };
1181 if rebuild {
1182 self.store.extend(iter);
1183 self.heap_build();
1184 } else {
1185 for (item, priority) in iter {
1186 self.push(item, priority);
1187 }
1188 }
1189 }
1190}
1191
1192use std::fmt;
1193
1194impl<I, P, H> fmt::Debug for DoublePriorityQueue<I, P, H>
1195where
1196 I: Hash + Eq + fmt::Debug,
1197 P: Ord + fmt::Debug,
1198{
1199 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
1200 self.store.fmt(f)
1201 }
1202}
1203
1204use std::cmp::PartialEq;
1205
1206impl<I, P1, H1, P2, H2> PartialEq<DoublePriorityQueue<I, P2, H2>> for DoublePriorityQueue<I, P1, H1>
1207where
1208 I: Hash + Eq,
1209 P1: Ord,
1210 P1: PartialEq<P2>,
1211 Option<P1>: PartialEq<Option<P2>>,
1212 P2: Ord,
1213 H1: BuildHasher,
1214 H2: BuildHasher,
1215{
1216 fn eq(&self, other: &DoublePriorityQueue<I, P2, H2>) -> bool {
1217 self.store == other.store
1218 }
1219}
1220
1221/// Compute the index of the left child of an item from its index
1222#[inline(always)]
1223const fn left(i: Position) -> Position {
1224 Position((i.0 * 2) + 1)
1225}
1226/// Compute the index of the right child of an item from its index
1227#[inline(always)]
1228const fn right(i: Position) -> Position {
1229 Position((i.0 * 2) + 2)
1230}
1231/// Compute the index of the parent element in the heap from its index
1232#[inline(always)]
1233const fn parent(i: Position) -> Position {
1234 Position((i.0 - 1) / 2)
1235}
1236
1237// Compute the level of a node from its index
1238#[inline(always)]
1239const fn level(i: Position) -> usize {
1240 log2_fast(i.0 + 1)
1241}
1242
1243#[inline(always)]
1244const fn log2_fast(x: usize) -> usize {
1245 (usize::BITS - x.leading_zeros() - 1) as usize
1246}
1247
1248// `rebuild` takes O(len1 + len2) operations
1249// and about 2 * (len1 + len2) comparisons in the worst case
1250// while `extend` takes O(len2 * log_2(len1)) operations
1251// and about 1 * len2 * log_2(len1) comparisons in the worst case,
1252// assuming len1 >= len2.
1253fn better_to_rebuild(len1: usize, len2: usize) -> bool {
1254 // log(1) == 0, so the inequation always falsy
1255 // log(0) is inapplicable and produces panic
1256 if len1 <= 1 {
1257 return false;
1258 }
1259
1260 2 * (len1 + len2) < len2 * log2_fast(len1)
1261}
1262
1263#[cfg(feature = "serde")]
1264#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1265mod serde {
1266 use std::cmp::{Eq, Ord};
1267 use std::hash::{BuildHasher, Hash};
1268
1269 use serde::de::{Deserialize, Deserializer};
1270 use serde::ser::{Serialize, Serializer};
1271
1272 use super::DoublePriorityQueue;
1273 use crate::store::Store;
1274
1275 impl<I, P, H> Serialize for DoublePriorityQueue<I, P, H>
1276 where
1277 I: Hash + Eq + Serialize,
1278 P: Ord + Serialize,
1279 H: BuildHasher,
1280 {
1281 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1282 where
1283 S: Serializer,
1284 {
1285 self.store.serialize(serializer)
1286 }
1287 }
1288
1289 impl<'de, I, P, H> Deserialize<'de> for DoublePriorityQueue<I, P, H>
1290 where
1291 I: Hash + Eq + Deserialize<'de>,
1292 P: Ord + Deserialize<'de>,
1293 H: BuildHasher + Default,
1294 {
1295 fn deserialize<D>(deserializer: D) -> Result<DoublePriorityQueue<I, P, H>, D::Error>
1296 where
1297 D: Deserializer<'de>,
1298 {
1299 Store::deserialize(deserializer).map(|store| {
1300 let mut pq = DoublePriorityQueue { store };
1301 pq.heap_build();
1302 pq
1303 })
1304 }
1305 }
1306}