token_trie 0.1.0

A high-performance Radix Trie implementation with sorted children for efficient binary search operations
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

use token_trie::Trie;

fn main() {
    println!("=== Token Trie Demo ===\n");

    // Demo 1: Basic operations with character keys
    println!("1. Basic Operations with Character Keys");
    let mut char_trie = Trie::new();

    // Insert some words
    char_trie.insert(&['h', 'e', 'l', 'l', 'o'], "greeting");
    char_trie.insert(&['h', 'e', 'l', 'p'], "assistance");
    char_trie.insert(&['h', 'i'], "informal_greeting");
    char_trie.insert(&['w', 'o', 'r', 'l', 'd'], "earth");

    println!("Inserted words: hello, help, hi, world");

    // Search for values
    println!(
        "Looking up 'hello': {:?}",
        char_trie.get(&['h', 'e', 'l', 'l', 'o'])
    );
    println!(
        "Looking up 'help': {:?}",
        char_trie.get(&['h', 'e', 'l', 'p'])
    );
    println!("Looking up 'hi': {:?}", char_trie.get(&['h', 'i']));
    println!(
        "Looking up 'foo' (not in trie): {:?}",
        char_trie.get(&['f', 'o', 'o'])
    );

    // Prefix search
    println!(
        "\nWords starting with 'he': {:?}",
        char_trie.keys_with_prefix(&['h', 'e'])
    );
    println!(
        "Words starting with 'h': {:?}",
        char_trie.keys_with_prefix(&['h'])
    );

    // Common prefix length
    println!("\nCommon prefix length tests:");
    println!(
        "'hello' vs trie: {}",
        char_trie.common_prefix_length(&['h', 'e', 'l', 'l', 'o'])
    );
    println!(
        "'helper' vs trie: {}",
        char_trie.common_prefix_length(&['h', 'e', 'l', 'p', 'e', 'r'])
    );
    println!(
        "'hex' vs trie: {}",
        char_trie.common_prefix_length(&['h', 'e', 'x'])
    );
    println!(
        "'xyz' vs trie: {}",
        char_trie.common_prefix_length(&['x', 'y', 'z'])
    );

    println!("\n{}\n", "=".repeat(50));

    // Demo 2: Integer keys (useful for token IDs)
    println!("2. Integer Keys Demo (Token IDs)");
    let mut token_trie = Trie::new();

    // Simulate token sequences
    token_trie.insert(&[1, 2, 3], "sequence_a");
    token_trie.insert(&[1, 2, 4], "sequence_b");
    token_trie.insert(&[1, 5], "sequence_c");
    token_trie.insert(&[2, 3, 4, 5], "sequence_d");

    println!("Inserted token sequences:");
    println!("  [1,2,3] -> sequence_a");
    println!("  [1,2,4] -> sequence_b");
    println!("  [1,5] -> sequence_c");
    println!("  [2,3,4,5] -> sequence_d");

    println!("\nLookup results:");
    println!("  [1,2,3]: {:?}", token_trie.get(&[1, 2, 3]));
    println!("  [1,2]: {:?}", token_trie.get(&[1, 2]));
    println!("  [1,2,4]: {:?}", token_trie.get(&[1, 2, 4]));

    println!("\nSequences starting with [1]:");
    let prefix_1 = token_trie.keys_with_prefix(&[1]);
    for seq in &prefix_1 {
        println!("  {:?}", seq);
    }

    println!("\nSequences starting with [1,2]:");
    let prefix_12 = token_trie.keys_with_prefix(&[1, 2]);
    for seq in &prefix_12 {
        println!("  {:?}", seq);
    }

    println!("\n{}\n", "=".repeat(50));

    // Demo 3: Radix compression demonstration
    println!("3. Radix Compression Demo");
    let mut radix_trie = Trie::new();

    // These will be compressed in the radix trie
    radix_trie.insert(&['p', 'r', 'e', 'f', 'i', 'x', '_', '1'], "first");
    radix_trie.insert(&['p', 'r', 'e', 'f', 'i', 'x', '_', '2'], "second");
    radix_trie.insert(&['p', 'r', 'e', 'f', 'i', 'x', '_', '3'], "third");
    radix_trie.insert(&['p', 'r', 'e', 'f'], "prefix_itself");
    radix_trie.insert(&['p', 'r', 'e', 'p', 'a', 'r', 'e'], "prepare");

    println!("Inserted keys with common prefixes:");
    println!("  prefix_1, prefix_2, prefix_3, pref, prepare");

    println!("\nAll keys in trie:");
    let all_keys = radix_trie.keys();
    for key in &all_keys {
        let key_str: String = key.iter().collect();
        println!("  '{}' -> {:?}", key_str, radix_trie.get(key));
    }

    println!("\nCommon prefix analysis:");
    println!(
        "  'prefix_4' common length: {}",
        radix_trie.common_prefix_length(&['p', 'r', 'e', 'f', 'i', 'x', '_', '4'])
    );
    println!(
        "  'preparation' common length: {}",
        radix_trie.common_prefix_length(&['p', 'r', 'e', 'p', 'a', 'r', 'a', 't', 'i', 'o', 'n'])
    );

    println!("\n{}\n", "=".repeat(50));

    // Demo 4: Performance characteristics
    println!("4. Performance Demo");
    let mut perf_trie = Trie::new();

    // Insert many keys with various patterns
    println!("Inserting 1000 keys...");
    for i in 0..1000 {
        let key = generate_key_pattern(i);
        perf_trie.insert(&key, format!("value_{}", i));
    }

    println!("Total keys in trie: {}", perf_trie.len());

    // Test some lookups
    let test_key = generate_key_pattern(42);
    println!("Looking up key pattern 42: {:?}", perf_trie.get(&test_key));

    let test_key2 = generate_key_pattern(999);
    println!(
        "Looking up key pattern 999: {:?}",
        perf_trie.get(&test_key2)
    );

    // Test prefix search on large trie
    let prefix = vec![0, 1];
    let prefix_results = perf_trie.keys_with_prefix(&prefix);
    println!("Keys starting with [0,1]: {} found", prefix_results.len());

    println!("\n{}\n", "=".repeat(50));

    // Demo 5: Edge cases
    println!("5. Edge Cases Demo");
    let mut edge_trie = Trie::new();

    // Empty key
    edge_trie.insert(&[], "empty_key_value");
    println!("Inserted empty key");
    println!("Empty key lookup: {:?}", edge_trie.get(&[]));

    // Single element keys
    edge_trie.insert(&[42], "single_element");
    println!("Single element [42]: {:?}", edge_trie.get(&[42]));

    // Very long key
    let long_key: Vec<i32> = (0..50).collect();
    edge_trie.insert(&long_key, "very_long_sequence");
    println!(
        "Very long key (50 elements): {:?}",
        edge_trie.get(&long_key)
    );

    // Negative numbers
    edge_trie.insert(&[-1, -2, -3], "negative_sequence");
    println!(
        "Negative sequence [-1,-2,-3]: {:?}",
        edge_trie.get(&[-1, -2, -3])
    );

    println!("\nFinal edge trie stats:");
    println!("  Total keys: {}", edge_trie.len());
    println!("  Is empty: {}", edge_trie.is_empty());

    println!("\n=== Demo Complete ===");
}

// Helper function to generate test key patterns
fn generate_key_pattern(i: usize) -> Vec<i32> {
    match i % 4 {
        0 => vec![0, 1, (i % 10) as i32],
        1 => vec![1, (i % 5) as i32, (i % 3) as i32],
        2 => vec![(i % 7) as i32, 2, 3],
        3 => vec![3, (i % 8) as i32],
        _ => unreachable!(),
    }
}