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

dsa_rust/associative/
avl_tree_map.rs
