seen_set 0.1.1

HashSet that doesn't store values.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

use std::hash::BuildHasher;
use std::hash::RandomState;
use std::marker::PhantomData;

use hashbrown::HashTable;

/// A HashSet that doesn't store values, but instead only stores hashes.
///
/// This is useful when you only need to tell if you've seen a value before
/// and you don't want to clone the value for performance reasons.
///
/// ```rs
/// let mut seen = SeenSet::new();
/// for path in some_func_that_may_return_duplicate_paths() {
///   if !seen.insert(&path) {
///     continue;
///   }
///   // we haven't seen this path before
/// }
/// ```
///
/// Note: This will be slower for values like numbers. Just use a regular
/// HashSet for that.
pub struct SeenSet<
  T: std::hash::Hash + ?Sized,
  TValueHasher = RandomState,
> {
  _kind: PhantomData<T>,
  value_hasher: TValueHasher,
  checked_table: hashbrown::HashTable<u64>,
}

impl<T: std::hash::Hash + ?Sized, TValueHasher: Clone> Clone
  for SeenSet<T, TValueHasher>
{
  fn clone(&self) -> Self {
    Self {
      _kind: Default::default(),
      value_hasher: self.value_hasher.clone(),
      checked_table: self.checked_table.clone(),
    }
  }
}

impl<T: std::hash::Hash + ?Sized, TValueHasher> std::fmt::Debug
  for SeenSet<T, TValueHasher>
{
  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    f.debug_struct("CheckedSet")
      .field("checked", &self.checked_table)
      .finish()
  }
}

impl<
    T: std::hash::Hash + ?Sized,
    TValueHasher: Default,
  > Default for SeenSet<T, TValueHasher>
{
  fn default() -> Self {
    Self {
      _kind: Default::default(),
      value_hasher: Default::default(),
      checked_table: Default::default(),
    }
  }
}

impl<T: std::hash::Hash + ?Sized> SeenSet<T, RandomState> {
  pub fn new() -> Self {
    Self::default()
  }

  pub fn with_capacity(capacity: usize) -> Self {
    Self::with_capacity_and_hasher(capacity, Default::default())
  }
}

impl<T: std::hash::Hash + ?Sized, TValueHasher> SeenSet<T, TValueHasher> {
  pub fn with_capacity_and_hasher(
    capacity: usize,
    value_hasher: TValueHasher,
  ) -> Self {
    Self {
      _kind: PhantomData,
      value_hasher,
      checked_table: HashTable::with_capacity(capacity),
    }
  }
}

impl<
    T: std::hash::Hash + ?Sized,
    TValueHasher: BuildHasher,
  > SeenSet<T, TValueHasher>
{
  /// Check if the set contains the value.
  pub fn contains(&mut self, value: &T) -> bool {
    let hash = self.get_hash(value);
    let hasher = |val: &_| self.value_hasher.hash_one(val);
    match self.checked_table.entry(hash, |key| key == &hash, hasher) {
      hashbrown::hash_table::Entry::Occupied(_) => true,
      hashbrown::hash_table::Entry::Vacant(_) => false,
    }
  }

  /// Inserts a hash of the value into the set returning `true`
  /// if never seen before or `false` otherwise.
  pub fn insert(&mut self, value: &T) -> bool {
    let hash = self.get_hash(value);
    let hasher = |val: &_| self.value_hasher.hash_one(val);
    match self.checked_table.entry(hash, |key| key == &hash, hasher) {
      hashbrown::hash_table::Entry::Occupied(_) => false,
      hashbrown::hash_table::Entry::Vacant(entry) => {
        entry.insert(hash);
        true
      },
    }
  }

  #[inline]
  fn get_hash(&self, value: &T) -> u64 {
    self.value_hasher.hash_one(value)
  }
}

#[cfg(test)]
mod test {
  #[test]
  fn test_seen_set() {
    // Obviously don't use this with numbers because it will be slower
    // than a regular HashSet. This is just for testing.
    let mut seen = super::SeenSet::new();
    assert!(seen.insert(&1));
    assert!(!seen.insert(&1));
    assert!(seen.insert(&2));
    assert!(!seen.insert(&2));
    assert!(seen.contains(&2));
    assert!(!seen.contains(&3));
  }
}