kevy_ranktree/lib.rs
1//! `kevy-ranktree` — an order-statistic ordered set: a hand-written B-tree
2//! whose every node carries its subtree element count, so **rank** queries
3//! ("what position is this key at?") and **select** queries ("what key is at
4//! position k?") are single O(log N) descents instead of linear walks.
5//!
6//! This is the structure `std::collections::BTreeSet` cannot be: std's tree
7//! is not augmentable, so `Iterator::position` over it is the only way to a
8//! rank — O(N). Here each node's `total` field turns the same descent that
9//! finds a key into the arithmetic that counts everything to its left.
10//!
11//! # Why a counted B-tree and not a spanned skiplist
12//!
13//! Redis solves the same problem with a skiplist whose forward pointers carry
14//! spans. Both give O(log N) rank/select; the B-tree was chosen because:
15//!
16//! * **Cache behaviour** — a node holds up to `node::MAX_KEYS` keys in one
17//! contiguous buffer, so a descent touches ~log₈(N) cache lines where a
18//! skiplist chases one pointer per level *and* per element during range
19//! walks. Ordered full scans (persistence rewrites, snapshots) iterate
20//! arrays, not linked nodes.
21//! * **No probabilistic balance** — a skiplist needs a random level
22//! generator and its worst case is only expected-O(log N); the B-tree's
23//! bounds are deterministic.
24//! * **It matches what it replaces** — the callers previously held a
25//! `BTreeSet` and were tuned for its iteration pattern; this keeps that
26//! pattern and adds the rank arithmetic.
27//!
28//! The price is B-tree deletion (borrow/merge rebalancing), which is more
29//! code than a skiplist unlink — it lives in `remove.rs` and is held down by
30//! an exhaustive random-operation oracle test (`tests/oracle.rs`) that
31//! replays thousands of insert/remove/rank/select/range operations against a
32//! sorted-`Vec` reference.
33//!
34//! # Complexity
35//!
36//! | operation | cost |
37//! |---|---|
38//! | [`RankTree::insert`], [`RankTree::remove`] | O(log N) |
39//! | [`RankTree::rank_of`], [`RankTree::select`] | O(log N) |
40//! | [`RankTree::partition_point`], [`RankTree::count_in`] | O(log N) |
41//! | [`RankTree::range`], [`RankTree::iter_from`] | O(log N) seek + O(1) amortised per item |
42//! | [`RankTree::iter`], [`RankTree::iter_rev`] | O(1) amortised per item |
43//!
44//! Constraints: pure Rust, zero dependencies, `no_std`-capable behind the
45//! `alloc` feature, `#![forbid(unsafe_code)]`.
46//!
47//! ```
48//! use kevy_ranktree::RankTree;
49//!
50//! let t: RankTree<u32> = [50, 10, 40, 20, 30].into_iter().collect();
51//! assert_eq!(t.rank_of(&40), Some(3), "rank: how many keys sort before it");
52//! assert_eq!(t.select(1), Some(&20), "select: the key at a rank");
53//! assert_eq!(t.range(&(15..45)).copied().collect::<Vec<_>>(), vec![20, 30, 40]);
54//! assert_eq!(t.count_in(&(15..45)), 3, "counted, not walked");
55//! ```
56
57#![forbid(unsafe_code)]
58#![warn(missing_docs)]
59#![cfg_attr(not(feature = "std"), no_std)]
60
61extern crate alloc;
62
63mod insert;
64mod iter;
65mod node;
66mod remove;
67// Send and Sync are part of the public contract: a change that loses
68// either fails to compile here rather than in a caller.
69const _: () = {
70 const fn send_sync<T: Send + Sync>() {}
71 send_sync::<RankTree<u64>>();
72 send_sync::<Iter<'static, u64>>();
73 send_sync::<IterRev<'static, u64>>();
74 send_sync::<Range<'static, u64>>();
75};
76
77#[cfg(test)]
78mod tests_invariants;
79
80use core::ops::{Bound, RangeBounds};
81
82pub use iter::{Iter, IterRev, Range};
83use node::Node;
84
85/// An ordered set of `K` with O(log N) order statistics (rank / select).
86///
87/// Duplicate keys are rejected ([`RankTree::insert`] returns `false`), which
88/// makes every key's rank unique — the property the rank arithmetic rests on.
89/// # Examples
90///
91/// The point of an order-statistic tree is that rank is a lookup, not a
92/// scan: inserting out of order still answers rank in sorted order.
93///
94/// ```
95/// let mut t = kevy_ranktree::RankTree::new();
96/// for k in [30, 10, 20] {
97/// assert!(t.insert(k), "each key is new");
98/// }
99/// assert_eq!(t.len(), 3);
100/// assert_eq!(t.rank_of(&10), Some(0));
101/// assert_eq!(t.rank_of(&20), Some(1));
102/// assert_eq!(t.rank_of(&30), Some(2));
103/// assert_eq!(t.rank_of(&25), None, "a key that is not there has no rank");
104/// ```
105///
106/// Re-inserting an existing key reports that it was not new, and leaves
107/// the tree alone.
108///
109/// ```
110/// let mut t = kevy_ranktree::RankTree::new();
111/// assert!(t.insert(1));
112/// assert!(!t.insert(1));
113/// assert_eq!(t.len(), 1);
114/// ```
115#[derive(Debug, Clone)]
116pub struct RankTree<K> {
117 root: Node<K>,
118}
119
120impl<K> Default for RankTree<K> {
121 fn default() -> Self {
122 Self::new()
123 }
124}
125
126impl<K> RankTree<K> {
127 /// An empty tree.
128 /// # Examples
129 ///
130 /// ```
131 /// let t: kevy_ranktree::RankTree<u32> = kevy_ranktree::RankTree::new();
132 /// assert!(t.is_empty());
133 /// assert_eq!(t.len(), 0);
134 /// ```
135 #[must_use]
136 pub fn new() -> Self {
137 RankTree { root: Node::leaf() }
138 }
139
140 /// Number of keys in the tree. O(1): the root carries its subtree count.
141 /// # Examples
142 ///
143 /// ```
144 /// let mut t = kevy_ranktree::RankTree::new();
145 /// t.insert(1u32); t.insert(1);
146 /// assert_eq!(t.len(), 1, "a set: the repeat did not count");
147 /// ```
148 #[must_use]
149 pub fn len(&self) -> usize {
150 self.root.total
151 }
152
153 /// Whether the tree holds no keys.
154 /// # Examples
155 ///
156 /// ```
157 /// let mut t = kevy_ranktree::RankTree::new();
158 /// assert!(t.is_empty());
159 /// t.insert(1u32);
160 /// assert!(!t.is_empty());
161 /// ```
162 #[must_use]
163 pub fn is_empty(&self) -> bool {
164 self.root.total == 0
165 }
166
167 /// Drop every key.
168 /// # Examples
169 ///
170 /// ```
171 /// let mut t = kevy_ranktree::RankTree::new();
172 /// for k in [1u32, 2, 3] { t.insert(k); }
173 /// t.clear();
174 /// assert!(t.is_empty());
175 /// assert_eq!(t.select(0), None);
176 /// ```
177 pub fn clear(&mut self) {
178 self.root = Node::leaf();
179 }
180
181 /// The key at ascending `rank` (0-based; rank 0 = smallest), or `None`
182 /// past the end. O(log N): each level subtracts the child counts to the
183 /// left instead of walking them.
184 /// # Examples
185 ///
186 /// ```
187 /// let mut t = kevy_ranktree::RankTree::new();
188 /// for k in [30u32, 10, 20] { t.insert(k); }
189 /// // Rank is 0-based over the SORTED order, not insertion order.
190 /// assert_eq!(t.select(0), Some(&10));
191 /// assert_eq!(t.select(2), Some(&30));
192 /// assert_eq!(t.select(3), None);
193 /// ```
194 #[must_use]
195 pub fn select(&self, rank: usize) -> Option<&K> {
196 if rank >= self.root.total {
197 return None;
198 }
199 // Landing on a leaf offset and landing on a separator are the
200 // same answer here — both are `keys[idx]` of the node returned.
201 let (node, idx) = crate::node::descend_to_rank(&self.root, rank, |_, _| {});
202 Some(&node.keys[idx])
203 }
204
205 /// Forward in-order iterator over all keys.
206 /// # Examples
207 ///
208 /// ```
209 /// let mut t = kevy_ranktree::RankTree::new();
210 /// for k in [30u32, 10, 20] { t.insert(k); }
211 /// assert_eq!(t.iter().copied().collect::<Vec<_>>(), vec![10, 20, 30]);
212 /// assert_eq!(t.iter_rev().copied().collect::<Vec<_>>(), vec![30, 20, 10]);
213 /// ```
214 #[must_use]
215 pub fn iter(&self) -> Iter<'_, K> {
216 self.iter_from(0)
217 }
218
219 /// Forward in-order iterator starting at ascending `rank` (seek is one
220 /// O(log N) descent; an out-of-range rank yields nothing).
221 /// # Examples
222 ///
223 /// ```
224 /// let mut t = kevy_ranktree::RankTree::new();
225 /// for k in [10u32, 20, 30] { t.insert(k); }
226 /// // Start at a RANK, so paging costs a descent rather than a skip.
227 /// assert_eq!(t.iter_from(1).copied().collect::<Vec<_>>(), vec![20, 30]);
228 /// assert!(t.iter_from(9).next().is_none());
229 /// ```
230 #[must_use]
231 pub fn iter_from(&self, rank: usize) -> Iter<'_, K> {
232 Iter::new_from(&self.root, rank)
233 }
234
235 /// Reverse in-order iterator over all keys (largest first).
236 /// # Examples
237 ///
238 /// ```
239 /// let mut t = kevy_ranktree::RankTree::new();
240 /// for k in [10u32, 20, 30] { t.insert(k); }
241 /// assert_eq!(t.iter_rev().copied().collect::<Vec<_>>(), vec![30, 20, 10]);
242 /// ```
243 #[must_use]
244 pub fn iter_rev(&self) -> IterRev<'_, K> {
245 IterRev::new_through(&self.root, self.root.total)
246 }
247
248 /// Reverse iterator that starts at ascending rank `rank - 1` and walks
249 /// down to rank 0 — i.e. the SMALLEST `rank` keys, descending. `rank`
250 /// saturates at `len()`.
251 ///
252 /// (This line used to say "the largest `rank` keys". It is the first
253 /// `rank` keys read backwards, which is the opposite end; writing the
254 /// example below is what caught it.)
255 ///
256 /// # Examples
257 ///
258 /// ```
259 /// let mut t = kevy_ranktree::RankTree::new();
260 /// for k in [10u32, 20, 30] { t.insert(k); }
261 /// // Ascending ranks 1 and 0, walked down: the two SMALLEST keys.
262 /// assert_eq!(t.iter_rev_from(2).copied().collect::<Vec<_>>(), vec![20, 10]);
263 /// assert_eq!(t.iter_rev_from(1).copied().collect::<Vec<_>>(), vec![10]);
264 /// assert!(t.iter_rev_from(0).next().is_none());
265 /// // Saturating, not panicking.
266 /// assert_eq!(t.iter_rev_from(99).copied().collect::<Vec<_>>(), vec![30, 20, 10]);
267 /// ```
268 #[must_use]
269 pub fn iter_rev_from(&self, rank: usize) -> IterRev<'_, K> {
270 IterRev::new_through(&self.root, rank)
271 }
272}
273
274impl<K: Ord> RankTree<K> {
275 /// The ascending rank of `key`, or `None` if absent. O(log N).
276 /// # Examples
277 ///
278 /// ```
279 /// let mut t = kevy_ranktree::RankTree::new();
280 /// for k in [10u32, 20, 30] { t.insert(k); }
281 /// assert_eq!(t.rank_of(&20), Some(1));
282 /// // The inverse of `select`, and `None` for a key that is absent —
283 /// // never the rank it WOULD have.
284 /// assert_eq!(t.rank_of(&25), None);
285 /// assert_eq!(t.select(t.rank_of(&30).unwrap()), Some(&30));
286 /// ```
287 #[must_use]
288 pub fn rank_of(&self, key: &K) -> Option<usize> {
289 let mut node = &self.root;
290 let mut acc = 0usize;
291 loop {
292 match node.keys.binary_search(key) {
293 Ok(i) => {
294 for c in node.children.iter().take(i + 1) {
295 acc += c.total;
296 }
297 return Some(acc + i);
298 }
299 Err(i) => {
300 if node.is_leaf() {
301 return None;
302 }
303 acc += i;
304 for c in &node.children[..i] {
305 acc += c.total;
306 }
307 node = &node.children[i];
308 }
309 }
310 }
311 }
312
313 /// The number of leading keys for which `pred` holds. `pred` must be
314 /// monotone (true for a prefix of the ordered keys, false after) — the
315 /// same contract as `slice::partition_point`. O(log N).
316 ///
317 /// This is the primitive behind every bound query: a caller keying the
318 /// tree by a composite like `(score, member)` can seek on the score
319 /// alone with `pred = |(s, _)| *s < bound`.
320 /// # Examples
321 ///
322 /// ```
323 /// let mut t = kevy_ranktree::RankTree::new();
324 /// for k in [1u32, 3, 5, 7] { t.insert(k); }
325 /// // The rank of the first key the predicate rejects — so the whole
326 /// // tree when it never does, and 0 when it always does.
327 /// assert_eq!(t.partition_point(|k| *k < 5), 2);
328 /// assert_eq!(t.partition_point(|_| true), 4);
329 /// assert_eq!(t.partition_point(|_| false), 0);
330 /// ```
331 #[must_use]
332 pub fn partition_point<F: FnMut(&K) -> bool>(&self, mut pred: F) -> usize {
333 let mut node = &self.root;
334 let mut acc = 0usize;
335 loop {
336 let i = node.keys.partition_point(|k| pred(k));
337 if node.is_leaf() {
338 return acc + i;
339 }
340 // keys[..i] hold, so each of children[..i] (all strictly below
341 // keys[i-1]) holds entirely; children[i] is the mixed frontier.
342 acc += i;
343 for c in &node.children[..i] {
344 acc += c.total;
345 }
346 node = &node.children[i];
347 }
348 }
349
350 /// How many keys fall inside `bounds`. Two [`RankTree::partition_point`]
351 /// descents — O(log N), never a scan.
352 /// # Examples
353 ///
354 /// ```
355 /// let mut t = kevy_ranktree::RankTree::new();
356 /// for k in [1u32, 3, 5, 7] { t.insert(k); }
357 /// // Counted from the subtree sizes, not by walking the range.
358 /// assert_eq!(t.count_in(&(3..=7)), 3);
359 /// assert_eq!(t.count_in(&(3..7)), 2);
360 /// assert_eq!(t.count_in(&(8..)), 0);
361 /// ```
362 #[must_use]
363 pub fn count_in<R: RangeBounds<K>>(&self, bounds: &R) -> usize {
364 let (lo, hi) = self.bound_ranks(bounds);
365 hi.saturating_sub(lo)
366 }
367
368 /// Iterate the keys inside `bounds` in ascending order: one O(log N)
369 /// seek to the lower bound, then O(1) amortised per yielded key.
370 /// # Examples
371 ///
372 /// ```
373 /// let mut t = kevy_ranktree::RankTree::new();
374 /// for k in [1u32, 3, 5, 7] { t.insert(k); }
375 /// let got: Vec<_> = t.range(&(3..=5)).copied().collect();
376 /// assert_eq!(got, vec![3, 5]);
377 /// ```
378 #[must_use]
379 pub fn range<R: RangeBounds<K>>(&self, bounds: &R) -> Range<'_, K> {
380 let (lo, hi) = self.bound_ranks(bounds);
381 Range(Iter::new_from(&self.root, lo).capped(hi.saturating_sub(lo)))
382 }
383
384 /// `(first rank inside, first rank past)` for `bounds`.
385 fn bound_ranks<R: RangeBounds<K>>(&self, bounds: &R) -> (usize, usize) {
386 let lo = match bounds.start_bound() {
387 Bound::Unbounded => 0,
388 Bound::Included(k) => self.partition_point(|x| x < k),
389 Bound::Excluded(k) => self.partition_point(|x| x <= k),
390 };
391 let hi = match bounds.end_bound() {
392 Bound::Unbounded => self.len(),
393 Bound::Included(k) => self.partition_point(|x| x <= k),
394 Bound::Excluded(k) => self.partition_point(|x| x < k),
395 };
396 (lo, hi)
397 }
398}