bitstring_trees/
set.rs

1//! [`Set`] of bit string prefixes
2
3use core::cmp::Ordering;
4
5use bitstring::BitString;
6
7use crate::tree::{
8	DefaultCompare,
9	InsertPositionWith,
10	Tree,
11	TreeProperties,
12};
13
14mod hidden {
15	use bitstring::BitString;
16	use core::marker::PhantomData;
17
18	/// make it public so we can use it in returned types, but don't make it directly accessible
19	pub struct TpSet<K: BitString + Clone>(PhantomData<*const K>);
20}
21use hidden::TpSet;
22
23impl<K: BitString + Clone> TreeProperties for TpSet<K> {
24	type Key = K;
25	type LeafValue = ();
26	type LeafValueComparer = DefaultCompare;
27	type Value = ();
28
29	const EMPTY: bool = true;
30	const IGNORE_LEAFS: bool = false;
31	const LEAF_EMPTY: bool = true;
32}
33
34/// Set of bit string prefixes
35///
36/// Sibling prefixes are automatically merged.
37///
38/// This is implemented as a [`crate::tree::Tree`] where nodes don't carry
39/// values at all, buf leaf nodes represent set membership of the associated
40/// key.
41#[derive(Clone)]
42pub struct Set<K: BitString + Clone> {
43	tree: Tree<TpSet<K>>,
44}
45
46impl<K: BitString + Clone> Default for Set<K> {
47	fn default() -> Self {
48		Self::new()
49	}
50}
51
52impl<K: BitString + Clone + core::fmt::Debug> core::fmt::Debug for Set<K> {
53	fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
54		f.debug_set().entries(self.iter()).finish()
55	}
56}
57
58impl<K: BitString + Clone> Set<K> {
59	/// New (empty) set.
60	pub const fn new() -> Self {
61		Self { tree: Tree::new() }
62	}
63
64	/// Access raw tree of set
65	pub fn tree(&self) -> &Tree<TpSet<K>> {
66		&self.tree
67	}
68
69	/// Insert prefix into set
70	pub fn insert(&mut self, key: K) {
71		self.tree.set_leaf_value(key, ());
72	}
73
74	/// Remove everything covered by prefix from set
75	pub fn remove(&mut self, key: K) {
76		let mut walk = self.tree.walk_mut();
77		walk.goto_insert(&key);
78		match walk.current().node() {
79			None => (), // empty tree
80			Some(node) => {
81				match node.get_key().len().cmp(&key.len()) {
82					Ordering::Less => {
83						// node is a leaf and covers key; need to split and remove key
84						// create explicit node with key we want to remove
85						walk.insert(key);
86						// now remove it
87						walk.delete_current();
88					},
89					Ordering::Equal | Ordering::Greater => {
90						// remove subtree
91						walk.delete_current();
92					},
93				}
94			},
95		}
96	}
97
98	/// Whether prefix is (completely) contained in set
99	pub fn contains(&self, key: &K) -> bool {
100		match self.tree.goto_insert(key) {
101			Some(InsertPositionWith::BelowLeaf(_)) => true,
102			Some(InsertPositionWith::AlreadyExists(_)) => true,
103			Some(InsertPositionWith::ReplaceNode(_)) => false,
104			None => false,
105		}
106	}
107
108	/// Iterate over all contained prefixes
109	pub fn iter(&self) -> IterSet<'_, K> {
110		IterSet {
111			iter: self.tree.iter_leaf(),
112		}
113	}
114
115	/// Iterate over smallest list of bit strings that cover everything with information whether they are part of the set or not
116	pub fn iter_full(&self) -> IterSetFull<'_, K> {
117		IterSetFull {
118			iter: self.tree.iter_leaf_full(),
119		}
120	}
121}
122
123/// Iterate over all prefixes contained in a set
124pub struct IterSet<'s, K: BitString + Clone> {
125	iter: super::tree::IterLeaf<'s, TpSet<K>>,
126}
127
128impl<'s, K: BitString + Clone> Iterator for IterSet<'s, K> {
129	type Item = &'s K;
130
131	fn next(&mut self) -> Option<Self::Item> {
132		Some(self.iter.next()?.0.get_key())
133	}
134}
135
136/// Iterate over smallest list of bit strings that cover everything with information whether they are part of the set or not
137pub struct IterSetFull<'s, K: BitString + Clone> {
138	iter: super::tree::IterLeafFull<'s, TpSet<K>>,
139}
140
141impl<'s, K: BitString + Clone> Iterator for IterSetFull<'s, K> {
142	type Item = (K, bool);
143
144	fn next(&mut self) -> Option<Self::Item> {
145		let (key, value) = self.iter.next()?;
146		Some((key, value.is_some()))
147	}
148}
bitstring_trees/set.rs

bitstring_trees/
set.rs
