1 | //! Useful traits for manipulating sequences of data stored in `GenericArray`s
|
2 |
|
3 | use super::*;
|
4 | use core::ops::{Add, Sub};
|
5 | use core::mem::MaybeUninit;
|
6 | use core::ptr;
|
7 | use 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.
|
12 | pub 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.
|
73 | pub type SequenceItem<T> = <T as IntoIterator>::Item;
|
74 |
|
75 | unsafe impl<'a, T: 'a, S: GenericSequence<T>> GenericSequence<T> for &'a S
|
76 | where
|
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 |
|
91 | unsafe impl<'a, T: 'a, S: GenericSequence<T>> GenericSequence<T> for &'a mut S
|
92 | where
|
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`
|
111 | pub 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.
|
152 | pub 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 |
|
190 | unsafe impl<T, N: ArrayLength<T>> Lengthen<T> for GenericArray<T, N>
|
191 | where
|
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 |
|
232 | unsafe impl<T, N: ArrayLength<T>> Shorten<T> for GenericArray<T, N>
|
233 | where
|
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.
|
266 | pub unsafe trait Split<T, K>: GenericSequence<T>
|
267 | where
|
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 |
|
279 | unsafe impl<T, N, K> Split<T, K> for GenericArray<T, N>
|
280 | where
|
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>::Output> = ptr::read(src:whole.as_ptr().add(K::USIZE) as *const _);
|
296 |
|
297 | (head, tail)
|
298 | }
|
299 | }
|
300 | }
|
301 |
|
302 | unsafe impl<'a, T, N, K> Split<T, K> for &'a GenericArray<T, N>
|
303 | where
|
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>::Output> = &*(ptr_to_first.add(K::USIZE) as *const _);
|
317 | (head, tail)
|
318 | }
|
319 | }
|
320 | }
|
321 |
|
322 | unsafe impl<'a, T, N, K> Split<T, K> for &'a mut GenericArray<T, N>
|
323 | where
|
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 GenericArray = &mut *(ptr_to_first as *mut _);
|
336 | let tail: &mut GenericArray>::Output> = &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.
|
343 | pub unsafe trait Concat<T, M>: GenericSequence<T>
|
344 | where
|
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 |
|
357 | unsafe impl<T, N, M> Concat<T, M> for GenericArray<T, N>
|
358 | where
|
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 | |