algorithms_rs/
queue.rs

1use alloc::format;
2use alloc::vec;
3use alloc::vec::Vec;
4
5/// Queue data structure
6#[derive(Debug)]
7pub struct Queue<T> {
8    // data
9    data: Vec<T>,
10    // the queue head pointer
11    head: usize,
12    // the queue tail pointer
13    tail: usize,
14    // the queue size
15    len: usize,
16}
17
18impl<T: Clone + Default> Queue<T> {
19    /// Create an empty queue of fixed size
20    ///
21    /// ```rust
22    /// use algorithms_rs::Queue;
23    ///
24    /// let empty_queue = Queue::<i32>::new(1);
25    ///
26    /// assert_eq!(empty_queue.is_empty(), true);
27    /// ```
28    pub fn new(length: usize) -> Self {
29        let data = vec![T::default(); length];
30        Self {
31            data,
32            head: 0,
33            tail: 0,
34            len: length,
35        }
36    }
37
38    /// Determine if queue is empty
39    ///
40    /// ```rust
41    /// use algorithms_rs::Queue;
42    ///
43    /// let empty_queue = Queue::<i32>::new(1);
44    ///
45    /// assert_eq!(empty_queue.is_empty(), true);
46    /// ```
47    pub fn is_empty(&self) -> bool {
48        self.head == self.tail
49    }
50
51    /// Enter the queue from the end of the queue
52    ///
53    /// ```rust
54    /// use algorithms_rs::Queue;
55    ///
56    /// let mut queue = Queue::<i32>::new(3);
57    ///
58    /// queue.en_queue(1);
59    /// queue.en_queue(2);
60    ///
61    /// assert_eq!(queue.is_empty(), false);
62    /// ```
63    pub fn en_queue(&mut self, element: T) -> anyhow::Result<()> {
64        if self.head == (self.tail + 1) % self.len {
65            return Err(anyhow::anyhow!("overflow"));
66        }
67        if let Some(value) = self.data.get_mut(self.tail) {
68            *value = element;
69        } else {
70            return Err(anyhow::anyhow!(format!(
71                "get index of {} element",
72                self.tail
73            )));
74        }
75
76        if self.tail == (self.len - 1) {
77            self.tail = 0;
78        } else {
79            self.tail += 1;
80        }
81
82        Ok(())
83    }
84
85    /// From the head of the queue Out of the queue
86    ///
87    /// ```rust
88    /// use algorithms_rs::Queue;
89    ///
90    /// let mut queue = Queue::<i32>::new(3);
91    ///
92    /// queue.en_queue(1);
93    /// queue.en_queue(2);
94    ///
95    /// queue.de_queue();
96    /// queue.de_queue();
97    ///
98    /// assert_eq!(queue.is_empty(), true);
99    /// ```
100    pub fn de_queue(&mut self) -> anyhow::Result<T> {
101        if self.is_empty() {
102            return Err(anyhow::anyhow!("underflow"));
103        }
104        let element = self.data.get(self.head);
105        if self.head == (self.len - 1) {
106            self.head = 0;
107        } else {
108            self.head += 1;
109        }
110        Ok(element.unwrap().clone())
111    }
112}
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117
118    fn process_result<T>(result: Result<T, anyhow::Error>) {
119        match result {
120            Ok(_value) => {}
121            Err(err) => {
122                if err.to_string() == *"overflow" {
123                    assert_eq!(err.to_string(), "overflow".to_string());
124                } else if err.to_string() == *"underflow" {
125                    assert_eq!(err.to_string(), "underflow".to_string());
126                }
127            }
128        }
129    }
130
131    #[test]
132    fn test_is_empty_queue() {
133        let empty_queue = Queue::<i32>::new(3);
134        assert!(empty_queue.is_empty());
135    }
136
137    #[test]
138    fn test_is_enqueue_success() {
139        let mut queue = Queue::<i32>::new(3);
140        let ret = queue.en_queue(1);
141        process_result(ret);
142        let ret = queue.en_queue(2);
143        process_result(ret);
144    }
145
146    #[test]
147    fn test_is_enqueue_overflow() {
148        let mut queue = Queue::<i32>::new(3);
149        let ret = queue.en_queue(1);
150        process_result(ret);
151        let ret = queue.en_queue(2);
152        process_result(ret);
153        let ret = queue.en_queue(3);
154        process_result(ret);
155    }
156
157    #[test]
158    fn test_is_dequeue_success() {
159        let mut queue = Queue::<i32>::new(3);
160        let ret = queue.en_queue(1);
161        process_result(ret);
162        let ret = queue.en_queue(2);
163        process_result(ret);
164        let ret = queue.de_queue();
165        process_result(ret);
166        let ret = queue.de_queue();
167        process_result(ret);
168        let ret = queue.en_queue(4);
169        process_result(ret);
170        let ret = queue.de_queue();
171        process_result(ret);
172        let ret = queue.en_queue(5);
173        process_result(ret);
174        let ret = queue.en_queue(6);
175        process_result(ret);
176        let ret = queue.de_queue();
177        process_result(ret);
178        let ret = queue.de_queue();
179        process_result(ret);
180        let ret = queue.en_queue(7);
181        process_result(ret);
182        let ret = queue.en_queue(8);
183        process_result(ret);
184    }
185}
algorithms_rs/queue.rs

algorithms_rs/
queue.rs
