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.6")]
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
355impl<T: PartialEq> PartialEq for CircularQueue<T> {
356    #[inline]
357    fn eq(&self, other: &CircularQueue<T>) -> bool {
358        self.len() == other.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
359    }
360}
361
362impl<T: Eq> Eq for CircularQueue<T> {}
363
364#[cfg(test)]
365mod tests {
366    use super::*;
367
368    #[test]
369    fn zero_capacity() {
370        let mut q = CircularQueue::<i32>::with_capacity(0);
371        assert_eq!(q.len(), 0);
372        assert_eq!(q.capacity(), 0);
373        assert!(q.is_empty());
374
375        q.push(3);
376        q.push(4);
377        q.push(5);
378
379        assert_eq!(q.len(), 0);
380        assert_eq!(q.capacity(), 0);
381        assert!(q.is_empty());
382
383        assert_eq!(q.iter().count(), 0);
384        assert_eq!(q.asc_iter().count(), 0);
385
386        q.clear();
387    }
388
389    #[test]
390    fn empty_queue() {
391        let q = CircularQueue::<i32>::with_capacity(5);
392
393        assert!(q.is_empty());
394        assert_eq!(q.iter().next(), None);
395    }
396
397    #[test]
398    fn partially_full_queue() {
399        let mut q = CircularQueue::with_capacity(5);
400        q.push(1);
401        q.push(2);
402        q.push(3);
403
404        assert!(!q.is_empty());
405        assert_eq!(q.len(), 3);
406
407        let res: Vec<_> = q.iter().map(|&x| x).collect();
408        assert_eq!(res, [3, 2, 1]);
409    }
410
411    #[test]
412    fn full_queue() {
413        let mut q = CircularQueue::with_capacity(5);
414        q.push(1);
415        q.push(2);
416        q.push(3);
417        q.push(4);
418        q.push(5);
419
420        assert_eq!(q.len(), 5);
421
422        let res: Vec<_> = q.iter().map(|&x| x).collect();
423        assert_eq!(res, [5, 4, 3, 2, 1]);
424    }
425
426    #[test]
427    fn over_full_queue() {
428        let mut q = CircularQueue::with_capacity(5);
429        q.push(1);
430        q.push(2);
431        q.push(3);
432        q.push(4);
433        q.push(5);
434        q.push(6);
435        q.push(7);
436
437        assert_eq!(q.len(), 5);
438
439        let res: Vec<_> = q.iter().map(|&x| x).collect();
440        assert_eq!(res, [7, 6, 5, 4, 3]);
441    }
442
443    #[test]
444    fn clear() {
445        let mut q = CircularQueue::with_capacity(5);
446        q.push(1);
447        q.push(2);
448        q.push(3);
449        q.push(4);
450        q.push(5);
451        q.push(6);
452        q.push(7);
453
454        q.clear();
455
456        assert_eq!(q.len(), 0);
457        assert_eq!(q.iter().next(), None);
458
459        q.push(1);
460        q.push(2);
461        q.push(3);
462
463        assert_eq!(q.len(), 3);
464
465        let res: Vec<_> = q.iter().map(|&x| x).collect();
466        assert_eq!(res, [3, 2, 1]);
467    }
468
469    #[test]
470    fn mutable_iterator() {
471        let mut q = CircularQueue::with_capacity(5);
472        q.push(1);
473        q.push(2);
474        q.push(3);
475        q.push(4);
476        q.push(5);
477        q.push(6);
478        q.push(7);
479
480        for x in q.iter_mut() {
481            *x *= 2;
482        }
483
484        let res: Vec<_> = q.iter().map(|&x| x).collect();
485        assert_eq!(res, [14, 12, 10, 8, 6]);
486    }
487
488    #[test]
489    fn zero_sized() {
490        let mut q = CircularQueue::with_capacity(3);
491        assert_eq!(q.capacity(), 3);
492
493        q.push(());
494        q.push(());
495        q.push(());
496        q.push(());
497
498        assert_eq!(q.len(), 3);
499
500        let mut iter = q.iter();
501        assert_eq!(iter.next(), Some(&()));
502        assert_eq!(iter.next(), Some(&()));
503        assert_eq!(iter.next(), Some(&()));
504        assert_eq!(iter.next(), None);
505    }
506
507    #[test]
508    fn empty_queue_eq() {
509        let q1 = CircularQueue::<i32>::with_capacity(5);
510        let q2 = CircularQueue::<i32>::with_capacity(5);
511        assert_eq!(q1, q2);
512
513        let q3 = CircularQueue::<i32>::with_capacity(6);
514        assert_eq!(q1, q3); // Capacity doesn't matter as long as the same elements are yielded.
515    }
516
517    #[test]
518    fn partially_full_queue_eq() {
519        let mut q1 = CircularQueue::with_capacity(5);
520        q1.push(1);
521        q1.push(2);
522        q1.push(3);
523
524        let mut q2 = CircularQueue::with_capacity(5);
525        q2.push(1);
526        q2.push(2);
527        assert_ne!(q1, q2);
528
529        q2.push(3);
530        assert_eq!(q1, q2);
531
532        q2.push(4);
533        assert_ne!(q1, q2);
534    }
535
536    #[test]
537    fn full_queue_eq() {
538        let mut q1 = CircularQueue::with_capacity(5);
539        q1.push(1);
540        q1.push(2);
541        q1.push(3);
542        q1.push(4);
543        q1.push(5);
544
545        let mut q2 = CircularQueue::with_capacity(5);
546        q2.push(1);
547        q2.push(2);
548        q2.push(3);
549        q2.push(4);
550        q2.push(5);
551
552        assert_eq!(q1, q2);
553    }
554
555    #[test]
556    fn over_full_queue_eq() {
557        let mut q1 = CircularQueue::with_capacity(5);
558        q1.push(1);
559        q1.push(2);
560        q1.push(3);
561        q1.push(4);
562        q1.push(5);
563        q1.push(6);
564        q1.push(7);
565
566        let mut q2 = CircularQueue::with_capacity(5);
567        q2.push(1);
568        q2.push(2);
569        q2.push(3);
570        q2.push(4);
571        q2.push(5);
572        q2.push(6);
573        assert_ne!(q1, q2);
574
575        q2.push(7);
576        assert_eq!(q1, q2);
577
578        q2.push(8);
579        assert_ne!(q1, q2);
580
581        q2.push(3);
582        q2.push(4);
583        q2.push(5);
584        q2.push(6);
585        q2.push(7);
586        assert_eq!(q1, q2);
587    }
588
589    #[test]
590    fn clear_eq() {
591        let mut q1 = CircularQueue::with_capacity(5);
592        q1.push(1);
593        q1.push(2);
594        q1.push(3);
595        q1.push(4);
596        q1.push(5);
597        q1.push(6);
598        q1.push(7);
599        q1.clear();
600
601        let mut q2 = CircularQueue::with_capacity(5);
602        assert_eq!(q1, q2);
603
604        q2.push(1);
605        q2.clear();
606        assert_eq!(q1, q2);
607    }
608
609    #[test]
610    fn zero_sized_eq() {
611        let mut q1 = CircularQueue::with_capacity(3);
612        q1.push(());
613        q1.push(());
614        q1.push(());
615        q1.push(());
616
617        let mut q2 = CircularQueue::with_capacity(3);
618        q2.push(());
619        q2.push(());
620        assert_ne!(q1, q2);
621
622        q2.push(());
623        assert_eq!(q1, q2);
624
625        q2.push(());
626        assert_eq!(q1, q2);
627
628        q2.push(());
629        assert_eq!(q1, q2);
630    }
631}
circular_queue/lib.rs

circular_queue/
lib.rs
