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 opinion) under the terms 9 * of the Mozilla Public License version 2.0. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public License 17 * along with this program. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 //! This module defines iterator types that are used only with the [`DoublePriorityQueue`] 21 //! 22 //! Usually you don't need to explicitly `use` any of the types declared here. 23 24 #[cfg(not(has_std))] 25 pub(crate) mod std { 26 pub use core::*; 27 pub mod alloc { 28 pub use ::alloc::*; 29 } 30 pub mod collections { 31 pub use ::alloc::collections::*; 32 } 33 pub use ::alloc::vec; 34 } 35 36 use std::cmp::{Eq, Ord}; 37 #[cfg(has_std)] 38 use std::collections::hash_map::RandomState; 39 use std::hash::Hash; 40 use std::iter::*; 41 42 use crate::DoublePriorityQueue; 43 44 /// A mutable iterator over the couples `(item, priority)` of the `DoublePriorityQueue` 45 /// in arbitrary order. 46 /// 47 /// It can be obtained calling the `iter_mut` method. 48 /// 49 /// It can be used to update the priorities of the elements in the queue. 50 /// When the iterator goes out of scope, the heap is rebuilt to restore the 51 /// structural properties. 52 /// 53 /// The item is mutable too, but it is a logical error to modify it in a way that 54 /// changes the result of any of `hash` or `eq`. 55 #[cfg(has_std)] 56 pub struct IterMut<'a, I: 'a, P: 'a, H: 'a = RandomState> 57 where 58 I: Hash + Eq, 59 P: Ord, 60 { 61 pq: &'a mut DoublePriorityQueue<I, P, H>, 62 pos: usize, 63 } 64 65 #[cfg(not(has_std))] 66 pub struct IterMut<'a, I: 'a, P: 'a, H: 'a> 67 where 68 I: Hash + Eq, 69 P: Ord, 70 { 71 pq: &'a mut DoublePriorityQueue<I, P, H>, 72 pos: usize, 73 } 74 75 impl<'a, I: 'a, P: 'a, H: 'a> IterMut<'a, I, P, H> 76 where 77 I: Hash + Eq, 78 P: Ord, 79 { 80 pub(crate) fn new(pq: &'a mut DoublePriorityQueue<I, P, H>) -> Self { 81 IterMut { pq, pos: 0 } 82 } 83 } 84 85 impl<'a, 'b: 'a, I: 'a, P: 'a, H: 'a> Iterator for IterMut<'a, I, P, H> 86 where 87 I: Hash + Eq, 88 P: Ord, 89 { 90 type Item = (&'a mut I, &'a mut P); 91 fn next(&mut self) -> Option<Self::Item> { 92 let r: Option<(&'a mut I, &'a mut P)> = self 93 .pq 94 .store 95 .map 96 .get_index_mut(self.pos) 97 .map(|(i, p)| (i as *mut I, p as *mut P)) 98 .map(|(i, p)| unsafe { (i.as_mut().unwrap(), p.as_mut().unwrap()) }); 99 self.pos += 1; 100 r 101 } 102 } 103 104 impl<'a, I: 'a, P: 'a, H: 'a> Drop for IterMut<'a, I, P, H> 105 where 106 I: Hash + Eq, 107 P: Ord, 108 { 109 fn drop(&mut self) { 110 self.pq.heap_build(); 111 } 112 } 113 114 /// A consuming iterator over the couples `(item, priority)` of the `PriorityQueue` 115 /// ordered by priority, from the lowest to the highest. 116 /// 117 /// It can be obtained calling the `into_sorted_iter` method. 118 /// 119 /// Since it implements [`DoubleEndedIterator`], this iterator can be reversed at any time 120 /// calling `rev`, at which point, elements will be extracted from the one with maximum priority 121 /// to the one with minimum priority. 122 #[cfg(has_std)] 123 pub struct IntoSortedIter<I, P, H = RandomState> 124 where 125 I: Hash + Eq, 126 P: Ord, 127 { 128 pub(crate) pq: DoublePriorityQueue<I, P, H>, 129 } 130 131 #[cfg(not(has_std))] 132 pub struct IntoSortedIter<I, P, H> 133 where 134 I: Hash + Eq, 135 P: Ord, 136 { 137 pub(crate) pq: DoublePriorityQueue<I, P, H>, 138 } 139 140 impl<I, P, H> Iterator for IntoSortedIter<I, P, H> 141 where 142 I: Hash + Eq, 143 P: Ord, 144 { 145 type Item = (I, P); 146 fn next(&mut self) -> Option<(I, P)> { 147 self.pq.pop_min() 148 } 149 } 150 151 impl<I, P, H> DoubleEndedIterator for IntoSortedIter<I, P, H> 152 where 153 I: Hash + Eq, 154 P: Ord, 155 { 156 fn next_back(&mut self) -> Option<(I, P)> { 157 self.pq.pop_max() 158 } 159 } 160