csc_7b_fc/
avlmap.rs

1//! ## **CSC 7B/FC Rust Assignment 2**
2//!
3//! Study the implementation of the [crate::avltree] module.  Then complete
4//! the implementation of the [AVLMap] data structure, which has a skeleton
5//! in this module.  Some of the functions you will have to define just
6//! involve calling the equivalent function on [avltree::AVLSet], but others
7//! you will have to re-define from scratch, following the sample code in
8//! [crate::avltree], because you will have to separate the key from the value.
9//! A "map" as opposed to a "set" contains [key-value pairs](KVPair). The key
10//! implements the [std::cmp::Ord] and [std::cmp::Eq] traits, but the value
11//! type can be anything.  The tree is ordered and searched by the key.
12//!
13//! Note: `cargo new` your own crate and copy whatever you need into it:
14//! don't try to edit this crate directly.
15//!
16//! **Additional Requirement:** all your functions (and any structs/enums) must
17//! be properly documented using `cargo doc`.
18
19use crate::avltree::Bst::*;
20use crate::avltree::*;
21use std::fmt;
22//use std::cmp::{PartialOrd,PartialEq};
23
24/// A key-value pair:
25pub struct KVPair<KT, VT> {
26    pub key: KT,
27    pub val: VT,
28}
29impl<KT: PartialEq, VT> PartialEq for KVPair<KT, VT> {
30    fn eq(&self, other: &Self) -> bool {
31        &self.key == &other.key
32    }
33}
34impl<KT: Eq, VT> Eq for KVPair<KT, VT> {}
35
36impl<KT: PartialOrd + Eq, VT> PartialOrd for KVPair<KT, VT> {
37    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
38        self.key.partial_cmp(&other.key)
39    }
40}
41impl<KT: Ord + Eq, VT> Ord for KVPair<KT, VT> {
42    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
43        self.key.cmp(&other.key)
44    }
45}
46impl<KT: fmt::Display, VT: fmt::Display> fmt::Display for KVPair<KT, VT> {
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        write!(f, "({} : {})", &self.key, &self.val)
49    }
50}
51
52/// convenient function to create a [KVPair]
53pub fn newpair<K, V>(k: K, v: V) -> KVPair<K, V> {
54    KVPair { key: k, val: v }
55}
56
57/// Wrapper for an AVL "map" (as opposed to "set").  
58/// **Your assignment is to complete the implementation of this class**
59/// by modifying or adding the following methods.
60/// ```   
61///   pub fn insert(&mut self, key:KT, val:VT) -> bool
62///   pub fn get(&self, key:&KT) -> Option<&VT>
63///   pub fn take(&mut self, key:&KT) -> Option<KVPair<KT,VT>> //aka remove
64///   pub fn iter<'lt>(&'lt self) -> InorderIter<'lt,KVPair<KT,VT>>
65///   pub fn successor(&self, key:&KT) -> &Bst<KVPair<KT,VT>>
66///   pub fn predecessor(&self, key:&KT) -> &Bst<KVPair<KT,VT>>
67///   pub fn main()  // demonstrate (this has to be in main.rs)
68/// ```
69/// Study the similar methods in the [crate::avltree] module.
70///
71/// **Additional Hints**
72///
73/// You will have to add some procedures specific to type `Bst<KVPair<KT,VT>>`.
74/// Instead of editing the avltree.rs file, you can do this with another 
75/// "impl" block:
76/// ```
77///   impl<KT:Ord,VT> Bst<KVPair<KT,VT>> {
78///     // add new procedures here
79///   }
80/// ```
81///
82/// Also, it's ok to move an item out of a struct right before the end
83/// of its lifetime (about to be deallocated). Just as an example:
84/// ```
85///   fn f() -> String {
86///     let pair = KVPair{key: String::from("abc"), val:123};
87///     pair.key // Ok because pair won't be needed again
88///   }
89/// ```
90///
91pub struct AVLMap<KT, VT> {
92    inner: AVLSet<KVPair<KT, VT>>,
93}
94impl<KT: Ord + Eq, VT> AVLMap<KT, VT> {
95    /// returns size of map: this I'll do for you because it's easy.
96    pub fn len(&self) -> usize {
97        self.inner.len()
98    }
99
100    /// Some procedures are easy to define: just call the cooresponding
101    /// procedure for avlset:
102    pub fn insert(&mut self, key: KT, val: VT) -> bool {
103        self.inner.add(newpair(key, val))
104    }
105
106    /// Write a procedure to return reference to value associated with
107    /// the key, if it exists.  The supplied dummy procedure returns None.
108    /// This is slightly harder because to you have to distinguish the 
109    /// key from the value.
110    pub fn get(&self, key: &KT) -> Option<&VT> {
111        None
112    } //get
113
114    /// Write a procedure that removes and returns the key-value pair
115    /// associated with the key, if it exists.  The supplied function
116    /// just returns None
117    pub fn take(&mut self, key: &KT) -> Option<KVPair<KT, VT>> {
118        None
119    } //delete
120
121    // add your code here.
122
123    /// Complete the `and_modify` function.  The result of this
124    /// function should be that the map will contain the key (note that it's
125    /// an owned key, not a reference) and the key is associated with the value
126    /// returned by the supplied closure.  The closure is applied to either
127    /// the existing key-value pair, or to None.  The function should return
128    /// the previous key-value pair, if it exists.  If you define this function
129    /// correctly, then the [Self::insert] function can be implemented by
130    /// calling `self.and_modify(key, |_|val).is_none()`.
131    ///
132    /// After you're done with this, don't forget to implement `iter`,
133    /// `successor` and `predecessor`.  Write `main` to demonstrate.
134    pub fn and_modify<F>(&mut self, key: KT, modifier: F) -> Option<KVPair<KT, VT>>
135    where
136        F: FnOnce(Option<&KVPair<KT, VT>>) -> VT,
137    {
138        // write this function
139        None
140    } // treemap.and_modify(key, |vopt|vopt.map(|x|*x+1).unwrap_or(1))
141} //avlmap
csc_7b_fc/avlmap.rs

csc_7b_fc/
avlmap.rs
