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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
use std::collections::HashMap;
use super::{error, Mapping};
/// A prefix tree
pub struct MappingTree {
root: Node,
}
#[derive(Clone)]
pub struct Node {
children: HashMap<char, Node>,
value: Option<Mapping>,
/// The key needed to get to this node
location: String,
}
impl MappingTree {
pub fn new() -> Self {
Self {
root: Node::new(String::new(), None),
}
}
/// Returns the node at the key, otherwise None
pub fn get(&self, key: &str) -> Option<&Node> {
let mut current_node = &self.root;
for ch in key.chars() {
current_node = current_node.children.get(&ch)?
}
Some(current_node)
}
/// Returns the node at the key, otherwise None. The node can be changed
pub fn get_mut(&mut self, key: &str) -> Option<&mut Node> {
let mut current_node = &mut self.root;
for ch in key.chars() {
current_node = current_node.children.get_mut(&ch)?
}
Some(current_node)
}
/// Returns the node at the key, otherwise the last node that matched.
pub fn try_get(&self, key: &str) -> &Node {
let mut current_node = &self.root;
for ch in key.chars() {
if let Some(node) = current_node.children.get(&ch) {
current_node = node;
} else {
return current_node;
}
}
current_node
}
pub fn insert(&mut self, key: &str, mapping: Mapping) -> Result<(), error::Error> {
let node = self.try_get(key).clone();
if node.location.as_str() != key {
let needed_nodes_key = key.trim_start_matches(node.location.as_str());
let needed_nodes_length = needed_nodes_key.chars().count();
let mut current_node = self
.get_mut(&node.location)
.expect("This should always exists");
let mut current_location = node.location.clone();
let mut counter = 0;
for ch in needed_nodes_key.chars() {
current_location.push(ch);
let next_node = if counter == needed_nodes_length {
Node::new(current_location.clone(), Some(mapping.clone()))
} else {
Node::new(current_location.clone(), None)
};
current_node.children.insert(ch, next_node);
current_node = current_node
.children
.get_mut(&ch)
.expect("Was just inserted");
counter += 1;
}
} else {
return Err(error::Error::NodeExits(key.to_owned()));
}
Ok(())
}
}
impl Node {
pub fn new(location: String, mapping: Option<Mapping>) -> Self {
Self {
children: HashMap::new(),
location,
value: mapping,
}
}
}
|
