lobby_queue/
lib.rs

1//! This crate provides a const-size queue-like data structure. When full, pushing new items will
2//! remove the head (first-added) items.
3//!
4//! ```toml
5//! [dependencies]
6//! lobby-queue = "0.2"
7//! ```
8//!
9//! ```
10//! use lobby_queue::Lobby;
11//!
12//! let mut m = Lobby::new([None, None, None]);
13//!
14//! m.push(0);
15//! m.push(1);
16//! m.push(2);
17//! assert_eq!(Some(&0), m.first());
18//!
19//! let v0 = m.push(3);
20//! assert_eq!(Some(0), v0);
21//! assert_eq!(Some(&1), m.first());
22//!
23//! for v in m {
24//!     println!("{}", v);
25//! }
26//! ```
27
28pub mod iter;
29
30use crate::iter::{IntoIter, Iter, IterMut};
31
32use std::mem;
33
34/// A const-size queue-like data structure.
35#[derive(Debug, Clone)]
36pub struct Lobby<T, const N: usize> {
37    arr: [Option<T>; N],
38
39    head: usize,
40    tail: usize,
41
42    len: usize,
43}
44
45impl<T, const N: usize> Lobby<T, N> {
46    /// Create a new Lobby. The caller **must** pass in an array of all [`None`].
47    ///
48    /// # Limitation
49    ///
50    /// Until some workaround/fix for [#44796](https://github.com/rust-lang/rust/issues/44796)
51    /// becomes available, an initial array must be passed in.
52    ///
53    /// ```
54    /// use lobby_queue::Lobby;
55    ///
56    /// let mut lobby = Lobby::new([None, None, None, None]);
57    /// lobby.push(0);
58    /// ```
59    #[inline]
60    pub const fn new(arr: [Option<T>; N]) -> Self {
61        Self {
62            arr,
63            head: 0,
64            tail: 0,
65            len: 0,
66        }
67    }
68
69    /// Get the head item.
70    ///
71    /// ```
72    /// use lobby_queue::Lobby;
73    ///
74    /// let mut lobby = Lobby::new([None, None, None]);
75    /// assert_eq!(None, lobby.first());
76    ///
77    /// lobby.push(0);
78    /// assert_eq!(Some(&0), lobby.first());
79    ///
80    /// lobby.push(1);
81    /// assert_eq!(Some(&0), lobby.first());
82    /// ```
83    #[inline]
84    pub const fn first(&self) -> Option<&T> {
85        self.arr[self.head].as_ref()
86    }
87
88    /// Get a mutable reference to the head item. See [`Self::first`].
89    #[inline]
90    pub fn first_mut(&mut self) -> Option<&mut T> {
91        self.arr[self.head].as_mut()
92    }
93
94    /// Get the tail item.
95    ///
96    /// ```
97    /// use lobby_queue::Lobby;
98    ///
99    /// let mut lobby = Lobby::new([None, None, None]);
100    /// assert_eq!(None, lobby.last());
101    ///
102    /// lobby.push(0);
103    /// assert_eq!(Some(&0), lobby.last());
104    ///
105    /// lobby.push(1);
106    /// assert_eq!(Some(&1), lobby.last());
107    /// ```
108    #[inline]
109    pub const fn last(&self) -> Option<&T> {
110        self.arr[self.tail].as_ref()
111    }
112
113    /// Get a mutable reference to the head item. See [`Self::last`].
114    #[inline]
115    pub fn last_mut(&mut self) -> Option<&mut T> {
116        self.arr[self.tail].as_mut()
117    }
118
119    /// Get the nth item.
120    ///
121    /// ```
122    /// use lobby_queue::Lobby;
123    ///
124    /// let mut lobby = Lobby::new([None, None, None]);
125    /// assert_eq!(None, lobby.nth(1));
126    ///
127    /// lobby.push(0);
128    /// assert_eq!(None, lobby.nth(1));
129    ///
130    /// lobby.push(1);
131    /// assert_eq!(Some(&1), lobby.nth(1));
132    /// ```
133    ///
134    /// # Panics
135    ///
136    /// Panics if `n` is greater than or equal to `N`.
137    ///
138    /// ```should_panic
139    /// use lobby_queue::Lobby;
140    ///
141    /// let mut lobby = Lobby::new([None, None, None]);
142    /// lobby.push(0);
143    ///
144    /// let _ = lobby.nth(3);
145    /// ```
146    #[inline]
147    pub const fn nth(&self, n: usize) -> Option<&T> {
148        let idx = if n >= N {
149            N
150        } else {
151            Self::mod_incr(self.head, n)
152        };
153
154        self.arr[idx].as_ref()
155    }
156
157    /// Get a mutable reference to the nth item. See [`Self::nth`].
158    ///
159    /// ```
160    /// use lobby_queue::Lobby;
161    ///
162    /// let mut lobby = Lobby::new([None, None, None]);
163    ///
164    /// lobby.push(0);
165    /// lobby.push(1);
166    ///
167    /// let v1 = lobby.nth_mut(1).unwrap();
168    /// *v1 = 3;
169    ///
170    /// assert_eq!(Some(&3), lobby.nth(1));
171    /// ```
172    ///
173    /// # Panics
174    ///
175    /// Panics under the same conditions as [`Self::nth`].
176    #[inline]
177    pub fn nth_mut(&mut self, n: usize) -> Option<&mut T> {
178        let idx = if n >= N {
179            N
180        } else {
181            Self::mod_incr(self.head, n)
182        };
183
184        self.arr[idx].as_mut()
185    }
186
187    /// Push a new item to the lobby, returning the head if the lobby is currently full.
188    ///
189    /// ```
190    /// use lobby_queue::Lobby;
191    ///
192    /// let mut lobby = Lobby::new([None, None, None]);
193    ///
194    /// lobby.push(0);
195    /// assert_eq!(Some(&0), lobby.first());
196    ///
197    /// lobby.push(1);
198    /// assert_eq!(Some(&0), lobby.first());
199    ///
200    /// lobby.push(2);
201    /// assert_eq!(Some(&0), lobby.first());
202    ///
203    /// lobby.push(3);
204    /// assert_eq!(Some(&1), lobby.first());
205    /// ```
206    #[inline]
207    pub fn push(&mut self, v: T) -> Option<T> {
208        if self.arr[self.tail].is_some() {
209            // Increment tail position to insert at next spot.
210            self.tail = Self::mod_incr(self.tail, 1);
211        }
212
213        // Make push.
214        let mut v = Some(v);
215        mem::swap(&mut v, &mut self.arr[self.tail]);
216
217        // Head position should be moved if the new element overrides an old.
218        if v.is_some() {
219            self.head = Self::mod_incr(self.head, 1);
220        } else {
221            self.len += 1;
222        }
223
224        v
225    }
226
227    /// Shift out the head item from the lobby.
228    ///
229    /// ```
230    /// use lobby_queue::Lobby;
231    ///
232    /// let mut lobby = Lobby::new([None, None, None]);
233    /// lobby.push(0);
234    /// lobby.push(1);
235    /// lobby.push(2);
236    ///
237    /// assert_eq!(Some(0), lobby.shift());
238    /// assert_eq!(Some(1), lobby.shift());
239    /// assert_eq!(Some(2), lobby.shift());
240    /// assert_eq!(None, lobby.shift());
241    /// ```
242    #[inline]
243    pub fn shift(&mut self) -> Option<T> {
244        let mut v = None;
245        mem::swap(&mut v, &mut self.arr[self.head]);
246
247        let next = Self::mod_incr(self.head, 1);
248        if self.arr[next].is_some() {
249            self.head = next;
250        }
251
252        if v.is_some() {
253            self.len -= 1;
254        }
255
256        v
257    }
258
259    /// Pop off the tail item from the lobby.
260    ///
261    /// ```
262    /// use lobby_queue::Lobby;
263    ///
264    /// let mut lobby = Lobby::new([None, None, None]);
265    /// lobby.push(0);
266    /// lobby.push(1);
267    /// lobby.push(2);
268    ///
269    /// assert_eq!(Some(2), lobby.pop());
270    /// assert_eq!(Some(1), lobby.pop());
271    /// assert_eq!(Some(0), lobby.pop());
272    /// assert_eq!(None, lobby.pop());
273    /// ```
274    #[inline]
275    pub fn pop(&mut self) -> Option<T> {
276        let mut v = None;
277        mem::swap(&mut v, &mut self.arr[self.tail]);
278
279        let prev = Self::mod_decr(self.tail, 1);
280        if self.arr[prev].is_some() {
281            self.tail = prev;
282        }
283
284        if v.is_some() {
285            self.len -= 1;
286        }
287
288        v
289    }
290
291    /// Returns `true` if the Lobby is empty, `false` if it is not.
292    ///
293    /// ```
294    /// use lobby_queue::Lobby;
295    ///
296    /// let mut lobby = Lobby::new([None, None, None]);
297    /// assert!(lobby.is_empty());
298    ///
299    /// lobby.push(0);
300    /// assert!(!lobby.is_empty());
301    ///
302    /// lobby.shift();
303    /// assert!(lobby.is_empty());
304    /// ```
305    #[inline]
306    pub const fn is_empty(&self) -> bool {
307        self.len == 0
308    }
309
310    /// Returns `true` if the Lobby is full, `false` if it is not.
311    ///
312    /// ```
313    /// use lobby_queue::Lobby;
314    ///
315    /// let mut lobby = Lobby::new([None, None, None]);
316    /// assert!(!lobby.is_full());
317    ///
318    /// lobby.push(0);
319    /// assert!(!lobby.is_full());
320    ///
321    /// lobby.push(1);
322    /// assert!(!lobby.is_full());
323    ///
324    /// lobby.push(2);
325    /// assert!(lobby.is_full());
326    /// ```
327    #[inline]
328    pub const fn is_full(&self) -> bool {
329        Self::mod_incr(self.tail, 1) == self.head
330    }
331
332    /// Returns the current number of items stored in the lobby.
333    #[inline]
334    pub const fn len(&self) -> usize {
335        self.len
336    }
337
338    /// Returns the capacity of the lobby, which will always be `N`.
339    #[inline]
340    pub const fn capacity(&self) -> usize {
341        N
342    }
343
344    #[inline]
345    const fn mod_incr(counter: usize, d: usize) -> usize {
346        (counter + d) % N
347    }
348
349    #[inline]
350    const fn mod_decr(counter: usize, d: usize) -> usize {
351        let d = d % N;
352        if counter >= d {
353            counter - d
354        } else {
355            counter + N - d
356        }
357    }
358}
359
360impl<T, const N: usize> PartialEq<Lobby<T, N>> for Lobby<T, N>
361where
362    T: PartialEq,
363{
364    #[inline]
365    fn eq(&self, other: &Lobby<T, N>) -> bool {
366        self.iter().eq(other.iter())
367    }
368}
369
370impl<T, const N: usize> PartialEq<[Option<T>; N]> for Lobby<T, N>
371where
372    T: PartialEq,
373{
374    #[inline]
375    fn eq(&self, other: &[Option<T>; N]) -> bool {
376        self.iter().with_full().eq(other.iter().map(|v| v.as_ref()))
377    }
378}
379
380impl<T, const N: usize> Lobby<T, N> {
381    /// Returns an iterator over the items in the lobby.
382    #[inline]
383    pub fn iter(&self) -> Iter<'_, T, N> {
384        Iter::new(self)
385    }
386
387    /// Returns an iterator that allows modifying each value.
388    #[inline]
389    pub fn iter_mut(&mut self) -> IterMut<'_, T, N> {
390        IterMut::new(self)
391    }
392}
393
394impl<T, const N: usize> IntoIterator for Lobby<T, N> {
395    type Item = T;
396    type IntoIter = IntoIter<T, N>;
397
398    #[inline]
399    fn into_iter(self) -> IntoIter<T, N> {
400        IntoIter::new(self)
401    }
402}
403
404#[cfg(test)]
405mod test {
406    use super::*;
407
408    #[test]
409    fn test_push() {
410        let mut x = Lobby::new([None, None, None]);
411
412        x.push(0);
413        assert_eq!([Some(0), None, None], x.arr);
414        assert_eq!((0, 0), (x.head, x.tail));
415        assert_eq!(1, x.len());
416
417        x.push(1);
418        assert_eq!([Some(0), Some(1), None], x.arr);
419        assert_eq!((0, 1), (x.head, x.tail));
420        assert_eq!(2, x.len());
421
422        x.push(2);
423        assert_eq!([Some(0), Some(1), Some(2)], x.arr);
424        assert_eq!((0, 2), (x.head, x.tail));
425        assert_eq!(3, x.len());
426
427        let v0 = x.push(3);
428        assert_eq!(Some(0), v0);
429        assert_eq!([Some(3), Some(1), Some(2)], x.arr);
430        assert_eq!((1, 0), (x.head, x.tail));
431        assert_eq!(3, x.len());
432
433        let v1 = x.push(4);
434        assert_eq!(Some(1), v1);
435        assert_eq!([Some(3), Some(4), Some(2)], x.arr);
436        assert_eq!((2, 1), (x.head, x.tail));
437        assert_eq!(3, x.len());
438    }
439
440    #[test]
441    fn test_shift() {
442        let mut x = Lobby::new([None, None, None]);
443        x.push(0);
444        x.push(1);
445        x.push(2);
446
447        assert_eq!([Some(0), Some(1), Some(2)], x.arr);
448        assert_eq!((0, 2), (x.head, x.tail));
449        assert_eq!(3, x.len());
450
451        let v0 = x.shift();
452        assert_eq!(Some(0), v0);
453        assert_eq!([None, Some(1), Some(2)], x.arr);
454        assert_eq!((1, 2), (x.head, x.tail));
455        assert_eq!(2, x.len());
456
457        let v1 = x.shift();
458        assert_eq!(Some(1), v1);
459        assert_eq!([None, None, Some(2)], x.arr);
460        assert_eq!((2, 2), (x.head, x.tail));
461        assert_eq!(1, x.len());
462
463        let v2 = x.shift();
464        assert_eq!(Some(2), v2);
465        assert_eq!([None, None, None], x.arr);
466        assert_eq!((2, 2), (x.head, x.tail));
467        assert_eq!(0, x.len());
468
469        let ve = x.shift();
470        assert_eq!(None, ve);
471        assert_eq!([None, None, None], x.arr);
472        assert_eq!((2, 2), (x.head, x.tail));
473        assert_eq!(0, x.len());
474    }
475
476    #[test]
477    fn test_pop() {
478        let mut x = Lobby::new([None, None, None]);
479        x.push(0);
480        x.push(1);
481        x.push(2);
482
483        assert_eq!([Some(0), Some(1), Some(2)], x.arr);
484        assert_eq!((0, 2), (x.head, x.tail));
485        assert_eq!(3, x.len());
486
487        let v2 = x.pop();
488        assert_eq!(Some(2), v2);
489        assert_eq!([Some(0), Some(1), None], x.arr);
490        assert_eq!((0, 1), (x.head, x.tail));
491        assert_eq!(2, x.len());
492
493        let v1 = x.pop();
494        assert_eq!(Some(1), v1);
495        assert_eq!([Some(0), None, None], x.arr);
496        assert_eq!((0, 0), (x.head, x.tail));
497        assert_eq!(1, x.len());
498
499        let v0 = x.pop();
500        assert_eq!(Some(0), v0);
501        assert_eq!([None, None, None], x.arr);
502        assert_eq!((0, 0), (x.head, x.tail));
503        assert_eq!(0, x.len());
504
505        let ve = x.pop();
506        assert_eq!(None, ve);
507        assert_eq!([None, None, None], x.arr);
508        assert_eq!((0, 0), (x.head, x.tail));
509        assert_eq!(0, x.len());
510    }
511
512    #[test]
513    fn test_is_empty() {
514        let mut x = Lobby::new([None, None, None]);
515        assert!(x.is_empty());
516
517        // [0, _, _]
518        x.push(0);
519        assert!(!x.is_empty());
520
521        // [0, 1, _]
522        x.push(1);
523        assert!(!x.is_empty());
524
525        // [0, 1, 2]
526        x.push(2);
527        assert!(!x.is_empty());
528
529        // [3, 1, 2]
530        x.push(3);
531        assert!(!x.is_empty());
532
533        // [3, _, 2]
534        x.shift();
535        assert!(!x.is_empty());
536
537        // [3, _, 2]
538        x.shift();
539        assert!(!x.is_empty());
540
541        // [_, _, _]
542        x.shift();
543        assert!(x.is_empty());
544    }
545
546    #[test]
547    fn test_is_full() {
548        let mut x = Lobby::new([None, None, None]);
549        assert!(!x.is_full());
550
551        // [0, _, _]
552        x.push(0);
553        assert!(!x.is_full());
554
555        // [0, 1, _]
556        x.push(1);
557        assert!(!x.is_full());
558
559        // [0, 1, 2]
560        x.push(2);
561        assert!(x.is_full());
562
563        // [3, 1, 2]
564        x.push(3);
565        assert!(x.is_full());
566
567        // [3, _, 2]
568        x.shift();
569        assert!(!x.is_full());
570
571        // [3, _, 2]
572        x.shift();
573        assert!(!x.is_full());
574
575        // [_, _, _]
576        x.shift();
577        assert!(!x.is_full());
578    }
579
580    #[test]
581    fn test_increase_counter() {
582        type L = Lobby<usize, 4>;
583
584        let x = 0;
585        assert_eq!(1, L::mod_incr(x, 1));
586        assert_eq!(2, L::mod_incr(x, 2));
587        assert_eq!(3, L::mod_incr(x, 3));
588        assert_eq!(0, L::mod_incr(x, 4));
589        assert_eq!(1, L::mod_incr(x, 5));
590        assert_eq!(0, L::mod_incr(x, 8));
591        assert_eq!(1, L::mod_incr(x, 9));
592    }
593
594    #[test]
595    fn test_decrease_counter() {
596        type L = Lobby<usize, 4>;
597
598        let x = 2;
599        assert_eq!(1, L::mod_decr(x, 1));
600        assert_eq!(0, L::mod_decr(x, 2));
601        assert_eq!(3, L::mod_decr(x, 3));
602        assert_eq!(2, L::mod_decr(x, 4));
603        assert_eq!(1, L::mod_decr(x, 5));
604        assert_eq!(0, L::mod_decr(x, 6));
605        assert_eq!(2, L::mod_decr(x, 8));
606        assert_eq!(1, L::mod_decr(x, 9));
607    }
608
609    #[test]
610    fn test_partial_eq() {
611        let mut x = Lobby::new([None, None, None]);
612        let mut y = Lobby::new([None, None, None]);
613
614        x.push(0);
615        x.push(1);
616
617        y.push(0);
618        y.push(1);
619
620        assert_eq!(x, y);
621
622        y.pop();
623        x.push(0);
624        x.shift();
625        x.shift();
626
627        assert_eq!(x, y);
628        assert_eq!(x, [Some(0), None, None]);
629    }
630
631    #[test]
632    fn test_iter() {
633        let mut x = Lobby::new([None, None, None]);
634
635        x.push(0);
636        assert_eq!(vec![&0], x.iter().collect::<Vec<_>>());
637        assert_eq!(vec![0], x.clone().into_iter().collect::<Vec<_>>());
638
639        x.push(1);
640        x.push(2);
641        assert_eq!(vec![&0, &1, &2], x.iter().collect::<Vec<_>>());
642        assert_eq!(vec![0, 1, 2], x.clone().into_iter().collect::<Vec<_>>());
643
644        x.push(3);
645        assert_eq!(vec![&1, &2, &3], x.iter().collect::<Vec<_>>());
646        assert_eq!(vec![1, 2, 3], x.clone().into_iter().collect::<Vec<_>>());
647
648        x.shift();
649        assert_eq!(vec![&2, &3], x.iter().collect::<Vec<_>>());
650        assert_eq!(vec![2, 3], x.into_iter().collect::<Vec<_>>());
651    }
652
653    #[test]
654    fn test_iter_mut() {
655        let mut x = Lobby::new([None, None, None, None]);
656        x.push(1);
657        x.push(2);
658        x.push(3);
659        x.push(4);
660
661        for v in x.iter_mut() {
662            *v *= 2;
663        }
664
665        assert_eq!(x, [Some(2), Some(4), Some(6), Some(8)]);
666    }
667}
lobby_queue/lib.rs

lobby_queue/
lib.rs
