Skip to main content

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}