feanor_math/seq/mod.rs
1use std::alloc::Allocator;
2use std::fmt::{Debug, Formatter};
3use std::ops::{Bound, Range, RangeBounds};
4
5pub use conversion::{CloneElFn, VectorFnIter, VectorViewFn};
6pub use map::{VectorFnMap, VectorViewMap, VectorViewMapMut};
7use step_by::{StepBy, StepByFn};
8
9use crate::ring::*;
10
11mod conversion;
12mod map;
13
14/// Contains [`step_by::StepBy`] and [`step_by::StepByFn`], which wrap a
15/// [`VectorView`] or [`VectorFn`], respectively, and give a new [`VectorView`]
16/// or [`VectorFn`] that only yields every `n`-th element.
17pub mod step_by;
18
19/// Contains [`subvector::SubvectorView`] and [`subvector::SubvectorFn`], which
20/// wrap a [`VectorView`] or [`VectorFn`], respectively, and give a new [`VectorView`]
21/// or [`VectorFn`] that only yields elements from a given range.
22pub mod subvector;
23
24/// Contains the utility functions [`permute::permute()`] and [`permute::permute_inv()`]
25/// for applying permutations [`VectorViewMut`]s.
26pub mod permute;
27
28/// Contains [`sparse::SparseMapVector`], a container for sparse vectors.
29pub mod sparse;
30
31/// A trait for objects that provides random-position read access to a 1-dimensional
32/// sequence (or vector) of elements.
33///
34/// # Related traits
35///
36/// Other traits that represent sequences are
37/// - [`ExactSizeIterator`]: Returns elements by value; Since elements are moved, each element is
38/// returned only once, and they must be queried in order.
39/// - [`VectorFn`]: Also returns elements by value, but assumes that the underlying structure
40/// produces a new element whenever a position is queried. This allows accessing positions
41/// multiple times and in a random order, but depending on the represented items, it might
42/// require cloning an element on each access.
43///
44/// Apart from that, there are also the subtraits [`VectorViewMut`] and [`SwappableVectorViewMut`]
45/// that allow mutating the underlying sequence (but still don't allow moving elements out).
46/// Finally, there is [`SelfSubvectorView`], which directly supports taking subvectors.
47///
48/// # Example
49/// ```rust
50/// # use feanor_math::seq::*;
51/// fn compute_sum<V: VectorView<i32>>(vec: V) -> i32 {
52/// let mut result = 0;
53/// for i in 0..vec.len() {
54/// result += vec.at(i);
55/// }
56/// return result;
57/// }
58/// assert_eq!(10, compute_sum([1, 2, 3, 4]));
59/// assert_eq!(10, compute_sum(vec![1, 2, 3, 4]));
60/// assert_eq!(10, compute_sum(&[1, 2, 3, 4, 5][..4]));
61/// ```
62pub trait VectorView<T: ?Sized> {
63 fn len(&self) -> usize;
64 fn is_empty(&self) -> bool { self.len() == 0 }
65 fn at(&self, i: usize) -> &T;
66
67 /// Returns a refernce to the `i`-th entry of the vector view, causing
68 /// UB if `i >= self.len()`.
69 ///
70 /// # Safety
71 ///
72 /// Same as for [`slice::get_unchecked()`]. More concretely, calling this method with an
73 /// out-of-bounds index is undefined behavior even if the resulting reference is not used.
74 unsafe fn at_unchecked(&self, i: usize) -> &T { self.at(i) }
75
76 /// Calls `op` with `self` if this vector view supports sparse access.
77 /// Otherwise, `()` is returned.
78 ///
79 /// This is basically a workaround that enables users to specialize on
80 /// `V: VectorViewSparse`, even though specialization currently does not support
81 /// this.
82 fn specialize_sparse<'a, Op: SparseVectorViewOperation<T>>(&'a self, _op: Op) -> Option<Op::Output<'a>> { None }
83
84 /// Returns an iterator over all elements in this vector.
85 ///
86 /// NB: Not called `iter()` to prevent name conflicts, since many containers (e.g. `Vec<T>`)
87 /// have a function `iter()` and implement [`VectorView`]. As a result, whenever [`VectorView`]
88 /// is in scope, calling any one `iter()` would require fully-qualified call syntax.
89 fn as_iter<'a>(&'a self) -> VectorFnIter<VectorViewFn<'a, Self, T>, &'a T> { VectorFnIter::new(self.as_fn()) }
90
91 /// Converts this vector into a [`VectorFn`] that yields references `&T`.
92 fn as_fn<'a>(&'a self) -> VectorViewFn<'a, Self, T> { VectorViewFn::new(self) }
93
94 /// If the underlying data of this [`VectorView`] can be represented as a slice,
95 /// returns it. Otherwise, `None` is returned.
96 fn as_slice(&self) -> Option<&[T]>
97 where
98 T: Sized,
99 {
100 None
101 }
102
103 /// Moves this vector into a [`VectorFn`] that clones ring elements on access using
104 /// the given ring.
105 fn into_clone_ring_els<R: RingStore>(self, ring: R) -> CloneElFn<Self, T, CloneRingEl<R>>
106 where
107 Self: Sized,
108 T: Sized,
109 R::Type: RingBase<Element = T>,
110 {
111 self.into_clone_els_by(CloneRingEl(ring))
112 }
113
114 /// Converts this vector into a [`VectorFn`] that clones ring elements on access using
115 /// the given ring.
116 fn clone_ring_els<R: RingStore>(&self, ring: R) -> CloneElFn<&Self, T, CloneRingEl<R>>
117 where
118 T: Sized,
119 R::Type: RingBase<Element = T>,
120 {
121 self.into_clone_ring_els(ring)
122 }
123
124 /// Moves this vector into a [`VectorFn`] that clones elements on access using
125 /// the given function.
126 fn into_clone_els_by<F>(self, clone_entry: F) -> CloneElFn<Self, T, F>
127 where
128 Self: Sized,
129 T: Sized,
130 F: Fn(&T) -> T,
131 {
132 CloneElFn::new(self, clone_entry)
133 }
134
135 /// Converts this vector into a [`VectorFn`] that clones elements on access using
136 /// the given function.
137 fn clone_els_by<F>(&self, clone_entry: F) -> CloneElFn<&Self, T, F>
138 where
139 T: Sized,
140 F: Fn(&T) -> T,
141 {
142 self.into_clone_els_by(clone_entry)
143 }
144
145 /// Moves this vector into a [`VectorFn`] that clones elements on access.
146 fn into_clone_els(self) -> CloneElFn<Self, T, CloneValue>
147 where
148 Self: Sized,
149 T: Sized + Clone,
150 {
151 CloneElFn::new(self, CloneValue)
152 }
153
154 /// Converts this vector into a [`VectorFn`] that clones elements on access.
155 fn clone_els(&self) -> CloneElFn<&Self, T, CloneValue>
156 where
157 T: Sized + Clone,
158 {
159 self.into_clone_els()
160 }
161
162 /// Moves this vector into a [`VectorFn`] that copies elements on access.
163 fn into_copy_els(self) -> CloneElFn<Self, T, CloneValue>
164 where
165 Self: Sized,
166 T: Sized + Copy,
167 {
168 CloneElFn::new(self, CloneValue)
169 }
170
171 /// Converts this vector into a [`VectorFn`] that copies elements on access.
172 fn copy_els(&self) -> CloneElFn<&Self, T, CloneValue>
173 where
174 T: Sized + Copy,
175 {
176 self.into_copy_els()
177 }
178
179 /// Creates a new [`VectorView`] whose elements are the results of the given function
180 /// applied to the elements of this vector.
181 ///
182 /// The most common use case is a projection on contained elements. Since [`VectorView`]s
183 /// provide elements by reference, this is much less powerful than [`Iterator::map()`] or
184 /// [`VectorFn::map_fn()`], since the function cannot return created elements.
185 ///
186 /// Called `map_view()` to prevent name conflicts with [`Iterator::map()`].
187 ///
188 /// # Example
189 /// ```rust
190 /// use feanor_math::seq::*;
191 /// fn foo<V: VectorView<i64>>(data: V) {
192 /// // some logic
193 /// }
194 /// let data = vec![Some(1), Some(2), Some(3)];
195 /// // the `as_ref()` is necessary, since we have to return a reference
196 /// foo(data.map_view(|x| x.as_ref().unwrap()));
197 /// ```
198 fn map_view<F: for<'a> Fn(&'a T) -> &'a U, U>(self, func: F) -> VectorViewMap<Self, T, U, F>
199 where
200 Self: Sized,
201 {
202 VectorViewMap::new(self, func)
203 }
204
205 /// Called `step_by_view()` to prevent name conflicts with [`Iterator::step_by()`].
206 fn step_by_view(self, step_by: usize) -> StepBy<Self, T>
207 where
208 Self: Sized,
209 {
210 StepBy::new(self, step_by)
211 }
212}
213
214/// View on a sequence type that stores its data in a sparse format.
215/// This clearly requires that the underlying type `T` has some notion
216/// of a "zero" element.
217pub trait VectorViewSparse<T: ?Sized>: VectorView<T> {
218 type Iter<'a>: Iterator<Item = (usize, &'a T)>
219 where
220 Self: 'a,
221 T: 'a;
222
223 /// Returns an iterator over all elements of the sequence with their indices
224 /// that are "nonzero" (`T` must have an appropriate notion of zero).
225 ///
226 /// # Example
227 /// ```rust
228 /// # use feanor_math::seq::*;
229 /// # use feanor_math::ring::*;
230 /// # use feanor_math::primitive_int::*;
231 /// # use feanor_math::seq::sparse::*;
232 /// let mut vector = SparseMapVector::new(10, StaticRing::<i64>::RING);
233 /// *vector.at_mut(2) = 100;
234 /// assert_eq!(
235 /// vec![(2, 100)],
236 /// vector
237 /// .nontrivial_entries()
238 /// .map(|(i, x)| (i, *x))
239 /// .collect::<Vec<_>>()
240 /// );
241 /// ```
242 fn nontrivial_entries<'a>(&'a self) -> Self::Iter<'a>;
243}
244
245/// Operation that operates on a [`VectorViewSparse`].
246///
247/// Used as a workaround for specialization, together with [`VectorView::specialize_sparse()`].
248///
249/// TODO: on next breaking update (unfortunate that I missed 3.0.0), replace this by
250/// the more powerful workaround technique as used for finite rings in [`crate::specialization`].
251pub trait SparseVectorViewOperation<T: ?Sized> {
252 type Output<'a>
253 where
254 Self: 'a;
255
256 fn execute<'a, V: 'a + VectorViewSparse<T> + Clone>(self, vector: V) -> Self::Output<'a>
257 where
258 Self: 'a;
259}
260
261fn range_within<R: RangeBounds<usize>>(len: usize, range: R) -> Range<usize> {
262 let start = match range.start_bound() {
263 Bound::Unbounded => 0,
264 Bound::Included(i) => {
265 assert!(*i <= len);
266 *i
267 }
268 Bound::Excluded(i) => {
269 assert!(*i <= len);
270 *i + 1
271 }
272 };
273 let end = match range.end_bound() {
274 Bound::Unbounded => len,
275 Bound::Included(i) => {
276 assert!(*i >= start);
277 assert!(*i < len);
278 *i + 1
279 }
280 Bound::Excluded(i) => {
281 assert!(*i >= start);
282 assert!(*i <= len);
283 *i
284 }
285 };
286 return start..end;
287}
288
289/// Trait for [`VectorView`]s that support shrinking, i.e. transforming the
290/// vector into a subvector of itself.
291///
292/// Note that you can easily get a subvector of a vector by using [`subvector::SubvectorView`],
293/// but this will wrap the original type. This makes [`subvector::SubvectorView`] unsuitable
294/// for some applications, like recursive algorithms.
295///
296/// Note also that [`SelfSubvectorView::restrict()`] consumes the current object, thus
297/// it is most useful for vectors that implement [`Clone`]/[`Copy`], in particular for references
298/// to vectors.
299///
300/// This is the [`VectorView`]-counterpart to [`SelfSubvectorFn`].
301///
302/// # Example
303/// ```rust
304/// # use feanor_math::seq::*;
305/// # use feanor_math::seq::subvector::*;
306/// fn compute_sum_recursive<V: SelfSubvectorView<i32>>(vec: V) -> i32 {
307/// if vec.len() == 0 {
308/// 0
309/// } else {
310/// *vec.at(0) + compute_sum_recursive(vec.restrict(1..))
311/// }
312/// }
313/// assert_eq!(10, compute_sum_recursive(SubvectorView::new([1, 2, 3, 4])));
314/// assert_eq!(
315/// 10,
316/// compute_sum_recursive(SubvectorView::new(vec![1, 2, 3, 4]))
317/// );
318/// assert_eq!(
319/// 10,
320/// compute_sum_recursive(SubvectorView::new(&[1, 2, 3, 4, 5][..4]))
321/// );
322/// ```
323pub trait SelfSubvectorView<T: ?Sized>: Sized + VectorView<T> {
324 /// Returns a [`SelfSubvectorView`] that represents the elements within the given range
325 /// of this vector.
326 fn restrict_full(self, range: Range<usize>) -> Self;
327
328 /// Returns a [`SelfSubvectorView`] that represents the elements within the given range
329 /// of this vector.
330 fn restrict<R: RangeBounds<usize>>(self, range: R) -> Self {
331 let range_full = range_within(self.len(), range);
332 self.restrict_full(range_full)
333 }
334}
335
336impl<T: ?Sized, V: ?Sized + VectorView<T>> VectorView<T> for Box<V> {
337 fn len(&self) -> usize { (**self).len() }
338
339 fn at(&self, i: usize) -> &T { (**self).at(i) }
340
341 unsafe fn at_unchecked(&self, i: usize) -> &T { unsafe { (**self).at_unchecked(i) } }
342
343 fn specialize_sparse<'a, Op: SparseVectorViewOperation<T>>(&'a self, op: Op) -> Option<Op::Output<'a>> {
344 (**self).specialize_sparse(op)
345 }
346
347 fn as_slice(&self) -> Option<&[T]>
348 where
349 T: Sized,
350 {
351 (**self).as_slice()
352 }
353}
354
355impl<T: ?Sized, V: ?Sized + VectorViewMut<T>> VectorViewMut<T> for Box<V> {
356 fn at_mut(&mut self, i: usize) -> &mut T { (**self).at_mut(i) }
357
358 unsafe fn at_unchecked_mut<'a>(&mut self, i: usize) -> &mut T { unsafe { (**self).at_unchecked_mut(i) } }
359
360 fn as_slice_mut(&mut self) -> Option<&mut [T]>
361 where
362 T: Sized,
363 {
364 (**self).as_slice_mut()
365 }
366}
367
368impl<T: ?Sized, V: ?Sized + VectorViewSparse<T>> VectorViewSparse<T> for Box<V> {
369 type Iter<'b>
370 = V::Iter<'b>
371 where
372 Self: 'b,
373 T: 'b;
374
375 fn nontrivial_entries<'b>(&'b self) -> Self::Iter<'b> { (**self).nontrivial_entries() }
376}
377
378impl<T: ?Sized, V: ?Sized + VectorView<T>> VectorView<T> for &V {
379 fn len(&self) -> usize { (**self).len() }
380
381 fn at(&self, i: usize) -> &T { (**self).at(i) }
382
383 unsafe fn at_unchecked(&self, i: usize) -> &T { unsafe { (**self).at_unchecked(i) } }
384
385 fn specialize_sparse<'b, Op: SparseVectorViewOperation<T>>(&'b self, op: Op) -> Option<Op::Output<'b>> {
386 (**self).specialize_sparse(op)
387 }
388
389 fn as_slice(&self) -> Option<&[T]>
390 where
391 T: Sized,
392 {
393 (**self).as_slice()
394 }
395}
396
397impl<T: ?Sized, V: ?Sized + VectorViewSparse<T>> VectorViewSparse<T> for &V {
398 type Iter<'b>
399 = V::Iter<'b>
400 where
401 Self: 'b,
402 T: 'b;
403
404 fn nontrivial_entries<'b>(&'b self) -> Self::Iter<'b> { (**self).nontrivial_entries() }
405}
406
407impl<T: ?Sized, V: ?Sized + VectorView<T>> VectorView<T> for &mut V {
408 fn len(&self) -> usize { (**self).len() }
409
410 fn at(&self, i: usize) -> &T { (**self).at(i) }
411
412 unsafe fn at_unchecked(&self, i: usize) -> &T { unsafe { (**self).at_unchecked(i) } }
413
414 fn specialize_sparse<'b, Op: SparseVectorViewOperation<T>>(&'b self, op: Op) -> Option<Op::Output<'b>> {
415 (**self).specialize_sparse(op)
416 }
417
418 fn as_slice(&self) -> Option<&[T]>
419 where
420 T: Sized,
421 {
422 (**self).as_slice()
423 }
424}
425
426impl<T: ?Sized, V: ?Sized + VectorViewMut<T>> VectorViewMut<T> for &mut V {
427 fn at_mut(&mut self, i: usize) -> &mut T { (**self).at_mut(i) }
428
429 unsafe fn at_unchecked_mut(&mut self, i: usize) -> &mut T { unsafe { (**self).at_unchecked_mut(i) } }
430
431 fn as_slice_mut(&mut self) -> Option<&mut [T]>
432 where
433 T: Sized,
434 {
435 (**self).as_slice_mut()
436 }
437}
438
439impl<T: ?Sized, V: ?Sized + VectorViewSparse<T>> VectorViewSparse<T> for &mut V {
440 type Iter<'b>
441 = V::Iter<'b>
442 where
443 Self: 'b,
444 T: 'b;
445
446 fn nontrivial_entries<'b>(&'b self) -> Self::Iter<'b> { (**self).nontrivial_entries() }
447}
448
449impl<T: ?Sized, V: ?Sized + SwappableVectorViewMut<T>> SwappableVectorViewMut<T> for &mut V {
450 fn swap(&mut self, i: usize, j: usize) { (**self).swap(i, j) }
451}
452
453/// A trait for [`VectorView`]s that allow mutable access to one element at a time.
454///
455/// Note that a fundamental difference to many containers (like `&mut [T]`) is that
456/// this trait only defines functions that give a mutable reference to one element at
457/// a time. In particular, it is intentionally impossible to have a mutable reference
458/// to multiple elements at once. This enables implementations like sparse vectors,
459/// e.g. [`sparse::SparseMapVector`].
460pub trait VectorViewMut<T: ?Sized>: VectorView<T> {
461 fn at_mut(&mut self, i: usize) -> &mut T;
462
463 fn map_mut<F_const: for<'a> Fn(&'a T) -> &'a U, F_mut: for<'a> FnMut(&'a mut T) -> &'a mut U, U>(
464 self,
465 map_const: F_const,
466 map_mut: F_mut,
467 ) -> VectorViewMapMut<Self, T, U, F_const, F_mut>
468 where
469 Self: Sized,
470 {
471 VectorViewMapMut::new(self, (map_const, map_mut))
472 }
473
474 /// If the underlying data of this [`VectorView`] can be represented as a slice,
475 /// returns it. Otherwise, `None` is returned.
476 fn as_slice_mut(&mut self) -> Option<&mut [T]>
477 where
478 T: Sized,
479 {
480 None
481 }
482
483 /// Returns a refernce to the `i`-th entry of the vector view, causing
484 /// UB if `i >= self.len()`.
485 ///
486 /// # Safety
487 ///
488 /// Same as for [`slice::get_unchecked_mut()`]. More concretely, calling this method with an
489 /// out-of-bounds index is undefined behavior even if the resulting reference is not used.
490 unsafe fn at_unchecked_mut(&mut self, i: usize) -> &mut T { self.at_mut(i) }
491}
492
493/// A trait for [`VectorViewMut`]s that support swapping of two elements.
494///
495/// Since [`VectorViewMut`] is not necessarily able to return two mutable
496/// references to different entries, supporting swapping is indeed a stronger
497/// property than just being a [`VectorViewMut`].
498pub trait SwappableVectorViewMut<T: ?Sized>: VectorViewMut<T> {
499 fn swap(&mut self, i: usize, j: usize);
500}
501
502/// A trait for objects that provides random-position access to a 1-dimensional
503/// sequence (or vector) of elements that returned by value.
504///
505/// # Related traits
506///
507/// Other traits that represent sequences are
508/// - [`ExactSizeIterator`]: Also returns elements by value; However, to avoid copying elements, an
509/// `ExactSizeIterator` returns every item only once, and only in the order of the underlying
510/// vector.
511/// - [`VectorView`]: Returns only references to the underlying data, but also supports
512/// random-position access. Note that `VectorView<T>` is not the same as `VectorFn<&T>`, since
513/// the lifetime of returned references `&T` in the case of `VectorView` is the lifetime of the
514/// vector, but in the case of `VectorFn`, it must be a fixed lifetime parameter.
515///
516/// Finally, there is the subtrait [`SelfSubvectorFn`], which directly supports taking subvectors.
517///
518/// # Example
519/// ```rust
520/// # use feanor_math::seq::*;
521/// fn compute_sum<V: VectorFn<usize>>(vec: V) -> usize {
522/// let mut result = 0;
523/// for i in 0..vec.len() {
524/// result += vec.at(i);
525/// }
526/// return result;
527/// }
528/// assert_eq!(10, compute_sum(1..5));
529/// assert_eq!(10, compute_sum([1, 2, 3, 4].copy_els()));
530/// assert_eq!(10, compute_sum(vec![1, 2, 3, 4].copy_els()));
531/// assert_eq!(10, compute_sum((&[1, 2, 3, 4, 5][..4]).copy_els()));
532/// ```
533pub trait VectorFn<T> {
534 fn len(&self) -> usize;
535 fn is_empty(&self) -> bool { self.len() == 0 }
536 fn at(&self, i: usize) -> T;
537
538 /// Produces an iterator over the elements of this [`VectorFn`].
539 ///
540 /// This transfers ownership of the object to the iterator. If this
541 /// is not desired, consider using [`VectorFn::iter()`].
542 ///
543 /// Note that [`VectorFn`]s do not necessarily implement [`IntoIterator`] and
544 /// instead use this function. The reason for that is twofold:
545 /// - the only way of making all types implementing [`VectorFn`]s to also implement
546 /// [`IntoIterator`] would be to define `VectorFn` as a subtrait of `IntoIterator`. However,
547 /// this conflicts with the decision to have [`VectorFn`] have the element type as generic
548 /// parameter, since [`IntoIterator`] uses an associated type.
549 /// - If the above problem could somehow be circumvented, for types that implement both
550 /// [`Iterator`] and [`VectorFn`] (like [`Range`]), calling `into_iter()` would then require
551 /// fully-qualified call syntax, which is very unwieldy.
552 fn into_iter(self) -> VectorFnIter<Self, T>
553 where
554 Self: Sized,
555 {
556 VectorFnIter::new(self)
557 }
558
559 /// Produces an iterator over the elements of this [`VectorFn`].
560 ///
561 /// See also [`VectorFn::into_iter()`] if a transfer of ownership is required.
562 fn iter(&self) -> VectorFnIter<&Self, T> { self.into_iter() }
563
564 /// NB: Named `map_fn` to avoid conflicts with `map` of [`Iterator`]
565 fn map_fn<F: Fn(T) -> U, U>(self, func: F) -> VectorFnMap<Self, T, U, F>
566 where
567 Self: Sized,
568 {
569 VectorFnMap::new(self, func)
570 }
571
572 /// NB: Named `step_by_fn` to avoid conflicts with `step_by` of [`Iterator`]
573 fn step_by_fn(self, step_by: usize) -> StepByFn<Self, T>
574 where
575 Self: Sized,
576 {
577 StepByFn::new(self, step_by)
578 }
579}
580
581/// Trait for [`VectorFn`]s that support shrinking, i.e. transforming the
582/// vector into a subvector of itself.
583///
584/// Note that you can easily get a subvector of a vector by using [`subvector::SubvectorFn`],
585/// but this will wrap the original type. This makes [`subvector::SubvectorFn`] unsuitable
586/// for some applications, like recursive algorithms.
587///
588/// Note also that [`SelfSubvectorFn::restrict()`] consumes the current object, thus
589/// it is most useful for vectors that implement [`Clone`]/[`Copy`], in particular for references
590/// to vectors.
591///
592/// This is the [`VectorFn`]-counterpart to [`SelfSubvectorView`].
593///
594/// ## Default impls
595///
596/// As opposed to [`VectorView`], there are no implementations of [`VectorFn`] for standard
597/// containers like `Vec<T>`, `&[T]` etc. This is because it is not directly clear whether elements
598/// should be cloned on access, or whether a `VectorFn<&T>` is desired. Instead, use the appropriate
599/// functions [`VectorView::as_fn()`] or [`VectorView::clone_els()`] to create a [`VectorFn`].
600/// An exception is made for `Range<usize>`, which directly implements `VectorFn`. This allows
601/// for yet another way of creating arbitrary `VectorFn`s by using `(0..len).map_fn(|i| ...)`.
602///
603/// # Example
604/// ```rust
605/// # use feanor_math::seq::*;
606/// # use feanor_math::seq::subvector::*;
607/// fn compute_sum_recursive<V: SelfSubvectorFn<usize>>(vec: V) -> usize {
608/// if vec.len() == 0 {
609/// 0
610/// } else {
611/// vec.at(0) + compute_sum_recursive(vec.restrict(1..))
612/// }
613/// }
614/// assert_eq!(
615/// 10,
616/// compute_sum_recursive(SubvectorFn::new([1, 2, 3, 4].copy_els()))
617/// );
618/// assert_eq!(
619/// 10,
620/// compute_sum_recursive(SubvectorFn::new(vec![1, 2, 3, 4].copy_els()))
621/// );
622/// assert_eq!(
623/// 10,
624/// compute_sum_recursive(SubvectorFn::new((&[1, 2, 3, 4, 5][..4]).copy_els()))
625/// );
626/// ```
627pub trait SelfSubvectorFn<T>: Sized + VectorFn<T> {
628 /// Returns a [`SelfSubvectorFn`] that represents the elements within the given range
629 /// of this vector.
630 fn restrict_full(self, range: Range<usize>) -> Self;
631
632 /// Returns a [`SelfSubvectorFn`] that represents the elements within the given range
633 /// of this vector.
634 fn restrict<R: RangeBounds<usize>>(self, range: R) -> Self {
635 let range_full = range_within(self.len(), range);
636 self.restrict_full(range_full)
637 }
638}
639
640impl<T, V: ?Sized + VectorFn<T>> VectorFn<T> for &V {
641 fn len(&self) -> usize { (**self).len() }
642
643 fn at(&self, i: usize) -> T { (**self).at(i) }
644}
645
646impl<T> VectorView<T> for [T] {
647 fn len(&self) -> usize { <[T]>::len(self) }
648
649 fn at(&self, i: usize) -> &T { &self[i] }
650
651 unsafe fn at_unchecked(&self, i: usize) -> &T { unsafe { self.get_unchecked(i) } }
652
653 fn as_slice(&self) -> Option<&[T]>
654 where
655 T: Sized,
656 {
657 Some(self)
658 }
659}
660
661impl<T> SelfSubvectorView<T> for &[T] {
662 fn restrict_full(self, range: Range<usize>) -> Self { &self[range] }
663}
664
665impl<T> SelfSubvectorView<T> for &mut [T] {
666 fn restrict_full(self, range: Range<usize>) -> Self { &mut self[range] }
667}
668
669impl<T> VectorViewMut<T> for [T] {
670 fn at_mut(&mut self, i: usize) -> &mut T { &mut self[i] }
671
672 unsafe fn at_unchecked_mut<'a>(&mut self, i: usize) -> &mut T { unsafe { self.get_unchecked_mut(i) } }
673
674 fn as_slice_mut(&mut self) -> Option<&mut [T]>
675 where
676 T: Sized,
677 {
678 Some(self)
679 }
680}
681
682impl<T> SwappableVectorViewMut<T> for [T] {
683 fn swap(&mut self, i: usize, j: usize) { <[T]>::swap(self, i, j) }
684}
685
686impl<T, A: Allocator> VectorView<T> for Vec<T, A> {
687 fn len(&self) -> usize { <[T]>::len(self) }
688
689 fn at(&self, i: usize) -> &T { &self[i] }
690
691 unsafe fn at_unchecked(&self, i: usize) -> &T { unsafe { self.get_unchecked(i) } }
692
693 fn as_slice(&self) -> Option<&[T]>
694 where
695 T: Sized,
696 {
697 Some(self)
698 }
699}
700
701impl<T, A: Allocator> VectorViewMut<T> for Vec<T, A> {
702 fn at_mut(&mut self, i: usize) -> &mut T { &mut self[i] }
703
704 unsafe fn at_unchecked_mut<'a>(&mut self, i: usize) -> &mut T { unsafe { self.get_unchecked_mut(i) } }
705
706 fn as_slice_mut(&mut self) -> Option<&mut [T]>
707 where
708 T: Sized,
709 {
710 Some(&mut *self)
711 }
712}
713
714impl<T, A: Allocator> SwappableVectorViewMut<T> for Vec<T, A> {
715 fn swap(&mut self, i: usize, j: usize) { <[T]>::swap(self, i, j) }
716}
717
718impl<T, const N: usize> VectorView<T> for [T; N] {
719 fn len(&self) -> usize { N }
720
721 fn at(&self, i: usize) -> &T { &self[i] }
722
723 unsafe fn at_unchecked(&self, i: usize) -> &T { unsafe { self.get_unchecked(i) } }
724
725 fn as_slice(&self) -> Option<&[T]>
726 where
727 T: Sized,
728 {
729 Some(&self[..])
730 }
731}
732
733impl<T, const N: usize> VectorViewMut<T> for [T; N] {
734 fn at_mut(&mut self, i: usize) -> &mut T { &mut self[i] }
735
736 unsafe fn at_unchecked_mut<'a>(&mut self, i: usize) -> &mut T { unsafe { self.get_unchecked_mut(i) } }
737
738 fn as_slice_mut(&mut self) -> Option<&mut [T]>
739 where
740 T: Sized,
741 {
742 Some(&mut *self)
743 }
744}
745
746impl<T, const N: usize> SwappableVectorViewMut<T> for [T; N] {
747 fn swap(&mut self, i: usize, j: usize) { <[T]>::swap(self, i, j) }
748}
749
750/// # Why no impl for `Range<i64>` etc?
751///
752/// It is a common pattern to write `(0..n).map_fn(|x| ...)` to create general
753/// [`VectorFn`]s. If we provide impls for multiple [`Range`]s, then in this
754/// case however, explicit type arguments will be necessary. Instead, if you
755/// require a [`VectorFn`] over another numerical type `T`, consider using
756/// `((start as usize)..(end as usize)).map_fn(|x| x as T)`.
757impl VectorFn<usize> for Range<usize> {
758 fn at(&self, i: usize) -> usize {
759 assert!(i < <_ as VectorFn<_>>::len(self));
760 self.start + i
761 }
762
763 fn len(&self) -> usize { self.end - self.start }
764}
765
766/// A wrapper around a [`RingStore`] that is callable with signature `(&El<R>) -> El<R>`,
767/// and will clone the given ring element when called.
768///
769/// In order to be compatible with [`crate::iters::multi_cartesian_product()`], it
770/// additionally is also callable with signature `(usize, &El<R>) -> El<R>`. In this
771/// case, the first parameter is ignored.
772#[derive(Copy, Clone)]
773pub struct CloneRingEl<R: RingStore>(pub R);
774
775impl<'a, R: RingStore> FnOnce<(&'a El<R>,)> for CloneRingEl<R> {
776 type Output = El<R>;
777
778 extern "rust-call" fn call_once(self, args: (&'a El<R>,)) -> Self::Output { self.call(args) }
779}
780
781impl<'a, R: RingStore> FnMut<(&'a El<R>,)> for CloneRingEl<R> {
782 extern "rust-call" fn call_mut(&mut self, args: (&'a El<R>,)) -> Self::Output { self.call(args) }
783}
784
785impl<'a, R: RingStore> Fn<(&'a El<R>,)> for CloneRingEl<R> {
786 extern "rust-call" fn call(&self, args: (&'a El<R>,)) -> Self::Output { self.0.clone_el(args.0) }
787}
788
789impl<'a, R: RingStore> FnOnce<(usize, &'a El<R>)> for CloneRingEl<R> {
790 type Output = El<R>;
791
792 extern "rust-call" fn call_once(self, args: (usize, &'a El<R>)) -> Self::Output { self.call(args) }
793}
794
795impl<'a, R: RingStore> FnMut<(usize, &'a El<R>)> for CloneRingEl<R> {
796 extern "rust-call" fn call_mut(&mut self, args: (usize, &'a El<R>)) -> Self::Output { self.call(args) }
797}
798
799impl<'a, R: RingStore> Fn<(usize, &'a El<R>)> for CloneRingEl<R> {
800 extern "rust-call" fn call(&self, args: (usize, &'a El<R>)) -> Self::Output { self.0.clone_el(args.1) }
801}
802
803/// Callable struct that wraps [`Clone::clone()`].
804#[derive(Copy, Clone)]
805pub struct CloneValue;
806
807impl<'a, T: Clone> FnOnce<(&'a T,)> for CloneValue {
808 type Output = T;
809
810 extern "rust-call" fn call_once(self, args: (&'a T,)) -> Self::Output { self.call(args) }
811}
812
813impl<'a, T: Clone> FnMut<(&'a T,)> for CloneValue {
814 extern "rust-call" fn call_mut(&mut self, args: (&'a T,)) -> Self::Output { self.call(args) }
815}
816
817impl<'a, T: Clone> Fn<(&'a T,)> for CloneValue {
818 extern "rust-call" fn call(&self, args: (&'a T,)) -> Self::Output { args.0.clone() }
819}
820
821#[test]
822fn test_vector_fn_iter() {
823 let vec = vec![1, 2, 4, 8, 16];
824 assert_eq!(vec, vec.as_fn().into_iter().copied().collect::<Vec<_>>());
825}