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