priority_queue/double_priority_queue/
mod.rs

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