sans_io_runtime/collections/
dequeue.rs

1use std::collections::VecDeque;
2
3/// A dynamic deque that can store elements in a stack or a heap.
4/// First, elements are pushed to the stack. If the stack is full, elements are pushed to the heap.
5/// When popping elements, the stack is popped first. If the stack is empty and the heap is not, the
6/// heap is popped and the elements are pushed to the stack.
7/// Example:
8/// ```
9/// use sans_io_runtime::collections::DynamicDeque;
10/// let mut deque: DynamicDeque<i32, 5> = DynamicDeque::default();
11/// deque.push_back_stack(1).unwrap();
12/// deque.push_back_stack(2).unwrap();
13/// deque.push_back_stack(3).unwrap();
14/// deque.push_back_stack(4).unwrap();
15/// deque.push_back_stack(5).unwrap();
16/// deque.push_back(6); // Should overflow to heap
17/// assert_eq!(deque.len(), 6);
18/// ```
19#[derive(Debug)]
20pub struct DynamicDeque<T, const STACK_SIZE: usize> {
21    stack: heapless::Deque<T, STACK_SIZE>,
22    heap: VecDeque<T>,
23}
24
25impl<T, const STACK_SIZE: usize> Default for DynamicDeque<T, STACK_SIZE> {
26    fn default() -> Self {
27        Self {
28            stack: heapless::Deque::new(),
29            heap: VecDeque::new(),
30        }
31    }
32}
33
34#[allow(unused)]
35impl<T, const STATIC_SIZE: usize> DynamicDeque<T, STATIC_SIZE> {
36    /// Creates a new instance of `DynamicDeque` from an array of elements.
37    ///
38    /// # Arguments
39    ///
40    /// * `prepare` - An array of elements to initialize the deque with.
41    ///
42    /// # Returns
43    ///
44    /// A new instance of `DynamicDeque`.
45    pub fn from<const SIZE: usize>(prepare: [T; SIZE]) -> Self {
46        let mut instance = Self::default();
47        for item in prepare {
48            instance.push_back(item);
49        }
50        instance
51    }
52
53    /// Pushes an element to the stack of the deque.
54    ///
55    /// # Arguments
56    ///
57    /// * `value` - The value to be pushed.
58    ///
59    /// # Returns
60    ///
61    /// * `Ok(())` - If the element was successfully pushed.
62    /// * `Err(value)` - If the element could not be pushed due to overflow.
63    pub fn push_back_stack(&mut self, value: T) -> Result<(), T> {
64        self.stack.push_back(value)
65    }
66
67    /// Pushes an element to the stack or the heap of the deque.
68    ///
69    /// # Arguments
70    ///
71    /// * `value` - The value to be pushed.
72    pub fn push_back(&mut self, value: T) {
73        if let Err(value) = self.stack.push_back(value) {
74            self.heap.push_back(value);
75        }
76    }
77
78    /// Pops the element from the front of the deque.
79    ///
80    /// # Returns
81    ///
82    /// The popped element, or `None` if the deque is empty.
83    pub fn pop_front(&mut self) -> Option<T> {
84        let res = self.stack.pop_front();
85        if !self.stack.is_full() && !self.heap.is_empty() {
86            let front = self.heap.pop_front().expect("Should have");
87            if self.stack.push_back(front).is_err() {
88                panic!("cannot happen");
89            }
90        }
91        res
92    }
93
94    /// Checks if the deque is empty.
95    ///
96    /// # Returns
97    ///
98    /// `true` if the deque is empty, `false` otherwise.
99    pub fn is_empty(&self) -> bool {
100        self.stack.is_empty()
101    }
102
103    /// Returns the number of elements in the deque.
104    ///
105    /// # Returns
106    ///
107    /// The number of elements in the deque.
108    pub fn len(&self) -> usize {
109        self.stack.len() + self.heap.len()
110    }
111
112    /// This is useful in task where we usually doing output in queue
113    /// We need push to back then immediate pop from front
114    #[inline(always)]
115    pub fn pop2(&mut self, e: T) -> T {
116        if self.is_empty() {
117            e
118        } else {
119            let out = self.pop_front().expect("Should have because just push");
120            self.push_back(e);
121            out
122        }
123    }
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129
130    #[test]
131    fn test_push_back() {
132        let mut deque: DynamicDeque<i32, 2> = DynamicDeque::default();
133        assert!(deque.push_back_stack(1).is_ok());
134        assert!(deque.push_back_stack(2).is_ok());
135        assert!(deque.push_back_stack(3).is_err());
136        assert_eq!(deque.len(), 2);
137        deque.push_back(3);
138        assert_eq!(deque.len(), 3);
139    }
140
141    #[test]
142    fn test_pop_front() {
143        let mut deque: DynamicDeque<i32, 2> = DynamicDeque::default();
144        deque.push_back(1);
145        deque.push_back(2);
146        deque.push_back(3);
147        assert_eq!(deque.pop_front(), Some(1));
148        assert_eq!(deque.pop_front(), Some(2));
149        assert_eq!(deque.pop_front(), Some(3));
150        assert_eq!(deque.pop_front(), None);
151        assert_eq!(deque.len(), 0);
152    }
153
154    #[test]
155    fn test_is_empty() {
156        let mut deque: DynamicDeque<i32, 2> = DynamicDeque::default();
157        assert_eq!(deque.is_empty(), true);
158        deque.push_back(1);
159        assert_eq!(deque.is_empty(), false);
160        deque.pop_front();
161        assert_eq!(deque.is_empty(), true);
162    }
163}
sans_io_runtime/collections/dequeue.rs

sans_io_runtime/collections/
dequeue.rs
