1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

//! # Evicted Queue

#[cfg(feature = "serialize")]
use serde::{Deserialize, Serialize};
use std::collections::VecDeque;

/// This queue maintains an ordered list of elements, and a count of
/// dropped elements. Elements are removed from the queue in a first
/// in first out fashion.
#[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
#[derive(Clone, Debug, PartialEq)]
pub struct EvictedQueue<T> {
    queue: VecDeque<T>,
    capacity: u32,
    dropped_count: u32,
}

impl<T> EvictedQueue<T> {
    /// Create a new `EvictedQueue` with a given capacity.
    pub fn new(capacity: u32) -> Self {
        EvictedQueue {
            queue: Default::default(),
            capacity,
            dropped_count: 0,
        }
    }

    /// Push a new element to the back of the queue, dropping and
    /// recording dropped count if over capacity.
    pub(crate) fn push_back(&mut self, value: T) {
        if self.queue.len() as u32 == self.capacity {
            self.queue.pop_front();
            self.dropped_count += 1;
        }
        self.queue.push_back(value);
    }

    /// Moves all the elements of other into self, leaving other empty.
    pub fn append_vec(&mut self, other: &mut Vec<T>) {
        self.extend(other.drain(..));
    }

    /// Returns `true` if the `EvictedQueue` is empty.
    pub fn is_empty(&self) -> bool {
        self.queue.is_empty()
    }

    /// Returns a front-to-back iterator.
    pub fn iter(&self) -> std::collections::vec_deque::Iter<T> {
        self.queue.iter()
    }

    /// Returns the number of elements in the `EvictedQueue`.
    pub fn len(&self) -> usize {
        self.queue.len()
    }
}

impl<T> IntoIterator for EvictedQueue<T> {
    type Item = T;
    type IntoIter = std::collections::vec_deque::IntoIter<T>;

    /// Consumes the `EvictedQueue` into a front-to-back iterator yielding elements by
    /// value.
    fn into_iter(self) -> Self::IntoIter {
        self.queue.into_iter()
    }
}

impl<'a, T> IntoIterator for &'a EvictedQueue<T> {
    type Item = &'a T;
    type IntoIter = std::collections::vec_deque::Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.queue.iter()
    }
}

impl<'a, T> IntoIterator for &'a mut EvictedQueue<T> {
    type Item = &'a mut T;
    type IntoIter = std::collections::vec_deque::IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.queue.iter_mut()
    }
}

impl<T> Extend<T> for EvictedQueue<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        iter.into_iter().for_each(move |elt| self.push_back(elt));
    }
}

#[cfg(test)]
mod tests {
    use super::EvictedQueue;
    use std::collections::VecDeque;

    #[test]
    fn insert_over_capacity_test() {
        let capacity = 10;
        let mut queue = EvictedQueue::new(capacity);

        for i in 0..=capacity {
            queue.push_back(i)
        }

        assert_eq!(queue.dropped_count, 1);
        assert_eq!(queue.len(), capacity as usize);
        assert_eq!(queue.queue, (1..=capacity).collect::<VecDeque<_>>());
    }
}