dsa_rust/associative/
avl_tree_map.rs

1/*! A proper sorted map
2
3# About
4This sorted map uses the library's [AVL tree]() as its backing structure, providing _O(log(n))_ search, insert, and delete operations.
5
6# Example
7
8```rust
9    use dsa_rust::associative::avl_tree_map::TreeMap;
10
11    let text = "and the final paragraph clearly came from the heart, 
12    or whatever cool yet sensitive organ Sadie kept in place of one.";
13
14    let mut map = TreeMap::<char, usize>::new();
15
16    // SAFETY: This is a thing
17    unsafe {}
18
19    for e in text.chars() {
20        if map.contains(e) {
21            let old = map.remove(e).unwrap();
22            map.put(e, old.value() + 1);
23        } else {
24            map.put(e, 1);
25        }
26    }
27    println!("TreeMap character occurrence");
28    for e in map.iter() {
29        println!("{e:?}");
30    }
31
32    println!("\nTreeMap vowel occurrence");
33    for vowel in ['a', 'e', 'i', 'o', 'u', 'y'] {
34        eprintln!("{vowel}: {}", map.get(vowel).unwrap_or(&0));
35    }
36
37```
38
39```text
40TreeMap character occurrence
41('\n', 1)
42(' ', 24)
43(',', 1)
44('.', 1)
45('S', 1)
46('a', 12)
47('c', 4)
48('d', 2)
49('e', 14)
50('f', 3)
51('g', 2)
52('h', 5)
53('i', 5)
54('k', 1)
55('l', 5)
56('m', 2)
57('n', 6)
58('o', 7)
59('p', 4)
60('r', 8)
61('s', 2)
62('t', 7)
63('v', 2)
64('w', 1)
65('y', 2)
66
67TreeMap vowel occurrence
68a: 12
69e: 14
70i: 5
71o: 7
72u: 0
73y: 2
74```
75
76*/
77
78use crate::hierarchies::avl_tree::AVLTree;
79
80use std::fmt::Debug;
81use std::cmp::Ordering;
82use std::borrow::Borrow;
83
84/// The wrapper struct that allows TreeMap<K, V> to use AVLTree<T>. 
85/// Because `T` is [Ord], Entry<K, V> must implement [Eq] and [PartialOrd], 
86/// which themselves must implement [PartialEq]. 
87/// All traits use `key` for ordering.
88/// 
89/// See the [module-level documentation]() for more details.
90#[derive(Debug)]
91pub struct Entry<K, V> {
92    key: K,
93    value: V,
94}
95impl<K, V> Entry<K, V> {
96    pub fn key(&self) -> &K {
97        &self.key
98    }
99
100    pub fn value(&self) -> &V {
101        &self.value
102    }
103}
104impl<K: PartialEq, V> PartialEq for Entry<K, V> {
105    fn eq(&self, other: &Self) -> bool {
106        self.key == other.key
107    }
108}
109// Eq requires PartialEq
110impl<K: Eq, V> Eq for Entry<K, V> {}
111// PartialOrd requires PartialEq
112impl<K: PartialOrd, V> PartialOrd for Entry<K, V> {
113    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
114        self.key.partial_cmp(&other.key)
115    }
116}
117// Ord requires Eq + PartialOrd
118impl<K: Ord, V> Ord for Entry<K, V> {
119    fn cmp(&self, other: &Self) -> Ordering {
120        self.key.cmp(&other.key)
121    }
122}
123impl<K, V> Borrow<K> for Entry<K, V> {
124    fn borrow(&self) -> &K {
125        &self.key
126    }
127}
128
129/// 
130/// 
131/// See the [module-level documentation]() for more details.
132#[derive(Debug)]
133pub struct TreeMap<K, V> {
134    tree: AVLTree<Entry<K, V>>,
135    size: usize
136}
137impl<K, V> Default for TreeMap<K, V>
138where
139    K: Default + Eq + Ord + PartialEq,
140 {
141    fn default() -> Self {
142        Self::new()
143    }
144}
145impl<K, V> TreeMap<K, V> 
146where
147    K: Default + Eq + Ord + PartialEq,
148{
149    /// Constructor
150    pub fn new() -> Self {
151        Self {
152            tree: AVLTree::<Entry<K, V>>::new(),
153            size: 0
154        }
155    }
156
157    /// Returns the number of elements in the map.
158    pub fn size(&self) -> usize {
159        self.size
160    }
161
162    /// Returns `true` if the map contains an entry associated with the given key.
163    pub fn contains(&self, key: K) -> bool {
164        self.tree.contains(&key)
165    }
166
167    /// Returns the value associated with the key, if `Some`.
168    pub fn get(&self, key: K) -> Option<&V> {
169        if let Some(val) = self.tree.get_node(&key) {
170            return Some(&val.value)
171        } None
172    }
173
174    /// Inserts the entry into the map. If the key already exists, removes
175    /// and returns the old entry and inserts a new one. This allows for
176    /// situations where keys are `==` without being _identical_.
177    pub fn put(&mut self, key: K, value: V) -> Option<Entry<K, V>> {
178        let new_entry = Entry { key, value };
179        let old_entry = self.tree.remove(&new_entry.key);
180        self.tree.insert(new_entry);
181        if old_entry.is_none() {
182            self.size += 1;
183        }
184        old_entry
185    }
186
187    /// Mutates
188    pub fn mut_val_or() {}
189
190    /// Removes and returns the entry associated with the key:value pair, 
191    /// if it exists in the map.
192    pub fn remove(&mut self, key: K) -> Option<Entry<K, V>> {
193        if self.tree.contains(&key) {
194            self.size -= 1;
195            return self.tree.remove(&key)
196        } None
197    }
198
199    /// Returns an iterator over borrowed values. The resulting values
200    /// appear in sorted order.
201    ///
202    /// Example use:
203    /// ```rust
204    /// use dsa_rust::associative::probing_hash_table::HashMap;
205    /// let mut count: HashMap<char, u8> = HashMap::new();
206    /// let mut v = Vec::new();
207    /// for e in count.iter() {
208    ///     v.push(*e.0);
209    /// }
210    /// ```
211    pub fn iter(&self) -> Iter<'_, K, V> {
212        Iter {
213            iter: self.tree.iter(),
214        }
215    }
216
217}
218
219pub struct Iter<'a, K, V> {
220    //iter: std::slice::Iter<'a, Option<Entry<K, V>>>,
221    iter: crate::hierarchies::avl_tree::InOrderIter<'a, crate::associative::avl_tree_map::Entry<K, V>>
222}
223impl<'a, K, V> Iterator for Iter<'a, K, V>
224where
225    K: Debug + PartialEq,
226    V: PartialEq,
227{
228    type Item = (&'a K, &'a V);
229
230    fn next(&mut self) -> Option<Self::Item> {
231        self.iter.next().map(|entry| (&entry.key, &entry.value))
232    }
233}
234
235#[test]
236// Generic type test
237fn avl_tree_map_test() {
238    //Creates a new hash map
239    let mut map = TreeMap::<&str, u8>::new();
240
241    assert_eq!(map.size(), 0);
242
243    // Illustrates that put() and get() work
244    map.put("Peter", 40);
245    assert_eq!(map.size(), 1);
246
247    // Illustrates that the map grows correctly
248    map.put("Brain", 39); // Grows the map
249    map.put("Remus", 22);
250    map.put("Bobson", 36); // Grows the map
251    map.put("Dingus", 18);
252    map.put("Dangus", 27); // Grows the map
253    assert_eq!(map.size(), 6);
254
255    // Underlying tree arena check
256    eprintln!("Initial state");
257    assert_eq!(map.tree.arena.len(), 6);
258    for e in map.tree.arena.iter() {
259        eprintln!("{e:?}")
260    }
261
262    // Illustrates that contains() works as intended
263    assert!(map.contains("Dingus"));
264
265    // Illustrates that put() returns old values and
266    // overwrites existing values upon collision...
267    let old = map.put("Peter", 41).unwrap();
268    assert_eq!(old.value, 40_u8);
269    let new_val = map.get("Peter").unwrap();
270    assert_eq!(*new_val, 41);
271    assert_eq!(map.size(), 6);
272
273    // Underlying tree arena check
274    eprintln!("After replacement");
275    assert_eq!(map.tree.arena.len(), 7);
276    for e in map.tree.arena.iter() {
277        eprintln!("{e:?}")
278    }
279
280    // Illustrates that removes entries by key and returns the value
281    assert!(map.contains("Dangus"));
282    let removed = map.remove("Dangus").unwrap();
283    assert_eq!(map.size(), 5);
284
285    // Underlying tree arena check
286    eprintln!("After removal");
287    assert_eq!(map.tree.arena.len(), 7);
288    for e in map.tree.arena.iter() {
289        eprintln!("{e:?}")
290    }
291
292    //assert_eq!(removed.key(), &"Dangus");
293    //assert_eq!(removed.value(), &27);
294    assert_eq!(removed.key, "Dangus");
295    assert_eq!(removed.value, 27);
296    assert!(!map.contains("Dangus"));
297
298    eprintln!("{map:#?}");
299
300    //panic!("MANUAL TEST FAILURE");
301}
302//
303//#[test]
304// //Tests the custom update value function
305//fn mut_val_test() {
306//    //Creates a new hash map
307//    let mut count = HashMap::<char, u8>::new();
308//    let phrase: &str = "Hello, sickos";
309//
310//    // Seeds the map with just the characters and a default value
311//    for char in phrase.chars() {
312//        count.put(char, 0);
313//    }
314//
315//    eprintln!("\nInitial state:");
316//    count.contents();
317//
318//    // Iterates through the map again, updating each value based on its occurence
319//    // NOTE: Can also be used as initial mapping operation with the same code, 
320//    // but was split here for illustrative purposes
321//    for char in phrase.chars() {
322//        count.mut_val_or(char, |x| *x += 1, 1);
323//    }
324//
325//    // Pretty-prints the contents of the map
326//    eprintln!("\nModified:");
327//    count.contents();
328//
329//    // Uncomment to trigger debug print
330//    //assert!(count.is_empty());
331//}
332//
333#[test]
334// Tests that the structure is iterable
335fn iter_test() {
336    //Creates a new hash map of the frequence letters in the given phrase
337    let mut map = TreeMap::<usize, char>::new();
338    for (index, char) in "acbjfed".chars().enumerate() {
339        map.put(index, char); // index is key, char is value
340    }
341
342    // Indicates that the map is indeed sorted
343    eprintln!("\nSorted map:");
344    for e in map.tree.iter() {
345        eprintln!("{e:?}")
346    }
347
348    // Prints only the middle values based on key range
349    // which should be "b, j, f, e"
350    eprintln!("\nPrint values for indexes 2..=5:");
351    for e in 2..=5 {
352        let val = map.get(e).unwrap();
353        eprintln!("{val:?}");
354    }
355
356    //let text = "Not the most elegant text, but it sure 
357    //    does the trick when you need it. I could go on and on and on, 
358    //but instead Id rather just let the text explain itself in order to Illustrate
359    //    what this test is all about. Then again Im not sure I could do this without
360    //    just a little rambling, amirite? You're the kind of person that
361    //    gets it, I think.";
362
363    let text = "and the final paragraph clearly came from the heart, 
364    or whatever cool yet sensitive organ Sadie kept in place of one.";
365
366    // Establishes parity with the std BTreeMap
367    //let mut map = std::collections::BTreeMap::<char, usize>::new();
368    //for e in text.chars() {
369    //    if map.contains_key(&e) {
370    //        let old = map.remove(&e).unwrap();
371    //        map.insert(e, old + 1);
372    //    } else {
373    //        map.insert(e, 1);
374    //    }
375    //}
376    //eprintln!("\nBTreeMap character occurrence");
377    //for e in map.iter() {
378    //    eprintln!("{e:?}");
379    //}
380
381    // Second attempt with custom TreeMap
382    let mut map = TreeMap::<char, usize>::new();
383    for e in text.chars() {
384        if map.contains(e) {
385            let old = map.remove(e).unwrap();
386            map.put(e, old.value + 1);
387        } else {
388            map.put(e, 1);
389        }
390    }
391    eprintln!("\nTreeMap character occurrence");
392
393    //for e in map.tree.iter() {
394    //    eprintln!("({:?}, {})", e.key, e.value);
395    //}
396    for e in map.iter() {
397        eprintln!("{e:?}");
398    }
399
400    eprintln!("\nTreeMap vowel occurrence");
401    for vowel in ['a', 'e', 'i', 'o', 'u', 'y'] {
402        eprintln!("{vowel}: {}", map.get(vowel).unwrap_or(&0));
403    }
404    eprintln!("\nTreeMap occurrence of characters in my name");
405    for vowel in ['p', 'e', 't', 'r'] {
406        eprintln!("{vowel}: {}", map.get(vowel).unwrap_or(&0));
407    }
408
409    // Uncomment to trigger debug print
410    //panic!("MANUAL TEST FAILURE");
411}
dsa_rust/associative/avl_tree_map.rs

dsa_rust/associative/
avl_tree_map.rs
