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
5use std::collections::BinaryHeap;
6
7use crate::iter::plumbing::*;
8use crate::iter::*;
9
10use crate::vec;
11
12/// Parallel iterator over a binary heap
13#[derive(Debug, Clone)]
14pub struct IntoIter<T: Ord + Send> {
15 inner: vec::IntoIter<T>,
16}
17
18impl<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
29delegate_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)]
36pub struct Iter<'a, T: Ord + Sync> {
37 inner: vec::IntoIter<&'a T>,
38}
39
40impl<'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
48into_par_vec! {
49 &'a BinaryHeap<T> => Iter<'a, T>,
50 impl<'a, T: Ord + Sync>
51}
52
53delegate_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)]
63pub struct Drain<'a, T: Ord + Send> {
64 heap: &'a mut BinaryHeap<T>,
65}
66
67impl<'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
76impl<'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
91impl<'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
113impl<'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