1 //! This module contains the parallel iterator types for heaps 2 //! (`BinaryHeap<T>`). You will rarely need to interact with it directly 3 //! unless you have need to name one of the iterator types. 4 5 use std::collections::BinaryHeap; 6 7 use crate::iter::plumbing::*; 8 use crate::iter::*; 9 10 use crate::vec; 11 12 /// Parallel iterator over a binary heap 13 #[derive(Debug, Clone)] 14 pub struct IntoIter<T: Ord + Send> { 15 inner: vec::IntoIter<T>, 16 } 17 18 impl<T: Ord + Send> IntoParallelIterator for BinaryHeap<T> { 19 type Item = T; 20 type Iter = IntoIter<T>; 21 into_par_iter(self) -> Self::Iter22 fn into_par_iter(self) -> Self::Iter { 23 IntoIter { 24 inner: Vec::from(self).into_par_iter(), 25 } 26 } 27 } 28 29 delegate_indexed_iterator! { 30 IntoIter<T> => T, 31 impl<T: Ord + Send> 32 } 33 34 /// Parallel iterator over an immutable reference to a binary heap 35 #[derive(Debug)] 36 pub struct Iter<'a, T: Ord + Sync> { 37 inner: vec::IntoIter<&'a T>, 38 } 39 40 impl<'a, T: Ord + Sync> Clone for Iter<'a, T> { clone(&self) -> Self41 fn clone(&self) -> Self { 42 Iter { 43 inner: self.inner.clone(), 44 } 45 } 46 } 47 48 into_par_vec! { 49 &'a BinaryHeap<T> => Iter<'a, T>, 50 impl<'a, T: Ord + Sync> 51 } 52 53 delegate_indexed_iterator! { 54 Iter<'a, T> => &'a T, 55 impl<'a, T: Ord + Sync + 'a> 56 } 57 58 // `BinaryHeap` doesn't have a mutable `Iterator` 59 60 /// Draining parallel iterator that moves out of a binary heap, 61 /// but keeps the total capacity. 62 #[derive(Debug)] 63 pub struct Drain<'a, T: Ord + Send> { 64 heap: &'a mut BinaryHeap<T>, 65 } 66 67 impl<'a, T: Ord + Send> ParallelDrainFull for &'a mut BinaryHeap<T> { 68 type Iter = Drain<'a, T>; 69 type Item = T; 70 par_drain(self) -> Self::Iter71 fn par_drain(self) -> Self::Iter { 72 Drain { heap: self } 73 } 74 } 75 76 impl<'a, T: Ord + Send> ParallelIterator for Drain<'a, T> { 77 type Item = T; 78 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,79 fn drive_unindexed<C>(self, consumer: C) -> C::Result 80 where 81 C: UnindexedConsumer<Self::Item>, 82 { 83 bridge(self, consumer) 84 } 85 opt_len(&self) -> Option<usize>86 fn opt_len(&self) -> Option<usize> { 87 Some(self.len()) 88 } 89 } 90 91 impl<'a, T: Ord + Send> IndexedParallelIterator for Drain<'a, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,92 fn drive<C>(self, consumer: C) -> C::Result 93 where 94 C: Consumer<Self::Item>, 95 { 96 bridge(self, consumer) 97 } 98 len(&self) -> usize99 fn len(&self) -> usize { 100 self.heap.len() 101 } 102 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,103 fn with_producer<CB>(self, callback: CB) -> CB::Output 104 where 105 CB: ProducerCallback<Self::Item>, 106 { 107 super::DrainGuard::new(self.heap) 108 .par_drain(..) 109 .with_producer(callback) 110 } 111 } 112 113 impl<'a, T: Ord + Send> Drop for Drain<'a, T> { drop(&mut self)114 fn drop(&mut self) { 115 if !self.heap.is_empty() { 116 // We must not have produced, so just call a normal drain to remove the items. 117 self.heap.drain(); 118 } 119 } 120 } 121