1use std::marker::PhantomData;
2use std::fmt::Debug;
3
4use super::{SelfSubvectorFn, SelfSubvectorView, SparseVectorViewOperation, SwappableVectorViewMut, VectorFn, VectorView, VectorViewMut, VectorViewSparse};
5
6pub struct SubvectorView<V: VectorView<T>, T: ?Sized> {
7 begin: usize,
8 end: usize,
9 base: V,
10 element: PhantomData<T>
11}
12
13impl<V: Clone + VectorView<T>, T: ?Sized> Clone for SubvectorView<V, T> {
14
15 fn clone(&self) -> Self {
16 Self {
17 begin: self.begin,
18 end: self.end,
19 base: self.base.clone(),
20 element: PhantomData
21 }
22 }
23}
24
25impl<V: Copy + VectorView<T>, T: ?Sized> Copy for SubvectorView<V, T> {}
26
27impl<V: VectorView<T>, T: ?Sized> SubvectorView<V, T> {
28
29 pub fn new(base: V) -> Self {
30 Self {
31 begin: 0,
32 end: base.len(),
33 base: base,
34 element: PhantomData
35 }
36 }
37}
38
39impl<V: VectorView<T>, T: ?Sized> VectorView<T> for SubvectorView<V, T> {
40
41 fn at(&self, i: usize) -> &T {
42 assert!(i < self.len());
43 self.base.at(i + self.begin)
44 }
45
46 fn len(&self) -> usize {
47 self.end - self.begin
48 }
49
50 fn specialize_sparse<'a, Op: SparseVectorViewOperation<T>>(&'a self, op: Op) -> Result<Op::Output<'a>, ()> {
51
52 struct WrapSubvector<T: ?Sized, Op: SparseVectorViewOperation<T>> {
53 op: Op,
54 element: PhantomData<T>,
55 begin: usize,
56 end: usize
57 }
58
59 impl<T: ?Sized, Op: SparseVectorViewOperation<T>> SparseVectorViewOperation<T> for WrapSubvector<T, Op> {
60
61 type Output<'a> = Op::Output<'a>
62 where Self: 'a;
63
64 fn execute<'a, V: 'a + VectorViewSparse<T> + Clone>(self, vector: V) -> Self::Output<'a>
65 where Self: 'a
66 {
67 self.op.execute(SubvectorView::new(vector).restrict_full(self.begin..self.end))
68 }
69 }
70
71 self.base.specialize_sparse(WrapSubvector { op: op, element: PhantomData, begin: self.begin, end: self.end })
72 }
73
74 fn as_slice<'a>(&'a self) -> Option<&'a [T]>
75 where T: Sized
76 {
77 self.base.as_slice().map(|slice| &slice[self.begin..self.end])
78 }
79}
80
81impl<V: VectorView<T> + Debug, T: ?Sized> Debug for SubvectorView<V, T> {
82
83 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
84 f.debug_struct("SubvectorView")
85 .field("begin", &self.begin)
86 .field("end", &self.end)
87 .field("base", &self.base)
88 .finish()
89 }
90}
91
92pub struct FilterWithinRangeIter<'a, T: ?Sized, I>
93 where T: 'a,
94 I: Iterator<Item = (usize, &'a T)>
95{
96 it: I,
97 begin: usize,
98 end: usize
99}
100
101impl<'a, T: ?Sized, I> Iterator for FilterWithinRangeIter<'a, T, I>
102 where T: 'a,
103 I: Iterator<Item = (usize, &'a T)>
104{
105 type Item = (usize, &'a T);
106
107 fn next(&mut self) -> Option<Self::Item> {
108 self.it.by_ref().filter(|(i, _)| *i >= self.begin && *i < self.end).next()
109 }
110}
111
112impl<V: VectorViewSparse<T>, T: ?Sized> VectorViewSparse<T> for SubvectorView<V, T> {
113
114 type Iter<'a> = FilterWithinRangeIter<'a, T, V::Iter<'a>>
115 where Self: 'a, T: 'a;
116
117 fn nontrivial_entries<'a>(&'a self) -> Self::Iter<'a> {
118 FilterWithinRangeIter {
119 it: self.base.nontrivial_entries(),
120 begin: self.begin,
121 end: self.end
122 }
123 }
124}
125
126impl<V: VectorViewMut<T>, T: ?Sized> VectorViewMut<T> for SubvectorView<V, T> {
127
128 fn at_mut(&mut self, i: usize) -> &mut T {
129 assert!(i < self.len());
130 self.base.at_mut(i + self.begin)
131 }
132
133 fn as_slice_mut<'a>(&'a mut self) -> Option<&'a mut [T]>
134 where T: Sized
135 {
136 self.base.as_slice_mut().map(|slice| &mut slice[self.begin..self.end])
137 }
138}
139
140impl<V: SwappableVectorViewMut<T>, T: ?Sized> SwappableVectorViewMut<T> for SubvectorView<V, T> {
141
142 fn swap(&mut self, i: usize, j: usize) {
143 assert!(i < self.len());
144 assert!(j < self.len());
145 self.base.swap(i + self.begin, j + self.begin)
146 }
147}
148
149impl<V: VectorView<T>, T: ?Sized> SelfSubvectorView<T> for SubvectorView<V, T> {
150
151 fn restrict_full(mut self, range: std::ops::Range<usize>) -> Self {
152 assert!(range.end <= self.len());
153 debug_assert!(range.start <= range.end);
154 self.end = self.begin + range.end;
155 self.begin = self.begin + range.start;
156 return self;
157 }
158}
159
160pub struct SubvectorFn<V: VectorFn<T>, T> {
161 begin: usize,
162 end: usize,
163 base: V,
164 element: PhantomData<T>
165}
166
167impl<V: Clone + VectorFn<T>, T> Clone for SubvectorFn<V, T> {
168
169 fn clone(&self) -> Self {
170 Self {
171 begin: self.begin,
172 end: self.end,
173 base: self.base.clone(),
174 element: PhantomData
175 }
176 }
177}
178
179impl<V: Copy + VectorFn<T>, T> Copy for SubvectorFn<V, T> {}
180
181impl<V: VectorFn<T>, T> SubvectorFn<V, T> {
182
183 pub fn new(base: V) -> Self {
184 Self {
185 begin: 0,
186 end: base.len(),
187 base: base,
188 element: PhantomData
189 }
190 }
191}
192
193impl<V: VectorFn<T>, T> VectorFn<T> for SubvectorFn<V, T> {
194
195 fn at(&self, i: usize) -> T {
196 assert!(i < self.len());
197 self.base.at(i + self.begin)
198 }
199
200 fn len(&self) -> usize {
201 self.end - self.begin
202 }
203}
204
205impl<V: VectorFn<T>, T> SelfSubvectorFn<T> for SubvectorFn<V, T> {
206
207 fn restrict_full(mut self, range: std::ops::Range<usize>) -> Self {
208 assert!(range.end <= self.len());
209 debug_assert!(range.start <= range.end);
210 self.end = self.begin + range.end;
211 self.begin = self.begin + range.start;
212 return self;
213 }
214}
215
216#[cfg(test)]
217use crate::primitive_int::StaticRing;
218#[cfg(test)]
219use super::sparse::SparseMapVector;
220
221#[test]
222fn test_subvector_ranges() {
223 let a = SubvectorView::new([0, 1, 2, 3, 4]);
224 assert_eq!(3, a.restrict(0..3).len());
225 assert_eq!(3, a.restrict(0..=2).len());
226 assert_eq!(5, a.restrict(0..).len());
227 assert_eq!(5, a.restrict(..).len());
228 assert_eq!(2, a.restrict(3..).len());
229}
230
231#[test]
232fn test_subvector_subvector() {
233 let a = SubvectorView::new([0, 1, 2, 3, 4]);
234 let b = a.restrict(1..4);
235 assert_eq!(3, b.len());
236 assert_eq!(1, *b.at(0));
237 assert_eq!(2, *b.at(1));
238 assert_eq!(3, *b.at(2));
239}
240
241#[test]
242#[should_panic]
243fn test_subvector_subvector_oob() {
244 let a = SubvectorView::new([0, 1, 2, 3, 4]);
245 let b = a.restrict(1..4);
246 _ = b.restrict(0..4);
247}
248
249#[test]
250fn test_subvector_fn_ranges() {
251 let a = SubvectorFn::new([0, 1, 2, 3, 4].clone_els_by(|x| *x));
252 assert_eq!(3, a.restrict(0..3).len());
253 assert_eq!(3, a.restrict(0..=2).len());
254 assert_eq!(5, a.restrict(0..).len());
255 assert_eq!(5, a.restrict(..).len());
256 assert_eq!(2, a.restrict(3..).len());
257}
258
259#[test]
260fn test_subvector_fn_subvector() {
261 let a = SubvectorFn::new([0, 1, 2, 3, 4].clone_els_by(|x| *x));
262 let b = a.restrict(1..4);
263 assert_eq!(3, b.len());
264 assert_eq!(1, b.at(0));
265 assert_eq!(2, b.at(1));
266 assert_eq!(3, b.at(2));
267}
268
269#[test]
270#[should_panic]
271fn test_subvector_fn_subvector_oob() {
272 let a = SubvectorFn::new([0, 1, 2, 3, 4].clone_els_by(|x| *x));
273 let b = a.restrict(1..4);
274 _ = b.restrict(0..4);
275}
276
277#[test]
278fn test_subvector_sparse() {
279 let mut sparse_vector = SparseMapVector::new(1000, StaticRing::<i64>::RING);
280 *sparse_vector.at_mut(6) = 6;
281 *sparse_vector.at_mut(20) = 20;
282 *sparse_vector.at_mut(256) = 256;
283 *sparse_vector.at_mut(257) = 257;
284
285 let subvector = SubvectorView::new(sparse_vector).restrict(20..=256);
286
287 struct Verify;
288
289 impl SparseVectorViewOperation<i64> for Verify {
290
291 type Output<'a> = ();
292
293 fn execute<'a, V: 'a + VectorViewSparse<i64>>(self, vector: V) -> Self::Output<'a> {
294 assert!(
295 vec![(20, &20), (256, &256)] == vector.nontrivial_entries().collect::<Vec<_>>() ||
296 vec![(256, &256), (20, &20)] == vector.nontrivial_entries().collect::<Vec<_>>()
297 );
298 }
299 }
300
301 subvector.specialize_sparse(Verify).unwrap();
302}