syn_sem/ds/
queue.rs

1use crate::Map;
2use std::{
3    collections::{hash_map::Entry, vec_deque, VecDeque},
4    fmt,
5    hash::Hash,
6};
7
8pub trait Identify {
9    type Id: Eq + Hash;
10
11    fn id(&self) -> Self::Id;
12}
13
14pub struct OnceQueue<T: Identify> {
15    queue: VecDeque<T>,
16
17    /// Stores the number of identical values in the queue.
18    cnt: Map<T::Id, u32>,
19}
20
21impl<T: Identify> OnceQueue<T> {
22    pub fn new() -> Self {
23        Self {
24            queue: VecDeque::new(),
25            cnt: Map::default(),
26        }
27    }
28
29    pub fn len(&self) -> usize {
30        self.queue.len()
31    }
32
33    pub fn is_empty(&self) -> bool {
34        self.len() == 0
35    }
36
37    /// Clears the queue itself and insertion history.
38    pub fn reset(&mut self) {
39        self.queue.clear();
40        self.cnt.clear();
41    }
42
43    pub fn iter(&self) -> vec_deque::Iter<'_, T> {
44        self.queue.iter()
45    }
46
47    pub fn is_pushable(&self, value: &T) -> bool {
48        !self.cnt.contains_key(&value.id())
49    }
50
51    pub fn count(&self, value: &T) -> u32 {
52        self.cnt.get(&value.id()).cloned().unwrap_or(0)
53    }
54
55    /// Appends the value at the end of the queue if the queue has not seen the value before.
56    ///
57    /// If the queue has seen the value, then returns it within error.
58    pub fn push_back(&mut self, value: T) -> Result<(), T> {
59        self.push(value, |queue, value| queue.push_back(value))
60    }
61
62    /// Appends the value at the beginning of the queue if the queue has not seen the value before.
63    ///
64    /// If the queue has seen the value, then returns it within error.
65    pub fn push_front(&mut self, value: T) -> Result<(), T> {
66        self.push(value, |queue, value| queue.push_front(value))
67    }
68
69    /// Appends the value at the end of the queue regardless of whether the queue has seen the
70    /// value before.
71    pub fn push_back_force(&mut self, value: T) {
72        self.push_force(value, |queue, value| queue.push_back(value))
73    }
74
75    /// Appends the value at the beginning of the queue regardless of whether the queue has seen
76    /// the value before.
77    pub fn push_front_force(&mut self, value: T) {
78        self.push_force(value, |queue, value| queue.push_front(value))
79    }
80
81    /// Removes the last value, then returns it.
82    pub fn pop_back(&mut self) -> Option<T> {
83        self.pop(|queue| queue.pop_back())
84    }
85
86    /// Removes the first value, then returns it.
87    pub fn pop_front(&mut self) -> Option<T> {
88        self.pop(|queue| queue.pop_front())
89    }
90
91    fn push<F>(&mut self, value: T, push: F) -> Result<(), T>
92    where
93        F: FnOnce(&mut VecDeque<T>, T),
94    {
95        match self.cnt.entry(value.id()) {
96            Entry::Vacant(entry) => {
97                push(&mut self.queue, value);
98                entry.insert(1);
99                Ok(())
100            }
101            // regardless of count, seen value cannot be added.
102            Entry::Occupied(_) => Err(value),
103        }
104    }
105
106    fn push_force<F>(&mut self, value: T, push_force: F)
107    where
108        F: FnOnce(&mut VecDeque<T>, T),
109    {
110        self.cnt
111            .entry(value.id())
112            .and_modify(|c| *c += 1)
113            .or_insert(1);
114        push_force(&mut self.queue, value);
115    }
116
117    fn pop<F>(&mut self, pop: F) -> Option<T>
118    where
119        F: FnOnce(&mut VecDeque<T>) -> Option<T>,
120    {
121        let value = pop(&mut self.queue)?;
122
123        let c = self.cnt.get_mut(&value.id()).unwrap();
124        *c -= 1;
125
126        Some(value)
127    }
128}
129
130impl<T: Identify> Default for OnceQueue<T> {
131    fn default() -> Self {
132        Self::new()
133    }
134}
135
136impl<T: Identify + fmt::Debug> fmt::Debug for OnceQueue<T> {
137    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
138        self.queue.fmt(f)
139    }
140}
141
142impl<'a, T: Identify> IntoIterator for &'a OnceQueue<T> {
143    type Item = &'a T;
144    type IntoIter = vec_deque::Iter<'a, T>;
145
146    fn into_iter(self) -> Self::IntoIter {
147        self.iter()
148    }
149}
syn_sem/ds/queue.rs

syn_sem/ds/
queue.rs
