fifo_set/
lib.rs

1use std::collections::{HashSet, VecDeque};
2use std::collections::vec_deque::Iter;
3use std::hash::Hash;
4use std::iter::FromIterator;
5use std::ops::{Index, RangeBounds};
6
7/// A FIFO queue with unique values.
8#[derive(Clone, Default)]
9pub struct FIFOSet<T> {
10    deq: VecDeque<T>,
11    set: HashSet<T>,
12}
13
14impl<T: Eq + Hash> FIFOSet<T> {
15    pub fn new() -> Self {
16        Self {
17            deq: VecDeque::new(),
18            set: HashSet::new(),
19        }
20    }
21
22    pub fn with_capacity(capacity: usize) -> Self {
23        Self {
24            deq: VecDeque::with_capacity(capacity),
25            set: HashSet::with_capacity(capacity),
26        }
27    }
28
29    pub fn get(&self, index: usize) -> Option<&T> {
30        self.deq.get(index)
31    }
32
33    pub fn swap(&mut self, i: usize, j: usize) {
34        self.deq.swap(i, j)
35    }
36
37    pub fn capacity(&self) -> usize {
38        self.deq.capacity()
39    }
40
41    pub fn reserve(&mut self, additional: usize) {
42        self.deq.reserve(additional);
43        self.set.reserve(additional);
44    }
45
46    pub fn iter(&self) -> Iter<'_, T> {
47        self.deq.iter()
48    }
49
50    pub fn len(&self) -> usize {
51        self.deq.len()
52    }
53
54    pub fn is_empty(&self) -> bool {
55        self.deq.is_empty()
56    }
57
58    pub fn range<R: RangeBounds<usize>>(&self, range: R) -> Iter<'_, T> {
59        self.deq.range(range)
60    }
61
62    pub fn clear(&mut self) {
63        self.deq.clear();
64        self.set.clear();
65    }
66
67    pub fn contains(&self, x: &T) -> bool {
68        self.set.contains(x)
69    }
70
71    pub fn peek(&self) -> Option<&T> {
72        self.deq.front()
73    }
74
75    /// Retrieve the item that has been in the queue longest.
76    pub fn pop(&mut self) -> Option<T> {
77        let next = self.deq.pop_front();
78
79        if let Some(value) = next.as_ref() {
80            self.set.remove(value);
81        }
82
83        next
84    }
85
86    pub fn remove(&mut self, index: usize) -> Option<T> {
87        let removed = self.deq.remove(index);
88
89        if let Some(value) = removed.as_ref() {
90            self.set.remove(value);
91        }
92
93        removed
94    }
95}
96
97impl<T: Copy + Eq + Hash> FIFOSet<T> {
98    /// Add an item to the queue.
99    pub fn push(&mut self, element: T) {
100        if self.set.insert(element) {
101            self.deq.push_back(element);
102        }
103    }
104}
105
106impl<T> Index<usize> for FIFOSet<T> {
107    type Output = T;
108
109    fn index(&self, index: usize) -> &Self::Output {
110        self.deq.index(index)
111    }
112}
113
114impl<A: Copy + Eq + Hash> FromIterator<A> for FIFOSet<A> {
115    fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self {
116        let iterator = iter.into_iter();
117        let (lower, _) = iterator.size_hint();
118        let mut deq = FIFOSet::with_capacity(lower);
119        deq.extend(iterator);
120        deq
121    }
122}
123
124impl<A: Copy + Eq + Hash> Extend<A> for FIFOSet<A> {
125    fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T) {
126        for item in iter.into_iter() {
127            self.push(item);
128        }
129    }
130}
fifo_set/lib.rs

fifo_set/
lib.rs
