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