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::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}
rayon/collections/binary_heap.rs

rayon/collections/
binary_heap.rs
