b_trees/map/
mod.rs

1use crate::{AVL, Pair};
2
3pub struct BTreeMap<A, B> {
4    avl: AVL<Pair<A, B>>,
5}
6
7impl<K, V> BTreeMap<K, V> {
8    pub fn new() -> Self {
9        Self { avl: AVL::new() }
10    }
11}
12
13impl<K: Ord, V> BTreeMap<K, V> {
14    pub fn contains_key(&self, key: &K) -> bool {
15        self.avl.root.as_ref().map(|v| v.contains_by(|en| key.cmp(&en.key))).unwrap_or(false)
16    }
17
18    pub fn get(&self, key: &K) -> Option<&V> {
19        self.avl.root.as_ref().map(|v| v.get_by(|en| key.cmp(&en.key))).unwrap_or(None).map(|v| &v.val)
20    }
21
22    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
23        self.avl.root.as_mut().map(|v| v.get_mut_by(|en| key.cmp(&en.key))).unwrap_or(None).map(|v| &mut v.val)
24    }
25
26    pub fn insert(&mut self, key: K, val: V) -> bool {
27        let entry = Pair { key, val };
28        self.avl.insert_distinct(entry)
29    }
30
31    pub fn len(&self) -> usize {
32        self.avl.len()
33    }
34
35    pub fn iter(&self) -> impl Iterator<Item = &Pair<K, V>> {
36        self.avl.increasing()
37    }
38
39    pub fn into_iter(self) -> impl Iterator<Item = Pair<K, V>> {
40        self.avl.into_increasing()
41    }
42
43    pub fn keys(&self) -> impl Iterator<Item = &K> {
44        self.avl.increasing().map(|v| &v.key)
45    }
46
47    pub fn values(&self) -> impl Iterator<Item = &V> {
48        self.avl.increasing().map(|v| &v.val)
49    }
50
51    pub fn into_keys(self) -> impl Iterator<Item = K> {
52        self.avl.into_increasing().map(|v| v.key)
53    }
54
55    pub fn into_values(self) -> impl Iterator<Item = V> {
56        self.avl.into_increasing().map(|v| v.val)
57    }
58
59    pub fn increasing(&self) -> impl Iterator<Item = &Pair<K, V>> {
60        self.avl.increasing()
61    }
62
63    pub fn decreasing(&self) -> impl Iterator<Item = &Pair<K, V>> {
64        self.avl.decreasing()
65    }
66}
b_trees/map/mod.rs

b_trees/map/
mod.rs
