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