flat_veb/lib.rs
1//! Fast implementation of vEB trees without internal allocation.
2//!
3//! van Emde Boas tree is a data structure for maintaining
4//! a set of integers of bounded size supporting the following queries:
5//!
6//! * insert(x) - inserts the integer x into the set
7//! * remove(x) - removes the integer x from the set
8//! * contains(x) - returns whether the set contains x
9//! * next(x) - returns the smallest integer in the
10//! set that is greater or equal to x
11//! * prev(x) - returns the smallest integer in the
12//! set that is greater or equal to x
13//!
14//! All of these use $\mathcal{O}(\log \log U)$ time,
15//! and the structure uses $\mathcal{O}(U)$ space,
16//! where $U$ is the biggest integer you can put in the set.
17//!
18//!
19//! # Usage
20//! use the trait `VEBTree` and the type `VEBTreeX`
21//! where X is the number of bits in the elements you will insert.
22//! In other words, with `VEBTreeX` you can only insert elements with
23//! value less than 1 << X.
24//! ```
25//! use flat_veb::{VEBTree, VEBTree24};
26//! let mut tree = VEBTree24::new();
27//!
28//! // note that VEBTree24 is a quite big object, using over 2 MB while empty,
29//! // but the size doesn't increase when elements are inserted.
30//!
31//! assert_eq!(tree.insert(123), true); // returns true if it wasn't already there
32//! assert_eq!(tree.insert(1337), true);
33//! assert_eq!(tree.insert(123), false); // false because it was already there
34//!
35//! assert_eq!(tree.contains(123), true);
36//! assert_eq!(tree.contains(42), false);
37//!
38//! assert_eq!(tree.next(42), Some(123));
39//! assert_eq!(tree.next(123), Some(123));
40//! assert_eq!(tree.next(124), Some(1337));
41//!
42//! assert_eq!(tree.remove(1337), true);
43//! assert_eq!(tree.remove(1337), false); // it's not there when removing it the second time
44//!
45//! assert_eq!(tree.next(124), None); // there is no element in te set >= 124
46//! ```
47//!
48//!
49//! # Performance
50//!
51//! It is natural to use internal heap allocation and indirection to implement
52//! recursive data structures like vEB tree, but this implementation
53//! avoid that to be faster, at the cost of a bit cumbersome API.
54//!
55//! A BTreeSet can do all of the operations a vEB tree can and much more,
56//! but is slower.
57//! A vEB tree is more appropriate if there are enough operations that
58//! the speed improvement matters, but the integers are small enough that
59//! the vEB tree doesn't take too much space.
60//!
61//! vEB tree is about 10 times faster than BTreeSet on tests
62//! downloaded from <https://judge.yosupo.jp/problem/predecessor_problem>,
63//! but this includes IO, which is probably a significant
64//! amount of the time spent for the vEB tree. Better benchmarks are needed.
65//!
66//!
67//! # Todo
68//!
69//! - better benchmarks
70//! - create a function to return a Box<dyn VEBTree> of appropriate capacity
71//! - reverse iterator
72#![no_std]
73#![feature(generic_const_exprs)]
74#![allow(incomplete_features)]
75#![warn(missing_docs, missing_debug_implementations)]
76
77#[allow(missing_docs)]
78mod aliases;
79mod outer;
80mod small_set;
81pub use aliases::*;
82
83/// Common trait for the different implementations
84/// of sets for different sizes.
85pub trait VEBTree: Copy + Sized + Default + core::fmt::Debug {
86 /// The set can hold values with BITS bits.
87 const BITS: usize;
88
89 /// The set can hold values in [0, CAPACITY)
90 const CAPACITY: usize = 1 << Self::BITS;
91
92 /// Mask for which part of usize is
93 /// small enough to be held in this set.
94 const MASK: usize = Self::CAPACITY - 1;
95
96 /// Makes a new, empty vEB-tree-like object.
97 fn new() -> Self {
98 Default::default()
99 }
100
101 /// Clears the set, removing all elements.
102 fn clear(&mut self);
103
104 /// Returns true if the set contains no elements.
105 fn is_empty(&self) -> bool;
106
107 /// Returns true if the set contains x.
108 fn contains(&self, x: usize) -> bool;
109
110 /// Adds x to the set.
111 ///
112 /// If the set did not have x present, true is returned.
113 ///
114 /// If the set did have x present, false is returned,
115 /// and the entry is not updated.
116 fn insert(&mut self, x: usize) -> bool;
117
118 /// If the set contains x,
119 /// removes it from the set.
120 /// Returns whether such an element was present.
121 fn remove(&mut self, x: usize) -> bool;
122
123 /// Returns the first element in the set that is
124 /// greater or equal to x, if any.
125 fn next(&self, x: usize) -> Option<usize>;
126
127 /// Returns the last element in the set that is
128 /// smaller or equal to x, if any.
129 fn prev(&self, x: usize) -> Option<usize>;
130
131 /// Returns the first element in the set, if any.
132 /// This element is always the minimum of all elements in the set.
133 fn first(&self) -> Option<usize>;
134
135 /// Returns the last element in the set, if any.
136 /// This element is always the maximum of all elements in the set.
137 fn last(&self) -> Option<usize>;
138
139 /// Returns an iterator over the values in the set.
140 fn iter(&self) -> VEBIterator<'_, Self> {
141 VEBIterator {
142 tree: self,
143 next_start: 0,
144 }
145 }
146}
147
148/// This struct is created by the iter method
149/// on objects implementing VEBOperations
150#[derive(Debug)]
151pub struct VEBIterator<'a, T: VEBTree> {
152 tree: &'a T,
153 next_start: usize,
154}
155
156impl<'a, T: VEBTree> Iterator for VEBIterator<'a, T> {
157 type Item = usize;
158
159 fn next(&mut self) -> Option<Self::Item> {
160 if self.next_start == T::CAPACITY {
161 None
162 } else {
163 let value = self.tree.next(self.next_start)?;
164 self.next_start = value + 1;
165 Some(value)
166 }
167 }
168}
169
170#[cfg(test)]
171mod test {
172 use crate::VEBTree;
173
174 macro_rules! make_tests {
175 ($name:ident, $type:ty) => {
176 mod $name {
177 use crate::VEBTree;
178
179 type T = $type;
180
181 #[test]
182 fn empty_works() {
183 let mut s = T::new();
184 assert!(s.is_empty());
185 s.clear();
186 assert!(s.is_empty());
187
188 for x in 0..T::CAPACITY.min(1000) {
189 assert!(!s.contains(x));
190 }
191 }
192
193 #[test]
194 fn small_collect() {
195 let mut s = T::new();
196 s.insert(2);
197 s.insert(4);
198 s.insert(6);
199
200 let mut it = s.iter();
201 assert_eq!(it.next(), Some(2));
202 assert_eq!(it.next(), Some(4));
203 assert_eq!(it.next(), Some(6));
204 assert_eq!(it.next(), None);
205 }
206
207 #[test]
208 fn spaced_collect() {
209 let spacing = (T::CAPACITY / 20).max(2);
210 let mut s = T::new();
211
212 for x in (0..T::CAPACITY).step_by(spacing) {
213 s.insert(x);
214 }
215
216 let mut iter = s.iter();
217
218 for x in (0..T::CAPACITY).step_by(spacing) {
219 assert_eq!(iter.next(), Some(x));
220 }
221 assert_eq!(iter.next(), None);
222 }
223 }
224 };
225 }
226
227 make_tests! {size4, crate::VEBTree4}
228 make_tests! {size5, crate::VEBTree5}
229 make_tests! {size6, crate::VEBTree6}
230 make_tests! {size7, crate::VEBTree7}
231 make_tests! {size8, crate::VEBTree8}
232 make_tests! {size9, crate::VEBTree9}
233 make_tests! {size10, crate::VEBTree10}
234 make_tests! {size11, crate::VEBTree11}
235 make_tests! {size12, crate::VEBTree12}
236
237 #[test]
238 fn correct_bits() {
239 assert_eq!(crate::VEBTree4::BITS, 4);
240 assert_eq!(crate::VEBTree5::BITS, 5);
241 assert_eq!(crate::VEBTree6::BITS, 6);
242 assert_eq!(crate::VEBTree7::BITS, 7);
243 assert_eq!(crate::VEBTree8::BITS, 8);
244 assert_eq!(crate::VEBTree9::BITS, 9);
245 assert_eq!(crate::VEBTree10::BITS, 10);
246 assert_eq!(crate::VEBTree11::BITS, 11);
247 assert_eq!(crate::VEBTree12::BITS, 12);
248 assert_eq!(crate::VEBTree13::BITS, 13);
249 assert_eq!(crate::VEBTree14::BITS, 14);
250 assert_eq!(crate::VEBTree15::BITS, 15);
251 assert_eq!(crate::VEBTree16::BITS, 16);
252 assert_eq!(crate::VEBTree17::BITS, 17);
253 assert_eq!(crate::VEBTree18::BITS, 18);
254 assert_eq!(crate::VEBTree19::BITS, 19);
255 assert_eq!(crate::VEBTree20::BITS, 20);
256 assert_eq!(crate::VEBTree21::BITS, 21);
257 assert_eq!(crate::VEBTree22::BITS, 22);
258 assert_eq!(crate::VEBTree23::BITS, 23);
259 assert_eq!(crate::VEBTree24::BITS, 24);
260 assert_eq!(crate::VEBTree25::BITS, 25);
261 assert_eq!(crate::VEBTree26::BITS, 26);
262 assert_eq!(crate::VEBTree27::BITS, 27);
263 assert_eq!(crate::VEBTree28::BITS, 28);
264 assert_eq!(crate::VEBTree29::BITS, 29);
265 assert_eq!(crate::VEBTree30::BITS, 30);
266 assert_eq!(crate::VEBTree31::BITS, 31);
267 assert_eq!(crate::VEBTree32::BITS, 32);
268 }
269}