1
2extern crate alloc;
3use alloc::vec::Vec;
4
5use crate::*;
6
7#[derive(Clone, Default)]
10pub struct ReusingQueue<T> {
11 logical_start: usize,
12 logical_end: usize,
13 contents: Vec<T>
14}
15
16impl<T> core::fmt::Debug for ReusingQueue<T> where T: core::fmt::Debug {
17 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> Result<(), core::fmt::Error> {
18 write!(f, "{:?}", self as &[_])
19 }
20}
21
22impl<T> ReusingQueue<T> {
23 #[inline]
25 pub const fn new() -> Self {
26 Self {
27 logical_start: 0,
28 logical_end: 0,
29 contents: Vec::new()
30 }
31 }
32 #[inline]
34 pub fn with_capacity(capacity: usize) -> Self {
35 Self {
36 logical_start: 0,
37 logical_end: 0,
38 contents: Vec::with_capacity(capacity)
39 }
40 }
41 #[inline]
43 pub fn clear(&mut self) {
44 self.logical_start = 0;
45 self.logical_end = 0;
46 }
47 #[inline]
51 pub fn truncate(&mut self, len: usize) {
52 if len == 0 {
53 self.clear()
54 } else {
55 if len < (self.logical_end - self.logical_start) {
56 self.logical_end = self.logical_start + len;
57 }
58 }
59 }
60 #[inline]
62 pub fn len(&self) -> usize {
63 self.logical_end - self.logical_start
64 }
65 #[inline]
67 pub fn is_empty(&self) -> bool {
68 self.len() == 0
69 }
70 #[inline]
76 pub fn push_val(&mut self, val: T) {
77 if self.logical_end < self.contents.len() {
78 *self.contents.get_mut(self.logical_end).unwrap() = val;
79 } else {
80 self.contents.push(val);
81 }
82 self.logical_end += 1;
83 }
84 #[inline]
87 pub fn push_with<NewF, ResetF>(&mut self, new_f: NewF, reset_f: ResetF)
88 where
89 NewF: FnOnce() -> T,
90 ResetF: FnOnce(&mut T)
91 {
92 if self.logical_end < self.contents.len() {
93 reset_f(self.contents.get_mut(self.logical_end).unwrap());
94 } else {
95 self.contents.push(new_f());
96 }
97 self.logical_end += 1;
98 }
99 #[inline]
103 pub fn pop(&mut self) -> Option<&mut T> {
104 if self.logical_end > self.logical_start {
105 self.logical_end -= 1;
106 let old_idx = self.logical_end;
107 if self.logical_end == self.logical_start {
108 self.clear();
109 }
110 self.contents.get_mut(old_idx)
111 } else {
112 self.clear();
113 None
114 }
115 }
116 #[inline]
120 pub fn pop_front(&mut self) -> Option<&mut T> {
121 if self.logical_end > self.logical_start {
122 let old_idx = self.logical_start;
123 self.logical_start += 1;
124 if self.logical_end == self.logical_start {
125 self.clear();
126 }
127 self.contents.get_mut(old_idx)
128 } else {
129 self.clear();
130 None
131 }
132 }
133}
134
135impl<T> AsMut<[T]> for ReusingQueue<T> {
136 fn as_mut(&mut self) -> &mut [T] {
137 &mut self.contents[self.logical_start..self.logical_end]
138 }
139}
140
141impl<T> AsRef<[T]> for ReusingQueue<T> {
142 fn as_ref(&self) -> &[T] {
143 &self.contents[self.logical_start..self.logical_end]
144 }
145}
146
147impl<T> core::borrow::Borrow<[T]> for ReusingQueue<T> {
148 fn borrow(&self) -> &[T] {
149 &self.contents[self.logical_start..self.logical_end]
150 }
151}
152
153impl<T> core::borrow::BorrowMut<[T]> for ReusingQueue<T> {
154 fn borrow_mut(&mut self) -> &mut [T] {
155 &mut self.contents[self.logical_start..self.logical_end]
156 }
157}
158
159impl<T> core::ops::Deref for ReusingQueue<T> {
160 type Target = [T];
161 fn deref(&self) -> &[T] {
162 &self.contents[self.logical_start..self.logical_end]
163 }
164}
165
166impl<T> core::ops::DerefMut for ReusingQueue<T> {
167 fn deref_mut(&mut self) -> &mut [T] {
168 &mut self.contents[self.logical_start..self.logical_end]
169 }
170}
171
172impl<T> From<Vec<T>> for ReusingQueue<T> {
173 fn from(vec: Vec<T>) -> Self {
174 Self {
175 logical_start: 0,
176 logical_end: vec.len(),
177 contents: vec
178 }
179 }
180}
181
182impl<T> From<ReusingQueue<T>> for Vec<T> {
183 fn from(mut vec: ReusingQueue<T>) -> Self {
184 vec.contents.drain(0..vec.logical_start);
185 vec.contents.truncate(vec.logical_end - vec.logical_start);
186 vec.contents
187 }
188}
189
190impl<T, U> FromIterator<U> for ReusingQueue<T> where T: From<U> {
191 fn from_iter<I: IntoIterator<Item=U>>(iter: I) -> Self {
192 let contents: Vec<T> = iter.into_iter().map(|element| element.into()).collect();
193 Self {
194 logical_start: 0,
195 logical_end: contents.len(),
196 contents,
197 }
198 }
199}
200
201impl<T> IntoIterator for ReusingQueue<T> {
202 type Item = T;
203 type IntoIter = ReusingVecIter<T>;
204 fn into_iter(self) -> Self::IntoIter {
205 let mut iter = self.contents.into_iter();
206 if self.logical_start > 0 {
207 iter.nth(self.logical_start - 1);
208 }
209 iter.take(self.logical_end - self.logical_start)
210 }
211}
212
213impl<T> PartialEq<Self> for ReusingQueue<T> where T: PartialEq {
214 fn eq(&self, other: &Self) -> bool {
215 (self as &[T]).eq(other as &[T])
216 }
217}
218impl<T> Eq for ReusingQueue<T> where T: Eq {}
219
220impl<T> PartialEq<[T]> for ReusingQueue<T> where T: PartialEq {
221 fn eq(&self, other: &[T]) -> bool {
222 (self as &[T]).eq(other)
223 }
224}
225
226impl<T> PartialEq<Vec<T>> for ReusingQueue<T> where T: PartialEq {
227 fn eq(&self, other: &Vec<T>) -> bool {
228 (self as &[T]).eq(other)
229 }
230}
231
232impl<T> PartialEq<ReusingVec<T>> for ReusingQueue<T> where T: PartialEq {
233 fn eq(&self, other: &ReusingVec<T>) -> bool {
234 (self as &[T]).eq(other as &[T])
235 }
236}
237
238impl<T: ReusableElement> ReusingQueue<T> {
239 #[inline]
242 pub fn push_mut(&mut self) -> &mut T {
243 if self.logical_end < self.contents.len() {
244 self.contents.get_mut(self.logical_end).unwrap().reset();
245 } else {
246 self.contents.push(T::new());
247 }
248 let element = self.contents.get_mut(self.logical_end).unwrap();
249 self.logical_end += 1;
250 element
251 }
252}
253
254#[test]
255fn queue_test() {
256 let mut queue: ReusingQueue<i32> = (0..10).into_iter().collect();
257
258 assert_eq!(queue.len(), 10);
259 assert_eq!(*queue, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
260 queue.truncate(9);
261 assert_eq!(queue.len(), 9);
262 assert_eq!(*queue, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
263 assert_eq!(queue.pop(), Some(&mut 8));
264
265 queue.pop();
266 assert_eq!(queue.pop_front(), Some(&mut 0));
267 assert_eq!(queue.len(), 6);
268 assert_eq!(*queue, [1, 2, 3, 4, 5, 6]);
269
270 queue.truncate(5);
271 assert_eq!(queue.len(), 5);
272 assert_eq!(*queue, [1, 2, 3, 4, 5]);
273
274 let vec_1: Vec<i32> = queue.clone().into_iter().collect();
275 assert_eq!(*vec_1, *queue);
276
277 let vec_2: Vec<i32> = queue.clone().into();
278 assert_eq!(vec_1, vec_2);
279
280 while queue.pop().is_some() {
281 queue.pop_front();
282 }
283 assert_eq!(queue.len(), 0);
284 assert_eq!(queue.pop_front(), None);
285}