diff options
Diffstat (limited to 'src/ageset.rs')
-rw-r--r-- | src/ageset.rs | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/src/ageset.rs b/src/ageset.rs new file mode 100644 index 0000000..084afba --- /dev/null +++ b/src/ageset.rs @@ -0,0 +1,41 @@ +use std::collections::HashSet; +use std::hash::Hash; + +use blist::BList; + +/// So... this is a rather weird thing. +/// It allows to semi-efficiently check the oldest (earliest insertion) +/// elements for certain criteria and remove them in the order of insertion +/// if the criteria is met. +pub struct AgeSet<T> { + fifo: BList<T>, + set: HashSet<T> +} + +impl<T> AgeSet<T> where T: Eq + Hash + Clone { + pub fn new() -> Self { + AgeSet { + fifo: BList::new(), + set: HashSet::new() + } + } + + pub fn contains(&self, t: &T) -> bool { + self.set.contains(t) + } + + pub fn prune<F>(&mut self, kill: F) where F: Fn(&T) -> bool { + while let Some(ref e) = self.fifo.front().map(T::clone) { + if kill(&e) { + let removed = self.fifo.pop_front().unwrap(); + self.set.remove(&e); + assert!(*e == removed); + } else { break } + } + } + + pub fn push(&mut self, t: T) { + self.fifo.push_back(t.clone()); + self.set.insert(t); + } +} |