data_structures_lib/
tries.rs1use 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#[derive(Debug)]
14pub struct Trie {
15 root: TrieNode,
16 len: usize,
17}
18
19impl Trie {
20 pub fn new() -> Self {
22 Self {
23 root: TrieNode::default(),
24 len: 0,
25 }
26 }
27
28 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 pub fn search(&self, word: &str) -> bool {
43 self.find(word)
44 .map(|node| node.is_end)
45 .unwrap_or(false)
46 }
47
48 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 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 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 pub fn len(&self) -> usize {
118 self.len
119 }
120
121 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}