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 | |
22 | 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> { |
41 | 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 | |
71 | 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 | |
79 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
80 | where |
81 | C: UnindexedConsumer<Self::Item>, |
82 | { |
83 | bridge(self, consumer) |
84 | } |
85 | |
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> { |
92 | fn drive<C>(self, consumer: C) -> C::Result |
93 | where |
94 | C: Consumer<Self::Item>, |
95 | { |
96 | bridge(self, consumer) |
97 | } |
98 | |
99 | fn len(&self) -> usize { |
100 | self.heap.len() |
101 | } |
102 | |
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> { |
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 | |