pagecache/ds/
vecset.rs

1use serde::{Serialize, Deserialize};
2
3/// A set built on top of `Vec` and binary search,
4/// for use when calling `nth` to iterate over a set
5/// is too expensive, and the set size is expected to be
6/// ~10 or less most of the time.
7#[derive(Default, Clone, Debug, PartialEq, Serialize, Deserialize)]
8pub struct VecSet<T> {
9    inner: Vec<T>,
10}
11
12impl<T> VecSet<T>
13where
14    T: Ord + Eq,
15{
16    /// Insert a new item
17    pub fn insert(&mut self, item: T) -> bool {
18        if let Err(insert_idx) = self.inner.binary_search(&item) {
19            self.inner.insert(insert_idx, item);
20            true
21        } else {
22            false
23        }
24    }
25
26    /// Removes an item by value
27    pub fn remove(&mut self, item: &T) -> Option<T> {
28        if let Ok(at) = self.inner.binary_search(item) {
29            Some(self.inner.remove(at))
30        } else {
31            None
32        }
33    }
34
35    /// Returns `true` if the item is present
36    pub fn contains(&self, item: &T) -> bool {
37        self.inner.binary_search(item).is_ok()
38    }
39
40    /// Peeks the first element
41    pub fn peek_first(&self) -> Option<&T> {
42        self.inner.first()
43    }
44
45    /// Returns `true` if the set is empty
46    pub fn is_empty(&self) -> bool {
47        self.inner.is_empty()
48    }
49
50    /// Returns the size of the set
51    pub fn len(&self) -> usize {
52        self.inner.len()
53    }
54
55    /// Indexes into the underlying buffer
56    pub fn get(&self, idx: usize) -> Option<&T> {
57        self.inner.get(idx)
58    }
59
60    /// Clears the underlying buffer
61    pub fn clear(&mut self) {
62        self.inner.clear()
63    }
64
65    /// Iterate over the contents of this set
66    pub fn iter(&self) -> impl Iterator<Item = &T> {
67        self.inner.iter()
68    }
69}
pagecache/ds/vecset.rs

pagecache/ds/
vecset.rs
