jaggedarray/
jagged_array.rs

1use generic_array::{sequence::GenericSequence, ArrayLength, GenericArray};
2use num::traits::AsPrimitive;
3use num::traits::ConstOne;
4use num::traits::ConstZero;
5use num::traits::Num;
6use num::traits::NumAssignOps;
7use std::ops::Range;
8use std::{
9    iter::zip,
10    ops::{Index, IndexMut},
11};
12use typenum::{Const, IsEqual, NonZero, Sub1, ToUInt, Unsigned, B1, U, U2};
13
14use crate::vec_ext::Ext;
15use crate::vec_like::VecLike;
16#[derive(Debug, Clone, PartialEq, Eq, Hash)]
17pub struct JaggedArray<TVal, TBuffer: VecLike, const N: usize>
18where
19    <TBuffer as VecLike>::TI: AsPrimitive<usize> + Num,
20    U<N>: std::ops::Sub<B1>,
21    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
22    Const<N>: ToUInt,
23{
24    indices: GenericArray<TBuffer, Sub1<U<N>>>,
25    buffer: Vec<TVal>,
26}
27
28#[derive(Debug, Clone, PartialEq, Eq, Hash)]
29pub struct JaggedArrayView<'a, TVal, TNum, const N: usize>
30where
31    TNum: AsPrimitive<usize> + Num,
32    U<N>: std::ops::Sub<B1>,
33    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
34    Const<N>: ToUInt,
35{
36    indices: GenericArray<&'a [TNum], Sub1<U<N>>>,
37    buffer: &'a [TVal],
38}
39
40#[derive(Debug, PartialEq, Eq, Hash)]
41pub struct JaggedArrayMutView<'a, TVal, TNum, const N: usize>
42where
43    TNum: AsPrimitive<usize> + Num,
44    U<N>: std::ops::Sub<B1>,
45    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
46    Const<N>: ToUInt,
47{
48    indices: GenericArray<&'a mut [TNum], Sub1<U<N>>>,
49    buffer: &'a mut [TVal],
50}
51
52#[derive(Debug, Clone, PartialEq, Eq, Hash)]
53pub struct JaggedArrayOwnedView<TVal, TNum, const N: usize>
54where
55    TNum: AsPrimitive<usize> + Num,
56    U<N>: std::ops::Sub<B1>,
57    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
58    Const<N>: ToUInt,
59{
60    indices: GenericArray<Box<[TNum]>, Sub1<U<N>>>,
61    buffer: Box<[TVal]>,
62}
63
64impl<TVal, TBuffer: VecLike, const N: usize> Default for JaggedArray<TVal, TBuffer, N>
65where
66    <TBuffer as VecLike>::TI: AsPrimitive<usize> + Num + ConstOne + ConstZero,
67    U<N>: std::ops::Sub<B1>,
68    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
69    Const<N>: ToUInt,
70{
71    #[inline]
72    fn default() -> Self {
73        Self {
74            indices: GenericArray::generate(|_| {
75                let mut a = TBuffer::default();
76                a.push(TBuffer::TI::ZERO);
77                a
78            }),
79            buffer: Default::default(),
80        }
81    }
82}
83// Methods that are unique to JaggedArray
84impl<TVal, TBuffer: VecLike, const N: usize> JaggedArray<TVal, TBuffer, N>
85where
86    <TBuffer as VecLike>::TI:
87        AsPrimitive<usize> + Num + NumAssignOps + std::cmp::PartialOrd + ConstOne + ConstZero,
88    U<N>: std::ops::Sub<B1>,
89    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
90    Const<N>: ToUInt,
91    usize: num::traits::AsPrimitive<<TBuffer as VecLike>::TI>,
92{
93    #[inline]
94    pub fn new() -> Self {
95        Self::default()
96    }
97    #[inline]
98    pub fn with_capacity(capacity: [usize; N]) -> Self {
99        Self {
100            indices: GenericArray::generate(|i| {
101                let mut temp = TBuffer::default();
102                temp.push(TBuffer::TI::ZERO);
103                temp.reserve(capacity[i]);
104                temp
105            }),
106            buffer: Vec::with_capacity(*capacity.last().unwrap()),
107        }
108    }
109    #[inline]
110    pub fn reserve(&mut self, additional: [usize; N]) {
111        for (index, additional) in zip(self.indices.iter_mut(), additional.iter()) {
112            index.reserve(*additional);
113        }
114        self.buffer.reserve(additional[N - 1]);
115    }
116    #[inline]
117    pub fn buffer_reserve(&mut self, additional: usize) {
118        self.buffer.reserve(additional);
119    }
120    #[inline]
121    pub fn buffer_len(&self) -> usize {
122        self.buffer.len()
123    }
124    #[inline]
125    pub fn buffer_capacity(&self) -> usize {
126        self.buffer.capacity()
127    }
128
129    #[inline]
130    pub fn clear(&mut self) {
131        self.buffer.clear();
132        for index in self.indices.iter_mut() {
133            index.clear();
134            index.push(TBuffer::TI::ZERO);
135        }
136    }
137    /// # Example
138    ///
139    /// ```rust
140    /// use jaggedarray::jagged_array::JaggedArray;
141    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
142    /// data.new_row::<0>();
143    /// data.new_row::<0>();
144    /// data.push_to_last_row(1);
145    /// assert!(data[[1,0]] == 1);
146    /// ```
147    #[inline]
148    pub fn new_row<const DIM: usize>(&mut self)
149    where
150        U<N>: std::ops::Sub<U<DIM>>,
151        Sub1<<U<N> as std::ops::Sub<U<DIM>>>::Output>: Unsigned + NonZero,
152        <U<N> as std::ops::Sub<U<DIM>>>::Output: std::ops::Sub<typenum::B1>,
153        U<DIM>: ArrayLength,
154        Const<N>: ToUInt,
155        Const<DIM>: ToUInt,
156    {
157        let m = DIM;
158        let buffer = &mut self.indices[m];
159        let new_val = *buffer.last().unwrap();
160        buffer.push(new_val);
161        if m > 0 {
162            *self.indices[m - 1].last_mut().unwrap() += TBuffer::TI::ONE;
163        }
164    }
165    #[inline]
166    pub fn push_to_last_row(&mut self, val: TVal) {
167        self.buffer.push(val);
168        if let Some(value) = self.indices.last_mut() {
169            *value.last_mut().unwrap() += TBuffer::TI::ONE;
170        }
171    }
172    #[inline]
173    /// # Safety
174    ///
175    /// The caller must ensure that `self.buffer_len()` < `self.buffer_capacity()`
176    pub unsafe fn push_to_last_row_unchecked(&mut self, val: TVal) {
177        unsafe { self.buffer.unchecked_push(val) };
178        if let Some(value) = self.indices.last_mut() {
179            unsafe { *value.last_mut().unwrap_unchecked() += TBuffer::TI::ONE };
180        }
181    }
182    /// # Example
183    ///
184    /// ```
185    /// use jaggedarray::jagged_array::JaggedArray;
186    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
187    /// data.new_row::<0>();
188    /// data.push_to_last_row(1);
189    /// assert!(data.pop_from_last_row() == Some(1));
190    /// ```
191    #[inline]
192    pub fn pop_from_last_row(&mut self) -> Option<TVal> {
193        let mut iter: std::iter::Rev<std::slice::IterMut<<TBuffer as VecLike>::TI>> =
194            self.indices.last_mut().unwrap().iter_mut().rev();
195        let last = iter.next().unwrap();
196        if *last != TBuffer::TI::ZERO && iter.next().unwrap() < last {
197            *last -= TBuffer::TI::ONE;
198            self.buffer.pop()
199        } else {
200            None
201        }
202    }
203    /// # Example
204    ///
205    /// ```
206    /// use jaggedarray::jagged_array::JaggedArray;
207    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
208    /// data.new_row::<0>();
209    /// data.extend_last_row([1,2,3].into_iter());
210    /// assert!(data[[0,0]] == 1);
211    /// assert!(data[[0,1]] == 2);
212    /// assert!(data[[0,2]] == 3);
213    /// ```
214    #[inline]
215    pub fn extend_last_row(&mut self, values: impl Iterator<Item = TVal>) {
216        let initial = self.buffer.len();
217        self.buffer.extend(values);
218        *self.indices.last_mut().unwrap().last_mut().unwrap() +=
219            (self.buffer.len() - initial).as_();
220    }
221    /// # Example
222    ///
223    /// ```
224    /// use jaggedarray::jagged_array::JaggedArray;
225    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
226    /// data.new_row::<0>();
227    /// data.extend_last_row_from_slice(&[1,2,3]);
228    /// assert!(data[[0,0]] == 1);
229    /// assert!(data[[0,1]] == 2);
230    /// assert!(data[[0,2]] == 3);
231    /// ```
232    #[inline]
233    pub fn extend_last_row_from_slice(&mut self, values: &[TVal])
234    where
235        TVal: Clone,
236    {
237        let initial = self.buffer.len();
238        self.buffer.extend_from_slice(values);
239        *self.indices.last_mut().unwrap().last_mut().unwrap() +=
240            (self.buffer.len() - initial).as_();
241    }
242    /// # Example
243    ///
244    /// ```
245    /// use jaggedarray::jagged_array::JaggedArray;
246    /// use crate::jaggedarray::jagged_array::JaggedArrayViewTrait;
247    /// let mut data = JaggedArray::<usize, Vec<u16>, 3>::new();
248    /// data.new_row::<0>();
249    /// data.new_row::<1>();
250    /// data.extend_last_row_from_slice(&[1,2,3]);
251    /// let mut other = JaggedArray::<usize, Vec<u16>, 2>::new();
252    /// other.new_row::<0>();
253    /// other.extend_last_row_from_slice(&[4,5,6]);
254    /// data.append_from_view(other.view::<0,2>([]));
255    /// data.append_from_view(other.view::<1,1>([0]));
256    /// assert!(data[[0,0,0]] == 1);
257    /// assert!(data[[0,0,1]] == 2);
258    /// assert!(data[[0,0,2]] == 3);
259    /// assert!(data[[0,1,0]] == 4);
260    /// assert!(data[[0,1,1]] == 5);
261    /// assert!(data[[0,1,2]] == 6);
262    /// assert!(data[[0,1,3]] == 4);
263    /// assert!(data[[0,1,4]] == 5);
264    /// assert!(data[[0,1,5]] == 6);
265    /// ```
266    pub fn append_from_view<const M: usize>(&mut self, other: JaggedArrayView<TVal, TBuffer::TI, M>)
267    where
268        U<N>: std::ops::Sub<U<M>>,
269        <U<N> as std::ops::Sub<U<M>>>::Output: Unsigned,
270        U<M>: std::ops::Sub<B1>,
271        <U<M> as std::ops::Sub<B1>>::Output: ArrayLength,
272        U<M>: ArrayLength,
273        Const<N>: ToUInt,
274        Const<M>: ToUInt,
275        TVal: Clone,
276    {
277        let skipped = N - M;
278        if skipped == N - 1 {
279            *self.indices[skipped - 1].last_mut().unwrap() += other.len().as_();
280        } else if skipped != 0 {
281            *self.indices[skipped - 1].last_mut().unwrap() += TBuffer::TI::ONE;
282        }
283        for (dst, src) in zip(self.indices.iter_mut().skip(skipped), other.indices.iter()) {
284            let last = *dst.last().unwrap();
285            dst.extend(src.iter().skip(1).map(|&x| x + last));
286        }
287        self.buffer.extend_from_slice(other.buffer);
288    }
289    /// # Example
290    ///
291    /// ```
292    /// use jaggedarray::jagged_array::JaggedArray;
293    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
294    /// data.new_row::<0>();
295    /// data.extend_last_row_from_slice(&[1,2,3]);
296    /// let mut other = JaggedArray::<usize, Vec<u16>, 2>::new();
297    /// other.new_row::<0>();
298    /// other.extend_last_row_from_slice(&[4,5,6]);
299    /// data.append(other);
300    /// assert!(data[[0,0]] == 1);
301    /// assert!(data[[0,1]] == 2);
302    /// assert!(data[[0,2]] == 3);
303    /// assert!(data[[1,0]] == 4);
304    /// assert!(data[[1,1]] == 5);
305    /// assert!(data[[1,2]] == 6);
306    /// ```
307    pub fn append<const M: usize>(&mut self, other: JaggedArray<TVal, TBuffer, M>)
308    where
309        U<N>: std::ops::Sub<U<M>>,
310        <U<N> as std::ops::Sub<U<M>>>::Output: Unsigned,
311        U<M>: std::ops::Sub<B1>,
312        <U<M> as std::ops::Sub<B1>>::Output: ArrayLength,
313        U<M>: ArrayLength,
314        Const<N>: ToUInt,
315        Const<M>: ToUInt,
316    {
317        let skipped = N - M;
318        if skipped == N - 1 {
319            *self.indices[skipped - 1].last_mut().unwrap() += other.len().as_();
320        } else if skipped != 0 {
321            *self.indices[skipped - 1].last_mut().unwrap() += TBuffer::TI::ONE;
322        }
323        for (dst, src) in zip(self.indices.iter_mut().skip(skipped), other.indices.iter()) {
324            let last = *dst.last().unwrap();
325            dst.extend(src.iter().skip(1).map(|&x| x + last));
326        }
327        self.buffer.extend(other.buffer);
328    }
329    /// # Example
330    ///
331    /// ```
332    /// use jaggedarray::jagged_array::JaggedArray;
333    /// use crate::jaggedarray::jagged_array::JaggedArrayViewTrait;
334    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
335    /// data.new_row::<0>();
336    /// data.extend_last_row_from_slice(&[1,2,3]);
337    /// data.remove_last_row::<0>();
338    /// assert!(data.is_empty());
339    /// ```
340    // It may be possible to implement a drain-like variant of this method
341    pub fn remove_last_row<const DIM: usize>(&mut self) -> bool
342    where
343        U<N>: std::ops::Sub<U<DIM>>,
344        Sub1<<U<N> as std::ops::Sub<U<DIM>>>::Output>: Unsigned + NonZero,
345        <U<N> as std::ops::Sub<U<DIM>>>::Output: std::ops::Sub<typenum::B1>,
346        U<DIM>: ArrayLength,
347        Const<N>: ToUInt,
348        Const<DIM>: ToUInt,
349    {
350        self.truncate::<DIM>(self.indices[DIM].len() - 2)
351    }
352    /// # Example
353    ///
354    /// ```
355    /// use jaggedarray::jagged_array::JaggedArray;
356    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
357    /// data.new_row::<0>();
358    /// data.extend_last_row_from_slice(&[1, 2, 3]);
359    /// data.new_row::<0>();
360    /// data.extend_last_row_from_slice(&[4, 5, 6]);
361    /// data.new_row::<0>();
362    /// data.extend_last_row_from_slice(&[7, 8, 9]);
363    /// data.remove_rows(1..2);
364    /// assert!(data[[0, 0]] == 1);
365    /// assert!(data[[0, 1]] == 2);
366    /// assert!(data[[0, 2]] == 3);
367    /// assert!(data[[1, 0]] == 7);
368    /// assert!(data[[1, 1]] == 8);
369    /// assert!(data[[1, 2]] == 9);
370    /// ```
371    pub fn remove_rows(&mut self, mut range: Range<usize>)
372    where
373        U<N>: NonZero,
374    {
375        let (first, second) = self.indices.split_at_mut(1);
376        let first = &mut first[0];
377        let start = first[range.start].as_();
378        let end = first[range.end].as_();
379        first.remove_range(range.clone());
380        for i in first[range.start..].iter_mut() {
381            *i -= (end - start).as_();
382        }
383        range.start = start;
384        range.end = end;
385        for index in second {
386            let end = index[start].as_();
387            let start = index[start - 1].as_();
388            index.remove_range(range.clone());
389            for i in index[start..].iter_mut() {
390                *i -= (end - start).as_();
391            }
392            range.start = start;
393            range.end = end;
394        }
395        self.buffer.drain(range).for_each(drop);
396    }
397    /// # Example
398    ///
399    /// ```
400    /// use jaggedarray::jagged_array::JaggedArray;
401    /// use crate::jaggedarray::jagged_array::JaggedArrayViewTrait;
402    /// let mut data = JaggedArray::<usize, Vec<u16>, 2>::new();
403    /// data.new_row::<0>();
404    /// data.extend_last_row_from_slice(&[1,2,3]);
405    /// data.truncate::<0>(1);
406    /// assert!(data[[0,0]] == 1);
407    /// ```
408    pub fn truncate<const DIM: usize>(&mut self, row_length: usize) -> bool {
409        if row_length < self.indices[DIM].len() {
410            self.indices[DIM].truncate(row_length + 1);
411            let mut end = self.indices[DIM][row_length];
412            for index in self.indices.iter_mut().skip(DIM + 1) {
413                index.truncate(end.as_() + 1);
414                end = *index.last().unwrap();
415            }
416            self.buffer.truncate(end.as_());
417            true
418        } else {
419            false
420        }
421    }
422}
423pub trait JaggedArrayViewTrait<TVal, TNum, const N: usize>: Index<[usize; N]>
424where
425    TNum: AsPrimitive<usize> + Num,
426    U<N>: std::ops::Sub<B1>,
427    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
428    Const<N>: ToUInt,
429{
430    fn is_empty(&self) -> bool;
431    fn len(&self) -> usize;
432    fn view<const M: usize, const R: usize>(
433        &self,
434        index: [usize; M],
435    ) -> JaggedArrayView<TVal, TNum, R>
436    where
437        U<N>: std::ops::Sub<U2> + std::ops::Sub<typenum::B1>,
438        <U<N> as std::ops::Sub<U2>>::Output: ArrayLength,
439        <U<N> as std::ops::Sub<typenum::B1>>::Output: std::ops::Sub<typenum::B1>,
440        <<U<N> as std::ops::Sub<typenum::B1>>::Output as std::ops::Sub<typenum::B1>>::Output:
441            ArrayLength,
442        U<N>: std::ops::Sub<U<M>>,
443        <U<N> as std::ops::Sub<U<M>>>::Output: IsEqual<U<R>>,
444        U<R>: std::ops::Sub<B1>,
445        <U<R> as std::ops::Sub<B1>>::Output: ArrayLength,
446        <<U<N> as std::ops::Sub<U<M>>>::Output as IsEqual<U<R>>>::Output: NonZero,
447        Const<N>: ToUInt,
448        Const<M>: ToUInt,
449        Const<R>: ToUInt;
450    /// # Safety
451    ///
452    /// The caller must ensure that every value in `index` is within the respective bounds of the view
453    unsafe fn view_unchecked<const M: usize, const R: usize>(
454        &self,
455        index: [usize; M],
456    ) -> JaggedArrayView<TVal, TNum, R>
457    where
458        U<N>: std::ops::Sub<U2> + std::ops::Sub<typenum::B1>,
459        <U<N> as std::ops::Sub<U2>>::Output: ArrayLength,
460        <U<N> as std::ops::Sub<typenum::B1>>::Output: std::ops::Sub<typenum::B1>,
461        <<U<N> as std::ops::Sub<typenum::B1>>::Output as std::ops::Sub<typenum::B1>>::Output:
462            ArrayLength,
463        U<N>: std::ops::Sub<U<M>>,
464        <U<N> as std::ops::Sub<U<M>>>::Output: IsEqual<U<R>>,
465        U<R>: std::ops::Sub<B1>,
466        <U<R> as std::ops::Sub<B1>>::Output: ArrayLength,
467        <<U<N> as std::ops::Sub<U<M>>>::Output as IsEqual<U<R>>>::Output: NonZero,
468        Const<N>: ToUInt,
469        Const<M>: ToUInt,
470        Const<R>: ToUInt;
471    /// # Safety
472    ///
473    /// The caller must ensure that `index` is within the bounds of the view
474    unsafe fn get_unchecked(&self, index: [usize; N]) -> &TVal;
475    fn get(&self, index: [usize; N]) -> Option<&TVal>;
476    fn to_owned(self) -> JaggedArrayOwnedView<TVal, TNum, N>
477    where
478        TVal: Clone;
479}
480
481pub trait JaggedArrayMutViewTrait<TVal, TNum, const N: usize>:
482    JaggedArrayViewTrait<TVal, TNum, N> + IndexMut<[usize; N]>
483where
484    TNum: AsPrimitive<usize> + Num,
485    U<N>: std::ops::Sub<B1>,
486    <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
487    Const<N>: ToUInt,
488{
489    fn view_mut<const M: usize, const R: usize>(
490        &mut self,
491        index: [usize; M],
492    ) -> JaggedArrayMutView<TVal, TNum, R>
493    where
494        U<N>: std::ops::Sub<U2> + std::ops::Sub<typenum::B1>,
495        <U<N> as std::ops::Sub<U2>>::Output: ArrayLength,
496        <U<N> as std::ops::Sub<typenum::B1>>::Output: std::ops::Sub<typenum::B1>,
497        <<U<N> as std::ops::Sub<typenum::B1>>::Output as std::ops::Sub<typenum::B1>>::Output:
498            ArrayLength,
499        U<N>: std::ops::Sub<U<M>>,
500        <U<N> as std::ops::Sub<U<M>>>::Output: IsEqual<U<R>>,
501        U<R>: std::ops::Sub<B1>,
502        <U<R> as std::ops::Sub<B1>>::Output: ArrayLength,
503        <<U<N> as std::ops::Sub<U<M>>>::Output as IsEqual<U<R>>>::Output: NonZero,
504        Const<N>: ToUInt,
505        Const<M>: ToUInt,
506        Const<R>: ToUInt;
507}
508
509pub trait JaggedArray1DViewTrait<TVal, TNum>
510where
511    TNum: AsPrimitive<usize> + Num,
512{
513    fn as_slice(&self) -> &[TVal];
514}
515pub trait JaggedArray1DMutViewTrait<TVal, TNum>
516where
517    TNum: AsPrimitive<usize> + Num,
518{
519    fn as_slice_mut(&mut self) -> &mut [TVal];
520}
521macro_rules! impl_view {
522    ($num:ty, $typ:ident< $( $gen:tt ),+>,$type1:ty,$type2:path) => {
523        impl<$( $gen ),+,const N:usize> JaggedArrayViewTrait<TVal, $num, N>
524            for $typ<$($gen),+, N>
525        where $type1:$type2,
526        $num: AsPrimitive<usize>+Num+ConstOne+ConstZero,
527        U<N>: std::ops::Sub<B1>,
528        U<N>:ArrayLength,
529        <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
530        Const<N>: ToUInt,
531        {
532            #[inline]
533            fn len(&self) -> usize {
534                match self.indices.first()
535                {
536                    Some(index)=>index.len()-1,
537                    None=>self.buffer.len()
538                }
539            }
540            #[inline]
541            fn is_empty(&self) -> bool {
542                self.buffer.is_empty()
543            }
544            /// Rust const generics does not support arithmetic, so we have to specify the view's dimension(R) as well
545            fn view<const M: usize, const R: usize>(
546                &self,
547                index: [usize; M],
548            ) -> JaggedArrayView<TVal, $num, R>
549            where
550            U<N>: std::ops::Sub<U2> + std::ops::Sub<typenum::B1>,
551            <U<N> as std::ops::Sub<U2>>::Output: ArrayLength,
552            <U<N> as std::ops::Sub<typenum::B1>>::Output: std::ops::Sub<typenum::B1>,
553            <<U<N> as std::ops::Sub<typenum::B1>>::Output as std::ops::Sub<typenum::B1>>::Output:
554                ArrayLength,
555            U<N>: std::ops::Sub<U<M>>,
556            <U<N> as std::ops::Sub<U<M>>>::Output: IsEqual<U<R>>,
557            U<R>: std::ops::Sub<B1>,
558            <U<R> as std::ops::Sub<B1>>::Output: ArrayLength,
559            <<U<N> as std::ops::Sub<U<M>>>::Output as IsEqual<U<R>>>::Output: NonZero,
560            Const<N>: ToUInt,
561            Const<M>: ToUInt,
562            Const<R>: ToUInt
563            {
564                let m = (M+1).min(self.indices.len());
565                let (first,remaining) = self.indices.split_at(m);
566                let (index_buffer, self_indices) = first.split_first().unwrap();
567                let mut index_buffer = &index_buffer[..];
568                for (&i, idx) in zip(index.iter(), self_indices.iter()) {
569                    index_buffer = &idx[index_buffer[i].as_()..index_buffer[i + 1].as_() + 1]
570                }
571                let mut result = GenericArray::<&[$num], Sub1<U<R>>>::uninit();
572                let (indices, buffer) = if R > 1 {
573                    result[0].write(index_buffer);
574                    for (src,dst) in remaining.iter().zip(result.iter_mut().skip(1)) {
575                        dst.write(src);
576                    }
577                    // SAFETY: Now safe as we initialized all elements from 0 to R-1
578                    (
579                        unsafe { GenericArray::assume_init(result) },
580                        &self.buffer[..],
581                    )
582                } else {
583                    let start_index = index_buffer[*index.last().unwrap()].as_();
584                    let end_index = index_buffer[*index.last().unwrap() + 1].as_();
585                    // SAFETY: zero-sized arrays don't need initialization
586                    (
587                        unsafe { GenericArray::assume_init(result) },
588                        &self.buffer[start_index..end_index],
589                    )
590                };
591                JaggedArrayView { indices, buffer }
592            }
593            /// Rust const generics does not support arithmetic, so we have to specify the view's dimension(R) as well
594            unsafe fn view_unchecked<const M: usize, const R: usize>(
595                &self,
596                index: [usize; M],
597            ) -> JaggedArrayView<TVal, $num, R>
598            where
599            U<N>: std::ops::Sub<U2> + std::ops::Sub<typenum::B1>,
600            <U<N> as std::ops::Sub<U2>>::Output: ArrayLength,
601            <U<N> as std::ops::Sub<typenum::B1>>::Output: std::ops::Sub<typenum::B1>,
602            <<U<N> as std::ops::Sub<typenum::B1>>::Output as std::ops::Sub<typenum::B1>>::Output:
603                ArrayLength,
604            U<N>: std::ops::Sub<U<M>>,
605            <U<N> as std::ops::Sub<U<M>>>::Output: IsEqual<U<R>>,
606            U<R>: std::ops::Sub<B1>,
607            <U<R> as std::ops::Sub<B1>>::Output: ArrayLength,
608            <<U<N> as std::ops::Sub<U<M>>>::Output as IsEqual<U<R>>>::Output: NonZero,
609            Const<N>: ToUInt,
610            Const<M>: ToUInt,
611            Const<R>: ToUInt
612            {
613                let mut index_buffer = self.indices.get_unchecked(0).get_unchecked(..);
614                let m = (M+1).min(self.indices.len());
615                for i in 1..m {
616                    index_buffer = self.indices.get_unchecked(i).get_unchecked((*index_buffer.get_unchecked(*index.get_unchecked(i-1))).as_()
617                    ..(*index_buffer.get_unchecked(*index.get_unchecked(i-1)+1)+<$num>::ONE).as_());
618                }
619                let mut result = GenericArray::<&[$num], Sub1<U<R>>>::uninit();
620                let (indices, buffer) = if R > 1 {
621                    result.get_unchecked_mut(0).write(index_buffer);
622                    for i in m..self.indices.len() {
623                        result.get_unchecked_mut(i-m+1).write(self.indices.get_unchecked(i));
624                    }
625                    // SAFETY: Now safe as we initialized all elements from 0 to R-1
626                    (
627                        unsafe { GenericArray::assume_init(result) },
628                        self.buffer.get_unchecked(..),
629                    )
630                } else {
631                    let last = *index.get_unchecked(M-1);
632                    let start_index = (*index_buffer.get_unchecked(last)).as_();
633                    let end_index = (*index_buffer.get_unchecked(last+1)).as_();
634                    // SAFETY: zero-sized arrays don't need initialization
635                    (
636                        unsafe { GenericArray::assume_init(result) },
637                        self.buffer.get_unchecked(start_index..end_index),
638                    )
639                };
640                JaggedArrayView { indices, buffer }
641            }
642            unsafe fn get_unchecked(&self, index: [usize; N]) -> &TVal {
643                if N > 1 {
644                    let mut buffer_ptr = self.indices.get_unchecked(0).get_unchecked(..).as_ptr();
645                    for i in 1..N-1 {
646                        let idx = self.indices.get_unchecked(i);
647                        let id = (*index.get_unchecked(i-1));
648                        let s = *buffer_ptr.add(id);
649                        buffer_ptr = idx.as_ptr().add(s.as_());
650                    }
651                    let last = *index.get_unchecked(N - 2);
652                    let start_index = (*buffer_ptr.add(last)).as_();
653                    self.buffer.get_unchecked(start_index+*index.get_unchecked(N - 1))
654                } else {
655                    self.buffer.get_unchecked(*index.get_unchecked(0))
656                }
657            }
658
659            fn get(&self, index:[usize;N])->Option<&TVal>{
660                if N > 1 {
661                    let mut buffer = &self.indices[0][..];
662                    for (&i, idx) in zip(index.iter(), self.indices[1..].iter()) {
663                        buffer = &idx.get(buffer.get(i)?.as_()..buffer.get(i + 1)?.as_() + 1)?
664                    }
665                    let last = index[index.len() - 2];
666                    let start_index = buffer.get(last)?.as_();
667                    let end_index = buffer.get(last + 1)?.as_();
668                    self.buffer.get(start_index..end_index)?.get(index[index.len() - 1])
669                } else {
670                    self.buffer.get(index[0])
671                }
672            }
673
674            fn to_owned(self) -> JaggedArrayOwnedView<TVal, $num, N> where TVal:Clone {
675                let indices = self.indices.iter().map(|idx| idx.to_vec().into_boxed_slice()).collect();
676                let buffer = self.buffer.to_vec().into_boxed_slice();
677                JaggedArrayOwnedView { indices, buffer }
678            }
679        }
680
681        impl<$( $gen ),+,const N:usize> Index<[usize; N]> for $typ<$($gen),+, N>
682        where
683        $num: AsPrimitive<usize>+Num,
684        $type1:$type2,
685            U<N>: std::ops::Sub<B1>,
686            <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
687            Const<N>: ToUInt,
688        {
689            type Output = TVal;
690            fn index(&self, index: [usize; N]) -> &Self::Output {
691                if N > 1 {
692                    let mut buffer = &self.indices[0][..];
693                    for (&i, idx) in zip(index.iter(), self.indices[1..].iter()) {
694                        buffer = &idx[buffer[i].as_()..buffer[i + 1].as_() + 1]
695                    }
696                    let last = index[index.len() - 2];
697                    let start_index = buffer[last].as_();
698                    let end_index = buffer[last + 1].as_();
699                    &self.buffer[start_index..end_index][index[index.len() - 1]]
700                } else {
701                    &self.buffer[index[0]]
702                }
703            }
704        }
705    };
706}
707
708macro_rules! impl_view_mut {
709    ($num:ty, $typ:ident< $( $gen:tt ),+>,$type1:ty,$type2:path) => {
710        impl<$( $gen ),+,const N:usize> JaggedArrayMutViewTrait<TVal, $num, N>
711            for $typ<$($gen),+, N>
712        where $type1:$type2,
713        $num: AsPrimitive<usize>+Num+ConstOne+ConstZero,
714        U<N>: std::ops::Sub<B1>,
715        U<N>:ArrayLength,
716        <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
717        Const<N>: ToUInt,
718        {
719            /// Rust const generics does not support arithmetic, so we have to specify the view's dimension(R) as well
720            fn view_mut<const M: usize, const R: usize>(
721                &mut self,
722                index: [usize; M],
723            ) -> JaggedArrayMutView<TVal, $num, R>
724            where
725            U<N>: std::ops::Sub<U2> + std::ops::Sub<typenum::B1>,
726            <U<N> as std::ops::Sub<U2>>::Output: ArrayLength,
727            <U<N> as std::ops::Sub<typenum::B1>>::Output: std::ops::Sub<typenum::B1>,
728            <<U<N> as std::ops::Sub<typenum::B1>>::Output as std::ops::Sub<typenum::B1>>::Output:
729                ArrayLength,
730            U<N>: std::ops::Sub<U<M>>,
731            <U<N> as std::ops::Sub<U<M>>>::Output: IsEqual<U<R>>,
732            U<R>: std::ops::Sub<B1>,
733            <U<R> as std::ops::Sub<B1>>::Output: ArrayLength,
734            <<U<N> as std::ops::Sub<U<M>>>::Output as IsEqual<U<R>>>::Output: NonZero,
735            Const<N>: ToUInt,
736            Const<M>: ToUInt,
737            Const<R>: ToUInt
738            {
739                let m = (M+1).min(self.indices.len());
740                let (first,remaining) = self.indices.split_at_mut(m);
741                let (index_buffer, self_indices) = first.split_first_mut().unwrap();
742                let mut index_buffer = &mut index_buffer[..];
743                for (&i, idx) in zip(index.iter(), self_indices.iter_mut()) {
744                    index_buffer = &mut idx[index_buffer[i].as_()..index_buffer[i + 1].as_() + 1]
745                }
746                let mut result = GenericArray::<&mut [$num], Sub1<U<R>>>::uninit();
747                let (indices, buffer) = if R > 1 {
748                    result[0].write(index_buffer);
749                    for (src,dst) in remaining.iter_mut().zip(result.iter_mut().skip(1)) {
750                        dst.write(src);
751                    }
752                    // SAFETY: Now safe as we initialized all elements from 0 to R-1
753                    (
754                        unsafe { GenericArray::assume_init(result) },
755                        &mut self.buffer[..],
756                    )
757                } else {
758                    let start_index = index_buffer[*index.last().unwrap()].as_();
759                    let end_index = index_buffer[*index.last().unwrap() + 1].as_();
760                    // SAFETY: zero-sized arrays don't need initialization
761                    (
762                        unsafe { GenericArray::assume_init(result) },
763                        &mut self.buffer[start_index..end_index],
764                    )
765                };
766                JaggedArrayMutView { indices, buffer }
767            }
768        }
769
770        impl<$( $gen ),+,const N:usize> IndexMut<[usize; N]> for $typ<$($gen),+, N>
771        where $type1:$type2,
772        $num: AsPrimitive<usize>+Num,
773            U<N>: std::ops::Sub<B1> + ArrayLength,
774            <U<N> as std::ops::Sub<B1>>::Output: ArrayLength,
775            Const<N>: ToUInt,
776        {
777            fn index_mut(&mut self, index: [usize; N]) -> &mut TVal {
778                if N > 1 {
779                    let mut buffer = &self.indices[0][..];
780                    for (&i, idx) in zip(index.iter(), self.indices[1..].iter()) {
781                        buffer = &idx[buffer[i].as_()..buffer[i + 1].as_() + 1]
782                    }
783                    let start_index = buffer[index[index.len() - 2]].as_();
784                    let end_index = buffer[index[index.len() - 2] + 1].as_();
785                    &mut self.buffer[start_index..end_index][index[index.len() - 1]]
786                } else {
787                    &mut self.buffer[index[0]]
788                }
789            }
790        }
791    };
792}
793macro_rules! impl_view1d_owned {
794    ($num:ty, $typ:ident< $( $gen:tt ),+>,$type1:ty,$type2:path) => {
795        impl<$( $gen ),+> JaggedArray1DViewTrait<TVal, $num> for $typ<$($gen),+,1> where $num: AsPrimitive<usize> + Num,$type1:$type2
796        {
797            fn as_slice(&self) -> &[TVal] {
798                &self.buffer
799            }
800        }
801    };
802}
803macro_rules! impl_view_mut1d_owned {
804    ($num:ty, $typ:ident< $( $gen:tt ),+>,$type1:ty,$type2:path) => {
805        impl<$( $gen ),+> JaggedArray1DMutViewTrait<TVal, $num> for $typ<$($gen),+,1> where $num: AsPrimitive<usize> + Num,$type1:$type2
806        {
807            fn as_slice_mut(&mut self) -> &mut [TVal] {
808                &mut self.buffer
809            }
810        }
811    };
812}
813
814impl<'a, TVal, TNum> JaggedArrayView<'a, TVal, TNum, 1>
815where
816    TNum: AsPrimitive<usize> + Num + NumAssignOps + std::cmp::PartialOrd + ConstOne + ConstZero,
817    usize: num::traits::AsPrimitive<TNum>,
818{
819    pub fn as_slice(&self) -> &'a [TVal] {
820        self.buffer
821    }
822}
823
824impl<'a, TVal, TNum> JaggedArrayMutView<'a, TVal, TNum, 1>
825where
826    TNum: AsPrimitive<usize> + Num + NumAssignOps + std::cmp::PartialOrd + ConstOne + ConstZero,
827    usize: num::traits::AsPrimitive<TNum>,
828{
829    pub fn as_slice<'b: 'a>(&'b self) -> &'a [TVal] {
830        // We need this mysterious lifetime to make the borrow checker happy
831        self.buffer
832    }
833
834    pub fn as_slice_mut<'b: 'a>(&'b mut self) -> &'a mut [TVal] {
835        self.buffer
836    }
837}
838
839impl_view!(<TBuffer as VecLike>::TI,JaggedArray<TVal, TBuffer>,TBuffer,VecLike);
840impl_view!(TNum, JaggedArrayView<'a, TVal, TNum>, TNum, Num);
841impl_view!(TNum, JaggedArrayMutView<'a, TVal, TNum>, TNum, Num);
842impl_view!(TNum,JaggedArrayOwnedView<TVal, TNum>,TNum,Num);
843impl_view1d_owned!(<TBuffer as VecLike>::TI,JaggedArray<TVal, TBuffer>,TBuffer,VecLike);
844impl_view1d_owned!(TNum,JaggedArrayOwnedView<TVal, TNum>,TNum,Num);
845impl_view_mut!(<TBuffer as VecLike>::TI,JaggedArray<TVal, TBuffer>,TBuffer,VecLike);
846impl_view_mut!(TNum, JaggedArrayMutView<'a, TVal, TNum>, TNum, Num);
847impl_view_mut!(TNum,JaggedArrayOwnedView<TVal, TNum>,TNum,Num);
848impl_view_mut1d_owned!(TNum,JaggedArrayOwnedView<TVal, TNum>,TNum,Num);
jaggedarray/jagged_array.rs

jaggedarray/
jagged_array.rs
