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
use std::cmp::Ordering::{Equal, Greater, Less};
use crate::{stc::Node, KEY_ARRAY};
impl<K: Ord, V> Node<K, V> {
pub fn replace(&mut self, key: &K, value: V) -> Option<V> {
'search: for (index, item) in self.keys.iter_mut().enumerate() {
match item {
Some(item) => match key.cmp(&item.key) {
Less => {
if let Some(pointer) = self.pointers[index].as_mut() {
return pointer.child.replace(key, value);
} else {
return None;
}
}
Equal => {
return Some(std::mem::replace(&mut item.value, value));
}
Greater => {
if index >= KEY_ARRAY - 1 {
if let Some(pointer) = self.pointers[index + 1].as_mut() {
return pointer.child.replace(key, value);
} else {
return None;
}
} else {
continue 'search;
}
}
},
None => {
if let Some(pointer) = self.pointers[index].as_mut() {
return pointer.child.replace(key, value);
} else {
return None;
}
}
}
}
None
}
}
impl<K, V: Copy> Node<K, V> {
pub fn replace_from_index(&mut self, mut index: usize, value: V) -> Option<V> {
if self.leaf {
if let Some(item) = self.keys[index].as_mut() {
let removed_value = Some(item.value);
item.value = value;
removed_value
} else {
None
}
} else {
for (loc, pointer) in self.pointers.iter_mut().enumerate() {
match pointer {
Some(pointer) => {
if index < pointer.counter {
return pointer.child.replace_from_index(index, value);
} else {
index -= pointer.counter
};
if index == 0 {
if let Some(item) = self.keys[loc].as_mut() {
let removed_value = Some(item.value);
item.value = value;
return removed_value;
} else {
return None;
}
} else {
index -= 1;
continue;
}
}
None => continue,
}
}
None
}
}
}