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 [`PriorityQueue`]. 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::PriorityQueue; 43 44 /// A mutable iterator over the couples `(item, priority)` of the `PriorityQueue` 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 PriorityQueue<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 PriorityQueue<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 PriorityQueue<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 highest to the lowest. 116 /// 117 /// It can be obtained calling the `into_sorted_iter` method. 118 #[cfg(has_std)] 119 pub struct IntoSortedIter<I, P, H = RandomState> 120 where 121 I: Hash + Eq, 122 P: Ord, 123 { 124 pub(crate) pq: PriorityQueue<I, P, H>, 125 } 126 127 #[cfg(not(has_std))] 128 pub struct IntoSortedIter<I, P, H> 129 where 130 I: Hash + Eq, 131 P: Ord, 132 { 133 pub(crate) pq: PriorityQueue<I, P, H>, 134 } 135 136 impl<I, P, H> Iterator for IntoSortedIter<I, P, H> 137 where 138 I: Hash + Eq, 139 P: Ord, 140 { 141 type Item = (I, P); 142 fn next(&mut self) -> Option<(I, P)> { 143 self.pq.pop() 144 } 145 } 146