Skip to main content

data_structures_lib/
tries.rs

1use std::collections::HashMap;
2
3use crate::Error;
4
5#[derive(Debug, Default)]
6struct TrieNode {
7    children: HashMap<char, TrieNode>,
8    is_end: bool,
9    count: usize,
10}
11
12/// A prefix tree for string storage.
13#[derive(Debug)]
14pub struct Trie {
15    root: TrieNode,
16    len: usize,
17}
18
19impl Trie {
20    /// Creates a new Trie.
21    pub fn new() -> Self {
22        Self {
23            root: TrieNode::default(),
24            len: 0,
25        }
26    }
27
28    /// Inserts a word.
29    pub fn insert(&mut self, word: &str) {
30        let mut node = &mut self.root;
31        for ch in word.chars() {
32            node = node.children.entry(ch).or_default();
33            node.count += 1;
34        }
35        if !node.is_end {
36            self.len += 1;
37            node.is_end = true;
38        }
39    }
40
41    /// Returns true if the word is in the trie.
42    pub fn search(&self, word: &str) -> bool {
43        self.find(word)
44            .map(|node| node.is_end)
45            .unwrap_or(false)
46    }
47
48    /// Returns true if any word starts with the prefix.
49    pub fn starts_with(&self, prefix: &str) -> bool {
50        self.find(prefix).is_some()
51    }
52
53    fn find(&self, word: &str) -> Option<&TrieNode> {
54        let mut node = &self.root;
55        for ch in word.chars() {
56            match node.children.get(&ch) {
57                Some(next) => node = next,
58                None => return None,
59            }
60        }
61        Some(node)
62    }
63
64    /// Deletes a word.
65    pub fn delete(&mut self, word: &str) -> Result<(), Error> {
66        if !self.search(word) {
67            return Err(Error::NotFound);
68        }
69        Self::delete_node(&mut self.root, word, 0);
70        self.len -= 1;
71        Ok(())
72    }
73
74    fn delete_node(node: &mut TrieNode, word: &str, index: usize) {
75        if index == word.chars().count() {
76            node.is_end = false;
77            return;
78        }
79        let ch = word.chars().nth(index).unwrap();
80        if let Some(child) = node.children.get_mut(&ch) {
81            Self::delete_node(child, word, index + 1);
82            child.count -= 1;
83            if child.count == 0 {
84                node.children.remove(&ch);
85            }
86        }
87    }
88
89    /// Returns all words with the given prefix.
90    pub fn words(&self, prefix: &str) -> Vec<String> {
91        let node = if prefix.is_empty() {
92            &self.root
93        } else {
94            match self.find(prefix) {
95                Some(n) => n,
96                None => return Vec::new(),
97            }
98        };
99        let mut result = Vec::new();
100        let mut current = prefix.to_string();
101        Self::collect(node, &mut current, &mut result);
102        result
103    }
104
105    fn collect(node: &TrieNode, prefix: &mut String, result: &mut Vec<String>) {
106        if node.is_end {
107            result.push(prefix.clone());
108        }
109        for (ch, child) in &node.children {
110            prefix.push(*ch);
111            Self::collect(child, prefix, result);
112            prefix.pop();
113        }
114    }
115
116    /// Returns the number of words.
117    pub fn len(&self) -> usize {
118        self.len
119    }
120
121    /// Returns true if the trie is empty.
122    pub fn is_empty(&self) -> bool {
123        self.len == 0
124    }
125}
126
127impl Default for Trie {
128    fn default() -> Self {
129        Self::new()
130    }
131}