array_queue/
array_queue.rs

1use std::mem::{drop, forget, replace, uninitialized, ManuallyDrop};
2
3use arrayvec::Array;
4
5use super::error::CapacityError;
6
7#[derive(Debug)]
8pub struct ArrayQueue<A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> {
9    array: ManuallyDrop<A>,
10    start: usize,
11    length: usize,
12}
13
14impl<A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> ArrayQueue<A> {
15    pub fn new() -> Self {
16        ArrayQueue {
17            array: unsafe { uninitialized() },
18            start: 0,
19            length: 0,
20        }
21    }
22
23    pub fn first(&self) -> Option<&<A as Array>::Item> {
24        self.element(0)
25    }
26
27    pub fn first_mut(&mut self) -> Option<&mut <A as Array>::Item> {
28        self.element_mut(0)
29    }
30
31    pub fn last(&self) -> Option<&<A as Array>::Item> {
32        if self.is_empty() {
33            return None;
34        }
35
36        self.element(self.length - 1)
37    }
38
39    pub fn last_mut(&mut self) -> Option<&mut <A as Array>::Item> {
40        if self.is_empty() {
41            return None;
42        }
43
44        let i = self.length - 1;
45        self.element_mut(i)
46    }
47
48    fn element(&self, i: usize) -> Option<&<A as Array>::Item> {
49        if self.is_empty() {
50            None
51        } else {
52            Some(&self.array.as_ref()[self.index(i)])
53        }
54    }
55
56    fn element_mut(&mut self, i: usize) -> Option<&mut <A as Array>::Item> {
57        if self.is_empty() {
58            None
59        } else {
60            let i = self.index(i);
61            Some(&mut self.array.as_mut()[i])
62        }
63    }
64
65    pub fn push_back(&mut self, x: &<A as Array>::Item) -> Result<(), CapacityError>
66    where
67        <A as Array>::Item: Clone,
68    {
69        if self.is_full() {
70            return Err(CapacityError);
71        }
72
73        let i = self.index(self.length);
74        forget(replace(&mut self.array.as_mut()[i], x.clone()));
75        self.length += 1;
76        Ok(())
77    }
78
79    pub fn push_front(&mut self, x: &<A as Array>::Item) -> Result<(), CapacityError>
80    where
81        <A as Array>::Item: Clone,
82    {
83        if self.is_full() {
84            return Err(CapacityError);
85        }
86
87        self.start = self.index(Self::capacity() - 1);
88        forget(replace(&mut self.array.as_mut()[self.start], x.clone()));
89        self.length += 1;
90        Ok(())
91    }
92
93    pub fn pop_back(&mut self) -> Option<<A as Array>::Item> {
94        if self.is_empty() {
95            return None;
96        }
97
98        let x = replace(&mut self.array.as_mut()[self.length - 1], unsafe {
99            uninitialized()
100        });
101        self.length -= 1;
102        Some(x)
103    }
104
105    pub fn pop_front(&mut self) -> Option<<A as Array>::Item> {
106        if self.is_empty() {
107            return None;
108        }
109
110        let x = replace(&mut self.array.as_mut()[self.start], unsafe {
111            uninitialized()
112        });
113        self.start = self.index(1);
114        self.length -= 1;
115        Some(x)
116    }
117
118    pub fn len(&self) -> usize {
119        self.length
120    }
121
122    pub fn is_empty(&self) -> bool {
123        self.len() == 0
124    }
125
126    pub fn is_full(&self) -> bool {
127        self.len() == Self::capacity()
128    }
129
130    fn index(&self, i: usize) -> usize {
131        (self.start + i) % Self::capacity()
132    }
133
134    fn capacity() -> usize {
135        A::capacity()
136    }
137}
138
139impl<A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> Clone for ArrayQueue<A>
140where
141    <A as Array>::Item: Clone,
142{
143    fn clone(&self) -> Self {
144        let mut a = Self::new();
145
146        for x in self {
147            a.push_back(x).unwrap();
148        }
149
150        a
151    }
152}
153
154impl<A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> Default
155    for ArrayQueue<A>
156{
157    fn default() -> Self {
158        ArrayQueue::new()
159    }
160}
161
162impl<A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> Drop for ArrayQueue<A> {
163    fn drop(&mut self) {
164        for x in self {
165            drop(replace(x, unsafe { uninitialized() }));
166        }
167    }
168}
169
170impl<'a, A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> IntoIterator
171    for &'a ArrayQueue<A>
172{
173    type Item = &'a <A as Array>::Item;
174    type IntoIter = ArrayQueueIterator<'a, A>;
175
176    fn into_iter(self) -> Self::IntoIter {
177        let l = self.len();
178
179        ArrayQueueIterator {
180            queue: self,
181            first: 0,
182            last: l,
183        }
184    }
185}
186
187impl<'a, A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> IntoIterator
188    for &'a mut ArrayQueue<A>
189{
190    type Item = &'a mut <A as Array>::Item;
191    type IntoIter = ArrayQueueMutIterator<'a, A>;
192
193    fn into_iter(self) -> Self::IntoIter {
194        let l = self.len();
195
196        ArrayQueueMutIterator {
197            queue: self,
198            first: 0,
199            last: l,
200        }
201    }
202}
203
204#[derive(Debug)]
205pub struct ArrayQueueIterator<
206    'a,
207    A: 'a + Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>,
208> {
209    queue: &'a ArrayQueue<A>,
210    first: usize,
211    last: usize,
212}
213
214impl<'a, A: 'a + Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>>
215    ArrayQueueIterator<'a, A>
216{
217    fn exhausted(&self) -> bool {
218        self.first >= self.last
219    }
220}
221
222impl<'a, A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> Iterator
223    for ArrayQueueIterator<'a, A>
224{
225    type Item = &'a <A as Array>::Item;
226
227    fn next(&mut self) -> Option<Self::Item> {
228        if self.exhausted() {
229            return None;
230        }
231
232        let x = &self.queue.array.as_ref()[self.queue.index(self.first)];
233        self.first += 1;
234        Some(x)
235    }
236}
237
238impl<'a, A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> DoubleEndedIterator
239    for ArrayQueueIterator<'a, A>
240{
241    fn next_back(&mut self) -> Option<Self::Item> {
242        if self.exhausted() {
243            return None;
244        }
245
246        self.last -= 1;
247        let x = &self.queue.array.as_ref()[self.queue.index(self.last)];
248        Some(x)
249    }
250}
251
252#[derive(Debug)]
253pub struct ArrayQueueMutIterator<
254    'a,
255    A: 'a + Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>,
256> {
257    queue: &'a mut ArrayQueue<A>,
258    first: usize,
259    last: usize,
260}
261
262impl<'a, A: 'a + Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>>
263    ArrayQueueMutIterator<'a, A>
264{
265    fn exhausted(&self) -> bool {
266        self.first >= self.last
267    }
268}
269
270impl<'a, A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> Iterator
271    for ArrayQueueMutIterator<'a, A>
272{
273    type Item = &'a mut <A as Array>::Item;
274
275    fn next(&mut self) -> Option<Self::Item> {
276        if self.exhausted() {
277            return None;
278        }
279
280        let i = self.queue.index(self.first);
281        let x = &mut self.queue.array.as_mut()[i] as *mut <A as Array>::Item;
282        self.first += 1;
283        Some(unsafe { &mut *x })
284    }
285}
286
287impl<'a, A: Array + AsRef<[<A as Array>::Item]> + AsMut<[<A as Array>::Item]>> DoubleEndedIterator
288    for ArrayQueueMutIterator<'a, A>
289{
290    fn next_back(&mut self) -> Option<Self::Item> {
291        if self.exhausted() {
292            return None;
293        }
294
295        self.last -= 1;
296        let i = self.queue.index(self.last);
297        let x = &mut self.queue.array.as_mut()[i] as *mut <A as Array>::Item;
298        Some(unsafe { &mut *x })
299    }
300}
301
302#[cfg(test)]
303mod test {
304    use super::*;
305
306    #[test]
307    fn new() {
308        ArrayQueue::<[usize; 1]>::new();
309        ArrayQueue::<[usize; 2]>::new();
310    }
311
312    #[test]
313    fn first_and_last() {
314        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
315
316        assert_eq!(a.first(), None);
317        assert_eq!(a.first_mut(), None);
318        assert_eq!(a.last(), None);
319        assert_eq!(a.last_mut(), None);
320
321        assert!(a.push_back(&1).is_ok());
322
323        assert_eq!(a.first(), Some(&1));
324        assert_eq!(a.first_mut(), Some(&mut 1));
325        assert_eq!(a.last(), Some(&1));
326        assert_eq!(a.last_mut(), Some(&mut 1));
327
328        assert!(a.push_back(&2).is_ok());
329
330        assert_eq!(a.first(), Some(&1));
331        assert_eq!(a.first_mut(), Some(&mut 1));
332        assert_eq!(a.last(), Some(&2));
333        assert_eq!(a.last_mut(), Some(&mut 2));
334    }
335
336    #[test]
337    fn push_back() {
338        let mut a: ArrayQueue<[usize; 1]> = ArrayQueue::new();
339
340        assert_eq!(a.len(), 0);
341        assert!(a.push_back(&42).is_ok());
342        assert_eq!(a.len(), 1);
343        assert_eq!(a.push_back(&42), Err(CapacityError));
344        assert_eq!(a.len(), 1);
345
346        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
347
348        assert_eq!(a.len(), 0);
349        assert!(a.push_back(&42).is_ok());
350        assert_eq!(a.len(), 1);
351        assert!(a.push_back(&42).is_ok());
352        assert_eq!(a.len(), 2);
353        assert_eq!(a.push_back(&42), Err(CapacityError));
354        assert_eq!(a.len(), 2);
355    }
356
357    #[test]
358    fn push_front() {
359        let mut a: ArrayQueue<[usize; 1]> = ArrayQueue::new();
360
361        assert_eq!(a.len(), 0);
362        assert!(a.push_front(&42).is_ok());
363        assert_eq!(a.len(), 1);
364        assert_eq!(a.push_front(&42), Err(CapacityError));
365        assert_eq!(a.len(), 1);
366
367        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
368
369        assert_eq!(a.len(), 0);
370        assert!(a.push_front(&1).is_ok());
371        assert_eq!(a.first(), Some(&1));
372        assert_eq!(a.last(), Some(&1));
373        assert_eq!(a.len(), 1);
374        assert!(a.push_front(&2).is_ok());
375        assert_eq!(a.first(), Some(&2));
376        assert_eq!(a.last(), Some(&1));
377        assert_eq!(a.len(), 2);
378        assert_eq!(a.push_front(&3), Err(CapacityError));
379        assert_eq!(a.len(), 2);
380    }
381
382    #[test]
383    fn pop_back() {
384        let mut a: ArrayQueue<[usize; 1]> = ArrayQueue::new();
385
386        assert!(a.push_back(&42).is_ok());
387
388        assert_eq!(a.pop_back(), Some(42));
389        assert_eq!(a.len(), 0);
390
391        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
392
393        assert!(a.push_back(&123).is_ok());
394        assert!(a.push_back(&42).is_ok());
395
396        assert_eq!(a.pop_back(), Some(42));
397        assert_eq!(a.first(), Some(&123));
398        assert_eq!(a.last(), Some(&123));
399        assert_eq!(a.len(), 1);
400        assert_eq!(a.pop_back(), Some(123));
401        assert_eq!(a.len(), 0);
402    }
403
404    #[test]
405    fn pop_front() {
406        let mut a: ArrayQueue<[usize; 1]> = ArrayQueue::new();
407
408        assert!(a.push_back(&42).is_ok());
409
410        assert_eq!(a.pop_front(), Some(42));
411        assert_eq!(a.len(), 0);
412
413        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
414
415        assert!(a.push_back(&123).is_ok());
416        assert!(a.push_back(&42).is_ok());
417
418        assert_eq!(a.pop_front(), Some(123));
419        assert_eq!(a.first(), Some(&42));
420        assert_eq!(a.last(), Some(&42));
421        assert_eq!(a.len(), 1);
422        assert_eq!(a.pop_front(), Some(42));
423        assert_eq!(a.len(), 0);
424    }
425
426    #[test]
427    fn push_and_pop_across_edges() {
428        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
429
430        assert!(a.push_back(&1).is_ok());
431        assert!(a.push_back(&2).is_ok());
432
433        for i in 3..64 {
434            assert_eq!(a.pop_front(), Some(i - 2));
435            assert_eq!(a.len(), 1);
436            assert!(a.push_back(&i).is_ok());
437            assert_eq!(a.len(), 2);
438        }
439    }
440
441    #[test]
442    fn is_empty() {
443        let a: ArrayQueue<[usize; 1]> = ArrayQueue::new();
444        assert!(a.is_empty());
445
446        let a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
447        assert!(a.is_empty());
448    }
449
450    #[test]
451    fn is_full() {
452        let mut a: ArrayQueue<[usize; 1]> = ArrayQueue::new();
453        assert!(a.push_back(&0).is_ok());
454        assert!(a.is_full());
455
456        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
457        assert!(a.push_back(&0).is_ok());
458        assert!(a.push_back(&0).is_ok());
459        assert!(a.is_full());
460    }
461
462    #[test]
463    fn iterator() {
464        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
465
466        assert!(a.push_back(&0).is_ok());
467        assert!(a.push_back(&1).is_ok());
468
469        for (i, e) in a.into_iter().enumerate() {
470            assert_eq!(*e, i);
471        }
472    }
473
474    #[test]
475    fn iterator_across_edges() {
476        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
477
478        assert!(a.push_back(&42).is_ok());
479        a.pop_front();
480        assert!(a.push_back(&0).is_ok());
481        assert!(a.push_back(&1).is_ok());
482
483        for (i, e) in a.into_iter().enumerate() {
484            assert_eq!(*e, i);
485        }
486    }
487
488    #[test]
489    fn iterate_forward_and_backward() {
490        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
491
492        assert!(a.push_back(&0).is_ok());
493        assert!(a.push_back(&1).is_ok());
494
495        let mut i = a.into_iter();
496
497        assert_eq!(i.next(), Some(&0));
498        assert_eq!(i.next_back(), Some(&1));
499        assert_eq!(i.next(), None);
500        assert_eq!(i.next_back(), None);
501    }
502
503    #[test]
504    fn iterate_forward_and_backward_mutablly() {
505        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
506
507        assert!(a.push_back(&0).is_ok());
508        assert!(a.push_back(&1).is_ok());
509
510        let mut i = (&mut a).into_iter();
511
512        assert_eq!(i.next(), Some(&mut 0));
513        assert_eq!(i.next_back(), Some(&mut 1));
514        assert_eq!(i.next(), None);
515        assert_eq!(i.next_back(), None);
516    }
517
518    #[test]
519    fn iterate_empty_queue() {
520        let a = ArrayQueue::<[usize; 0]>::new();
521
522        for _ in a.into_iter() {}
523    }
524
525    #[test]
526    fn iterator_mut() {
527        let mut a: ArrayQueue<[usize; 2]> = ArrayQueue::new();
528
529        assert!(a.push_back(&0).is_ok());
530        assert!(a.push_back(&1).is_ok());
531
532        for (i, e) in (&mut a).into_iter().enumerate() {
533            assert_eq!(*e, i);
534            *e = 42;
535        }
536    }
537
538    #[test]
539    fn reference_elements() {
540        let mut a: ArrayQueue<[Box<usize>; 2]> = ArrayQueue::new();
541        assert!(a.push_back(&Box::new(42)).is_ok());
542        assert!(a.push_front(&Box::new(42)).is_ok());
543    }
544
545    #[test]
546    fn clone() {
547        let mut a: ArrayQueue<[Box<usize>; 32]> = ArrayQueue::new();
548
549        for _ in 0..32 {
550            assert!(a.push_back(&Box::new(42)).is_ok());
551        }
552
553        a.clone();
554    }
555
556    static mut FOO_SUM: usize = 0;
557
558    #[derive(Clone)]
559    struct Foo;
560
561    impl Drop for Foo {
562        fn drop(&mut self) {
563            unsafe {
564                FOO_SUM += 1;
565            }
566        }
567    }
568
569    #[test]
570    fn no_drops_of_elements_on_push_back() {
571        assert_eq!(unsafe { FOO_SUM }, 0);
572
573        let mut a: ArrayQueue<[Foo; 32]> = ArrayQueue::new();
574
575        for _ in 0..32 {
576            assert!(a.push_back(&Foo).is_ok());
577        }
578
579        assert_eq!(unsafe { FOO_SUM }, 32); // drops of arguments `&Foo`
580
581        drop(a);
582
583        assert_eq!(unsafe { FOO_SUM }, 64); // drops of elements
584    }
585
586    static mut BAR_SUM: usize = 0;
587
588    #[derive(Clone)]
589    struct Bar;
590
591    impl Drop for Bar {
592        fn drop(&mut self) {
593            unsafe {
594                BAR_SUM += 1;
595            }
596        }
597    }
598
599    #[test]
600    fn drops_of_elements_on_pop_back() {
601        assert_eq!(unsafe { BAR_SUM }, 0);
602
603        let mut a: ArrayQueue<[Bar; 32]> = ArrayQueue::new();
604
605        for _ in 0..32 {
606            assert!(a.push_back(&Bar).is_ok());
607        }
608
609        assert_eq!(unsafe { BAR_SUM }, 32); // drops of arguments `&Bar`
610
611        for _ in 0..32 {
612            assert!(a.pop_back().is_some());
613        }
614
615        assert_eq!(unsafe { BAR_SUM }, 64); // drops of elements
616
617        drop(a);
618
619        assert_eq!(unsafe { BAR_SUM }, 64);
620    }
621}
array_queue/array_queue.rs

array_queue/
array_queue.rs
