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

/// Test that Key sorting produces the same order as C++ marisa-trie

#[test]
fn test_key_sort_order() {
    use rsmarisa::grimoire::algorithm::sort;
    use rsmarisa::grimoire::trie::key::Key;
    use rsmarisa::grimoire::vector::vector::Vector;

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

    println!("Original order:");
    for (i, word) in words.iter().enumerate() {
        println!("  {:2}: {}", i, word);
    }
    println!();

    // Create Keys like C++ does
    let mut keys: Vector<Key> = Vector::new();
    keys.resize(words.len(), Key::new());
    for (i, word) in words.iter().enumerate() {
        keys[i].set_str(word.as_bytes());
        keys[i].set_id(i);
    }

    // Sort
    let keys_slice = keys.as_mut_slice();
    let num_unique = sort::sort(keys_slice);

    println!("After sorting ({} unique):", num_unique);
    for (i, key) in keys_slice.iter().enumerate() {
        let word = std::str::from_utf8(key.as_bytes()).unwrap();
        println!("  {:2}: {} (id={})", i, word, key.id());
    }
    println!();

    // Expected order from C++ (lexicographically sorted forward strings):
    // a, app, apple, application, apply, banana, band, bank, can, cat, dog, door, test, testing, trie
    let expected_sorted_order = vec![
        "a",
        "app",
        "apple",
        "application",
        "apply",
        "banana",
        "band",
        "bank",
        "can",
        "cat",
        "dog",
        "door",
        "test",
        "testing",
        "trie",
    ];

    println!("Expected order (lexicographic):");
    for (i, word) in expected_sorted_order.iter().enumerate() {
        println!("  {:2}: {}", i, word);
    }
    println!();

    // Verify
    for (i, expected_word) in expected_sorted_order.iter().enumerate() {
        let actual_word = std::str::from_utf8(keys_slice[i].as_bytes()).unwrap();
        assert_eq!(
            actual_word, *expected_word,
            "Position {}: expected '{}', got '{}'",
            i, expected_word, actual_word
        );
    }

    println!("✓ Key sorting matches expected lexicographic order");
}