par_iter/collections/
binary_heap.rs

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::{
8    iter::{plumbing::*, *},
9    vec,
10};
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    // TODO (MSRV 1.80): this could use `slice::Iter` built from
38    // `BinaryHeap::as_slice`, rather than using a temp `Vec<&T>`.
39    inner: vec::IntoIter<&'a T>,
40}
41
42impl<'a, T: Ord + Sync> Clone for Iter<'a, T> {
43    fn clone(&self) -> Self {
44        Iter {
45            inner: self.inner.clone(),
46        }
47    }
48}
49
50into_par_vec! {
51    &'a BinaryHeap<T> => Iter<'a, T>,
52    impl<'a, T: Ord + Sync>
53}
54
55delegate_indexed_iterator! {
56    Iter<'a, T> => &'a T,
57    impl<'a, T: Ord + Sync + 'a>
58}
59
60// `BinaryHeap` doesn't have a mutable `Iterator`
61
62/// Draining parallel iterator that moves out of a binary heap,
63/// but keeps the total capacity.
64#[derive(Debug)]
65pub struct Drain<'a, T: Ord + Send> {
66    heap: &'a mut BinaryHeap<T>,
67}
68
69impl<'a, T: Ord + Send> ParallelDrainFull for &'a mut BinaryHeap<T> {
70    type Item = T;
71    type Iter = Drain<'a, T>;
72
73    fn par_drain(self) -> Self::Iter {
74        Drain { heap: self }
75    }
76}
77
78impl<'a, T: Ord + Send> ParallelIterator for Drain<'a, T> {
79    type Item = T;
80
81    fn drive_unindexed<C>(self, consumer: C) -> C::Result
82    where
83        C: UnindexedConsumer<Self::Item>,
84    {
85        bridge(self, consumer)
86    }
87
88    fn opt_len(&self) -> Option<usize> {
89        Some(self.len())
90    }
91}
92
93impl<'a, T: Ord + Send> IndexedParallelIterator for Drain<'a, T> {
94    fn drive<C>(self, consumer: C) -> C::Result
95    where
96        C: Consumer<Self::Item>,
97    {
98        bridge(self, consumer)
99    }
100
101    fn len(&self) -> usize {
102        self.heap.len()
103    }
104
105    fn with_producer<CB>(self, callback: CB) -> CB::Output
106    where
107        CB: ProducerCallback<Self::Item>,
108    {
109        super::DrainGuard::new(self.heap)
110            .par_drain(..)
111            .with_producer(callback)
112    }
113}
114
115impl<'a, T: Ord + Send> Drop for Drain<'a, T> {
116    fn drop(&mut self) {
117        if !self.heap.is_empty() {
118            // We must not have produced, so just call a normal drain to remove the items.
119            self.heap.drain();
120        }
121    }
122}
par_iter/collections/binary_heap.rs

par_iter/collections/
binary_heap.rs
