prefixtreemap

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

```rust use prefixtreemap::PrefixTreeMapBuilder;

let mut map_builder = PrefixTreeMapBuilder::new();

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

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

// To insert an key path with wildcards, mark key parts using prefix_tree_map::KeyPart and call insert() use prefixtreemap::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"; mapbuilder.insertexact(path.split('/'), "value3");

let anothorpath = "path/to/:some/value"; mapbuilder.insert( anothorpath.split('/').map(|part| { if part.startswith(':') { 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 asserteq!( Some(&"value3"), map.findexact(&["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(); asserteq!( Some(&"value4"), map.findand_capture(&["path", "to", "a", "value"], &mut captures) );

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

Customizing Capture map: ```rust struct Map { pub data: [Option; 2], }

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

use prefixtreemap::CaptureMap;

impl CaptureMap<&str, &str> for Map { fn insert(&mut self, key: &str, value: &str) { match key { ":userid" => self.data[0] = Some(value.tostring()), ":productid" => self.data[1] = Some(value.tostring()), _ => (), } }

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 prefixtreemap::{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