Crate tetengo_trie

source ·
Expand description

tetengo Trie 1.0.0

A trie library.

The trie is an associative data structure. Given a key, it returns the corresponding value in constant time.

The trie is also able to perform a prefix search. It has a method to enumerate the values with the same prefix.

The trie of this library is implemented with double arrays.

How to Use

Execute the cargo add command to add the library “tetengo_trie” to your cargo package.

An entry for “tetengo_trie” will be added to the “dependencies” section of Cargo.toml.

  • On Windows 
    • X:>cd \path\to\your\package
X:>cargo add tetengo_trie
  • On Linux 
    • $ cd /path/to/your/package
$ cargo add tetengo_trie

See the cargo document for details.

Source Files

The source files of this library are available on GitHub.

Copyright (C) 2023 kaoru https://www.tetengo.org/

This product is released under the MIT license. See the LICENSE file for details.

Examples

mod usage {
    use std::cell::RefCell;
    use tetengo_trie::{BuldingObserverSet, Serializer, StrSerializer, Trie};

    #[test]
    fn usage() {
        // Prepares a trie building observer set.
        // The observer set records the inserted keys and the end.
        let building_observer_reports = RefCell::<Vec<String>>::new(Vec::new());
        let mut adding = |key: &[u8]| {
            building_observer_reports
                .borrow_mut()
                .push(String::from_utf8(key.to_vec()).unwrap());
        };
        let mut done = || {
            building_observer_reports
                .borrow_mut()
                .push("DONE".to_string());
        };
        let mut building_observer_set = BuldingObserverSet::new(&mut adding, &mut done);

        // Builds a trie with initial elements.
        let trie = Trie::<&str, i32>::builder()
            .elements(
                [
                    ("tasakibashi", -5),
                    ("nihongiguchi", -3),
                    ("kumamotoekimae", 0),
                    ("gionbashi", 5),
                    ("gofukumachi", 10),
                    ("kawaramachi", 14),
                    ("keitokukoumae", 18),
                    ("karashimachou", 22),
                ]
                .to_vec(),
            )
            .key_serializer(StrSerializer::new(true))
            .build_with_observer_set(&mut building_observer_set)
            .unwrap();
        let stored_keys = &*building_observer_reports.borrow();
        let expected = [
            "gionbashi".to_string(),
            "gofukumachi".to_string(),
            "karashimachou".to_string(),
            "kawaramachi".to_string(),
            "keitokukoumae".to_string(),
            "kumamotoekimae".to_string(),
            "nihongiguchi".to_string(),
            "tasakibashi".to_string(),
            "DONE".to_string(),
        ]
        .to_vec();
        assert_eq!(stored_keys, &expected);

        // Searches the trie.
        // If a perfect-matching key is found, its value is returned.
        let found_for_gionbashi = trie.find("gionbashi").unwrap().unwrap();
        assert_eq!(*found_for_gionbashi, 5);

        // If not found, None is returned.
        let found_for_hanabatachou = trie.find("hanabatachou").unwrap();
        assert!(found_for_hanabatachou.is_none());

        // Creates a subtrie consisting of the elements with the common key prefix.
        let subtrie = trie.subtrie("ka").unwrap().unwrap();

        // Enumerates the values in the subtrie.
        let subtrie_values = subtrie.iter().map(|v| *v).collect::<Vec<_>>();
        assert_eq!(
            subtrie_values,
            [
                22, // karashimachou
                14, // kawaramachi
            ]
            .to_vec()
        );
    }
}

Re-exports

Modules