fixed_size_vector/
array_vec.rs

1use std::mem::replace;
2
3use super::error::CapacityError;
4
5#[derive(Clone, Copy, Debug)]
6pub struct ArrayVec<A> {
7    array: A,
8    start: usize,
9    length: usize,
10}
11
12impl<A> ArrayVec<A> {
13    pub fn new() -> Self
14    where
15        A: Default,
16    {
17        ArrayVec {
18            array: Default::default(),
19            start: 0,
20            length: 0,
21        }
22    }
23
24    pub fn push<T: Clone>(&mut self, x: &T) -> Result<(), CapacityError>
25    where
26        A: AsRef<[T]> + AsMut<[T]>,
27    {
28        if self.length == self.capacity() {
29            return Err(CapacityError);
30        }
31
32        let i = self.index(self.length);
33        self.array.as_mut()[i] = x.clone();
34        self.length += 1;
35        Ok(())
36    }
37
38    pub fn pop_front<T: Default>(&mut self) -> Option<T>
39    where
40        A: AsRef<[T]> + AsMut<[T]>,
41    {
42        if self.length == 0 {
43            return None;
44        }
45
46        let x = replace(&mut self.array.as_mut()[self.start], Default::default());
47        self.start = self.index(1);
48        self.length -= 1;
49        Some(x)
50    }
51
52    pub fn len(&self) -> usize {
53        self.length
54    }
55
56    pub fn is_empty<T>(&self) -> bool
57    where
58        A: AsRef<[T]>,
59    {
60        self.len() == 0
61    }
62
63    pub fn is_full<T>(&self) -> bool
64    where
65        A: AsRef<[T]>,
66    {
67        self.len() == self.capacity()
68    }
69
70    fn index<T>(&self, i: usize) -> usize
71    where
72        A: AsRef<[T]>,
73    {
74        (self.start + i) % self.capacity()
75    }
76
77    fn capacity<T>(&self) -> usize
78    where
79        A: AsRef<[T]>,
80    {
81        self.array.as_ref().len()
82    }
83}
84
85impl<A: Default> Default for ArrayVec<A> {
86    fn default() -> Self {
87        ArrayVec::new()
88    }
89}
90
91impl<'a, T: 'a, A: AsRef<[T]>> IntoIterator for &'a ArrayVec<A>
92where
93    &'a A: IntoIterator<Item = &'a T>,
94{
95    type Item = &'a T;
96    type IntoIter = ArrayVecIterator<'a, A>;
97
98    fn into_iter(self) -> Self::IntoIter {
99        ArrayVecIterator {
100            vec: self,
101            current: 0,
102        }
103    }
104}
105
106impl<'a, T: 'a, A: AsRef<[T]> + AsMut<[T]>> IntoIterator for &'a mut ArrayVec<A>
107where
108    &'a A: IntoIterator<Item = &'a T>,
109{
110    type Item = &'a mut T;
111    type IntoIter = ArrayVecMutIterator<'a, A>;
112
113    fn into_iter(self) -> Self::IntoIter {
114        ArrayVecMutIterator {
115            vec: self,
116            current: 0,
117        }
118    }
119}
120
121#[derive(Debug)]
122pub struct ArrayVecIterator<'a, A: 'a> {
123    vec: &'a ArrayVec<A>,
124    current: usize,
125}
126
127impl<'a, T: 'a, A: AsRef<[T]>> Iterator for ArrayVecIterator<'a, A>
128where
129    &'a A: IntoIterator<Item = &'a T>,
130{
131    type Item = &'a T;
132
133    fn next(&mut self) -> Option<Self::Item> {
134        if self.current == self.vec.length {
135            return None;
136        }
137
138        let x = &self.vec.array.as_ref()[self.vec.index(self.current)];
139        self.current += 1;
140        Some(x)
141    }
142}
143
144#[derive(Debug)]
145pub struct ArrayVecMutIterator<'a, A: 'a> {
146    vec: &'a mut ArrayVec<A>,
147    current: usize,
148}
149
150impl<'a, T: 'a, A: AsRef<[T]> + AsMut<[T]>> Iterator for ArrayVecMutIterator<'a, A>
151where
152    &'a A: IntoIterator<Item = &'a T>,
153{
154    type Item = &'a mut T;
155
156    fn next(&mut self) -> Option<Self::Item> {
157        if self.current == self.vec.length {
158            return None;
159        }
160
161        let i = self.vec.index(self.current);
162        let x = &mut self.vec.array.as_mut()[i] as *mut T;
163        self.current += 1;
164        Some(unsafe { &mut *x })
165    }
166}
167
168#[cfg(test)]
169mod test {
170    use super::*;
171
172    #[test]
173    fn new() {
174        let _: ArrayVec<[usize; 1]> = ArrayVec::new();
175        let _: ArrayVec<[usize; 2]> = ArrayVec::new();
176    }
177
178    #[test]
179    fn push() {
180        let mut a: ArrayVec<[usize; 1]> = ArrayVec::new();
181
182        assert_eq!(a.len(), 0);
183        assert!(a.push(&42).is_ok());
184        assert_eq!(a.len(), 1);
185        assert_eq!(a.push(&42), Err(CapacityError));
186        assert_eq!(a.len(), 1);
187
188        let mut a: ArrayVec<[usize; 2]> = ArrayVec::new();
189
190        assert_eq!(a.len(), 0);
191        assert!(a.push(&42).is_ok());
192        assert_eq!(a.len(), 1);
193        assert!(a.push(&42).is_ok());
194        assert_eq!(a.len(), 2);
195        assert_eq!(a.push(&42), Err(CapacityError));
196        assert_eq!(a.len(), 2);
197    }
198
199    #[test]
200    fn pop_front() {
201        let mut a: ArrayVec<[usize; 1]> = ArrayVec::new();
202
203        assert!(a.push(&42).is_ok());
204
205        assert_eq!(a.pop_front(), Some(42));
206        assert_eq!(a.len(), 0);
207
208        let mut a: ArrayVec<[usize; 2]> = ArrayVec::new();
209
210        assert!(a.push(&123).is_ok());
211        assert!(a.push(&42).is_ok());
212
213        assert_eq!(a.pop_front(), Some(123));
214        assert_eq!(a.len(), 1);
215        assert_eq!(a.pop_front(), Some(42));
216        assert_eq!(a.len(), 0);
217    }
218
219    #[test]
220    fn push_and_pop_front_across_edges() {
221        let mut a: ArrayVec<[usize; 2]> = ArrayVec::new();
222
223        assert!(a.push(&1).is_ok());
224        assert!(a.push(&2).is_ok());
225
226        for i in 3..64 {
227            assert_eq!(a.pop_front(), Some(i - 2));
228            assert_eq!(a.len(), 1);
229            assert!(a.push(&i).is_ok());
230            assert_eq!(a.len(), 2);
231        }
232    }
233
234    #[test]
235    fn is_empty() {
236        let a: ArrayVec<[usize; 1]> = ArrayVec::new();
237        assert!(a.is_empty());
238
239        let a: ArrayVec<[usize; 2]> = ArrayVec::new();
240        assert!(a.is_empty());
241    }
242
243    #[test]
244    fn is_full() {
245        let mut a: ArrayVec<[usize; 1]> = ArrayVec::new();
246        assert!(a.push(&0).is_ok());
247        assert!(a.is_full());
248
249        let mut a: ArrayVec<[usize; 2]> = ArrayVec::new();
250        assert!(a.push(&0).is_ok());
251        assert!(a.push(&0).is_ok());
252        assert!(a.is_full());
253    }
254
255    #[test]
256    fn iterator() {
257        let mut a: ArrayVec<[usize; 2]> = ArrayVec::new();
258
259        assert!(a.push(&0).is_ok());
260        assert!(a.push(&1).is_ok());
261
262        for (i, e) in a.into_iter().enumerate() {
263            assert_eq!(*e, i);
264        }
265    }
266
267    #[test]
268    fn iterator_across_edges() {
269        let mut a: ArrayVec<[usize; 2]> = ArrayVec::new();
270
271        assert!(a.push(&42).is_ok());
272        a.pop_front();
273        assert!(a.push(&0).is_ok());
274        assert!(a.push(&1).is_ok());
275
276        for (i, e) in a.into_iter().enumerate() {
277            assert_eq!(*e, i);
278        }
279    }
280
281    #[test]
282    fn iterator_mut() {
283        let mut a: ArrayVec<[usize; 2]> = ArrayVec::new();
284
285        assert!(a.push(&0).is_ok());
286        assert!(a.push(&1).is_ok());
287
288        for (i, e) in (&mut a).into_iter().enumerate() {
289            assert_eq!(*e, i);
290            *e = 42;
291        }
292    }
293
294    #[test]
295    fn reference_elements() {
296        let mut a: ArrayVec<[Box<usize>; 2]> = ArrayVec::new();
297        assert!(a.push(&Box::new(42)).is_ok());
298    }
299}
fixed_size_vector/array_vec.rs

fixed_size_vector/
array_vec.rs
