eastl_rs/
queue.rs

1use crate::allocator::{Allocator, DefaultAllocator};
2use crate::deque::iter::{Iter, IterMut};
3use crate::deque::Deque;
4use std::fmt::{Debug, Formatter};
5
6/// Queue with the default allocator.
7pub type DefaultQueue<'a, V> = Queue<'a, V, DefaultAllocator>;
8
9/// A first-in, first-out data structure backed by a Deque
10#[repr(C)]
11pub struct Queue<'a, T: 'a, A: Allocator> {
12    deque: Deque<'a, T, A>,
13}
14
15unsafe impl<'a, T: Send + 'a, A: Allocator + Send> Send for Queue<'a, T, A> {}
16unsafe impl<'a, T: Sync + 'a, A: Allocator + Sync> Sync for Queue<'a, T, A> {}
17
18impl<'a, T: 'a, A: Allocator + Default> Queue<'a, T, A> {
19    /// Creates a new empty queue
20    fn new() -> Self {
21        Self {
22            deque: Deque::new(),
23        }
24    }
25}
26
27impl<'a, T: 'a, A: Allocator> Queue<'a, T, A> {
28    /// Turns the `Queue` into its inner `Deque`
29    pub fn into_inner(self) -> Deque<'a, T, A> {
30        self.deque
31    }
32
33    /// Returns true if the queue contains no elements
34    pub fn is_empty(&self) -> bool {
35        self.deque.is_empty()
36    }
37
38    /// Produces an iterator over all of the elements in the queue
39    pub fn iter(&self) -> Iter<'a, T> {
40        self.deque.iter()
41    }
42
43    /// Produces a mutable iterator over all of the elements in the queue
44    pub fn iter_mut(&mut self) -> IterMut<'a, T> {
45        self.deque.iter_mut()
46    }
47
48    /// Returns the number of elements in the queue
49    pub fn len(&self) -> usize {
50        self.deque.len()
51    }
52
53    /// Creates a new queue inside an allocator
54    ///
55    /// # Arguments
56    ///
57    /// `allocator`: The allocator
58    ///
59    /// # Safety
60    ///
61    /// The allocator specified must safely allocate ande de-allocate valid memory
62    pub unsafe fn new_in(allocator: A) -> Self {
63        Self {
64            deque: Deque::new_in(allocator),
65        }
66    }
67
68    /// Pops an element from the queue, returning the element on top if there was one
69    pub fn pop(&mut self) -> Option<T> {
70        self.deque.pop_front()
71    }
72
73    /// Pushes an element to the queue
74    pub fn push(&mut self, elem: T) {
75        self.deque.push_back(elem);
76    }
77
78    /// Peeks the top element in the queue without popping it
79    pub fn top(&self) -> Option<&T> {
80        self.deque.front()
81    }
82}
83
84impl<'a, T: 'a + Debug, A: Allocator> Debug for Queue<'a, T, A> {
85    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
86        self.deque.fmt(f)
87    }
88}
89
90impl<'a, T: 'a, A: Allocator + Default> Default for Queue<'a, T, A> {
91    fn default() -> Self {
92        Self::new()
93    }
94}
95
96impl<'a, T: 'a, A: Allocator + Default> FromIterator<T> for Queue<'a, T, A> {
97    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
98        Self {
99            deque: Deque::from_iter(iter),
100        }
101    }
102}
103
104#[cfg(test)]
105mod test {
106    use crate::queue::DefaultQueue;
107
108    #[test]
109    fn layout() {
110        assert_eq!(
111            std::mem::size_of::<DefaultQueue<u32>>(),
112            std::mem::size_of::<usize>() * 11
113        );
114    }
115
116    #[test]
117    fn push_pop() {
118        let mut q = DefaultQueue::new();
119
120        assert!(q.is_empty());
121        assert_eq!(q.len(), 0);
122
123        for i in 0..256 {
124            q.push(i);
125        }
126        assert_eq!(q.top(), Some(&0));
127        assert!(!q.is_empty());
128        assert_eq!(q.len(), 256);
129
130        for i in 0..256 {
131            assert_eq!(q.pop(), Some(i));
132        }
133
134        assert!(q.is_empty());
135        assert_eq!(q.len(), 0);
136    }
137
138    #[test]
139    fn iter() {
140        let q: DefaultQueue<i32> = (0..256).collect();
141
142        q.iter().zip(0..256).for_each(|(l, r)| assert_eq!(*l, r));
143
144        let v: Vec<i32> = q.into_iter().collect();
145
146        assert_eq!(v.len(), 256);
147
148        v.iter().zip(0..256).for_each(|(l, r)| assert_eq!(*l, r));
149    }
150}
eastl_rs/queue.rs

eastl_rs/
queue.rs
