backtracking_iterator/
concurrent.rs1use super::{BacktrackingState, BacktrackingIterator};
23
24use std::sync::{Arc, RwLock, Mutex};
25
26static EXPECT_RW: &'static str = "The read-write lock on the history has been poisoned by a thread panic!";
27static EXPECT_MUTEX: &'static str = "The mutual exclusion lock on the iterator has been poisoned by a thread panic!";
28
29
30impl<'item, Iter> From<Iter> for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
31 fn from(iterator: Iter) -> Self {
33 ConcurrentReferencingBacktrackingIterator {
34 item_marker: std::marker::PhantomData,
35 iterator: Arc::new(Mutex::new(iterator)),
36 backtracking_vec: Arc::new(RwLock::new(vec![])),
37 position: 0,
38 }
39 }
40}
41
42pub struct ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
43 item_marker: std::marker::PhantomData<&'item Iter::Item>,
44 iterator: Arc<Mutex<Iter>>,
45 backtracking_vec: Arc<RwLock<Vec<Iter::Item>>>,
46 position: usize,
47}
48
49impl<'item, Iter> Clone for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
50 fn clone(&self) -> Self {
51 ConcurrentReferencingBacktrackingIterator {
52 item_marker: std::marker::PhantomData,
53 iterator: self.iterator.clone(),
54 backtracking_vec: self.backtracking_vec.clone(),
55 position: self.position,
56 }
57 }
58}
59
60impl<'item, Iter> Iterator for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
61 type Item = &'item Iter::Item;
62
63 fn next(&mut self) -> Option<&'item Iter::Item> {
64 macro_rules! unsafe_backtracking_index {
65 ($index:expr) => {
66 unsafe {
67 &*(&self.backtracking_vec.read().expect(EXPECT_RW)[$index] as *const Iter::Item)
68 }
69 };
70 }
71
72 use crate::{Backtracking, Progressing};
73 if self.position >= self.backtracking_vec.read().expect(EXPECT_RW).len() {
74 if let Some(val) = self.iterator.lock().expect(EXPECT_MUTEX).next() {
75 self.backtracking_vec.write().expect(EXPECT_RW).push(val);
76 self.position = self.position + 1;
77 Some(unsafe_backtracking_index!(self.backtracking_vec.read().expect(EXPECT_RW).len() - 1))
78 } else {
79 None
80 }
81 } else {
82 let old_position = self.position;
83 self.position = self.position + 1;
84 Some(unsafe_backtracking_index!(old_position))
85 }
86 }
87}
88
89impl<'item, Iter> BacktrackingIterator for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
90 type RefPoint = usize;
91
92 fn get_ref_point(&self) -> usize {
93 self.position
94 }
95
96 fn get_oldest_point(&self) -> usize {
97 0_usize
99 }
100
101 fn backtrack(&mut self, position: usize) {
102 self.position = position;
103 }
104}
105
106impl<Iter> From<Iter> for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
109 fn from(iterator: Iter) -> Self {
111 ConcurrentCopyingBacktrackingIterator {
112 iterator: Arc::new(Mutex::new(iterator)),
113 backtracking_vec: Arc::new(RwLock::new(vec![])),
114 position: 0,
115 }
116 }
117}
118
119pub struct ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
120 iterator: Arc<Mutex<Iter>>,
121 backtracking_vec: Arc<RwLock<Vec<Iter::Item>>>,
122 position: usize,
123}
124
125impl<Iter> Clone for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
126 fn clone(&self) -> Self {
127 ConcurrentCopyingBacktrackingIterator {
128 iterator: self.iterator.clone(),
129 backtracking_vec: self.backtracking_vec.clone(),
130 position: self.position,
131 }
132 }
133}
134
135impl<Iter> Iterator for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
136 type Item = Iter::Item;
137
138 fn next(&mut self) -> Option<Iter::Item> {
139
140 use crate::{Backtracking, Progressing};
141 if self.position >= self.backtracking_vec.read().expect(EXPECT_RW).len() {
142 if let Some(val) = self.iterator.lock().expect(EXPECT_MUTEX).next() {
143 self.backtracking_vec.write().expect(EXPECT_RW).push(val.clone());
144 self.position = self.position + 1;
145 Some(val)
146 } else {
147 None
148 }
149 } else {
150 let old_position = self.position;
151 self.position = self.position + 1;
152 Some(self.backtracking_vec.read().expect(EXPECT_RW)[old_position].clone())
153 }
154 }
155}
156
157impl<Iter> BacktrackingIterator for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
158 type RefPoint = usize;
159
160 fn get_ref_point(&self) -> usize {
161 self.position
162 }
163
164 fn get_oldest_point(&self) -> usize {
165 0_usize
167 }
168
169 fn backtrack(&mut self, position: usize) {
170 self.position = position;
171 }
172}
173
174
175#[cfg(test)]
176mod tests {
177 #[test]
178 fn many_iter_test() {
179 use matches::{matches};
180
181 let bt_con_iter = crate::concurrent::ConcurrentReferencingBacktrackingIterator::from(1..1000);
182
183 for _ in 1..3 {
184 let mut bt_iter = bt_con_iter.clone();
185 for expected in 1..1000 {
186 assert!(matches!(bt_iter.next(), Some(&i) if i == expected))
187 }
188 }
189 }
190
191 #[test]
192 fn many_iter_clone_test() {
193 use matches::{matches};
194
195 let bt_con_iter = crate::concurrent::ConcurrentCopyingBacktrackingIterator::from(1..1000);
196
197 for _ in 1..3 {
198 let mut bt_iter = bt_con_iter.clone();
199 for expected in 1..1000 {
200 assert!(matches!(bt_iter.next(), Some(i) if i == expected))
201 }
202 }
203 }
204
205 #[test]
206 fn dont_need_clone_test() {
207 use matches::{matches};
208
209 struct Uncloneable {};
210 let uncloneables = vec![Uncloneable {}];
211 let mut bt_con_iter = crate::concurrent::ConcurrentReferencingBacktrackingIterator::from(uncloneables.into_iter());
212
213 assert!(matches!(bt_con_iter.next(), Some(&Uncloneable {})))
214 }
215}
216