reusing_vec/
queue.rs

1
2extern crate alloc;
3use alloc::vec::Vec;
4
5use crate::*;
6
7/// A structure similar to [`ReusingVec`](crate::ReusingVec), but with support for a
8/// [`pop_front`](Self::pop_front) operation
9#[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    /// Create a new empty vector, does not allocate until the first element is added
24    #[inline]
25    pub const fn new() -> Self {
26        Self {
27            logical_start: 0,
28            logical_end: 0,
29            contents: Vec::new()
30        }
31    }
32    /// Create a new empty vector with at least the specified capacity preallocated
33    #[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    /// Clears the vector, logically removing all values, but not dropping them
42    #[inline]
43    pub fn clear(&mut self) {
44        self.logical_start = 0;
45        self.logical_end = 0;
46    }
47    /// Shortens the vector, keeping the first `len` elements and logically removing the rest
48    ///
49    /// If `len` is greater or equal to the vector’s current logical length, this has no effect.
50    #[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    /// Returns the number of logical elements in the vector, also referred to as its ‘length’
61    #[inline]
62    pub fn len(&self) -> usize {
63        self.logical_end - self.logical_start
64    }
65    /// Returns `true` if the vector contains no logical elements
66    #[inline]
67    pub fn is_empty(&self) -> bool {
68        self.len() == 0
69    }
70    /// Appends the provided element to the back of a vector, increasing the logical length by 1
71    ///
72    /// NOTE: This operation may cause an inactive `T` to be dropped, as it is overwritten by the
73    /// new element provided, so [`push_with`](Self::push_with) or [`push_mut`](Self::push_mut)
74    /// is the usual way to get the full benefit from this crate.
75    #[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    /// Appends an element to the back of a vector, increasing the logical length by 1,
85    /// creating or reinitializing the element with one of the supplied closures
86    #[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    /// Removes the last element from the vector
100    ///
101    /// Returns a mutable reference to the element that was removed, or `None` if the vector was already empty
102    #[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    /// Removes the first element from the vector
117    ///
118    /// Returns a mutable reference to the element that was removed, or `None` if the vector was already empty
119    #[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    /// Appends an empty element to the back of a vector, increasing the logical length by 1, and returns
240    /// a mutable reference to the new / re-initialized element
241    #[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}
reusing_vec/queue.rs

reusing_vec/
queue.rs
