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