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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

//! # Evicted Queue

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.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct EvictedQueue<T> {
    queue: Option<VecDeque<T>>,
    max_len: u32,
    dropped_count: u32,
}

impl<T> EvictedQueue<T> {
    /// Create a new `EvictedQueue` with a given max length.
    pub fn new(max_len: u32) -> Self {
        EvictedQueue {
            queue: None,
            max_len,
            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) {
        let queue = self.queue.get_or_insert_with(Default::default);
        queue.push_back(value);

        if queue.len() as u32 > self.max_len {
            queue.pop_front();
            self.dropped_count += 1;
        }
    }

    /// 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.as_ref().map_or(true, |queue| queue.is_empty())
    }

    /// Returns a front-to-back iterator.
    pub fn iter(&self) -> Iter<'_, T> {
        Iter(self.queue.as_ref().map(|queue| queue.iter()))
    }

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

    /// Count of dropped attributes
    pub fn dropped_count(&self) -> u32 {
        self.dropped_count
    }
}

/// An owned iterator over the entries of a `EvictedQueue`.
#[derive(Debug)]
pub struct IntoIter<T>(Option<std::collections::vec_deque::IntoIter<T>>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.as_mut().and_then(|iter| iter.next())
    }
}

impl<T> IntoIterator for EvictedQueue<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

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

/// An iterator over the entries of an `EvictedQueue`.
#[derive(Debug)]
pub struct Iter<'a, T>(Option<std::collections::vec_deque::Iter<'a, T>>);

impl<'a, T: 'static> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.as_mut().and_then(|iter| iter.next())
    }
}

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.unwrap(),
            (1..=capacity).collect::<VecDeque<_>>()
        );
    }

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

        queue.push_back(1);

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