radix_immutable 0.1.0

Generic immutable radix trie data-structure.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! # Radix Immutable
//!
//! An immutable radix trie (patricia trie) with structural sharing via `Arc`.
//! Each mutation returns a new trie, sharing unchanged subtrees with the original.
//!
//! ## Features
//!
//! - **Immutable API**: insert/remove return new tries; originals are unchanged
//! - **Structural sharing**: unchanged subtrees shared via `Arc`, making clones cheap
//! - **Longest prefix match**: find the most specific stored prefix for a key
//! - **Prefix iteration**: iterate entries under a prefix without scanning the full trie
//! - **Prefix views**: lightweight subtrie handles for comparison and lookup
//! - **Structural hashing**: lazily cached hashes for fast subtree equality checks
//! - **Serde support**: optional `serde` feature flag
//! - **Key generic**: supports any type convertible to bytes
//!
//! ## Example
//!
//! ```rust
//! use radix_immutable::StringTrie;
//!
//! let trie = StringTrie::<String, i32>::new()
//!     .insert("hello".to_string(), 1)
//!     .insert("help".to_string(), 2)
//!     .insert("world".to_string(), 3);
//!
//! // Lookup
//! assert_eq!(trie.get(&"hello".to_string()), Some(&1));
//!
//! // Longest prefix match
//! let trie = trie.insert("/api".to_string(), 10)
//!     .insert("/api/users".to_string(), 20);
//! assert_eq!(
//!     trie.longest_prefix_match(&"/api/users/123".to_string()),
//!     Some((&"/api/users".to_string(), &20))
//! );
//!
//! // Prefix iteration
//! let hel_entries: Vec<_> = trie.iter_prefix("hel".to_string()).collect();
//! assert_eq!(hel_entries.len(), 2);
//! ```
//!
//! You can also use custom types with a specialized key converter:
//!
//! ```rust
//! use radix_immutable::{Trie, KeyToBytes};
//! use std::path::{Path, PathBuf};
//! use std::borrow::Cow;
//! use std::marker::PhantomData;
//!
//! // Create a custom key converter for PathBuf
//! #[derive(Clone, Debug)]
//! struct PathKeyConverter<K>(PhantomData<K>);
//!
//! impl<K> Default for PathKeyConverter<K> {
//!     fn default() -> Self {
//!         Self(PhantomData)
//!     }
//! }
//!
//! impl<K: Clone + std::hash::Hash + Eq + AsRef<Path>> KeyToBytes<K> for PathKeyConverter<K> {
//!     fn convert<'a>(key: &'a K) -> Cow<'a, [u8]> {
//!         // Convert path to string and then to bytes
//!         let path_str = key.as_ref().to_string_lossy();
//!         Cow::Owned(path_str.as_bytes().to_vec())
//!     }
//! }
//!
//! // Create a trie that uses PathBuf as keys with our custom converter
//! let trie = Trie::<PathBuf, i32, PathKeyConverter<PathBuf>>::new();
//! ```

pub mod key_converter;
pub mod node;
mod prefix_view;
mod trie;
mod util;

// Re-export public types
pub use crate::key_converter::{BytesKeyConverter, KeyToBytes, StrKeyConverter};
pub use crate::node::TrieNode;
pub use crate::prefix_view::{PrefixView, PrefixViewIter, PrefixViewArcIter};
pub use crate::trie::Trie;

/// Type alias for a Trie that uses string-based keys (anything implementing `AsRef<str>`)
///
/// This provides a convenient type for working with any keys that can be converted to strings.
/// Examples of compatible types include: String, &str, PathBuf, Url, etc.
pub type StringTrie<K, V> = Trie<K, V, StrKeyConverter<K>>;

/// Type alias for a Trie that uses byte-based keys (anything implementing AsRef<[u8]>)
///
/// This provides a convenient type for working with any keys that can be converted to byte slices.
/// Examples of compatible types include: `Vec<u8>`, `&[u8]`, etc.
pub type BytesTrie<K, V> = Trie<K, V, BytesKeyConverter<K>>;

/// Type alias for a PrefixView of a StringTrie
///
/// This provides a convenient type for working with prefix views over string-based keys.
pub type StringPrefixView<K, V> = PrefixView<K, V, StrKeyConverter<K>>;

/// Type alias for a PrefixView of a BytesTrie
///
/// This provides a convenient type for working with prefix views over byte-based keys.
pub type BytesPrefixView<K, V> = PrefixView<K, V, BytesKeyConverter<K>>;

/// Errors that can occur in trie operations
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Error {
    /// Key is invalid for the operation
    InvalidKey,
    /// Other error with description
    Other(String),
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Error::InvalidKey => write!(f, "Invalid key for this operation"),
            Error::Other(msg) => write!(f, "{}", msg),
        }
    }
}

impl std::error::Error for Error {}