rsmarisa 0.4.0

Pure Rust port of marisa-trie: a static and space-efficient trie data structure
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

/// Test to verify that Rust marisa produces the same key_id assignments as C++ marisa-trie
///
/// This test verifies that when building a trie with the same test data,
/// both implementations assign the same key_id to each word.

#[test]
fn test_key_id_assignment_matches_cpp() {
    use rsmarisa::{Agent, Keyset, Trie};

    let words = vec![
        "a",
        "app",
        "apple",
        "application",
        "apply",
        "banana",
        "band",
        "bank",
        "can",
        "cat",
        "dog",
        "door",
        "test",
        "testing",
        "trie",
    ];

    // Build trie
    let mut keyset = Keyset::new();
    for word in &words {
        keyset.push_back_str(word).unwrap();
    }

    let mut trie = Trie::new();
    trie.build(&mut keyset, 0);

    // Expected key_id for each word based on C++ marisa-trie output
    // From: LD_LIBRARY_PATH=.../lib/.libs tmp/test_sort_cpp
    // Reverse lookup by key_id:
    //   key_id=0: a
    //   key_id=1: app
    //   key_id=2: banana
    //   key_id=3: band
    //   key_id=4: bank
    //   key_id=5: test
    //   key_id=6: trie
    //   key_id=7: can
    //   key_id=8: cat
    //   key_id=9: dog
    //   key_id=10: door
    //   key_id=11: testing
    //   key_id=12: apple
    //   key_id=13: application
    //   key_id=14: apply
    let expected_key_ids = vec![
        ("a", 0),
        ("app", 1),
        ("apple", 12),
        ("application", 13),
        ("apply", 14),
        ("banana", 2),
        ("band", 3),
        ("bank", 4),
        ("can", 7),
        ("cat", 8),
        ("dog", 9),
        ("door", 10),
        ("test", 5),
        ("testing", 11),
        ("trie", 6),
    ];

    // Verify each word has the expected key_id
    for (word, expected_id) in &expected_key_ids {
        let mut agent = Agent::new();
        agent.set_query_str(word);

        assert!(
            trie.lookup(&mut agent),
            "Word '{}' should be found in trie",
            word
        );

        let actual_id = agent.key().id();
        assert_eq!(
            actual_id, *expected_id,
            "Word '{}' has key_id={}, expected {}",
            word, actual_id, expected_id
        );
    }

    // Verify reverse lookup produces the expected order
    let expected_reverse_order = vec![
        "a",
        "app",
        "banana",
        "band",
        "bank",
        "test",
        "trie",
        "can",
        "cat",
        "dog",
        "door",
        "testing",
        "apple",
        "application",
        "apply",
    ];

    for (key_id, expected_word) in expected_reverse_order.iter().enumerate() {
        let mut agent = Agent::new();
        agent.set_query_id(key_id);
        trie.reverse_lookup(&mut agent);

        let actual_word = std::str::from_utf8(agent.key().as_bytes()).unwrap();
        assert_eq!(
            actual_word, *expected_word,
            "Reverse lookup at key_id={} returned '{}', expected '{}'",
            key_id, actual_word, expected_word
        );
    }
}