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
43/// A mutable iterator over the couples `(item, priority)` of the `DoublePriorityQueue`
44/// in arbitrary order.
45///
46/// It can be obtained calling the [`iter_mut`](DoublePriorityQueue::iter_mut) method.
47///
48/// It can be used to update the priorities of the elements in the queue.
49/// When the iterator goes out of scope, the heap is rebuilt to restore the
50/// structural properties.
51///
52/// The item is mutable too, but it is a logical error to modify it in a way that
53/// changes the result of any of `hash` or `eq`.
54#[cfg(feature = "std")]
55pub struct IterMut<'a, I: 'a, P: 'a, H: 'a = RandomState>
56where
57    P: Ord,
58{
59    pq: &'a mut DoublePriorityQueue<I, P, H>,
60    pos: usize,
61}
62
63#[cfg(not(feature = "std"))]
64pub struct IterMut<'a, I: 'a, P: 'a, H: 'a>
65where
66    P: Ord,
67{
68    pq: &'a mut DoublePriorityQueue<I, P, H>,
69    pos: usize,
70}
71
72impl<'a, I: 'a, P: 'a, H: 'a> IterMut<'a, I, P, H>
73where
74    P: Ord,
75{
76    pub(crate) fn new(pq: &'a mut DoublePriorityQueue<I, P, H>) -> Self {
77        IterMut { pq, pos: 0 }
78    }
79}
80
81impl<'a, I: 'a, P: 'a, H: 'a> Iterator for IterMut<'a, I, P, H>
82where
83    P: Ord,
84    H: BuildHasher,
85{
86    type Item = (&'a mut I, &'a mut P);
87    fn next(&mut self) -> Option<Self::Item> {
88        use indexmap::map::MutableKeys;
89        let r: Option<(&'a mut I, &'a mut P)> = self
90            .pq
91            .store
92            .map
93            .get_index_mut2(self.pos)
94            .map(|(i, p)| (i as *mut I, p as *mut P))
95            .map(|(i, p)| unsafe { (i.as_mut().unwrap(), p.as_mut().unwrap()) });
96        self.pos += 1;
97        r
98    }
99}
100
101impl<'a, I: 'a, P: 'a, H: 'a> DoubleEndedIterator for IterMut<'a, I, P, H>
102where
103    P: Ord,
104    H: BuildHasher,
105{
106    fn next_back(&mut self) -> Option<Self::Item> {
107        use indexmap::map::MutableKeys;
108        let r: Option<(&'a mut I, &'a mut P)> = self
109            .pq
110            .store
111            .map
112            .get_index_mut2(self.pos)
113            .map(|(i, p)| (i as *mut I, p as *mut P))
114            .map(|(i, p)| unsafe { (i.as_mut().unwrap(), p.as_mut().unwrap()) });
115        self.pos -= 1;
116        r
117    }
118}
119
120impl<I, P, H> ExactSizeIterator for IterMut<'_, I, P, H>
121where
122    P: Ord,
123    H: BuildHasher,
124{
125    fn len(&self) -> usize {
126        self.pq.len()
127    }
128}
129
130impl<I, P, H> FusedIterator for IterMut<'_, I, P, H>
131where
132    P: Ord,
133    H: BuildHasher,
134{
135}
136
137impl<'a, I: 'a, P: 'a, H: 'a> Drop for IterMut<'a, I, P, H>
138where
139    P: Ord,
140{
141    fn drop(&mut self) {
142        self.pq.heap_build();
143    }
144}
145
146/// A consuming iterator over the couples `(item, priority)` of the `PriorityQueue`
147/// ordered by priority, from the lowest to the highest.
148///
149/// It can be obtained calling the [`into_sorted_iter`](DoublePriorityQueue::into_sorted_iter) method.
150///
151/// Since it implements [`DoubleEndedIterator`], this iterator can be reversed at any time
152/// calling `rev`, at which point, elements will be extracted from the one with maximum priority
153/// to the one with minimum priority.
154#[cfg(feature = "std")]
155pub struct IntoSortedIter<I, P, H = RandomState>
156where
157    P: Ord,
158{
159    pub(crate) pq: DoublePriorityQueue<I, P, H>,
160}
161
162#[cfg(not(feature = "std"))]
163pub struct IntoSortedIter<I, P, H>
164where
165    P: Ord,
166{
167    pub(crate) pq: DoublePriorityQueue<I, P, H>,
168}
169
170impl<I, P, H> Iterator for IntoSortedIter<I, P, H>
171where
172    P: Ord,
173{
174    type Item = (I, P);
175    fn next(&mut self) -> Option<(I, P)> {
176        self.pq.pop_min()
177    }
178}
179
180impl<I, P, H> DoubleEndedIterator for IntoSortedIter<I, P, H>
181where
182    P: Ord,
183{
184    fn next_back(&mut self) -> Option<(I, P)> {
185        self.pq.pop_max()
186    }
187}
188
189impl<I, P, H> ExactSizeIterator for IntoSortedIter<I, P, H>
190where
191    P: Ord,
192{
193    fn len(&self) -> usize {
194        self.pq.len()
195    }
196}
197
198impl<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
