radix_immutable/
lib.rs

1//! # Radix Immutable
2//!
3//! An immutable radix trie (patricia trie) with structural sharing via `Arc`.
4//! Each mutation returns a new trie, sharing unchanged subtrees with the original.
5//!
6//! ## Features
7//!
8//! - **Immutable API**: insert/remove return new tries; originals are unchanged
9//! - **Structural sharing**: unchanged subtrees shared via `Arc`, making clones cheap
10//! - **Longest prefix match**: find the most specific stored prefix for a key
11//! - **Prefix iteration**: iterate entries under a prefix without scanning the full trie
12//! - **Prefix views**: lightweight subtrie handles for comparison and lookup
13//! - **Structural hashing**: lazily cached hashes for fast subtree equality checks
14//! - **Serde support**: optional `serde` feature flag
15//! - **Key generic**: supports any type convertible to bytes
16//!
17//! ## Example
18//!
19//! ```rust
20//! use radix_immutable::StringTrie;
21//!
22//! let trie = StringTrie::<String, i32>::new()
23//!     .insert("hello".to_string(), 1)
24//!     .insert("help".to_string(), 2)
25//!     .insert("world".to_string(), 3);
26//!
27//! // Lookup
28//! assert_eq!(trie.get(&"hello".to_string()), Some(&1));
29//!
30//! // Longest prefix match
31//! let trie = trie.insert("/api".to_string(), 10)
32//!     .insert("/api/users".to_string(), 20);
33//! assert_eq!(
34//!     trie.longest_prefix_match(&"/api/users/123".to_string()),
35//!     Some((&"/api/users".to_string(), &20))
36//! );
37//!
38//! // Prefix iteration
39//! let hel_entries: Vec<_> = trie.iter_prefix("hel".to_string()).collect();
40//! assert_eq!(hel_entries.len(), 2);
41//! ```
42//!
43//! You can also use custom types with a specialized key converter:
44//!
45//! ```rust
46//! use radix_immutable::{Trie, KeyToBytes};
47//! use std::path::{Path, PathBuf};
48//! use std::borrow::Cow;
49//! use std::marker::PhantomData;
50//!
51//! // Create a custom key converter for PathBuf
52//! #[derive(Clone, Debug)]
53//! struct PathKeyConverter<K>(PhantomData<K>);
54//!
55//! impl<K> Default for PathKeyConverter<K> {
56//!     fn default() -> Self {
57//!         Self(PhantomData)
58//!     }
59//! }
60//!
61//! impl<K: Clone + std::hash::Hash + Eq + AsRef<Path>> KeyToBytes<K> for PathKeyConverter<K> {
62//!     fn convert<'a>(key: &'a K) -> Cow<'a, [u8]> {
63//!         // Convert path to string and then to bytes
64//!         let path_str = key.as_ref().to_string_lossy();
65//!         Cow::Owned(path_str.as_bytes().to_vec())
66//!     }
67//! }
68//!
69//! // Create a trie that uses PathBuf as keys with our custom converter
70//! let trie = Trie::<PathBuf, i32, PathKeyConverter<PathBuf>>::new();
71//! ```
72
73pub mod key_converter;
74pub mod node;
75mod prefix_view;
76mod trie;
77mod util;
78
79// Re-export public types
80pub use crate::key_converter::{BytesKeyConverter, KeyToBytes, StrKeyConverter};
81pub use crate::node::TrieNode;
82pub use crate::prefix_view::{PrefixView, PrefixViewIter, PrefixViewArcIter};
83pub use crate::trie::Trie;
84
85/// Type alias for a Trie that uses string-based keys (anything implementing `AsRef<str>`)
86///
87/// This provides a convenient type for working with any keys that can be converted to strings.
88/// Examples of compatible types include: String, &str, PathBuf, Url, etc.
89pub type StringTrie<K, V> = Trie<K, V, StrKeyConverter<K>>;
90
91/// Type alias for a Trie that uses byte-based keys (anything implementing AsRef<[u8]>)
92///
93/// This provides a convenient type for working with any keys that can be converted to byte slices.
94/// Examples of compatible types include: `Vec<u8>`, `&[u8]`, etc.
95pub type BytesTrie<K, V> = Trie<K, V, BytesKeyConverter<K>>;
96
97/// Type alias for a PrefixView of a StringTrie
98///
99/// This provides a convenient type for working with prefix views over string-based keys.
100pub type StringPrefixView<K, V> = PrefixView<K, V, StrKeyConverter<K>>;
101
102/// Type alias for a PrefixView of a BytesTrie
103///
104/// This provides a convenient type for working with prefix views over byte-based keys.
105pub type BytesPrefixView<K, V> = PrefixView<K, V, BytesKeyConverter<K>>;
106
107/// Errors that can occur in trie operations
108#[derive(Debug, Clone, PartialEq, Eq)]
109pub enum Error {
110    /// Key is invalid for the operation
111    InvalidKey,
112    /// Other error with description
113    Other(String),
114}
115
116impl std::fmt::Display for Error {
117    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
118        match self {
119            Error::InvalidKey => write!(f, "Invalid key for this operation"),
120            Error::Other(msg) => write!(f, "{}", msg),
121        }
122    }
123}
124
125impl std::error::Error for Error {}
126
radix_immutable/lib.rs

radix_immutable/
lib.rs
