1//! Useful traits for manipulating sequences of data stored in `GenericArray`s
2
3use super::*;
4use core::ops::{Add, Sub};
5use core::mem::MaybeUninit;
6use core::ptr;
7use typenum::operator_aliases::*;
8
9/// Defines some sequence with an associated length and iteration capabilities.
10///
11/// This is useful for passing N-length generic arrays as generics.
12pub unsafe trait GenericSequence<T>: Sized + IntoIterator {
13 /// `GenericArray` associated length
14 type Length: ArrayLength<T>;
15
16 /// Concrete sequence type used in conjuction with reference implementations of `GenericSequence`
17 type Sequence: GenericSequence<T, Length = Self::Length> + FromIterator<T>;
18
19 /// Initializes a new sequence instance using the given function.
20 ///
21 /// If the generator function panics while initializing the sequence,
22 /// any already initialized elements will be dropped.
23 fn generate<F>(f: F) -> Self::Sequence
24 where
25 F: FnMut(usize) -> T;
26
27 #[doc(hidden)]
28 fn inverted_zip<B, U, F>(
29 self,
30 lhs: GenericArray<B, Self::Length>,
31 mut f: F,
32 ) -> MappedSequence<GenericArray<B, Self::Length>, B, U>
33 where
34 GenericArray<B, Self::Length>: GenericSequence<B, Length = Self::Length>
35 + MappedGenericSequence<B, U>,
36 Self: MappedGenericSequence<T, U>,
37 Self::Length: ArrayLength<B> + ArrayLength<U>,
38 F: FnMut(B, Self::Item) -> U,
39 {
40 unsafe {
41 let mut left = ArrayConsumer::new(lhs);
42
43 let (left_array_iter, left_position) = left.iter_position();
44
45 FromIterator::from_iter(left_array_iter.zip(self.into_iter()).map(
46 |(l, right_value)| {
47 let left_value = ptr::read(l);
48
49 *left_position += 1;
50
51 f(left_value, right_value)
52 },
53 ))
54 }
55 }
56
57 #[doc(hidden)]
58 fn inverted_zip2<B, Lhs, U, F>(self, lhs: Lhs, mut f: F) -> MappedSequence<Lhs, B, U>
59 where
60 Lhs: GenericSequence<B, Length = Self::Length> + MappedGenericSequence<B, U>,
61 Self: MappedGenericSequence<T, U>,
62 Self::Length: ArrayLength<B> + ArrayLength<U>,
63 F: FnMut(Lhs::Item, Self::Item) -> U,
64 {
65 FromIterator::from_iter(lhs.into_iter().zip(self.into_iter()).map(|(l, r)| f(l, r)))
66 }
67}
68
69/// Accessor for `GenericSequence` item type, which is really `IntoIterator::Item`
70///
71/// For deeply nested generic mapped sequence types, like shown in `tests/generics.rs`,
72/// this can be useful for keeping things organized.
73pub type SequenceItem<T> = <T as IntoIterator>::Item;
74
75unsafe impl<'a, T: 'a, S: GenericSequence<T>> GenericSequence<T> for &'a S
76where
77 &'a S: IntoIterator,
78{
79 type Length = S::Length;
80 type Sequence = S::Sequence;
81
82 #[inline]
83 fn generate<F>(f: F) -> Self::Sequence
84 where
85 F: FnMut(usize) -> T,
86 {
87 S::generate(f)
88 }
89}
90
91unsafe impl<'a, T: 'a, S: GenericSequence<T>> GenericSequence<T> for &'a mut S
92where
93 &'a mut S: IntoIterator,
94{
95 type Length = S::Length;
96 type Sequence = S::Sequence;
97
98 #[inline]
99 fn generate<F>(f: F) -> Self::Sequence
100 where
101 F: FnMut(usize) -> T,
102 {
103 S::generate(f)
104 }
105}
106
107/// Defines any `GenericSequence` which can be lengthened or extended by appending
108/// or prepending an element to it.
109///
110/// Any lengthened sequence can be shortened back to the original using `pop_front` or `pop_back`
111pub unsafe trait Lengthen<T>: Sized + GenericSequence<T> {
112 /// `GenericSequence` that has one more element than `Self`
113 type Longer: Shorten<T, Shorter = Self>;
114
115 /// Returns a new array with the given element appended to the end of it.
116 ///
117 /// Example:
118 ///
119 /// ```rust
120 /// # use generic_array::{arr, sequence::Lengthen};
121 /// # fn main() {
122 /// let a = arr![i32; 1, 2, 3];
123 ///
124 /// let b = a.append(4);
125 ///
126 /// assert_eq!(b, arr![i32; 1, 2, 3, 4]);
127 /// # }
128 /// ```
129 fn append(self, last: T) -> Self::Longer;
130
131 /// Returns a new array with the given element prepended to the front of it.
132 ///
133 /// Example:
134 ///
135 /// ```rust
136 /// # use generic_array::{arr, sequence::Lengthen};
137 /// # fn main() {
138 /// let a = arr![i32; 1, 2, 3];
139 ///
140 /// let b = a.prepend(4);
141 ///
142 /// assert_eq!(b, arr![i32; 4, 1, 2, 3]);
143 /// # }
144 /// ```
145 fn prepend(self, first: T) -> Self::Longer;
146}
147
148/// Defines a `GenericSequence` which can be shortened by removing the first or last element from it.
149///
150/// Additionally, any shortened sequence can be lengthened by
151/// appending or prepending an element to it.
152pub unsafe trait Shorten<T>: Sized + GenericSequence<T> {
153 /// `GenericSequence` that has one less element than `Self`
154 type Shorter: Lengthen<T, Longer = Self>;
155
156 /// Returns a new array without the last element, and the last element.
157 ///
158 /// Example:
159 ///
160 /// ```rust
161 /// # use generic_array::{arr, sequence::Shorten};
162 /// # fn main() {
163 /// let a = arr![i32; 1, 2, 3, 4];
164 ///
165 /// let (init, last) = a.pop_back();
166 ///
167 /// assert_eq!(init, arr![i32; 1, 2, 3]);
168 /// assert_eq!(last, 4);
169 /// # }
170 /// ```
171 fn pop_back(self) -> (Self::Shorter, T);
172
173 /// Returns a new array without the first element, and the first element.
174 /// Example:
175 ///
176 /// ```rust
177 /// # use generic_array::{arr, sequence::Shorten};
178 /// # fn main() {
179 /// let a = arr![i32; 1, 2, 3, 4];
180 ///
181 /// let (head, tail) = a.pop_front();
182 ///
183 /// assert_eq!(head, 1);
184 /// assert_eq!(tail, arr![i32; 2, 3, 4]);
185 /// # }
186 /// ```
187 fn pop_front(self) -> (T, Self::Shorter);
188}
189
190unsafe impl<T, N: ArrayLength<T>> Lengthen<T> for GenericArray<T, N>
191where
192 N: Add<B1>,
193 Add1<N>: ArrayLength<T>,
194 Add1<N>: Sub<B1, Output = N>,
195 Sub1<Add1<N>>: ArrayLength<T>,
196{
197 type Longer = GenericArray<T, Add1<N>>;
198
199 fn append(self, last: T) -> Self::Longer {
200 let mut longer: MaybeUninit<Self::Longer> = MaybeUninit::uninit();
201
202 // Note this is *mut Self, so add(1) increments by the whole array
203 let out_ptr = longer.as_mut_ptr() as *mut Self;
204
205 unsafe {
206 // write self first
207 ptr::write(out_ptr, self);
208 // increment past self, then write the last
209 ptr::write(out_ptr.add(1) as *mut T, last);
210
211 longer.assume_init()
212 }
213 }
214
215 fn prepend(self, first: T) -> Self::Longer {
216 let mut longer: MaybeUninit<Self::Longer> = MaybeUninit::uninit();
217
218 // Note this is *mut T, so add(1) increments by a single T
219 let out_ptr = longer.as_mut_ptr() as *mut T;
220
221 unsafe {
222 // write the first at the start
223 ptr::write(out_ptr, first);
224 // increment past the first, then write self
225 ptr::write(out_ptr.add(1) as *mut Self, self);
226
227 longer.assume_init()
228 }
229 }
230}
231
232unsafe impl<T, N: ArrayLength<T>> Shorten<T> for GenericArray<T, N>
233where
234 N: Sub<B1>,
235 Sub1<N>: ArrayLength<T>,
236 Sub1<N>: Add<B1, Output = N>,
237 Add1<Sub1<N>>: ArrayLength<T>,
238{
239 type Shorter = GenericArray<T, Sub1<N>>;
240
241 fn pop_back(self) -> (Self::Shorter, T) {
242 let whole = ManuallyDrop::new(self);
243
244 unsafe {
245 let init = ptr::read(whole.as_ptr() as _);
246 let last = ptr::read(whole.as_ptr().add(Sub1::<N>::USIZE) as _);
247
248 (init, last)
249 }
250 }
251
252 fn pop_front(self) -> (T, Self::Shorter) {
253 // ensure this doesn't get dropped
254 let whole = ManuallyDrop::new(self);
255
256 unsafe {
257 let head = ptr::read(whole.as_ptr() as _);
258 let tail = ptr::read(whole.as_ptr().offset(1) as _);
259
260 (head, tail)
261 }
262 }
263}
264
265/// Defines a `GenericSequence` that can be split into two parts at a given pivot index.
266pub unsafe trait Split<T, K>: GenericSequence<T>
267where
268 K: ArrayLength<T>,
269{
270 /// First part of the resulting split array
271 type First: GenericSequence<T>;
272 /// Second part of the resulting split array
273 type Second: GenericSequence<T>;
274
275 /// Splits an array at the given index, returning the separate parts of the array.
276 fn split(self) -> (Self::First, Self::Second);
277}
278
279unsafe impl<T, N, K> Split<T, K> for GenericArray<T, N>
280where
281 N: ArrayLength<T>,
282 K: ArrayLength<T>,
283 N: Sub<K>,
284 Diff<N, K>: ArrayLength<T>,
285{
286 type First = GenericArray<T, K>;
287 type Second = GenericArray<T, Diff<N, K>>;
288
289 fn split(self) -> (Self::First, Self::Second) {
290 unsafe {
291 // ensure this doesn't get dropped
292 let whole: ManuallyDrop> = ManuallyDrop::new(self);
293
294 let head: GenericArray = ptr::read(src:whole.as_ptr() as *const _);
295 let tail: GenericArray> = ptr::read(src:whole.as_ptr().add(K::USIZE) as *const _);
296
297 (head, tail)
298 }
299 }
300}
301
302unsafe impl<'a, T, N, K> Split<T, K> for &'a GenericArray<T, N>
303where
304 N: ArrayLength<T>,
305 K: ArrayLength<T> + 'static,
306 N: Sub<K>,
307 Diff<N, K>: ArrayLength<T>,
308{
309 type First = &'a GenericArray<T, K>;
310 type Second = &'a GenericArray<T, Diff<N, K>>;
311
312 fn split(self) -> (Self::First, Self::Second) {
313 unsafe {
314 let ptr_to_first: *const T = self.as_ptr();
315 let head: &GenericArray = &*(ptr_to_first as *const _);
316 let tail: &GenericArray> = &*(ptr_to_first.add(K::USIZE) as *const _);
317 (head, tail)
318 }
319 }
320}
321
322unsafe impl<'a, T, N, K> Split<T, K> for &'a mut GenericArray<T, N>
323where
324 N: ArrayLength<T>,
325 K: ArrayLength<T> + 'static,
326 N: Sub<K>,
327 Diff<N, K>: ArrayLength<T>,
328{
329 type First = &'a mut GenericArray<T, K>;
330 type Second = &'a mut GenericArray<T, Diff<N, K>>;
331
332 fn split(self) -> (Self::First, Self::Second) {
333 unsafe {
334 let ptr_to_first: *mut T = self.as_mut_ptr();
335 let head: &mut T = &mut *(ptr_to_first as *mut _);
336 let tail: &mut T = &mut *(ptr_to_first.add(K::USIZE) as *mut _);
337 (head, tail)
338 }
339 }
340}
341
342/// Defines `GenericSequence`s which can be joined together, forming a larger array.
343pub unsafe trait Concat<T, M>: GenericSequence<T>
344where
345 M: ArrayLength<T>,
346{
347 /// Sequence to be concatenated with `self`
348 type Rest: GenericSequence<T, Length = M>;
349
350 /// Resulting sequence formed by the concatenation.
351 type Output: GenericSequence<T>;
352
353 /// Concatenate, or join, two sequences.
354 fn concat(self, rest: Self::Rest) -> Self::Output;
355}
356
357unsafe impl<T, N, M> Concat<T, M> for GenericArray<T, N>
358where
359 N: ArrayLength<T> + Add<M>,
360 M: ArrayLength<T>,
361 Sum<N, M>: ArrayLength<T>,
362{
363 type Rest = GenericArray<T, M>;
364 type Output = GenericArray<T, Sum<N, M>>;
365
366 fn concat(self, rest: Self::Rest) -> Self::Output {
367 let mut output: MaybeUninit<Self::Output> = MaybeUninit::uninit();
368
369 let out_ptr: *mut GenericArray = output.as_mut_ptr() as *mut Self;
370
371 unsafe {
372 // write all of self to the pointer
373 ptr::write(dst:out_ptr, self);
374 // increment past self, then write the rest
375 ptr::write(dst:out_ptr.add(1) as *mut _, src:rest);
376
377 output.assume_init()
378 }
379 }
380}
381