Crate tetengo_trie

Source
Expand description

§tetengo Trie 1.2.4

A trie library.

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

It also supports prefix searches, allowing you to enumerate values with the same prefix.

The trie in this library is implemented using double arrays.

§How to Use

Execute the cargo add command to add the “tetengo_trie” library 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 for this library are available on GitHub.

Copyright (C) 2023-2024 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§