feanor_math/seq/
mod.rs

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

feanor_math/seq/
mod.rs
