prefix_tree_map

A Rust implementation of generic prefix tree (trie) map with wildcard capture support.

Pros and Cons

Pros

• Fast and efficient
• Wildcard Capture Support - Capture wildcard characters in a map while matching.
• Generalization - Supports any type of key and value, as long as key parts are implemented the Ord and the Clone trait.
• Capture Map Customization - Customize the way key parts captured by wildcard stored.
• No recursion in find operations - Since the key could be huge data structure, to avoid stack overflow, this prefix tree map only store those tiny wildcard node pointers for backtracking, rather than store the whole context of every node searching

Cons

• The map itself is immutable, because the map builder is using Binary Heap to sort the nodes when they are inserted. We can't get a item from a Binary Heap without whole iteration on it. Once the build() is called, Binary Heaps are converted into sorted Vecs. We can't push any item to the Vec without a sort.
• A single wildcard cannot be matched more than one time. It means word can only be matched by w**d, not w*d.

Usage

use prefix_tree_map::PrefixTreeMapBuilder;

let mut map_builder = PrefixTreeMapBuilder::new();

// To insert an exact key path, call `insert_exact()`
map_builder.insert_exact(["path", "to", "value"], "value0");

// Insert into a existed key path could overwrite the value in it
map_builder.insert_exact(["path", "to", "value"], "value1");

// To insert an key path with wildcards, mark key parts using `prefix_tree_map::KeyPart` and call `insert()`
use prefix_tree_map::KeyPart;

map_builder.insert(
    [
        KeyPart::Exact("path"),
        KeyPart::Wildcard("to"),
        KeyPart::Exact("value"),
    ],
    "value2",
);

// Anything implemented trait `FromIterator` can be inserted as a key path:
let path = "path/to/anothor/value";
map_builder.insert_exact(path.split('/'), "value3");

let anothor_path = "path/to/:some/value";
map_builder.insert(
    anothor_path.split('/').map(|part| {
        if part.starts_with(':') {
            KeyPart::Wildcard(part)
        } else {
            KeyPart::Exact(part)
        }
    }),
    "value4",
);

// Then build the map
let map = map_builder.build();

// Find a value without matching any wildcard part
assert_eq!(
    Some(&"value3"),
    map.find_exact(&["path", "to", "anothor", "value"])
);

// Find a value with matching wildcard part
assert_eq!(Some(&"value4"), map.find(&["path", "to", "a", "value"]));

// `KeyPart::Exact` has a higher match priority than `KeyPart::Wildcard`
assert_eq!(Some(&"value3"), map.find(&["path", "to", "anothor", "value"]));

// Find a value with matching wildcard part, and store captured matched wildcard parts in a map
use std::collections::HashMap;

let mut captures = HashMap::new();
assert_eq!(
    Some(&"value4"),
    map.find_and_capture(&["path", "to", "a", "value"], &mut captures)
);

assert_eq!(Some(&"a"), captures.get(&":some"));

Customizing Capture map:

struct Map {
    pub data: [Option<String>; 2],
}

impl Map {
    fn new() -> Self {
        Self { data: [None, None] }
    }
}

use prefix_tree_map::Captures;

impl Captures<&str, &str> for Map {
    fn insert(&mut self, key: &str, value: &str) {
        match key {
            ":user_id" => self.data[0] = Some(value.to_string()),
            ":product_id" => self.data[1] = Some(value.to_string()),
            _ => (),
        }
    }
}

fn capture() {
    use prefix_tree_map::{KeyPart, PrefixTreeMapBuilder};

    let mut builder = PrefixTreeMapBuilder::new();

    builder.insert(
        [
            KeyPart::Exact("user"),
            KeyPart::Wildcard(":user_id"),
            KeyPart::Exact("home"),
        ],
        "user",
    );

    builder.insert(
        [
            KeyPart::Exact("product"),
            KeyPart::Wildcard(":product_id"),
            KeyPart::Exact("info"),
        ],
        "product",
    );

    let map = builder.build();
    let mut captures = Map::new();

    map.find_and_capture(
        &"/user/00000/home".split('/').collect::<Vec<_>>(),
        &mut captures,
    );

    assert_eq!("00000", captures.data[0].as_ref().unwrap());
}

For more infomation, check out examples/router.rs

no_std

Opt out the std feature by disabling default-features in Cargo.toml to remove the Rust standard library dependency.

Examples

Check examples.

License

GNU General Public License v3.0