1use either::Either::{self, Left, Right};
2use std::cell::RefCell;
3use std::collections::VecDeque;
4use std::rc::Rc;
5use std::sync::Arc;
6pub use parking_lot::RwLock;
7
8pub enum NonAtomic {}
9
10pub enum Atomic {}
11
12pub trait Sharing<T: ?Sized> {
13 type Shared: Clone;
14 fn create(v: T) -> Self::Shared where T: Sized;
15 fn modify<R, F>(this: &Self::Shared, f: F) -> R where F: FnMut(&mut T) -> R;
16 fn inspect<R, F>(this: &Self::Shared, f: F) -> R where F: FnMut(&T) -> R;
17}
18
19impl<T: ?Sized> Sharing<T> for NonAtomic {
20 type Shared = Rc<RefCell<T>>;
21
22 fn create(v: T) -> Rc<RefCell<T>>
23 where T: Sized
24 {
25 Rc::new(RefCell::new(v))
26 }
27
28 fn modify<R, F>(this: &Rc<RefCell<T>>, f: F) -> R
29 where F: FnOnce(&mut T) -> R
30 {
31 f(&mut this.borrow_mut())
32 }
33
34 fn inspect<R, F>(this: &Rc<RefCell<T>>, f: F) -> R
35 where F: FnOnce(&T) -> R
36 {
37 f(&this.borrow())
38 }
39}
40
41impl<T: ?Sized> Sharing<T> for Atomic {
42 type Shared = Arc<RwLock<T>>;
43
44 fn create(v: T) -> Arc<RwLock<T>>
45 where T: Sized
46 {
47 Arc::new(RwLock::new(v))
48 }
49
50 fn modify<R, F>(this: &Arc<RwLock<T>>, f: F) -> R
51 where F: FnOnce(&mut T) -> R
52 {
53 f(&mut this.write())
54 }
55
56 fn inspect<R, F>(this: &Arc<RwLock<T>>, f: F) -> R
57 where F: FnOnce(&T) -> R
58 {
59 f(&this.read())
60 }
61}
62
63pub struct SplitEitherImpl<A, B, I: ?Sized> {
64 left: VecDeque<A>,
65 right: VecDeque<B>,
66 left_back: VecDeque<A>,
67 right_back: VecDeque<B>,
68 inner: I,
69}
70
71pub struct SplitEitherLeft<A, B, I: ?Sized, S: ?Sized = NonAtomic>(
72 <S as Sharing<SplitEitherImpl<A, B, I>>>::Shared)
73 where S: Sharing<SplitEitherImpl<A, B, I>>;
74
75pub struct SplitEitherRight<A, B, I: ?Sized, S: ?Sized = NonAtomic>(
76 <S as Sharing<SplitEitherImpl<A, B, I>>>::Shared)
77 where S: Sharing<SplitEitherImpl<A, B, I>>;
78
79pub fn split_either<A, B, I, S: ?Sized>
80 (inner: I)
81 -> (SplitEitherLeft<A, B, I::IntoIter, S>, SplitEitherRight<A, B, I::IntoIter, S>)
82 where I: IntoIterator<Item = Either<A, B>>,
83 S: Sharing<SplitEitherImpl<A, B, I::IntoIter>>
84{
85 let shared_left = <S as Sharing<SplitEitherImpl<A, B, I::IntoIter>>>::create(SplitEitherImpl {
86 left: VecDeque::new(),
87 right: VecDeque::new(),
88 left_back: VecDeque::new(),
89 right_back: VecDeque::new(),
90 inner: inner.into_iter(),
91 });
92 let shared_right = shared_left.clone();
93 (SplitEitherLeft(shared_left), SplitEitherRight(shared_right))
94}
95
96impl<A, B, I: ?Sized, S: ?Sized> Iterator for SplitEitherLeft<A, B, I, S>
97 where I: Iterator<Item = Either<A, B>>,
98 S: Sharing<SplitEitherImpl<A, B, I>>
99{
100 type Item = A;
101
102 fn next(&mut self) -> Option<A> {
103 <S as Sharing<SplitEitherImpl<A, B, I>>>::modify(&self.0, |this| {
104 if let Some(val) = this.left.pop_front() {
105 return Some(val);
106 }
107 while let Some(val_or_other) = this.inner.next() {
108 match val_or_other {
109 Left(val) => return Some(val),
110 Right(other) => this.right.push_back(other),
111 }
112 }
113 this.left_back.pop_back()
114 })
115 }
116
117 fn size_hint(&self) -> (usize, Option<usize>) {
118 <S as Sharing<SplitEitherImpl<A, B, I>>>::inspect(&self.0, |this| {
119 let mut low = 0usize;
120 let mut high_opt = this.inner.size_hint().1;
121 let front_extra = this.left.len();
122 let back_extra = this.left.len();
123 low = low.saturating_add(front_extra);
124 high_opt = high_opt.map(|high| high.saturating_add(front_extra));
125 low = low.saturating_add(back_extra);
126 high_opt = high_opt.map(|high| high.saturating_add(back_extra));
127 (low, high_opt)
128 })
129 }
130}
131
132impl<A, B, I: ?Sized, S: ?Sized> DoubleEndedIterator for SplitEitherLeft<A, B, I, S>
133 where I: DoubleEndedIterator<Item = Either<A, B>>,
134 S: Sharing<SplitEitherImpl<A, B, I>>
135{
136 fn next_back(&mut self) -> Option<A> {
137 <S as Sharing<SplitEitherImpl<A, B, I>>>::modify(&self.0, |this| {
138 if let Some(val) = this.left_back.pop_front() {
139 return Some(val);
140 }
141 while let Some(val_or_other) = this.inner.next() {
142 match val_or_other {
143 Left(val) => return Some(val),
144 Right(other) => this.right_back.push_back(other),
145 }
146 }
147 this.left.pop_back()
148 })
149 }
150}
151
152impl<A, B, I: ?Sized, S: ?Sized> Iterator for SplitEitherRight<A, B, I, S>
153 where I: Iterator<Item = Either<A, B>>,
154 S: Sharing<SplitEitherImpl<A, B, I>>
155{
156 type Item = B;
157
158 fn next(&mut self) -> Option<B> {
159 <S as Sharing<SplitEitherImpl<A, B, I>>>::modify(&self.0, |this| {
160 if let Some(val) = this.right.pop_front() {
161 return Some(val);
162 }
163 while let Some(val_or_other) = this.inner.next() {
164 match val_or_other {
165 Right(val) => return Some(val),
166 Left(other) => this.left.push_back(other),
167 }
168 }
169 this.right_back.pop_back()
170 })
171 }
172
173 fn size_hint(&self) -> (usize, Option<usize>) {
174 <S as Sharing<SplitEitherImpl<A, B, I>>>::inspect(&self.0, |this| {
175 let mut low = 0usize;
176 let mut high_opt = this.inner.size_hint().1;
177 let front_extra = this.right.len();
178 let back_extra = this.right.len();
179 low = low.saturating_add(front_extra);
180 high_opt = high_opt.map(|high| high.saturating_add(front_extra));
181 low = low.saturating_add(back_extra);
182 high_opt = high_opt.map(|high| high.saturating_add(back_extra));
183 (low, high_opt)
184 })
185 }
186}
187
188impl<A, B, I: ?Sized, S: ?Sized> DoubleEndedIterator for SplitEitherRight<A, B, I, S>
189 where I: DoubleEndedIterator<Item = Either<A, B>>,
190 S: Sharing<SplitEitherImpl<A, B, I>>
191{
192 fn next_back(&mut self) -> Option<B> {
193 <S as Sharing<SplitEitherImpl<A, B, I>>>::modify(&self.0, |this| {
194 if let Some(val) = this.right_back.pop_front() {
195 return Some(val);
196 }
197 while let Some(val_or_other) = this.inner.next() {
198 match val_or_other {
199 Right(val) => return Some(val),
200 Left(other) => this.left_back.push_back(other),
201 }
202 }
203 this.right.pop_back()
204 })
205 }
206}