token_trie 0.1.0

# Token Trie

A high-performance Radix Trie implementation in Rust with sorted children for efficient binary search operations.

## Features

- **Radix Compression**: Efficient space usage through path compression
- **Sorted Children**: All child nodes are kept sorted for O(log k) lookups where k is the branching factor
- **Binary Search**: Fast child node lookup using binary search
- **Generic Keys**: Works with any key type that implements `Clone + Ord + PartialEq`
- **Prefix Operations**: Efficient prefix search and common prefix length calculation
- **Memory Safe**: Written in safe Rust with comprehensive test coverage

## Installation

Add this to your `Cargo.toml`:

```toml
[dependencies]
token_trie = "0.1.0"
```

## Quick Start

```rust
use token_trie::Trie;

// Create a new trie
let mut trie = Trie::new();

// Insert key-value pairs
trie.insert(&['h', 'e', 'l', 'l', 'o'], "greeting");
trie.insert(&['h', 'e', 'l', 'p'], "assistance");
trie.insert(&['w', 'o', 'r', 'l', 'd'], "earth");

// Look up values
assert_eq!(trie.get(&['h', 'e', 'l', 'l', 'o']), Some(&"greeting"));
assert_eq!(trie.get(&['f', 'o', 'o']), None);

// Prefix search
let he_words = trie.keys_with_prefix(&['h', 'e']);
println!("Words starting with 'he': {:?}", he_words);

// Common prefix length
let prefix_len = trie.common_prefix_length(&['h', 'e', 'l', 'p', 'e', 'r']);
assert_eq!(prefix_len, 4); // Matches "help"
```

## Usage with Integer Keys (Token IDs)

The trie works excellently with integer sequences, making it perfect for token-based applications:

```rust
use token_trie::Trie;

let mut token_trie = Trie::new();

// Insert 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");

// Find all sequences starting with [1, 2]
let sequences = token_trie.keys_with_prefix(&[1, 2]);
// Returns: [[1, 2, 3], [1, 2, 4]]
```

## API Reference

### Core Operations

- `new()` - Create a new empty trie
- `insert(&[Key], Value)` - Insert a key-value pair
- `get(&[Key]) -> Option<&Value>` - Get value for a key
- `remove(&[Key]) -> Option<Value>` - Remove and return value for a key
- `contains_key(&[Key]) -> bool` - Check if key exists

### Advanced Operations

- `keys_with_prefix(&[Key]) -> Vec<Vec<Key>>` - Get all keys with given prefix
- `common_prefix_length(&[Key]) -> usize` - Find longest common prefix length
- `iter() -> Vec<(Vec<Key>, &Value)>` - Get all key-value pairs
- `keys() -> Vec<Vec<Key>>` - Get all keys
- `len() -> usize` - Number of key-value pairs
- `is_empty() -> bool` - Check if trie is empty

## Performance Characteristics

- **Insert**: O(m) where m is the key length
- **Lookup**: O(m + log k) where k is the average branching factor
- **Delete**: O(m + log k)
- **Prefix Search**: O(p + n) where p is prefix length and n is number of matching keys
- **Space**: O(total_characters) with radix compression

## Algorithm Details

This implementation uses a **Radix Trie** (compressed trie) with the following optimizations:

1. **Path Compression**: Nodes with single children are compressed into their parent
2. **Sorted Children**: Child nodes are maintained in sorted order
3. **Binary Search**: Child lookup uses binary search for O(log k) performance
4. **Root Constraint**: The root node always has an empty key

## Examples

Run the comprehensive demo:

```bash
cargo run --example demo
```

## Testing

The implementation includes extensive test coverage:

```bash
cargo test
```

Test categories:
- Basic operations (insert, get, remove)
- Radix compression behavior
- Children ordering after all operations
- Binary search efficiency
- Edge cases with various key types
- Random operations stress testing
- Common prefix length accuracy

## License

MIT License - see LICENSE file for details.

## Contributing

Contributions are welcome! Please ensure all tests pass and add tests for new features.