csc_7b_fc/
bimap.rs

1//!  **CSC 123/252 Assignment**
2//!
3//!  This module contains the skeleton of a bijective hashmap that you should
4//!  implement fully.  It is based on the implementation of my version of
5//!  one-way hashmaps found in [crate::hmap].  Consult the documentation
6//!  and source code of [crate::hmap::Hmap] to understand it before proceeding.
7//!  The idea is to use two Hmaps underneath, each mapping a key to the index
8//!  in the other map's underlying vector where the corresponding value is
9//!  stored.  This way a bijective hashmap can be constructed without
10//!  resorting to Copy, Clone, Rc, or anything unsafe.  Click on the
11//!  [Bimap] structure link to see the functions you need to implement.
12//!
13//!  As a challenge, try to also implement an iterator for your structure.
14//!  Try to use the iterator for [Hmap].
15
16#![allow(dead_code, unused_imports, unused_variables)]
17
18use crate::hmap::*;
19use std::hash::{BuildHasher,Hash,Hasher};
20
21//////////////Bimap
22pub struct Bimap<TA,TB> {
23  pub forward : Hmap<TA,usize>,
24  pub backward: Hmap<TB,usize>,
25}
26impl<TA:Hash+Eq, TB:Hash+Eq> Bimap<TA,TB> {
27
28  /// Constructs a new Bimap with default capacity 16.  This function has
29  /// been written for you.
30  pub fn new() -> Self {
31    Bimap {
32      forward : Hmap::new(),
33      backward: Hmap::new(),
34    }
35  }
36
37  /// Constructs a new Bimap with requested capacity.  The actual capacity
38  /// will be the closest power of two that's greater than or equal to the
39  /// requested capacity.  This function has been written for you.
40  pub fn with_capacity(cap:usize) -> Self {
41    Bimap {
42      forward: Hmap::with_capacity(cap),
43      backward: Hmap::with_capacity(cap),
44    }
45  }
46
47  /// Gets the value associated with the key in the forward direction, if
48  /// it exists.  This function has been written for you.
49  pub fn get_forward(&self, key:&TA) -> Option<&TB> {
50    match self.forward.get(key) {
51      Some(vi) => self.backward.table[*vi].as_ref().map(|(v,_)|v),
52      None => None,
53    }
54  }
55
56  /// Complete the implementation of this function
57  pub fn get_backward(&self, key:&TB) -> Option<&TA> {
58    None
59  }
60
61  /// Removes the value associated with the key in the forward direction,
62  /// returning the existing key-value pair, if it exists.  This function
63  /// has been written for you.
64  pub fn remove_forward(&mut self, key:&TA) -> Option<(TA,TB)> {
65    let rf = self.forward.remove(&key);
66    rf.and_then(|(k,vi)|{
67      let mut temp = None;
68      core::mem::swap(&mut temp, &mut self.backward.table[vi]);
69      self.backward.count -= 1;
70      temp.map(|(v,ki)|(k,v))
71    })
72  }
73
74  /// Complete the implementation of this function
75  pub fn remove_backward(&mut self, key:&TB) -> Option<(TA,TB)> {
76    None
77  }  
78
79  /// Complete the implementation of this function.  The general approach is
80  /// the following.  First, call [Bimap::remove_forward] and [Bimap::remove_backward] to
81  /// clear existing values.  Then call [Hmap::find_new_slot]
82  /// to find appropriate places to place the key and values in the forward
83  /// and backward maps.  Then place in the forward map `Some((key,vi))`
84  /// where vi is the index in the backward map where the value
85  /// is found.  And place in the backwards map `Some((val,ki))` where ki
86  /// is the index in the forward map where the key is found.
87  /// Besure to call resize if necessary when adding manually to the forward
88  /// and backwards maps, as well as increase their `count`.
89  ///
90  /// Note that this function returns a pair of options because both the
91  /// key and value could've had prior associations that must be deleted.
92  pub fn set(&mut self, key:TA, val:TB) -> (Option<(TA,TB)>,Option<(TA,TB)>) {
93    (None,None)
94  }
95
96  /// Returns the number of key-value pairs in the bijective map.  This function
97  /// has been written for you, unless you decide to change it.
98  pub fn len(&self) -> usize { self.forward.len() }
99
100}// impl
101
102
103/// Function thesting the implementation - run when finished
104pub fn test() {
105  let mut days = Bimap::new();
106  days.set("Monday",1);
107  days.set("Tuesday",2);
108  days.set("Wednesday",3);
109  days.set("Thursday",4);
110  days.set("Friday",5);
111  days.set("Saturday",6);
112  days.set("Sunday",7);
113  println!("tuesday to 4: {:?}", days.set("Tuesday",4));
114  println!("{:?}",days.get_forward(&"Sunday"));
115  println!("{:?}",days.get_backward(&4));
116  println!("{:?}",days.get_backward(&7));
117  println!("size {}", days.len());
118  /*
119  for (k,v) in days.iter() {
120    println!("{} : {}", k, v);
121  }
122  */
123}
124
csc_7b_fc/bimap.rs

csc_7b_fc/
bimap.rs
