priority_queue/double_priority_queue/
iterators.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 defines iterator types that are used only with the [`DoublePriorityQueue`]
29//!
30//! Usually you don't need to explicitly `use` any of the types declared here.
31
32#[cfg(not(feature = "std"))]
33use crate::core_iterators::std;
34
35use core::hash::BuildHasher;
36use std::cmp::Ord;
37#[cfg(feature = "std")]
38use std::collections::hash_map::RandomState;
39use std::iter::*;
40
41use crate::DoublePriorityQueue;
42
43use super::Index;
44
45/// An `Iterator` in arbitrary order which uses a `predicate` to determine if
46/// an element should be removed from the `DoublePriorityQueue`.
47///
48/// It can be obtained calling the [`extract_if`](DoublePriorityQueue::extract_if) method.
49///
50/// The `predicate` has mutable access to the `(item, priority)` pairs.
51///
52/// It can update the priorities of the elements in the queue and the items
53/// in a way that does not change the result of any of `hash` or `eq`.
54///
55/// When the iterator goes out of scope, the heap is rebuilt to restore the
56/// structural properties.
57#[cfg(feature = "std")]
58pub struct ExtractIf<'a, I: 'a, P: 'a, F, H: 'a = RandomState>
59where
60    P: Ord,
61{
62    pq: &'a mut DoublePriorityQueue<I, P, H>,
63    predicate: F,
64    idx: Index,
65}
66
67#[cfg(not(feature = "std"))]
68pub struct ExtractIf<'a, I: 'a, P: 'a, F, H: 'a>
69where
70    P: Ord,
71{
72    pq: &'a mut DoublePriorityQueue<I, P, H>,
73    predicate: F,
74    idx: Index,
75}
76
77impl<'a, I: 'a, P: 'a, F, H: 'a> ExtractIf<'a, I, P, F, H>
78where
79    P: Ord,
80{
81    pub(crate) fn new(pq: &'a mut DoublePriorityQueue<I, P, H>, predicate: F) -> Self {
82        ExtractIf {
83            pq,
84            predicate,
85            idx: Index(0),
86        }
87    }
88}
89
90impl<'a, I: 'a, P: 'a, F, H: 'a> Iterator for ExtractIf<'a, I, P, F, H>
91where
92    P: Ord,
93    F: FnMut(&mut I, &mut P) -> bool,
94    H: BuildHasher,
95{
96    type Item = (I, P);
97    fn next(&mut self) -> Option<Self::Item> {
98        use indexmap::map::MutableKeys;
99
100        loop {
101            let r: Option<bool> = self
102                .pq
103                .store
104                .map
105                .get_index_mut2(self.idx.0)
106                .map(|(i, p)| (self.predicate)(i, p));
107
108            match r {
109                Some(true) => return self.pq.store.swap_remove_index(self.idx),
110                Some(false) => self.idx.0 += 1,
111                None => return None,
112            }
113        }
114    }
115}
116
117impl<'a, I: 'a, P: 'a, F, H: 'a> Drop for ExtractIf<'a, I, P, F, H>
118where
119    P: Ord,
120{
121    fn drop(&mut self) {
122        self.pq.heap_build();
123    }
124}
125
126/// A mutable iterator over the couples `(item, priority)` of the `DoublePriorityQueue`
127/// in arbitrary order.
128///
129/// It can be obtained calling the [`iter_mut`](DoublePriorityQueue::iter_mut) method.
130///
131/// It can be used to update the priorities of the elements in the queue.
132/// When the iterator goes out of scope, the heap is rebuilt to restore the
133/// structural properties.
134///
135/// The item is mutable too, but it is a logical error to modify it in a way that
136/// changes the result of any of `hash` or `eq`.
137#[cfg(feature = "std")]
138pub struct IterMut<'a, I: 'a, P: 'a, H: 'a = RandomState>
139where
140    P: Ord,
141{
142    pq: &'a mut DoublePriorityQueue<I, P, H>,
143    pos: usize,
144}
145
146#[cfg(not(feature = "std"))]
147pub struct IterMut<'a, I: 'a, P: 'a, H: 'a>
148where
149    P: Ord,
150{
151    pq: &'a mut DoublePriorityQueue<I, P, H>,
152    pos: usize,
153}
154
155impl<'a, I: 'a, P: 'a, H: 'a> IterMut<'a, I, P, H>
156where
157    P: Ord,
158{
159    pub(crate) fn new(pq: &'a mut DoublePriorityQueue<I, P, H>) -> Self {
160        IterMut { pq, pos: 0 }
161    }
162}
163
164impl<'a, I: 'a, P: 'a, H: 'a> Iterator for IterMut<'a, I, P, H>
165where
166    P: Ord,
167    H: BuildHasher,
168{
169    type Item = (&'a mut I, &'a mut P);
170    fn next(&mut self) -> Option<Self::Item> {
171        use indexmap::map::MutableKeys;
172        let r: Option<(&'a mut I, &'a mut P)> = self
173            .pq
174            .store
175            .map
176            .get_index_mut2(self.pos)
177            .map(|(i, p)| (i as *mut I, p as *mut P))
178            .map(|(i, p)| unsafe { (i.as_mut().unwrap(), p.as_mut().unwrap()) });
179        self.pos += 1;
180        r
181    }
182}
183
184impl<'a, I: 'a, P: 'a, H: 'a> DoubleEndedIterator for IterMut<'a, I, P, H>
185where
186    P: Ord,
187    H: BuildHasher,
188{
189    fn next_back(&mut self) -> Option<Self::Item> {
190        use indexmap::map::MutableKeys;
191        let r: Option<(&'a mut I, &'a mut P)> = self
192            .pq
193            .store
194            .map
195            .get_index_mut2(self.pos)
196            .map(|(i, p)| (i as *mut I, p as *mut P))
197            .map(|(i, p)| unsafe { (i.as_mut().unwrap(), p.as_mut().unwrap()) });
198        self.pos -= 1;
199        r
200    }
201}
202
203impl<I, P, H> ExactSizeIterator for IterMut<'_, I, P, H>
204where
205    P: Ord,
206    H: BuildHasher,
207{
208    fn len(&self) -> usize {
209        self.pq.len()
210    }
211}
212
213impl<I, P, H> FusedIterator for IterMut<'_, I, P, H>
214where
215    P: Ord,
216    H: BuildHasher,
217{
218}
219
220impl<'a, I: 'a, P: 'a, H: 'a> Drop for IterMut<'a, I, P, H>
221where
222    P: Ord,
223{
224    fn drop(&mut self) {
225        self.pq.heap_build();
226    }
227}
228
229/// A consuming iterator over the couples `(item, priority)` of the `PriorityQueue`
230/// ordered by priority, from the lowest to the highest.
231///
232/// It can be obtained calling the [`into_sorted_iter`](DoublePriorityQueue::into_sorted_iter) method.
233///
234/// Since it implements [`DoubleEndedIterator`], this iterator can be reversed at any time
235/// calling `rev`, at which point, elements will be extracted from the one with maximum priority
236/// to the one with minimum priority.
237#[cfg(feature = "std")]
238pub struct IntoSortedIter<I, P, H = RandomState>
239where
240    P: Ord,
241{
242    pub(crate) pq: DoublePriorityQueue<I, P, H>,
243}
244
245#[cfg(not(feature = "std"))]
246pub struct IntoSortedIter<I, P, H>
247where
248    P: Ord,
249{
250    pub(crate) pq: DoublePriorityQueue<I, P, H>,
251}
252
253impl<I, P, H> Iterator for IntoSortedIter<I, P, H>
254where
255    P: Ord,
256{
257    type Item = (I, P);
258    fn next(&mut self) -> Option<(I, P)> {
259        self.pq.pop_min()
260    }
261}
262
263impl<I, P, H> DoubleEndedIterator for IntoSortedIter<I, P, H>
264where
265    P: Ord,
266{
267    fn next_back(&mut self) -> Option<(I, P)> {
268        self.pq.pop_max()
269    }
270}
271
272impl<I, P, H> ExactSizeIterator for IntoSortedIter<I, P, H>
273where
274    P: Ord,
275{
276    fn len(&self) -> usize {
277        self.pq.len()
278    }
279}
280
281impl<I, P, H> FusedIterator for IntoSortedIter<I, P, H> where P: Ord {}
priority_queue/double_priority_queue/iterators.rs

priority_queue/double_priority_queue/
iterators.rs
