fera_array/
array.rs

1use std::marker::PhantomData;
2use std::ops::{Index, IndexMut};
3use std::ptr;
4
5use fera_fun::vec;
6
7// TODO: Should Array be called AbstractArray (https://en.wikipedia.org/wiki/Array_data_type)?
8/// A simple trait for array like structs.
9pub trait Array<T>: IndexMut<usize, Output = T> {
10    /// Creates a new array with `n` repeated `value`.
11    fn with_value(value: T, n: usize) -> Self
12    where
13        Self: Sized,
14        T: Clone;
15
16    /// Returns the number of elements in the array.
17    fn len(&self) -> usize;
18
19    /// Returns `true` if the array contains `value`, `false` otherwise.
20    fn contains(&self, value: &T) -> bool
21    where
22        T: PartialEq,
23    {
24        for i in 0..self.len() {
25            if unsafe { self.get_unchecked(i) } == value {
26                return true;
27            }
28        }
29        false
30    }
31
32    /// Returns `true` if the length of the array is 0, otherwise `false`.
33    #[inline]
34    fn is_empty(&self) -> bool {
35        self.len() == 0
36    }
37
38    /// Returns a reference to the element of the array at `index`, or `None` if the index is out
39    /// of bounds.
40    fn get(&self, index: usize) -> Option<&T> {
41        if index < self.len() {
42            Some(unsafe { self.get_unchecked(index) })
43        } else {
44            None
45        }
46    }
47
48    /// Returns a mutable reference to the element of the array at `index`, or `None` if the index
49    /// is out of bounds.
50    fn get_mut(&mut self, index: usize) -> Option<&mut T> {
51        if index < self.len() {
52            Some(unsafe { self.get_unchecked_mut(index) })
53        } else {
54            None
55        }
56    }
57
58    /// Returns a reference to the element of the array at `index`, without doing bounds checking.
59    unsafe fn get_unchecked(&self, index: usize) -> &T;
60
61    /// Returns a mutable reference to the element of the array at `index`, without doing bounds
62    /// checking.
63    unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T;
64
65    // TODO: Allow each implementation to specify the iterator
66    /// Returns a iterator over the array.
67    fn iter(&self) -> Iter<T, Self>
68    where
69        Self: Sized,
70    {
71        Iter {
72            cur: 0,
73            len: self.len(),
74            array: self,
75            _marker: PhantomData,
76        }
77    }
78}
79
80/// A simple trait for a dynamic array like struct.
81pub trait DynamicArray<T>: Array<T> {
82    /// Creates a array with the specified capacity.
83    ///
84    /// The implementation is free to choose if the array can grow beyond this capacity or not.
85    fn with_capacity(capacity: usize) -> Self
86    where
87        Self: Sized;
88
89    /// Returns the capacity of the array.
90    fn capacity(&self) -> usize;
91
92    // TODO: see Vec docs and add some fundamentals methods, like shrink_to_fit, reserve_exact
93
94    /// Change the length of the array.
95    unsafe fn set_len(&mut self, len: usize);
96
97    /// Reserve capacity for at least `additional` more elements.
98    ///
99    /// # Panics
100    ///
101    /// If the array cannot satisfy the request.
102    ///
103    /// The default implementation panics if `additional > (self.capacity() - self.len())`.
104    #[inline]
105    fn reserve(&mut self, additional: usize) {
106        if additional > (self.capacity() - self.len()) {
107            panic!(
108                "cannot grow: cap {}, len {}, additional {}",
109                self.capacity(),
110                self.len(),
111                additional
112            )
113        }
114    }
115
116    /// Write value to the end of the array and increment the length.
117    ///
118    /// This method is used in the default implementation of `push`, `extend_with_element` and
119    /// `extend_from_slice`.
120    ///
121    /// # Safety
122    ///
123    /// It's unsafe because the capacity is not checked.
124    #[inline]
125    unsafe fn push_unchecked(&mut self, value: T) {
126        let len = self.len();
127        ptr::write(self.get_unchecked_mut(len), value);
128        self.set_len(len + 1);
129    }
130
131    /// Appends the `value` to the array.
132    ///
133    /// # Panics
134    ///
135    /// If the array is full and cannot grow.
136    #[inline]
137    fn push(&mut self, value: T) {
138        self.reserve(1);
139        unsafe {
140            self.push_unchecked(value);
141        }
142    }
143
144    // TODO: remove this method, should implement Extend
145    /// Appends all elements of `iter` to the array.
146    ///
147    /// # Panics
148    ///
149    /// If the array cannot grow to accommodate all elements.
150    fn extend<I>(&mut self, iter: I)
151    where
152        Self: Sized,
153        I: IntoIterator<Item = T>,
154    {
155        let iter = iter.into_iter();
156        self.reserve(iter.size_hint().0);
157        for value in iter {
158            self.push(value);
159        }
160    }
161
162    /// Appends all elements in a slice to the array.
163    ///
164    /// # Panics
165    ///
166    /// If the array cannot grow to accommodate all elements.
167    fn extend_from_slice(&mut self, other: &[T])
168    where
169        T: Clone,
170    {
171        self.reserve(other.len());
172
173        for i in 0..other.len() {
174            unsafe { self.push_unchecked(other.get_unchecked(i).clone()) }
175        }
176    }
177
178    /// Extend the array by `n` additional clones of `value`.
179    ///
180    /// # Panics
181    ///
182    /// If the array cannot grow to accommodate all elements.
183    fn extend_with_element(&mut self, value: T, n: usize)
184    where
185        T: Clone,
186    {
187        self.reserve(n);
188
189        for _ in 1..n {
190            unsafe {
191                self.push_unchecked(value.clone());
192            }
193        }
194
195        if n > 0 {
196            // do not clone the last one
197            unsafe {
198                self.push_unchecked(value);
199            }
200        }
201    }
202}
203
204/// An iterator over `Array`.
205pub struct Iter<'a, T, A: 'a + Array<T>> {
206    cur: usize,
207    len: usize,
208    array: &'a A,
209    _marker: PhantomData<*const T>,
210}
211
212impl<'a, T, A> Iterator for Iter<'a, T, A>
213where
214    A: 'a + Array<T>,
215    T: 'a,
216{
217    type Item = &'a T;
218
219    fn next(&mut self) -> Option<Self::Item> {
220        if self.cur == self.len {
221            None
222        } else {
223            let item = unsafe { self.array.get_unchecked(self.cur) };
224            self.cur += 1;
225            Some(item)
226        }
227    }
228
229    fn size_hint(&self) -> (usize, Option<usize>) {
230        (self.len(), Some(self.len()))
231    }
232}
233
234impl<'a, T, A> ExactSizeIterator for Iter<'a, T, A>
235where
236    A: 'a + Array<T>,
237    T: 'a,
238{
239    fn len(&self) -> usize {
240        self.len - self.cur
241    }
242}
243
244/// A set of tests for `Array` implementations.
245#[doc(hidden)]
246pub trait ArrayTests {
247    type A: Array<usize>;
248
249    fn basic_0() {
250        Self::basic(0);
251    }
252
253    fn basic_001k() {
254        Self::basic(1024);
255    }
256
257    fn basic_100k() {
258        Self::basic(100 * 1024);
259    }
260
261    fn clone_001k()
262    where
263        Self::A: Clone,
264    {
265        Self::clone(1024);
266    }
267
268    fn clone_100k()
269    where
270        Self::A: Clone,
271    {
272        Self::clone(100 * 1024);
273    }
274
275    fn basic(n: usize) {
276        let mut exp = vec![0; n];
277        let mut actual = Self::A::with_value(0, n);
278
279        Self::assert_all(&exp, &mut actual);
280
281        for i in 0..n {
282            actual[i] = i;
283            exp[i] = i;
284        }
285        Self::assert_all(&exp, &mut actual);
286
287        for i in 0..n {
288            *actual.get_mut(i).unwrap() = i + 1;
289            *exp.index_mut(i) = i + 1;
290        }
291        Self::assert_all(&exp, &mut actual);
292
293        for i in 0..n {
294            unsafe {
295                *actual.get_unchecked_mut(i) = i + 2;
296            }
297            *exp.index_mut(i) = i + 2;
298        }
299        Self::assert_all(&exp, &mut actual);
300    }
301
302    fn clone(n: usize)
303    where
304        Self::A: Clone,
305    {
306        let mut exp1 = vec![0; n];
307        let mut exp2 = vec![0; n];
308        let mut actual1 = Self::A::with_value(0, n);
309        let mut actual2 = actual1.clone();
310
311        actual1[0] = 10;
312        exp1[0] = 10;
313        Self::assert_all(&exp1, &mut actual1);
314        Self::assert_all(&exp2, &mut actual2);
315
316        actual2[0] = 20;
317        exp2[0] = 20;
318        Self::assert_all(&exp1, &mut actual1);
319        Self::assert_all(&exp2, &mut actual2);
320
321        actual1[n / 2] = 30;
322        exp1[n / 2] = 30;
323        actual2[n / 2] = 40;
324        exp2[n / 2] = 40;
325        Self::assert_all(&exp1, &mut actual1);
326        Self::assert_all(&exp2, &mut actual2);
327    }
328
329    fn assert_all(exp: &[usize], actual: &mut Self::A) {
330        let n = actual.len();
331        assert_eq!(exp.len(), actual.len());
332        assert_eq!(exp.is_empty(), actual.is_empty());
333        assert_eq!(exp, &*vec(actual.iter().cloned()));
334        assert_eq!(exp, &*vec((0..n).map(|i| *actual.index(i))));
335        assert_eq!(exp, &*vec((0..n).map(|i| *actual.get(i).unwrap())));
336        assert_eq!(
337            exp,
338            &*vec((0..n).map(|i| unsafe { *actual.get_unchecked(i) }))
339        );
340        assert_eq!(exp, &*vec((0..n).map(|i| *actual.index_mut(i))));
341        assert_eq!(exp, &*vec((0..n).map(|i| *actual.get_mut(i).unwrap())));
342        assert_eq!(
343            exp,
344            &*vec((0..n).map(|i| unsafe { *actual.get_unchecked_mut(i) }))
345        );
346
347        assert_eq!(None, actual.get(n));
348        assert_eq!(None, actual.get_mut(n));
349    }
350}
351
352/// A set of tests for `Array` implementations.
353#[doc(hidden)]
354pub trait DynamicArrayTests: ArrayTests
355where
356    Self::A: DynamicArray<usize>,
357{
358    fn push_1k() {
359        Self::push(1024);
360    }
361
362    fn capacity() {
363        assert_eq!(0, Self::A::with_capacity(0).len());
364
365        assert!(1000 <= Self::A::with_capacity(1000).capacity());
366        assert_eq!(0, Self::A::with_capacity(0).len());
367    }
368
369    fn clone_push()
370    where
371        Self::A: Clone,
372    {
373        let mut a = Self::A::with_capacity(10);
374        let b = a.clone();
375        a.push(100);
376        assert_eq!(1, a.len());
377        assert_eq!(0, b.len());
378    }
379
380    fn push(n: usize) {
381        let mut actual = Self::A::with_capacity(n);
382        let mut exp = Vec::with_capacity(n);
383
384        for i in 0..n {
385            Self::assert_all(&exp, &mut actual);
386            actual.push(i);
387            exp.push(i);
388        }
389
390        Self::assert_all(&*exp, &mut actual)
391    }
392}
393
394#[cfg(all(feature = "nightly", test))]
395use test::Bencher;
396
397/// A set of benchmarks for `Array` implementations.
398#[cfg(all(feature = "nightly", test))]
399pub trait ArrayBenchs: ArrayTests
400where
401    Self::A: Clone,
402{
403    fn fold_xor_0001k(b: &mut Bencher) {
404        Self::fold_xor(b, 1024)
405    }
406
407    fn fold_xor_0010k(b: &mut Bencher) {
408        Self::fold_xor(b, 10 * 1024)
409    }
410
411    fn fold_xor_0100k(b: &mut Bencher) {
412        Self::fold_xor(b, 100 * 1024)
413    }
414
415    fn fold_xor_1000k(b: &mut Bencher) {
416        Self::fold_xor(b, 1000 * 1024)
417    }
418
419    fn fold_xor(b: &mut Bencher, n: usize) {
420        let mut v = Self::A::with_value(0, n);
421        for i in 0..n {
422            v[i] = i;
423        }
424        b.iter(|| v.iter().fold(0, |acc, e| acc ^ e))
425    }
426
427    fn clone_change_0001k(b: &mut Bencher) {
428        Self::clone_change(b, 1024, 1);
429    }
430
431    fn clone_change_0010k(b: &mut Bencher) {
432        Self::clone_change(b, 10 * 1024, 1);
433    }
434
435    fn clone_change_0100k(b: &mut Bencher) {
436        Self::clone_change(b, 100 * 1024, 1);
437    }
438
439    fn clone_change_1000k(b: &mut Bencher) {
440        Self::clone_change(b, 1000 * 1024, 1);
441    }
442
443    fn clone_change(b: &mut Bencher, n: usize, ins: usize) {
444        fn setup<A: Array<usize>>(n: usize, ins: usize) -> (Vec<A>, Vec<usize>, Vec<usize>) {
445            use rand::{Rng, SeedableRng, XorShiftRng};
446            let mut rng =
447                XorShiftRng::from_seed([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]);
448            let mut arrays = Vec::with_capacity(ins + 1);
449            arrays.push(A::with_value(0, n));
450            let ii = vec((0..ins).map(|e| rng.gen_range(0, e + 1)));
451            let jj = vec((0..ins).map(|_| rng.gen_range(0, n)));
452            (arrays, ii, jj)
453        }
454
455        let (mut arrays, ii, jj) = setup::<Self::A>(n, ins);
456        b.iter(|| {
457            for (&i, &j) in ii.iter().zip(jj.iter()) {
458                let mut new = arrays[i].clone();
459                new[j] = j + i;
460                arrays.push(new);
461            }
462        });
463    }
464}
fera_array/array.rs

fera_array/
array.rs
