ECE 522 | Software Construction, Verification and Evolution
Question 3: Consider the following code:
use std::collections::HashMap;
#[derive(Debug)]
struct TrieNode {
chs: HashMap,
value: Option,
}
#[derive(Debug)]
struct Trie {
root: TrieNode,
}
impl Trie {
fn new() -> Trie {
Trie {
root: TrieNode {
chs: HashMap::new(),
value: None,
},
}
}
fn add_string(&mut self, string: String, value: i32) {
let mut current_node = &mut self.root;
for c in string.chars() {
current_node = current_node.chs
.entry(c)
.or_insert(TrieNode {
chs: HashMap::new(),
value: None,
});
}
current_node.value = Some(value);
}
}
fn main() {
let mut trie = Trie::new();
trie.add_string("B".to_string(), 1);
trie.add_string("Bar".to_string(), 2);
println!("{:#?}", trie);
}
2
ECE 522 | Software Construction, Verification and Evolution
The above code implements a Trie
(https://docs.rs/radix_trie/0.0.9/radix_trie/struct.Trie.html#method.len) which is a data-structure for
storing and querying string-like keys and associated values.
a- Add your own implementation for length(&self)->usize that returns the number of elements
stored in the trie.
b- Add your own implementation for iter(&self) -> Vec<(char, Option)> which returns an
iterator over the keys and values of the Trie.
c- Add your own implementation for find(&self, key: &String) -> Option<&TrieNode> which
searches the Trie for a given key and returns a reference to that key’s corresponding node if
found.
d- Add your own implementation for delete(&mut self, key: &String) -> Option to remove a
key (from a Trie) and returns the value corresponding to that key.