circular_queue/lib.rs
1//! A circular buffer-like queue.
2//!
3//! The `CircularQueue<T>` is created with a set capacity, then items are pushed in. When the queue
4//! runs out of capacity, newer items start overwriting the old ones, starting from the oldest.
5//!
6//! There are built-in iterators that go from the newest items to the oldest ones and from the
7//! oldest items to the newest ones.
8//!
9//! Two queues are considered equal if iterating over them with `iter()` would yield the same
10//! sequence of elements.
11//!
12//! Enable the `serde_support` feature for [Serde](https://serde.rs/) support.
13//!
14//! # Examples
15//!
16//! ```
17//! use circular_queue::CircularQueue;
18//!
19//! let mut queue = CircularQueue::with_capacity(3);
20//! queue.push(1);
21//! queue.push(2);
22//! queue.push(3);
23//! queue.push(4);
24//!
25//! assert_eq!(queue.len(), 3);
26//!
27//! let mut iter = queue.iter();
28//!
29//! assert_eq!(iter.next(), Some(&4));
30//! assert_eq!(iter.next(), Some(&3));
31//! assert_eq!(iter.next(), Some(&2));
32//! ```
33
34#![cfg_attr(has_extern_crate_alloc, no_std)]
35#![doc(html_root_url = "https://docs.rs/circular-queue/0.2.7")]
36
37#[cfg(has_extern_crate_alloc)]
38extern crate alloc;
39
40#[cfg(has_extern_crate_alloc)]
41use alloc::vec::Vec;
42#[cfg(has_extern_crate_alloc)]
43use core::iter::{Chain, Rev};
44#[cfg(has_extern_crate_alloc)]
45use core::mem::replace;
46#[cfg(has_extern_crate_alloc)]
47use core::slice::{Iter as SliceIter, IterMut as SliceIterMut};
48
49#[cfg(not(has_extern_crate_alloc))]
50use std::iter::{Chain, Rev};
51#[cfg(not(has_extern_crate_alloc))]
52use std::mem::replace;
53#[cfg(not(has_extern_crate_alloc))]
54use std::slice::{Iter as SliceIter, IterMut as SliceIterMut};
55
56#[cfg(feature = "serde_support")]
57mod serde_support;
58
59/// A circular buffer-like queue.
60#[derive(Clone, Debug)]
61pub struct CircularQueue<T> {
62 data: Vec<T>,
63 // Using our own capacity instead of the one stored in Vec to ensure consistent behavior with
64 // zero-sized types.
65 capacity: usize,
66 insertion_index: usize,
67}
68
69/// An iterator over `CircularQueue<T>`.
70pub type Iter<'a, T> = Chain<Rev<SliceIter<'a, T>>, Rev<SliceIter<'a, T>>>;
71
72/// A mutable iterator over `CircularQueue<T>`.
73pub type IterMut<'a, T> = Chain<Rev<SliceIterMut<'a, T>>, Rev<SliceIterMut<'a, T>>>;
74
75/// An ascending iterator over `CircularQueue<T>`.
76pub type AscIter<'a, T> = Chain<SliceIter<'a, T>, SliceIter<'a, T>>;
77
78/// An mutable ascending iterator over `CircularQueue<T>`.
79pub type AscIterMut<'a, T> = Chain<SliceIterMut<'a, T>, SliceIterMut<'a, T>>;
80
81/// A value popped from `CircularQueue<T>` as the result of a push operation.
82pub type Popped<T> = Option<T>;
83
84impl<T> CircularQueue<T> {
85 /// Constructs a new, empty `CircularQueue<T>` with the requested capacity.
86 ///
87 /// # Examples
88 ///
89 /// ```
90 /// use circular_queue::CircularQueue;
91 ///
92 /// let mut queue: CircularQueue<i32> = CircularQueue::with_capacity(5);
93 /// ```
94 #[inline]
95 pub fn with_capacity(capacity: usize) -> Self {
96 Self {
97 data: Vec::with_capacity(capacity),
98 capacity,
99 insertion_index: 0,
100 }
101 }
102
103 /// Returns the current number of elements in the queue.
104 ///
105 /// # Examples
106 ///
107 /// ```
108 /// use circular_queue::CircularQueue;
109 ///
110 /// let mut queue = CircularQueue::with_capacity(5);
111 /// queue.push(1);
112 /// queue.push(2);
113 /// queue.push(3);
114 ///
115 /// assert_eq!(queue.len(), 3);
116 /// ```
117 #[inline]
118 pub fn len(&self) -> usize {
119 self.data.len()
120 }
121
122 /// Returns `true` if the queue contains no elements.
123 ///
124 /// # Examples
125 ///
126 /// ```
127 /// use circular_queue::CircularQueue;
128 ///
129 /// let mut queue = CircularQueue::with_capacity(5);
130 /// assert!(queue.is_empty());
131 ///
132 /// queue.push(1);
133 /// assert!(!queue.is_empty());
134 /// ```
135 #[inline]
136 pub fn is_empty(&self) -> bool {
137 self.data.is_empty()
138 }
139
140 /// Returns `true` if the queue is full.
141 ///
142 /// # Examples
143 ///
144 /// ```
145 /// use circular_queue::CircularQueue;
146 ///
147 /// let mut queue = CircularQueue::with_capacity(5);
148 ///
149 /// assert!(!queue.is_full());
150 ///
151 /// queue.push(1);
152 /// queue.push(2);
153 /// queue.push(3);
154 /// queue.push(4);
155 /// queue.push(5);
156 ///
157 /// assert!(queue.is_full());
158 /// ```
159 #[inline]
160 pub fn is_full(&self) -> bool {
161 self.capacity() == self.len()
162 }
163
164 /// Returns the capacity of the queue.
165 ///
166 /// # Examples
167 ///
168 /// ```
169 /// use circular_queue::CircularQueue;
170 ///
171 /// let queue: CircularQueue<i32> = CircularQueue::with_capacity(5);
172 /// assert_eq!(queue.capacity(), 5);
173 /// ```
174 #[inline]
175 pub fn capacity(&self) -> usize {
176 self.capacity
177 }
178
179 /// Clears the queue.
180 ///
181 /// # Examples
182 ///
183 /// ```
184 /// use circular_queue::CircularQueue;
185 ///
186 /// let mut queue = CircularQueue::with_capacity(5);
187 /// queue.push(1);
188 /// queue.push(2);
189 /// queue.push(3);
190 ///
191 /// queue.clear();
192 /// assert_eq!(queue.len(), 0);
193 /// ```
194 #[inline]
195 pub fn clear(&mut self) {
196 self.data.clear();
197 self.insertion_index = 0;
198 }
199
200 /// Pushes a new element into the queue.
201 ///
202 /// Once the capacity is reached, pushing new items will overwrite old ones.
203 ///
204 /// In case an old value is overwritten, it will be returned.
205 ///
206 /// # Examples
207 ///
208 /// ```
209 /// use circular_queue::CircularQueue;
210 ///
211 /// let mut queue = CircularQueue::with_capacity(3);
212 ///
213 /// queue.push(1);
214 /// queue.push(2);
215 ///
216 /// assert_eq!(queue.push(3), None);
217 /// assert_eq!(queue.push(4), Some(1));
218 ///
219 /// assert_eq!(queue.len(), 3);
220 ///
221 /// let mut iter = queue.iter();
222 ///
223 /// assert_eq!(iter.next(), Some(&4));
224 /// assert_eq!(iter.next(), Some(&3));
225 /// assert_eq!(iter.next(), Some(&2));
226 /// ```
227 #[inline]
228 pub fn push(&mut self, x: T) -> Popped<T> {
229 let mut old = None;
230
231 if self.capacity() == 0 {
232 return old;
233 }
234
235 if !self.is_full() {
236 self.data.push(x);
237 } else {
238 old = Some(replace(&mut self.data[self.insertion_index], x));
239 }
240
241 self.insertion_index = (self.insertion_index + 1) % self.capacity();
242
243 old
244 }
245
246 /// Returns an iterator over the queue's contents.
247 ///
248 /// The iterator goes from the most recently pushed items to the oldest ones.
249 ///
250 /// # Examples
251 ///
252 /// ```
253 /// use circular_queue::CircularQueue;
254 ///
255 /// let mut queue = CircularQueue::with_capacity(3);
256 /// queue.push(1);
257 /// queue.push(2);
258 /// queue.push(3);
259 /// queue.push(4);
260 ///
261 /// let mut iter = queue.iter();
262 ///
263 /// assert_eq!(iter.next(), Some(&4));
264 /// assert_eq!(iter.next(), Some(&3));
265 /// assert_eq!(iter.next(), Some(&2));
266 /// ```
267 #[inline]
268 pub fn iter(&self) -> Iter<T> {
269 let (a, b) = self.data.split_at(self.insertion_index);
270 a.iter().rev().chain(b.iter().rev())
271 }
272
273 /// Returns a mutable iterator over the queue's contents.
274 ///
275 /// The iterator goes from the most recently pushed items to the oldest ones.
276 ///
277 /// # Examples
278 ///
279 /// ```
280 /// use circular_queue::CircularQueue;
281 ///
282 /// let mut queue = CircularQueue::with_capacity(3);
283 /// queue.push(1);
284 /// queue.push(2);
285 /// queue.push(3);
286 /// queue.push(4);
287 ///
288 /// let mut iter = queue.iter_mut();
289 ///
290 /// assert_eq!(iter.next(), Some(&mut 4));
291 /// assert_eq!(iter.next(), Some(&mut 3));
292 /// assert_eq!(iter.next(), Some(&mut 2));
293 /// ```
294 #[inline]
295 pub fn iter_mut(&mut self) -> IterMut<T> {
296 let (a, b) = self.data.split_at_mut(self.insertion_index);
297 a.iter_mut().rev().chain(b.iter_mut().rev())
298 }
299
300 /// Returns an ascending iterator over the queue's contents.
301 ///
302 /// The iterator goes from the least recently pushed items to the newest ones.
303 ///
304 /// # Examples
305 ///
306 /// ```
307 /// use circular_queue::CircularQueue;
308 ///
309 /// let mut queue = CircularQueue::with_capacity(3);
310 /// queue.push(1);
311 /// queue.push(2);
312 /// queue.push(3);
313 /// queue.push(4);
314 ///
315 /// let mut iter = queue.asc_iter();
316 ///
317 /// assert_eq!(iter.next(), Some(&2));
318 /// assert_eq!(iter.next(), Some(&3));
319 /// assert_eq!(iter.next(), Some(&4));
320 /// ```
321 #[inline]
322 pub fn asc_iter(&self) -> AscIter<T> {
323 let (a, b) = self.data.split_at(self.insertion_index);
324 b.iter().chain(a.iter())
325 }
326
327 /// Returns a mutable ascending iterator over the queue's contents.
328 ///
329 /// The iterator goes from the least recently pushed items to the newest ones.
330 ///
331 /// # Examples
332 ///
333 /// ```
334 /// use circular_queue::CircularQueue;
335 ///
336 /// let mut queue = CircularQueue::with_capacity(3);
337 /// queue.push(1);
338 /// queue.push(2);
339 /// queue.push(3);
340 /// queue.push(4);
341 ///
342 /// let mut iter = queue.asc_iter_mut();
343 ///
344 /// assert_eq!(iter.next(), Some(&mut 2));
345 /// assert_eq!(iter.next(), Some(&mut 3));
346 /// assert_eq!(iter.next(), Some(&mut 4));
347 /// ```
348 #[inline]
349 pub fn asc_iter_mut(&mut self) -> AscIterMut<T> {
350 let (a, b) = self.data.split_at_mut(self.insertion_index);
351 b.iter_mut().chain(a.iter_mut())
352 }
353
354 /// Converts the queue into a `Vec<T>` going from the most recently pushed items to the oldest
355 /// ones.
356 ///
357 /// # Examples
358 ///
359 /// ```
360 /// use circular_queue::CircularQueue;
361 ///
362 /// let mut queue = CircularQueue::with_capacity(3);
363 /// queue.push(1);
364 /// queue.push(2);
365 /// queue.push(3);
366 /// queue.push(4);
367 ///
368 /// let v = queue.into_vec();
369 ///
370 /// assert_eq!(v, vec![4, 3, 2]);
371 /// ```
372 #[inline]
373 pub fn into_vec(mut self) -> Vec<T> {
374 self.data[self.insertion_index..].reverse(); // Reverse the upper part.
375 self.data[..self.insertion_index].reverse(); // Reverse the lower part.
376 self.data
377 }
378}
379
380impl<T: PartialEq> PartialEq for CircularQueue<T> {
381 #[inline]
382 fn eq(&self, other: &CircularQueue<T>) -> bool {
383 self.len() == other.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
384 }
385}
386
387impl<T: Eq> Eq for CircularQueue<T> {}
388
389#[cfg(has_relaxed_orphan_rule)]
390impl<T> From<CircularQueue<T>> for Vec<T> {
391 #[inline]
392 fn from(queue: CircularQueue<T>) -> Self {
393 queue.into_vec()
394 }
395}
396
397#[cfg(test)]
398mod tests {
399 use super::*;
400 #[cfg(has_extern_crate_alloc)]
401 use alloc::vec;
402
403 #[test]
404 fn zero_capacity() {
405 let mut q = CircularQueue::<i32>::with_capacity(0);
406 assert_eq!(q.len(), 0);
407 assert_eq!(q.capacity(), 0);
408 assert!(q.is_empty());
409
410 q.push(3);
411 q.push(4);
412 q.push(5);
413
414 assert_eq!(q.len(), 0);
415 assert_eq!(q.capacity(), 0);
416 assert!(q.is_empty());
417
418 assert_eq!(q.iter().count(), 0);
419 assert_eq!(q.asc_iter().count(), 0);
420
421 q.clear();
422 }
423
424 #[test]
425 fn empty_queue() {
426 let q = CircularQueue::<i32>::with_capacity(5);
427
428 assert!(q.is_empty());
429 assert_eq!(q.iter().next(), None);
430 }
431
432 #[test]
433 fn partially_full_queue() {
434 let mut q = CircularQueue::with_capacity(5);
435 q.push(1);
436 q.push(2);
437 q.push(3);
438
439 assert!(!q.is_empty());
440 assert_eq!(q.len(), 3);
441
442 let res: Vec<_> = q.iter().map(|&x| x).collect();
443 assert_eq!(res, [3, 2, 1]);
444 }
445
446 #[test]
447 fn full_queue() {
448 let mut q = CircularQueue::with_capacity(5);
449 q.push(1);
450 q.push(2);
451 q.push(3);
452 q.push(4);
453 q.push(5);
454
455 assert_eq!(q.len(), 5);
456
457 let res: Vec<_> = q.iter().map(|&x| x).collect();
458 assert_eq!(res, [5, 4, 3, 2, 1]);
459 }
460
461 #[test]
462 fn over_full_queue() {
463 let mut q = CircularQueue::with_capacity(5);
464 q.push(1);
465 q.push(2);
466 q.push(3);
467 q.push(4);
468 q.push(5);
469 q.push(6);
470 q.push(7);
471
472 assert_eq!(q.len(), 5);
473
474 let res: Vec<_> = q.iter().map(|&x| x).collect();
475 assert_eq!(res, [7, 6, 5, 4, 3]);
476 }
477
478 #[test]
479 fn clear() {
480 let mut q = CircularQueue::with_capacity(5);
481 q.push(1);
482 q.push(2);
483 q.push(3);
484 q.push(4);
485 q.push(5);
486 q.push(6);
487 q.push(7);
488
489 q.clear();
490
491 assert_eq!(q.len(), 0);
492 assert_eq!(q.iter().next(), None);
493
494 q.push(1);
495 q.push(2);
496 q.push(3);
497
498 assert_eq!(q.len(), 3);
499
500 let res: Vec<_> = q.iter().map(|&x| x).collect();
501 assert_eq!(res, [3, 2, 1]);
502 }
503
504 #[test]
505 fn mutable_iterator() {
506 let mut q = CircularQueue::with_capacity(5);
507 q.push(1);
508 q.push(2);
509 q.push(3);
510 q.push(4);
511 q.push(5);
512 q.push(6);
513 q.push(7);
514
515 for x in q.iter_mut() {
516 *x *= 2;
517 }
518
519 let res: Vec<_> = q.iter().map(|&x| x).collect();
520 assert_eq!(res, [14, 12, 10, 8, 6]);
521 }
522
523 #[test]
524 fn zero_sized() {
525 let mut q = CircularQueue::with_capacity(3);
526 assert_eq!(q.capacity(), 3);
527
528 q.push(());
529 q.push(());
530 q.push(());
531 q.push(());
532
533 assert_eq!(q.len(), 3);
534
535 let mut iter = q.iter();
536 assert_eq!(iter.next(), Some(&()));
537 assert_eq!(iter.next(), Some(&()));
538 assert_eq!(iter.next(), Some(&()));
539 assert_eq!(iter.next(), None);
540 }
541
542 #[test]
543 fn empty_queue_eq() {
544 let q1 = CircularQueue::<i32>::with_capacity(5);
545 let q2 = CircularQueue::<i32>::with_capacity(5);
546 assert_eq!(q1, q2);
547
548 let q3 = CircularQueue::<i32>::with_capacity(6);
549 assert_eq!(q1, q3); // Capacity doesn't matter as long as the same elements are yielded.
550 }
551
552 #[test]
553 fn partially_full_queue_eq() {
554 let mut q1 = CircularQueue::with_capacity(5);
555 q1.push(1);
556 q1.push(2);
557 q1.push(3);
558
559 let mut q2 = CircularQueue::with_capacity(5);
560 q2.push(1);
561 q2.push(2);
562 assert_ne!(q1, q2);
563
564 q2.push(3);
565 assert_eq!(q1, q2);
566
567 q2.push(4);
568 assert_ne!(q1, q2);
569 }
570
571 #[test]
572 fn full_queue_eq() {
573 let mut q1 = CircularQueue::with_capacity(5);
574 q1.push(1);
575 q1.push(2);
576 q1.push(3);
577 q1.push(4);
578 q1.push(5);
579
580 let mut q2 = CircularQueue::with_capacity(5);
581 q2.push(1);
582 q2.push(2);
583 q2.push(3);
584 q2.push(4);
585 q2.push(5);
586
587 assert_eq!(q1, q2);
588 }
589
590 #[test]
591 fn over_full_queue_eq() {
592 let mut q1 = CircularQueue::with_capacity(5);
593 q1.push(1);
594 q1.push(2);
595 q1.push(3);
596 q1.push(4);
597 q1.push(5);
598 q1.push(6);
599 q1.push(7);
600
601 let mut q2 = CircularQueue::with_capacity(5);
602 q2.push(1);
603 q2.push(2);
604 q2.push(3);
605 q2.push(4);
606 q2.push(5);
607 q2.push(6);
608 assert_ne!(q1, q2);
609
610 q2.push(7);
611 assert_eq!(q1, q2);
612
613 q2.push(8);
614 assert_ne!(q1, q2);
615
616 q2.push(3);
617 q2.push(4);
618 q2.push(5);
619 q2.push(6);
620 q2.push(7);
621 assert_eq!(q1, q2);
622 }
623
624 #[test]
625 fn clear_eq() {
626 let mut q1 = CircularQueue::with_capacity(5);
627 q1.push(1);
628 q1.push(2);
629 q1.push(3);
630 q1.push(4);
631 q1.push(5);
632 q1.push(6);
633 q1.push(7);
634 q1.clear();
635
636 let mut q2 = CircularQueue::with_capacity(5);
637 assert_eq!(q1, q2);
638
639 q2.push(1);
640 q2.clear();
641 assert_eq!(q1, q2);
642 }
643
644 #[test]
645 fn zero_sized_eq() {
646 let mut q1 = CircularQueue::with_capacity(3);
647 q1.push(());
648 q1.push(());
649 q1.push(());
650 q1.push(());
651
652 let mut q2 = CircularQueue::with_capacity(3);
653 q2.push(());
654 q2.push(());
655 assert_ne!(q1, q2);
656
657 q2.push(());
658 assert_eq!(q1, q2);
659
660 q2.push(());
661 assert_eq!(q1, q2);
662
663 q2.push(());
664 assert_eq!(q1, q2);
665 }
666
667 #[test]
668 fn into_vec() {
669 let mut q = CircularQueue::with_capacity(4);
670 q.push(1);
671 q.push(2);
672 q.push(3);
673
674 let v = q.clone().into_vec();
675 assert_eq!(v, vec![3, 2, 1]);
676
677 q.push(4);
678 q.push(5);
679 let v = q.clone().into_vec();
680 assert_eq!(v, vec![5, 4, 3, 2]);
681
682 q.push(6);
683 let v = q.into_vec();
684 assert_eq!(v, vec![6, 5, 4, 3]);
685 }
686
687 #[cfg(has_relaxed_orphan_rule)]
688 #[test]
689 fn vec_from() {
690 let mut q = CircularQueue::with_capacity(3);
691 q.push(1);
692 q.push(2);
693 q.push(3);
694 q.push(4);
695
696 let v = Vec::from(q);
697 assert_eq!(v, vec![4, 3, 2]);
698 }
699}