1//! This module contains the parallel iterator types for double-ended queues
2//! (`VecDeque<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::VecDeque;
6use std::ops::{Range, RangeBounds};
7
8use crate::iter::plumbing::*;
9use crate::iter::*;
10use crate::math::simplify_range;
11
12use crate::slice;
13use crate::vec;
14
15/// Parallel iterator over a double-ended queue
16#[derive(Debug, Clone)]
17pub struct IntoIter<T: Send> {
18 inner: vec::IntoIter<T>,
19}
20
21impl<T: Send> IntoParallelIterator for VecDeque<T> {
22 type Item = T;
23 type Iter = IntoIter<T>;
24
25 fn into_par_iter(self) -> Self::Iter {
26 // NOTE: requires data movement if the deque doesn't start at offset 0.
27 let inner: IntoIter = Vec::from(self).into_par_iter();
28 IntoIter { inner }
29 }
30}
31
32delegate_indexed_iterator! {
33 IntoIter<T> => T,
34 impl<T: Send>
35}
36
37/// Parallel iterator over an immutable reference to a double-ended queue
38#[derive(Debug)]
39pub struct Iter<'a, T: Sync> {
40 inner: Chain<slice::Iter<'a, T>, slice::Iter<'a, T>>,
41}
42
43impl<'a, T: Sync> Clone for Iter<'a, T> {
44 fn clone(&self) -> Self {
45 Iter {
46 inner: self.inner.clone(),
47 }
48 }
49}
50
51impl<'a, T: Sync> IntoParallelIterator for &'a VecDeque<T> {
52 type Item = &'a T;
53 type Iter = Iter<'a, T>;
54
55 fn into_par_iter(self) -> Self::Iter {
56 let (a: &[T], b: &[T]) = self.as_slices();
57 Iter {
58 inner: a.into_par_iter().chain(b),
59 }
60 }
61}
62
63delegate_indexed_iterator! {
64 Iter<'a, T> => &'a T,
65 impl<'a, T: Sync + 'a>
66}
67
68/// Parallel iterator over a mutable reference to a double-ended queue
69#[derive(Debug)]
70pub struct IterMut<'a, T: Send> {
71 inner: Chain<slice::IterMut<'a, T>, slice::IterMut<'a, T>>,
72}
73
74impl<'a, T: Send> IntoParallelIterator for &'a mut VecDeque<T> {
75 type Item = &'a mut T;
76 type Iter = IterMut<'a, T>;
77
78 fn into_par_iter(self) -> Self::Iter {
79 let (a: &mut [T], b: &mut [T]) = self.as_mut_slices();
80 IterMut {
81 inner: a.into_par_iter().chain(b),
82 }
83 }
84}
85
86delegate_indexed_iterator! {
87 IterMut<'a, T> => &'a mut T,
88 impl<'a, T: Send + 'a>
89}
90
91/// Draining parallel iterator that moves a range out of a double-ended queue,
92/// but keeps the total capacity.
93#[derive(Debug)]
94pub struct Drain<'a, T: Send> {
95 deque: &'a mut VecDeque<T>,
96 range: Range<usize>,
97 orig_len: usize,
98}
99
100impl<'a, T: Send> ParallelDrainRange<usize> for &'a mut VecDeque<T> {
101 type Iter = Drain<'a, T>;
102 type Item = T;
103
104 fn par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter {
105 Drain {
106 orig_len: self.len(),
107 range: simplify_range(range, self.len()),
108 deque: self,
109 }
110 }
111}
112
113impl<'a, T: Send> ParallelIterator for Drain<'a, T> {
114 type Item = T;
115
116 fn drive_unindexed<C>(self, consumer: C) -> C::Result
117 where
118 C: UnindexedConsumer<Self::Item>,
119 {
120 bridge(self, consumer)
121 }
122
123 fn opt_len(&self) -> Option<usize> {
124 Some(self.len())
125 }
126}
127
128impl<'a, T: Send> IndexedParallelIterator for Drain<'a, T> {
129 fn drive<C>(self, consumer: C) -> C::Result
130 where
131 C: Consumer<Self::Item>,
132 {
133 bridge(self, consumer)
134 }
135
136 fn len(&self) -> usize {
137 self.range.len()
138 }
139
140 fn with_producer<CB>(self, callback: CB) -> CB::Output
141 where
142 CB: ProducerCallback<Self::Item>,
143 {
144 // NOTE: requires data movement if the deque doesn't start at offset 0.
145 superDrain<'_, T>::DrainGuard::new(self.deque)
146 .par_drain(self.range.clone())
147 .with_producer(callback)
148 }
149}
150
151impl<'a, T: Send> Drop for Drain<'a, T> {
152 fn drop(&mut self) {
153 if self.deque.len() != self.orig_len - self.range.len() {
154 // We must not have produced, so just call a normal drain to remove the items.
155 assert_eq!(self.deque.len(), self.orig_len);
156 self.deque.drain(self.range.clone());
157 }
158 }
159}
160