algorithm/arr/circular_buffer.rs
1use std::{marker::PhantomData, ops::{Index, IndexMut}};
2
3/// 循环的圆结构
4/// 如果数据满了之后将自动在结尾后续添加,并保持最大个数
5///
6/// # Examples
7///
8/// ```
9/// use algorithm::CircularBuffer;
10/// fn main() {
11/// let mut circular = CircularBuffer::new(2);
12/// circular.push_back(1);
13/// circular.push_back(2);
14/// circular.push_back(3);
15/// assert_eq!(circular.len(), 2);
16/// assert_eq!(circular[0], 2);
17/// assert_eq!(circular[1], 3);
18/// }
19/// ```
20pub struct CircularBuffer<T> {
21 arr: Vec<T>,
22 head: usize,
23 tail: usize,
24 len: usize,
25 cap: usize,
26}
27
28impl<T> CircularBuffer<T> {
29 pub fn new(cap: usize) -> Self {
30 Self {
31 arr: Vec::with_capacity(cap),
32 head: 0,
33 tail: cap - 1,
34 len: 0,
35 cap,
36 }
37 }
38
39 /// 是否已经填满过所有的元素
40 ///
41 /// # Examples
42 ///
43 /// ```
44 /// use algorithm::CircularBuffer;
45 /// fn main() {
46 /// let mut circular = CircularBuffer::new(2);
47 /// circular.push_back(1);
48 /// assert_eq!(circular.is_inited(), false);
49 /// circular.push_back(2);
50 /// assert_eq!(circular.is_inited(), true);
51 /// circular.pop_back();
52 /// assert_eq!(circular.is_inited(), true);
53 /// }
54 /// ```
55 pub fn is_inited(&self) -> bool {
56 self.cap == self.arr.len()
57 }
58
59 /// 是否元素已满
60 ///
61 /// # Examples
62 ///
63 /// ```
64 /// use algorithm::CircularBuffer;
65 /// fn main() {
66 /// let mut circular = CircularBuffer::new(2);
67 /// circular.push_back(1);
68 /// assert_eq!(circular.is_full(), false);
69 /// circular.push_back(2);
70 /// assert_eq!(circular.is_full(), true);
71 /// circular.pop_back();
72 /// assert_eq!(circular.is_full(), false);
73 /// }
74 /// ```
75 pub fn is_full(&self) -> bool {
76 self.cap == self.len
77 }
78
79 /// 是否元素为空
80 ///
81 /// # Examples
82 ///
83 /// ```
84 /// use algorithm::CircularBuffer;
85 /// fn main() {
86 /// let mut circular = CircularBuffer::new(2);
87 /// assert_eq!(circular.is_empty(), true);
88 /// circular.push_back(1);
89 /// assert_eq!(circular.is_empty(), false);
90 /// }
91 /// ```
92 pub fn is_empty(&self) -> bool {
93 self.len == 0
94 }
95
96 /// 返回元素长度
97 ///
98 /// # Examples
99 ///
100 /// ```
101 /// use algorithm::CircularBuffer;
102 /// fn main() {
103 /// let mut circular = CircularBuffer::new(2);
104 /// assert_eq!(circular.is_empty(), true);
105 /// circular.push_back(1);
106 /// circular.push_back(2);
107 /// assert_eq!(circular.len(), 2);
108 /// circular.push_front(1);
109 /// assert_eq!(circular.len(), 2);
110 /// circular.pop_front();
111 /// assert_eq!(circular.len(), 1);
112 /// }
113 /// ```
114 pub fn len(&self) -> usize {
115 self.len
116 }
117
118 fn add_fix(&self, val: usize) -> usize {
119 (val + 1) % self.cap
120 }
121
122 fn sub_fix(&self, val: usize) -> usize {
123 if val == 0 {
124 self.cap - 1
125 } else {
126 val - 1
127 }
128 }
129
130
131 /// 在元素末尾添加元素
132 ///
133 /// # Examples
134 ///
135 /// ```
136 /// use algorithm::CircularBuffer;
137 /// fn main() {
138 /// let mut circular = CircularBuffer::new(2);
139 /// assert_eq!(circular.is_empty(), true);
140 /// circular.push_back(1);
141 /// circular.push_back(2);
142 /// assert_eq!(circular[0], 1);
143 /// }
144 /// ```
145 pub fn push_back(&mut self, val: T) {
146 if self.is_inited() {
147 self.tail = self.add_fix(self.tail);
148 self.arr[self.tail] = val;
149 self.head = self.add_fix(self.head);
150 } else {
151 if self.tail + 1 < self.arr.len() {
152 self.tail = self.add_fix(self.tail);
153 self.arr[self.tail] = val;
154 } else {
155 self.arr.push(val);
156 self.tail = self.arr.len() - 1;
157 }
158 self.len += 1;
159 }
160 }
161
162 /// 在元素前面添加元素
163 ///
164 /// # Examples
165 ///
166 /// ```
167 /// use algorithm::CircularBuffer;
168 /// fn main() {
169 /// let mut circular = CircularBuffer::new(2);
170 /// assert_eq!(circular.is_empty(), true);
171 /// circular.push_front(1);
172 /// circular.push_front(2);
173 /// assert_eq!(circular[0], 2);
174 /// }
175 /// ```
176 pub fn push_front(&mut self, val: T) {
177 if self.is_inited() {
178 self.head = self.sub_fix(self.head);
179 self.arr[self.head] = val;
180 self.tail = self.sub_fix(self.tail);
181 } else {
182 if self.head > 0 {
183 self.head = self.sub_fix(self.head);
184 self.arr[self.head] = val;
185 } else {
186 self.arr.insert(0, val);
187 self.head = 0;
188 self.tail = self.add_fix(self.tail);
189 }
190 self.len += 1;
191 }
192 }
193
194 /// 将最前面的元素弹出
195 ///
196 /// # Examples
197 ///
198 /// ```
199 /// use algorithm::CircularBuffer;
200 /// fn main() {
201 /// let mut circular = CircularBuffer::new(2);
202 /// assert_eq!(circular.is_empty(), true);
203 /// circular.push_front(1);
204 /// circular.push_front(2);
205 /// assert_eq!(circular[0], 2);
206 /// circular.pop_front();
207 /// assert_eq!(circular[0], 1);
208 /// }
209 /// ```
210 pub fn pop_front(&mut self) {
211 debug_assert!(!self.is_empty());
212 self.head = self.add_fix(self.head);
213 self.len -= 1;
214 }
215
216 /// 将最后面的元素弹出
217 ///
218 /// # Examples
219 ///
220 /// ```
221 /// use algorithm::CircularBuffer;
222 /// fn main() {
223 /// let mut circular = CircularBuffer::new(2);
224 /// assert_eq!(circular.is_empty(), true);
225 /// circular.push_back(1);
226 /// circular.push_back(2);
227 /// assert_eq!(circular[0], 1);
228 /// circular.pop_back();
229 /// assert_eq!(circular[0], 1);
230 /// }
231 /// ```
232 pub fn pop_back(&mut self) {
233 debug_assert!(!self.is_empty());
234 self.tail = self.sub_fix(self.tail);
235 self.len -= 1;
236 }
237
238 /// 迭代器
239 ///
240 /// # Examples
241 ///
242 /// ```
243 /// use algorithm::CircularBuffer;
244 /// fn main() {
245 /// let mut circular = CircularBuffer::new(2);
246 /// assert_eq!(circular.is_empty(), true);
247 /// circular.push_back(1);
248 /// circular.push_back(2);
249 /// let val: Vec<i32> = circular.iter().map(|s| *s).collect();
250 /// assert_eq!(val, vec![1, 2]);
251 /// let val: Vec<i32> = circular.iter().rev().map(|s| *s).collect();
252 /// assert_eq!(val, vec![2, 1]);
253 /// }
254 /// ```
255 pub fn iter(&self) -> Iter<'_, T> {
256 Iter {
257 arr: &self.arr,
258 len: self.len,
259 head: self.head,
260 tail: self.tail,
261 cap: self.cap,
262 }
263 }
264
265 /// 迭代更改器
266 ///
267 /// # Examples
268 ///
269 /// ```
270 /// use algorithm::CircularBuffer;
271 /// fn main() {
272 /// let mut circular = CircularBuffer::new(2);
273 /// assert_eq!(circular.is_empty(), true);
274 /// circular.push_back(1);
275 /// circular.push_back(2);
276 /// let val: Vec<i32> = circular.iter_mut().map(|v| { *v *= 2; *v }).collect();
277 /// assert_eq!(val, vec![2, 4]);
278 /// let val: Vec<i32> = circular.iter_mut().rev().map(|v| { *v *= 2; *v }).collect();
279 /// assert_eq!(val, vec![8, 4]);
280 /// }
281 /// ```
282 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
283 IterMut {
284 arr: self.arr.as_mut_ptr(),
285 len: self.len,
286 head: self.head,
287 tail: self.tail,
288 cap: self.cap,
289 _marker: PhantomData,
290 }
291 }
292}
293
294
295impl<T> Index<usize> for CircularBuffer<T> {
296 type Output = T;
297
298 #[inline]
299 fn index(&self, index: usize) -> &T {
300 if index < self.len {
301 let ridx = (index + self.head) % self.cap;
302 &self.arr[ridx]
303 } else {
304 panic!("index error");
305 }
306 }
307}
308
309impl<T> IndexMut<usize> for CircularBuffer<T> {
310 #[inline]
311 fn index_mut(&mut self, index: usize) -> &mut T {
312 if index < self.len {
313 let ridx = (index + self.head) % self.cap;
314 &mut self.arr[ridx]
315 } else {
316 panic!("index error");
317 }
318 }
319}
320
321impl<T: Clone> Clone for CircularBuffer<T> {
322 fn clone(&self) -> Self {
323 Self {
324 arr: self.arr.clone(),
325 head: self.head,
326 tail: self.tail,
327 len: self.len,
328 cap: self.cap,
329 }
330 }
331}
332
333pub struct Iter<'a, T: 'a> {
334 len: usize,
335 arr: &'a Vec<T>,
336 head: usize,
337 tail: usize,
338 cap: usize,
339}
340
341impl<'a, T> Iterator for Iter<'a, T> {
342 type Item = &'a T;
343
344 fn next(&mut self) -> Option<Self::Item> {
345 if self.len == 0 {
346 return None;
347 }
348 let now = self.head;
349 self.head = (self.head + 1) % self.cap;
350 self.len -= 1;
351 Some(&self.arr[now])
352 }
353
354 fn size_hint(&self) -> (usize, Option<usize>) {
355 (self.len, Some(self.len))
356 }
357}
358
359
360impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
361 fn next_back(&mut self) -> Option<Self::Item> {
362 if self.len == 0 {
363 return None;
364 }
365 let now = self.tail;
366 self.tail = (self.tail + self.cap - 1) % self.cap;
367 self.len -= 1;
368 Some(&self.arr[now])
369 }
370}
371
372pub struct IterMut<'a, T: 'a> {
373 len: usize,
374 arr: *mut T,
375 head: usize,
376 tail: usize,
377 cap: usize,
378 _marker: PhantomData<&'a mut T>,
379}
380
381impl<'a, T> Iterator for IterMut<'a, T> {
382 type Item = &'a mut T;
383
384 fn next(&mut self) -> Option<Self::Item> {
385 if self.len == 0 {
386 return None;
387 }
388 let now = self.head;
389 self.head = (self.head + 1) % self.cap;
390 self.len -= 1;
391 unsafe {
392 let ptr = self.arr.add(now);
393 return Some(&mut *ptr)
394 }
395 }
396
397 fn size_hint(&self) -> (usize, Option<usize>) {
398 (self.len, Some(self.len))
399 }
400}
401
402
403impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
404 fn next_back(&mut self) -> Option<Self::Item> {
405 if self.len == 0 {
406 return None;
407 }
408 let now = self.tail;
409 self.tail = (self.tail + self.cap - 1) % self.cap;
410 self.len -= 1;
411 unsafe {
412 let ptr = self.arr.add(now);
413 return Some(&mut *ptr)
414 }
415 }
416}
417
418
419
420impl<T> PartialEq for CircularBuffer<T>
421 where
422 T: Eq,
423{
424 fn eq(&self, other: &CircularBuffer<T>) -> bool {
425 if self.len() != other.len() {
426 return false;
427 }
428
429 self.iter().enumerate().all(|(idx, value)| &other[idx] == value)
430 }
431}
432
433impl<T> Eq for CircularBuffer<T>
434 where
435 T: Eq,
436{}
437
438#[cfg(test)]
439mod tests {
440 use super::CircularBuffer;
441
442 #[test]
443 fn test_iter() {
444 let mut circular = CircularBuffer::new(2);
445 assert_eq!(circular.is_empty(), true);
446 circular.push_back(1);
447 circular.push_back(2);
448 let val: Vec<i32> = circular.iter().map(|s| *s).collect();
449 assert_eq!(val, vec![1, 2]);
450 let val: Vec<i32> = circular.iter().rev().map(|s| *s).collect();
451 assert_eq!(val, vec![2, 1]);
452 }
453}