prefix_tree_map

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

Design

Trie is a good data structure for storing key-value pairs with wildcard support ability.

This prefix tree map implementation supports any type of key and value, as long as key parts are implemented the Ord and Clone trait. Internally, nodes are stored in a sorted Vec. So technically it can achieve O(log n) time complexity on finding every node by using binary search on the sorted Vec.

Using as a route-table-like structure could be the best scenario for this crate.

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 Clone trait.
• Capture Map Customization - Customize the way key parts captured by wildcard stored.
• No recursion in find operations - Rather than store the whole context of every node searching, this prefix tree map only store those tiny wildcard node pointers for backtracking on heap.

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 iterating the whole Binary Heap. Once the build() is called, Binary Heaps are converted into sorted Vecs. We can't push any item to the Vec without a whole sort operation.
• Currently, a single wildcard cannot be matched more than one time. It means word can 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::CaptureMap;

impl CaptureMap<&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 remove(&mut self, key: &&str) {
        match key {
            &":user_id" => self.data[0] = None,
            &":product_id" => self.data[1] = None,
            _ => (),
        }
    }

    fn clear(&mut self) {
        self.data = [None, None];
    }
}

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

Examples

Check examples.

License

GNU General Public License v3.0