rayon/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::iter::plumbing::*;
8use crate::iter::*;
9
10use crate::slice;
11use crate::vec;
12
13/// Parallel iterator over a binary heap
14#[derive(Debug, Clone)]
15pub struct IntoIter<T> {
16    inner: vec::IntoIter<T>,
17}
18
19impl<T: Send> IntoParallelIterator for BinaryHeap<T> {
20    type Item = T;
21    type Iter = IntoIter<T>;
22
23    fn into_par_iter(self) -> Self::Iter {
24        IntoIter {
25            inner: Vec::from(self).into_par_iter(),
26        }
27    }
28}
29
30delegate_indexed_iterator! {
31    IntoIter<T> => T,
32    impl<T: Send>
33}
34
35/// Parallel iterator over an immutable reference to a binary heap
36#[derive(Debug)]
37pub struct Iter<'a, T> {
38    inner: slice::Iter<'a, T>,
39}
40
41impl<T> Clone for Iter<'_, T> {
42    fn clone(&self) -> Self {
43        Iter {
44            inner: self.inner.clone(),
45        }
46    }
47}
48
49impl<'a, T: Sync> IntoParallelIterator for &'a BinaryHeap<T> {
50    type Item = &'a T;
51    type Iter = Iter<'a, T>;
52
53    fn into_par_iter(self) -> Self::Iter {
54        Iter {
55            inner: self.as_slice().into_par_iter(),
56        }
57    }
58}
59
60delegate_indexed_iterator! {
61    Iter<'a, T> => &'a T,
62    impl<'a, T: Sync + 'a>
63}
64
65// `BinaryHeap` doesn't have a mutable `Iterator`
66
67/// Draining parallel iterator that moves out of a binary heap,
68/// but keeps the total capacity.
69#[derive(Debug)]
70pub struct Drain<'a, T> {
71    heap: &'a mut BinaryHeap<T>,
72}
73
74// NB: The only reason we require `T: Ord` is for `DrainGuard` to reconstruct
75// the heap `From<Vec<T>>` afterward, even though that will actually be empty.
76impl<'a, T: Ord + Send> ParallelDrainFull for &'a mut BinaryHeap<T> {
77    type Iter = Drain<'a, T>;
78    type Item = T;
79
80    fn par_drain(self) -> Self::Iter {
81        Drain { heap: self }
82    }
83}
84
85impl<T: Ord + Send> ParallelIterator for Drain<'_, T> {
86    type Item = T;
87
88    fn drive_unindexed<C>(self, consumer: C) -> C::Result
89    where
90        C: UnindexedConsumer<Self::Item>,
91    {
92        bridge(self, consumer)
93    }
94
95    fn opt_len(&self) -> Option<usize> {
96        Some(self.len())
97    }
98}
99
100impl<T: Ord + Send> IndexedParallelIterator for Drain<'_, T> {
101    fn drive<C>(self, consumer: C) -> C::Result
102    where
103        C: Consumer<Self::Item>,
104    {
105        bridge(self, consumer)
106    }
107
108    fn len(&self) -> usize {
109        self.heap.len()
110    }
111
112    fn with_producer<CB>(self, callback: CB) -> CB::Output
113    where
114        CB: ProducerCallback<Self::Item>,
115    {
116        super::DrainGuard::new(self.heap)
117            .par_drain(..)
118            .with_producer(callback)
119    }
120}
121
122impl<T> Drop for Drain<'_, T> {
123    fn drop(&mut self) {
124        if !self.heap.is_empty() {
125            // We must not have produced, so just call a normal drain to remove the items.
126            self.heap.drain();
127        }
128    }
129}
rayon/collections/binary_heap.rs

rayon/collections/
binary_heap.rs
