plain_trie

Crates.ioplain_trie
lib.rsplain_trie
version
sourcesrc
created_at2024-07-21 21:49:26.111896
updated_at2024-12-05 00:34:37.824007
descriptionClassic trie implementation capable of mapping any T to char iterator.
homepagehttps://github.com/bravequickcleverfibreyarn/tries/tree/main/trie
repositoryhttps://github.com/bravequickcleverfibreyarn/tries/tree/main/trie
max_upload_size
id1310600
Cargo.toml error:TOML parse error at line 18, column 1 | 18 | autolib = false | ^^^^^^^ unknown field `autolib`, expected one of `name`, `version`, `edition`, `authors`, `description`, `readme`, `license`, `repository`, `homepage`, `documentation`, `build`, `resolver`, `links`, `default-run`, `default_dash_run`, `rust-version`, `rust_dash_version`, `rust_version`, `license-file`, `license_dash_file`, `license_file`, `licenseFile`, `license_capital_file`, `forced-target`, `forced_dash_target`, `autobins`, `autotests`, `autoexamples`, `autobenches`, `publish`, `metadata`, `keywords`, `categories`, `exclude`, `include`
size0
boldswiftsmartfiberhank (bravequickcleverfibreyarn)

documentation

https://docs.rs/plain_trie/latest/plain_trie/index.html

README

(plain) trie

  • plain trie is classic retrieval tree implementation with fixed size alphabet per node
  • allows to use any impl Iterator<Item = char> type as key
  • oob support for English small letters only
  • all methods with classic trie asymptotic computational complexity
  • customizable alphabet support

basic usage

let mut trie = Trie::new();
let key = || "oomph".chars();
let val = 333;

_ = trie.ins(key(), val);
match trie.acq(key()) {
    AcqRes::Ok(v) => assert_eq!(&val, v),
    _ => panic!("Expected AcqRes::Ok(_).")
}

let val = 444;
_ = trie.ins(key(), val);
match trie.acq(key()) {
    AcqRes::Ok(v) => assert_eq!(&val, v),
    _ => panic!("Expected AcqRes::Ok(_).")
}

let catch = catch_unwind(move|| _ = trie.ins("A".chars(), 0));
assert!(catch.is_err());

custom alphabet implementation

  • use Trie::new_with in conjunction with implementation for char-index conversion function and apposite alphabet length

  • example bellow shows sample implementation for alphabet extended with capital letters

use plain_trie::{AcqRes, RemRes, Trie};

const ALPHABET_LEN: u32 = 52;

fn ix(c: char) -> usize {
    let big_a = u32::from('A');
    let big_z = u32::from('Z');

    let sma_a = u32::from('a');
    let sma_z = u32::from('z');

    let cod_poi = u32::from(c);
    (match cod_poi {
        c if c >= big_a && c <= big_z => c - big_a,
        c if c >= sma_a && c <= sma_z => c - sma_a + ALPHABET_LEN / 2,
        _ => {
            panic!("Index conversion impossible.")
        }
    }) as usize
}

#[test]
fn test() {
    let mut trie = Trie::new_with(ix, ALPHABET_LEN as usize);

    let kv_1 = ("AZ", 1);
    let kv_2 = ("az", 2);

    for kv in [kv_1, kv_2] {
        let res = trie.ins(kv.0.chars(), kv.1);
        assert_eq!(true, res.is_ok());
    }

    for kv in [kv_1, kv_2] {
        let res = trie.acq(kv.0.chars());
        assert_eq!(AcqRes::Ok(&kv.1), res);
    }

    for kv in [kv_1, kv_2] {
        let res = trie.rem(kv.0.chars());
        assert_eq!(RemRes::Ok(kv.1), res);
    }
}
Commit count: 0

cargo fmt