libdawg 1.0.0

A fast, memory-efficient DAWG (Directed Acyclic Word Graph) for word validation and prefix queries
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

/// DAWG builder module for constructing wordlists from sorted word lists.
pub mod builder;
/// Trait for types that can serve as DAWG edge labels.
pub mod char_trait;
/// DAWG node and children module containing the core graph data structures.
pub mod children;
/// Internal chunked arena allocator.
pub(crate) mod node_arena;
/// Owned DAWG that manages its own arena internally.
pub mod owned;

pub use builder::IntoWord;
pub use char_trait::DawgChar;
pub use children::DawgNode;

/// Re-export `typed_arena::Arena` for use with the arena-based API.
#[cfg(feature = "arena")]
pub use typed_arena::Arena;

#[cfg(test)]
#[cfg(feature = "arena")]
mod test {
    use super::builder::build_dawg;
    use std::fs::File;
    use std::io::{BufRead, BufReader};
    use typed_arena::Arena;

    fn is_word<'w>(root: &'w super::DawgNode<'w, char>, word: &str) -> bool {
        word.chars()
            .try_fold(root, |n, ch| n.get(ch))
            .is_some_and(|n| n.is_word())
    }

    #[test]
    fn all_words() {
        let dict_filename = "../dict-sv.txt";
        let file = File::open(dict_filename).unwrap();
        let words: Vec<String> = BufReader::new(file)
            .lines()
            .map(|l| l.unwrap())
            .filter(|w| !w.is_empty() && !w.starts_with('#'))
            .collect();
        let arena = Arena::new();
        let root = build_dawg(&arena, &words).unwrap();
        for word in &words {
            assert!(is_word(root, word), "{}", word);
        }
        // test some non-words
        assert!(!is_word(root, "URSINN"));
        assert!(!is_word(root, "URSINNESS"));
        assert!(!is_word(root, "ÅTMINSTON"));
        assert!(!is_word(root, "ÅTMINSTONDE"));
    }

    #[test]
    fn add_word() {
        let words = ["TEST", "TESTER", "WTEST"];
        let arena = Arena::new();
        let root = build_dawg(&arena, words).unwrap();

        let n = root.get('T').unwrap();
        assert!(!n.is_word());

        let n = n.get('E').unwrap();
        assert!(!n.is_word());

        let n = n.get('S').unwrap();
        assert!(!n.is_word());

        let n = n.get('T').unwrap();
        assert!(n.is_word());

        let n = n.get('E').unwrap();
        assert!(!n.is_word());

        let n = n.get('R').unwrap();
        assert!(n.is_word());

        let n = n.get('T');
        assert_eq!(n, None);
    }
}