feanor_math/seq/
mod.rs

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

feanor_math/seq/
mod.rs
