csc_7b_fc/
bijectivemap.rs

1//! Skeleton module for the bijective hashmap assignment.
2//!
3//! Be sure to read the assignment description in the
4//! **[C++ version](https://github.com/chuckcscccl/csc_7b_fc/blob/main/src/bijectivemap.cpp)** of this
5//! program that you're supposed to emulate.
6//!
7//! This module currently compiles and provides you with some helpful code,
8//! but there are four methods that you must implement properly
9//! (see documentation for each [BijectiveMap] method).
10//!
11//! Go into the `csc_7b_fc` crate and `git pull` the latest updates.  Then
12//! `cargo new` a fresh crate for your assignment and optionally add the `path` to
13//! `csc_7b_fc` to Cargo.toml as you did for the first Rust assignment.
14//!
15//! Do not touch the `csc_7b_fc` crate.  Copy the `bijectivemap.rs` file
16//! to the src directory of your own crate, then
17//! place the following in the main.rs of your crate.
18//! ```
19//!    mod bijectivemap;
20//!    use bijectivemap::*;
21//! ```
22//!
23//! **NOTE: DO NOT EDIT THE csc_7b_fc CRATE. Copy the skeleton code to
24//!       your own crate!**
25//!
26//! When you have completed the implementation, emulate the main in the
27//! C++ program to test it.  It can begin with ...
28//!```
29//!    let mut daynum:BijectiveMap<&'static str,u8> = BijectiveMap::new();
30//!    let days = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"];
31//!    for i in 0..days.len() { daynum.set(days[i],(i+1) as u8); }
32//!    daynum.get_by_key(&"Wednesday").map(|d|{
33//!      println!("Wednesday is day {}",d);
34//!    });
35//!```
36//!The `studenthasher` component that tests hash collisions is optional.
37//!
38#![allow(unused_mut)]
39use std::collections::{hash_map::RandomState, HashMap};
40use std::hash::{BuildHasher, Hash, Hasher};
41
42///The `HashStealer` struct and methods allows you to "steal" the hash functions
43///from Rust, and base_hash can be called on any key that implements Hash+Eq.
44///Hashing requires equality and must be consistent with it: if x==y then
45///hash(x)==hash(y).
46
47pub struct HashStealer {
48    state: RandomState,
49}
50impl HashStealer {
51    /// creates a new hash stealer. Here, `Self` refers to the type being
52    /// "impl"ed while `self` refers to the current instance of `Self`.
53    pub fn new() -> Self {
54        HashStealer {
55            state: RandomState::new(),
56        }
57    } //new
58
59    /// do what's needed to return a hash value on any hashable key
60    pub fn base_hash<K: Hash + Eq>(&mut self, key: &K) -> usize {
61        let mut builder = self.state.build_hasher();
62        key.hash(&mut builder);
63        builder.finish() as usize
64    } //base_hash
65} //impl HashStealer
66
67/// This is your bijective map struct
68pub struct BijectiveMap<KT, VT, const CAP: usize = 16> {
69    keys: HashMap<usize, Vec<(KT, usize, usize)>>,
70    vals: HashMap<usize, Vec<(VT, usize, usize)>>,
71    size: usize,
72    hasher: HashStealer,
73} // struct BijectiveMap
74
75// some more code to get you started ...
76// Under no circumstances can KT, VT impl any trait other than Hash and Eq:
77impl<KT: Hash + Eq, VT: Hash + Eq, const CAP: usize> BijectiveMap<KT, VT, CAP> {
78    // non-public internal function to use HashStealer
79    fn hash<K: Hash + Eq>(&mut self, key: &K) -> usize {
80        self.hasher.base_hash(key)
81    } //hash
82
83    /// creates a new BijectiveMap with default initial capacity:
84    pub fn new() -> Self {
85        // Self refers to this TYPE, BijectiveMap
86        BijectiveMap {
87            keys: HashMap::with_capacity(CAP), // just initial capacity
88            vals: HashMap::with_capacity(CAP), // can expand if needed
89            size: 0,
90            hasher: HashStealer::new(),
91        }
92    } //new
93
94    /// Returns a immutable reference to the value corresponding to
95    /// the given key, if it exists.  Note that there can't be a
96    /// `Option<&mut T>` version of this method because changing the
97    /// value will require adjusting other associations in the map.
98    /// This function has been completed and you can consult its source
99    /// as hint.
100    pub fn get_by_key(&mut self, key: &KT) -> Option<&VT> {
101        let hk = self.hash(key);
102        if !self.keys.contains_key(&hk) {
103            return None;
104        }
105        for (k, vr, vc) in self.keys[&hk].iter() {
106            if k == key {
107                return Some(&self.vals[vr][*vc].0); //.0 is first in tuple
108            }
109        }
110        None
111    } //get
112} // impl
113
114/// **Place all your code in another impl block, and fully implement the
115/// methods** [BijectiveMap::get_by_val], [BijectiveMap::take_by_key],
116/// [BijectiveMap::take_by_val], and [BijectiveMap::set].
117impl<KT: Hash + Eq, VT: Hash + Eq, const CAP: usize> BijectiveMap<KT, VT, CAP> {
118    /// Returns number of key-value pairs in this map.
119    /// This one's too easy so I just did it for you again.  I will give
120    /// away more stuff if you come to me for help ...
121    pub fn len(&self) -> usize {
122        self.size
123    }
124
125    /// **This is the first method you need to implement.**
126    /// Returns an immutable reference to the key associated with the
127    /// given value, if it exists. The dummy provided here just returns
128    /// `None` and you need to rewrite it appropriately.
129    pub fn get_by_val(&mut self, val: &VT) -> Option<&KT> {
130        None
131    }
132
133    /// This is another method you need to implement.
134    /// Removes key-value pair from map by searching for it by key.
135    /// Returns the key and value if found.  Note that this function
136    /// is "take" and not "get" because it **moves** the actual key and value
137    /// out of the map.  It doesn't return references.  Sometimes you
138    /// may need to convert an `Option<T>` to an `Option<&T>`.  To do
139    /// that, given such an `Option<T>` `opt`, use the expression `opt.as_ref()`.
140    ///
141    /// The dummy implemenetation provided here just returns `None`
142    pub fn take_by_key(&mut self, key: &KT) -> Option<(KT, VT)> {
143        None
144    }
145
146    /// Dummies always return `None`.  Are you a dummy?
147    pub fn take_by_val(&mut self, val: &VT) -> Option<(KT, VT)> {
148        None
149    }
150
151    /// Change or add key-val pair, return a pair to represent information
152    /// that was deleted.  Note that the returned key,value, if they
153    /// exist, may indicate a different key or value that existed in the
154    /// map before the change (see "daynum" example that you should
155    /// replicate in main).  Replace the dummy implementation.
156    pub fn set(&mut self, mut key: KT, mut val: VT) -> Option<(KT, VT)> {
157        None
158    }
159} // can have multiple impl blocks
csc_7b_fc/bijectivemap.rs

csc_7b_fc/
bijectivemap.rs
