squeue/

queue.rs

// Copyright (C) 2024 Christian Mauduit <ufoot@ufoot.org>

use crate::drain::Drain;
use std::collections::vec_deque::IntoIter;
use std::collections::VecDeque;
use std::fmt;

/// FIFO queue with a fixed capacity.
///
/// This is in a LRU package because it has a semantic behavior
/// similar to an LRU, in the sense that when capacity is reached,
/// the oldest element is dropped.
///
/// In practice it in just some syntaxic sugar over a `VecDeque`,
/// and data is dropped when you exceed capacity.
///
/// # Examples
///
/// ```
/// use squeue::Queue;
///
/// let mut queue: Queue<usize> = Queue::new(3);
/// assert_eq!(None, queue.push(1));
/// assert_eq!(None, queue.push(2));
/// assert_eq!(None, queue.push(3));
/// assert_eq!(Some(1), queue.push(4));
/// assert_eq!(3, queue.len());
/// ```
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone)]
pub struct Queue<T> {
    capacity: usize,
    data: VecDeque<T>,
}

/// Pretty-print queue content.
///
/// Prints the next element to be popped, and the len/capacity.
///
/// # Examples
///
/// ```
/// use squeue::Queue;
///
/// let mut queue = Queue::new(100);
/// queue.push(123);
/// queue.push(4);
/// queue.push(5);
/// assert_eq!("{ next: 123, len: 3, capacity: 100 }", format!("{}", queue));
/// queue.clear();
/// assert_eq!("{ len: 0, capacity: 100 }", format!("{}", queue));
/// ```
impl<T> fmt::Display for Queue<T>
where
    T: fmt::Display,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self.peek() {
            Some(item) => write!(
                f,
                "{{ next: {}, len: {}, capacity: {} }}",
                item,
                self.len(),
                self.capacity()
            ),
            None => write!(
                f,
                "{{ len: {}, capacity: {} }}",
                self.len(),
                self.capacity()
            ),
        }
    }
}

impl<T> Queue<T> {
    /// Create a new queue.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let queue: Queue<String> = Queue::new(10);
    /// assert_eq!(10, queue.capacity());
    /// ```
    pub fn new(capacity: usize) -> Self {
        Queue {
            capacity,
            data: VecDeque::with_capacity(capacity + 1),
        }
    }

    /// Return queue length.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<&str> = Queue::new(10);
    /// assert_eq!(0, queue.len());
    /// queue.push("x");
    /// queue.push("y");
    /// assert_eq!(2, queue.len());
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.data.len()
    }

    /// Return queue capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<f64> = Queue::new(100);
    /// assert_eq!(100, queue.capacity());
    /// ```
    #[inline]
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Returns true if queue is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<String> = Queue::new(100);
    /// assert!(queue.is_empty());
    /// queue.push(String::from("abc"));
    /// assert!(!queue.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    /// Returns true if queue is full.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<usize> = Queue::new(10);
    /// assert!(!queue.is_full());
    /// for i in 0..10 {
    ///     queue.push(i);
    /// }
    /// assert!(queue.is_full());
    /// ```
    #[inline]
    pub fn is_full(&self) -> bool {
        self.len() >= self.capacity()
    }

    /// Clear all data.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<String> = Queue::new(100);
    /// queue.push(String::from("abc"));
    /// queue.clear();
    /// assert!(queue.is_empty());
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        self.data.clear()
    }

    /// Resize queue.
    ///
    /// Returns the number of dropped items, if any.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<usize> = Queue::new(10);
    /// assert_eq!(10, queue.capacity());
    /// assert_eq!(0, queue.resize(100));
    /// assert_eq!(100, queue.capacity());
    /// for i in 0..1000 {
    ///     queue.push(i);
    /// }
    /// assert_eq!(100, queue.len());
    /// assert_eq!(90, queue.resize(10));
    /// assert_eq!(10, queue.capacity());
    /// assert_eq!(10, queue.len());
    /// assert_eq!(Some(990), queue.pop());
    /// ```
    pub fn resize(&mut self, capacity: usize) -> usize {
        self.capacity = capacity;
        let old_size = self.data.len();
        if old_size > capacity {
            self.data.truncate(capacity);
            old_size - capacity
        } else {
            if capacity > old_size {
                self.data.try_reserve(capacity + 1 - old_size).ok();
            }
            0
        }
    }

    /// Push data into the queue.
    ///
    /// If the queue is full and data needs to be dropped,
    /// that data is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<usize> = Queue::new(2);
    /// assert_eq!(None, queue.push(1));
    /// assert_eq!(None, queue.push(10));
    /// assert_eq!(Some(1), queue.push(100));
    /// assert_eq!(Some(10), queue.push(1000));
    /// assert_eq!(2, queue.len());
    /// ```
    pub fn push(&mut self, item: T) -> Option<T> {
        if self.capacity == 0 {
            return None;
        }
        self.data.push_front(item);
        if self.data.len() > self.capacity {
            self.pop()
        } else {
            None
        }
    }

    /// Pop data from the queue.
    ///
    /// The oldest item is returned, this works in FIFO mode.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<usize> = Queue::new(5);
    /// assert_eq!(None, queue.pop());
    /// assert_eq!(None, queue.push(1));
    /// assert_eq!(Some(1), queue.pop());
    /// assert_eq!(None, queue.push(2));
    /// assert_eq!(None, queue.push(3));
    /// assert_eq!(Some(2), queue.pop());
    /// assert_eq!(1, queue.len());
    /// ```
    pub fn pop(&mut self) -> Option<T> {
        self.data.pop_back()
    }

    /// Peek data, get it without removing it.
    ///
    /// This gives an insight on what pop() would return.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue: Queue<usize> = Queue::new(5);
    /// assert_eq!(None, queue.peek());
    /// assert_eq!(None, queue.push(1));
    /// assert_eq!(None, queue.push(2));
    /// assert_eq!(Some(&1), queue.peek());
    /// ```
    pub fn peek(&self) -> Option<&T> {
        // May sound a little convoluted, why not use
        // 0 as the "where we pop things" just do
        // queue.get(0). The reason is that if we
        // do this, truncate() does not work as expected
        // and drops recent entries.
        let len = self.data.len();
        if len > 0 {
            self.data.get(len - 1)
        } else {
            None
        }
    }

    /// Creates an iterator which drains the queue.
    ///
    /// Use this when you want to get all the items, at a given point,
    /// and free space in the queue.
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue = Queue::new(10);
    /// queue.push(1);
    /// queue.push(10);
    /// let drain = queue.drain();
    /// assert_eq!(0, queue.len());
    /// assert_eq!(2, drain.count());
    /// ```
    pub fn drain(&mut self) -> Drain<T> {
        Drain::new(self)
    }
}

impl<T> std::iter::IntoIterator for Queue<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    /// Creates an iterator over the queue.
    ///
    /// Takes ownership.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue = Queue::new(10);
    /// queue.push(4);
    /// queue.push(5);
    /// queue.push(6);
    ///
    /// let sum=queue.into_iter().sum();
    /// assert_eq!(15, sum);
    /// ```
    fn into_iter(self) -> IntoIter<T> {
        self.data.into_iter()
    }
}

impl<T> FromIterator<T> for Queue<T> {
    /// Creates a new queue from an iterator.
    ///
    /// With this, you can use collect() to build a queue.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let src: Vec<usize> = vec![4, 5, 6];
    ///
    /// let mut queue = src.into_iter().collect::<Queue<usize>>();
    /// assert_eq!(Some(4), queue.pop());
    /// assert_eq!(Some(5), queue.pop());
    /// assert_eq!(Some(6), queue.pop());
    /// assert_eq!(None, queue.pop());
    /// assert_eq!(3, queue.capacity());
    /// ```
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut queue = Queue::new(0);

        for i in iter {
            queue.resize(queue.len() + 1);
            queue.push(i);
        }

        queue
    }
}

impl<T> PartialEq<Queue<T>> for Queue<T>
where
    T: PartialEq,
{
    /// Compares two queues. Capacity, content and order must match.
    ///
    /// # Examples
    ///
    /// ```
    /// use squeue::Queue;
    ///
    /// let mut queue1 = Queue::new(10);
    /// queue1.push("Alice");
    /// queue1.push("Bob");
    /// let mut queue2 = Queue::new(10);
    /// queue2.push("Oscar");
    /// queue2.push("Alice");
    /// queue2.push("Bob");
    /// assert_ne!(&queue1, &queue2);
    /// queue2.pop();
    /// assert_eq!(&queue1, &queue2);
    /// ```
    fn eq(&self, other: &Self) -> bool {
        if self.capacity != other.capacity {
            return false;
        }
        if self.len() != other.len() {
            return false;
        }
        let mut iter_other = other.data.iter();
        for self_v in self.data.iter() {
            match iter_other.next() {
                Some(other_v) => {
                    if self_v != other_v {
                        return false;
                    }
                }
                None => return false,
            }
        }
        true
    }
}

impl<T> Eq for Queue<T> where T: Eq {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_queue_0() {
        let mut queue: Queue<usize> = Queue::new(0);
        assert_eq!(None, queue.push(42));
        assert_eq!(None, queue.pop());
        assert_eq!(0, queue.capacity());
        assert_eq!(true, queue.is_full());
        assert_eq!(true, queue.is_empty());
    }

    #[cfg(feature = "serde")]
    #[test]
    fn test_json() {
        use serde_json::json;

        let mut queue1 = Queue::<usize>::new(10);

        queue1.push(1);
        queue1.push(2);

        let export = json!(&queue1).to_string();

        assert_eq!("{\"capacity\":10,\"data\":[2,1]}", export);

        let queue2: Queue<usize> = serde_json::from_str(&export).unwrap();

        assert_eq!(&queue1, &queue2);
        queue1.clear();
        assert_eq!(0, queue1.len());
        assert_eq!(2, queue2.len());
    }
}