augmented_rbtree/
lib.rs

1//! # augmented-rbtree
2//!
3//! An augmented red-black tree with generic, user-defined per-node statistics.
4//!
5//! ## What is an Augmented Red-Black Tree?
6//!
7//! A standard [red-black tree] is a self-balancing binary search tree that guarantees
8//! O(log n) insert, delete, and lookup. An *augmented* variant extends each node with
9//! extra data (called *statistics* or *augmentation*), computed from its subtree.
10//! Because the tree stays balanced, the statistics at the root always reflect the entire
11//! collection, and any prefix or suffix can be queried in O(log n) time.
12//!
13//! Common examples built on this primitive:
14//!
15//! | Use case | Key | Value | Augmentation |
16//! |----------|-----|-------|-------------|
17//! | **Order-statistics tree** | any | any | subtree size |
18//! | **Interval tree** | interval start | interval end | max endpoint in subtree |
19//! | **Range-sum tree** | any | numeric | subtree sum |
20//! | **Range-max tree** | any | numeric | subtree max |
21//!
22//! [red-black tree]: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
23//!
24//! ## Quick Start
25//!
26//! Add to your `Cargo.toml`:
27//!
28//! ```toml
29//! [dependencies]
30//! augmented-rbtree = "0.1"
31//! ```
32//!
33//! Implement the [`Augment`] trait or use one of the built-in augmentations in [`augmentations`]. Then create a tree:
34//!
35//!
36//! # Examples
37//! ```
38//! use augmented_rbtree::{Augment, AugmentedRBTreeFactory};
39//!
40//! /// Tracks the number of nodes in each subtree.
41//! struct SubtreeCount;
42//!
43//! impl<K, V> Augment<K, V> for SubtreeCount {
44//!     type Stats = usize;
45//!
46//!     fn compute(_k: &K, _v: &V,
47//!                left:  Option<(&K, &V, &usize)>,
48//!                right: Option<(&K, &V, &usize)>) -> usize {
49//!         1 + left.map(|(_, _, &c)| c).unwrap_or(0)
50//!           + right.map(|(_, _, &c)| c).unwrap_or(0)
51//!     }
52//! }
53//! fn main() {
54//!     let mut tree = AugmentedRBTreeFactory::<SubtreeCount>::new_tree();
55//!     tree.insert(3, "c");
56//!     tree.insert(1, "a");
57//!     tree.insert(2, "b");
58//!
59//!     // Total count is always at the root
60//!     assert_eq!(tree.root_stats(), Some(&3));
61//!
62//!     // Standard ordered-map operations
63//!     assert_eq!(tree.get(&2), Some(&"b"));
64//!     assert_eq!(tree.first_key_value_stats(), Some((&1, &"a", &1)));
65//!
66//!     // Iterate in sorted order; each entry exposes (key, value, stats)
67//!     for (k, v, count) in tree.iter() {
68//!         println!("key={k}, value={v}, subtree_size={count}");
69//!     }
70//! }
71//! ```
72//!
73//! ## Feature Flags
74//!
75//! | Feature | Default | Description |
76//! |---------|---------|-------------|
77//! | `alloc` | **Yes** | Uses the standard `alloc` crate for baseline heap allocation support. |
78//! | `allocator-api` | No | Enables custom local allocator support on stable Rust via `allocator-api2`. |
79//! | `nightly` | No | Opts into the upstream standard `core::alloc::Allocator` API (Requires Nightly). |
80//! | `serde` | No | Implements [`serde::Serialize`] and [`serde::Deserialize`] for the tree. |
81//! | `debug` | No | Makes `verify_properties` and `verify_augmentation` available in release builds. |
82//! | `interval_tree` | No | Enables the [`interval_tree`] module, which implements an interval tree using this crate. |
83//!
84//! ## Red-Black Tree Properties
85//!
86//! 1. Every node is Red or Black.
87//! 2. The root is Black.
88//! 3. All nil leaves are Black.
89//! 4. A Red node's children are both Black.
90//! 5. Every path from a node to a descendant nil has the same number of Black nodes.
91
92#![no_std]
93// enable the allocator_api feature on nightly toolchains to access the `Allocator` trait and related APIs
94#![cfg_attr(feature = "nightly", feature(allocator_api))]
95#![deny(missing_debug_implementations)]
96#![deny(missing_docs)]
97#![warn(rust_2018_idioms)]
98#![allow(clippy::type_complexity)]
99#![deny(rustdoc::broken_intra_doc_links)]
100#![warn(clippy::doc_markdown)]
101#![cfg_attr(coverage_nightly, feature(coverage_attribute))]
102#![cfg_attr(docsrs, feature(doc_cfg))]
103#![doc = include_str!("../README.md")]
104#![cfg_attr(feature = "experimental", feature(dropck_eyepatch))]
105
106// If both are enabled, prioritize nightly and throw a helpful compiler warning
107#[cfg(all(feature = "nightly", feature = "allocator-api", not(doc)))]
108compile_error!(
109    "The features 'nightly' and 'allocator-api' are mutually exclusive. \
110     Please enable 'nightly' for nightly toolchains, or 'allocator-api' for stable toolchains."
111);
112
113#[cfg(any(
114    feature = "alloc",
115    feature = "allocator-api",
116    feature = "nightly",
117    test
118))]
119#[allow(unused_extern_crates)]
120extern crate alloc;
121
122mod alloc_proxy;
123mod augment;
124pub mod augmentations;
125mod augmented_rbtree;
126mod cursor;
127mod entry;
128#[cfg(feature = "interval-tree")]
129pub mod interval_tree;
130mod iterators;
131mod layout;
132mod node;
133mod node_allocator;
134mod policy;
135mod search;
136
137#[cfg(feature = "serde")]
138mod serde_impl;
139
140#[cfg(any(feature = "nightly", feature = "allocator-api", feature = "alloc"))]
141pub use alloc_proxy::proxy::{AllocError, Allocator, Global, Layout};
142pub use augment::Augment;
143pub use augmentations::{
144    IntervalMaxEnd, MaxAugmentation, MinAugmentation, SubtreeSize, SumAugmentation, Unit,
145};
146pub use augmented_rbtree::{
147    AugmentedRBTree, AugmentedRBTreeFactory, OutOfMemoryError, RBTree, TreeLocation,
148    internal_details::AugmentedRBTreeInt,
149};
150pub use cursor::{NavCursor, NavCursorMut};
151pub use entry::{Entry, OccupiedEntry, VacantEntry};
152pub use iterators::{
153    Iter, IterMut, Keys, NodeGuard, Range, RangeMut, ValueGuard, Values, ValuesMut,
154};
155pub use node::Color;
156pub use search::{InOrderIter, InOrderPruningPolicy};
157#[cfg(feature = "serde")]
158pub use serde_impl::AugmentedRBTreeSeed;
augmented_rbtree/lib.rs

augmented_rbtree/
lib.rs
