detcore_model/collections/
replay_cursor.rs

1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of this source tree.
7 */
8
9use std::collections::VecDeque;
10use std::fmt;
11use std::iter::FromIterator;
12
13/// This is a queue like data structure used when replaying schedule
14///
15/// Apart from being an [`Iterator`], it supports [`ReplayCursor::peek`] and
16/// [`ReplayCursor::peek_nth`] to look ahead an arbitrary number of events while replaying.
17#[derive(Debug)]
18pub struct ReplayCursor<T> {
19    inner_data: VecDeque<T>,
20}
21
22impl<T: Eq + fmt::Display> ReplayCursor<T> {
23    /// peeks the following nth element from the top of the cursor
24    pub fn peek_nth(&self, index: usize) -> Option<&T> {
25        self.inner_data.get(index)
26    }
27
28    /// peeks the following item from the top of the cursor
29    pub fn peek(&self) -> Option<&T> {
30        self.peek_nth(0)
31    }
32
33    /// Look ahead N positions to see if an element satisfying the predicate is found within that
34    /// window.  Return the position, if found.
35    pub fn prefix_contains<F>(&self, winsize: usize, pred: F) -> Option<usize>
36    where
37        F: Fn(&T) -> bool,
38    {
39        for (i, v) in self.inner_data.iter().enumerate().take(winsize) {
40            if pred(v) {
41                return Some(i);
42            }
43        }
44        None
45    }
46
47    /// Discard the next `count` elements (all of them if fewer remain), so the
48    /// element after them becomes the head.
49    pub fn drop(&mut self, count: usize) {
50        let count = count.min(self.inner_data.len());
51        self.inner_data.drain(..count);
52    }
53
54    /// How many elements remain to be replayed.
55    pub fn len(&self) -> usize {
56        self.inner_data.len()
57    }
58
59    /// Whether nothing remains to be replayed.
60    pub fn is_empty(&self) -> bool {
61        self.inner_data.is_empty()
62    }
63
64    // print a window of up to N events
65    pub fn display_first_n(&self, count: usize) -> String {
66        let mut acc = String::new();
67        let mut first = true;
68        for x in self.inner_data.iter().take(count) {
69            acc.push_str(&format!("{}{}", if first { "" } else { " " }, x));
70            first = false;
71        }
72        acc
73    }
74}
75
76impl<T> Iterator for ReplayCursor<T> {
77    type Item = T;
78
79    fn next(&mut self) -> Option<Self::Item> {
80        if self.inner_data.is_empty() {
81            None
82        } else {
83            self.inner_data.pop_front()
84        }
85    }
86}
87
88impl<T: fmt::Display> FromIterator<T> for ReplayCursor<T> {
89    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
90        let reverse_data: VecDeque<_> = VecDeque::from_iter(iter);
91        Self {
92            inner_data: reverse_data,
93        }
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use std::collections::VecDeque;
100    use std::fmt::Display;
101
102    use pretty_assertions::assert_eq;
103
104    use super::*;
105
106    fn peek_pair<T>(cursor: &ReplayCursor<T>) -> (Option<&T>, Option<&T>)
107    where
108        T: std::cmp::Eq + Display,
109    {
110        (cursor.peek_nth(0), cursor.peek_nth(1))
111    }
112
113    /// A fast-forward drops the stale head of the schedule and keeps the rest.
114    #[test]
115    fn drop_discards_the_head_and_keeps_the_rest() {
116        let mut cursor: ReplayCursor<usize> = vec![1, 2, 3, 4, 5].into_iter().collect();
117        cursor.drop(2);
118        assert_eq!(cursor.len(), 3);
119        assert_eq!(cursor.collect::<Vec<_>>(), vec![3, 4, 5]);
120
121        let mut short: ReplayCursor<usize> = vec![1, 2].into_iter().collect();
122        short.drop(5);
123        assert!(short.is_empty());
124    }
125
126    #[test]
127    fn test_peek() {
128        let cursor: ReplayCursor<usize> = vec![1, 2, 3, 4, 5, 6].into_iter().collect();
129        assert_eq!(cursor.peek(), Some(&1));
130    }
131
132    #[test]
133    fn test_peek_empty() {
134        let cursor = ReplayCursor::<usize> {
135            inner_data: VecDeque::new(),
136        };
137        assert_eq!(cursor.peek(), None);
138    }
139
140    #[test]
141    fn test_peek_pair() {
142        let cursor: ReplayCursor<usize> = vec![1, 2, 3].into_iter().collect();
143        assert_eq!(peek_pair(&cursor), (Some(&1), Some(&2)));
144        assert_eq!(peek_pair(&cursor), (Some(&1), Some(&2)));
145    }
146
147    #[test]
148    fn test_peek_pair_one() {
149        let cursor: ReplayCursor<usize> = vec![1].into_iter().collect();
150        assert_eq!(peek_pair(&cursor), (Some(&1), None));
151        assert_eq!(peek_pair(&cursor), (Some(&1), None));
152    }
153
154    #[test]
155    fn test_peek_pair_empty() {
156        let cursor: ReplayCursor<usize> = ReplayCursor {
157            inner_data: VecDeque::new(),
158        };
159        assert_eq!(peek_pair(&cursor), (None, None));
160        assert_eq!(peek_pair(&cursor), (None, None));
161    }
162
163    #[test]
164    fn test_next() {
165        let mut cursor: ReplayCursor<usize> = vec![1, 2, 3].into_iter().collect();
166        let result = vec![cursor.next(), cursor.next(), cursor.next(), cursor.next()];
167        assert_eq!(result, vec![Some(1), Some(2), Some(3), None]);
168    }
169
170    #[test]
171    fn test_peek_nth() {
172        let cursor: ReplayCursor<usize> = vec![1, 2, 3].into_iter().collect();
173        let result = vec![
174            cursor.peek_nth(0),
175            cursor.peek_nth(1),
176            cursor.peek_nth(2),
177            cursor.peek_nth(3),
178        ];
179        assert_eq!(result, vec![Some(&1), Some(&2), Some(&3), None]);
180    }
181}
detcore_model/collections/replay_cursor.rs

detcore_model/collections/
replay_cursor.rs
