array_queue/
array_queue.rs

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

array_queue/
array_queue.rs
