wabi_tree/lib.rs
1//! Order-statistic B-tree collections for Rust.
2//!
3//! This crate provides [`OSBTreeMap`] and [`OSBTreeSet`], which are drop-in replacements
4//! for the standard library's `BTreeMap` and `BTreeSet` with additional O(log n)
5//! order-statistic operations:
6//!
7//! - [`get_by_rank`](OSBTreeMap::get_by_rank) - Get the element at a given sorted position
8//! - [`rank_of`](OSBTreeMap::rank_of) - Get the sorted position of a key
9//! - Indexing by [`Rank`] - e.g., `map[Rank(0)]` for the first element
10//!
11//! # Example
12//!
13//! ```
14//! use wabi_tree::{OSBTreeMap, Rank};
15//!
16//! let mut scores = OSBTreeMap::new();
17//! scores.insert("Alice", 100);
18//! scores.insert("Bob", 85);
19//! scores.insert("Carol", 92);
20//!
21//! // Standard BTreeMap operations work as expected
22//! assert_eq!(scores.get(&"Bob"), Some(&85));
23//! assert_eq!(scores.len(), 3);
24//!
25//! // Order-statistic operations (O(log n))
26//! // Get the median (rank 1 = second element in sorted order)
27//! let (name, score) = scores.get_by_rank(1).unwrap();
28//! assert_eq!(*name, "Bob"); // Keys are sorted alphabetically
29//!
30//! // Find the rank of a key
31//! assert_eq!(scores.rank_of(&"Carol"), Some(2)); // Carol is third alphabetically
32//!
33//! // Index by rank
34//! assert_eq!(scores[Rank(0)], 100); // Alice's score (first alphabetically)
35//! ```
36//!
37//! # Features
38//!
39//! - **`no_std` compatible** - Only requires `alloc`, no standard library dependency
40//! - **Drop-in replacement** - API mirrors `std::collections::BTreeMap`/`BTreeSet`
41//! - **O(log n) rank operations** - Efficient order-statistic queries via subtree size augmentation
42//! - **Cache-efficient** - B+tree structure with contiguous node storage
43//!
44//! # Implementation
45//!
46//! The collections are implemented as B+trees (all data in leaves, linked leaf chain)
47//! with subtree size augmentation. Each internal node tracks the sizes of its subtrees,
48//! enabling O(log n) rank-based access without full traversal.
49
50#![no_std]
51// These forbid rules and lint groups are meant to be very restrictive.
52// NOTE: We have to allow unsafe code in order to performantly match BTreeMap and BTreeSet's functionality.
53// #![forbid(unsafe_code)]
54#![forbid(keyword_idents)]
55#![forbid(non_ascii_idents)]
56#![forbid(unreachable_pub)]
57#![warn(clippy::all)]
58#![warn(clippy::cargo)]
59#![warn(clippy::pedantic)]
60// Enable coverage attributes for nightly builds.
61#![cfg_attr(coverage_nightly, feature(coverage_attribute))]
62// Allow unused code during initial development.
63#![allow(unused)]
64// Allow todo!() placeholders during API scaffolding.
65#![allow(clippy::todo)]
66
67extern crate alloc;
68
69mod order_statistic;
70mod raw;
71
72pub mod osbtree_map;
73pub mod osbtree_set;
74
75pub use order_statistic::Rank;
76pub use osbtree_map::OSBTreeMap;
77pub use osbtree_set::OSBTreeSet;