rust - How to implement HashMap with two keys? -


hashmap implements get , insert methods take single immutable borrow , single move of value respectively.

i want trait takes 2 keys instead of one. uses map inside, it's detail of implementation.

pub struct table<a: eq + hash, b: eq + hash> {     map: hashmap<(a, b), f64>, }  impl<a: eq + hash, b: eq + hash> memory<a, b> table<a, b> {     fn get(&self, a: &a, b: &b) -> f64 {         let key: &(a, b) = ??;         *self.map.get(key).unwrap()     }      fn set(&mut self, a: a, b: b, v: f64) {         self.map.insert((a, b), v);     } } 

this possible. signature of get is

fn get<q: ?sized>(&self, k: &q) -> option<&v>      k: borrow<q>,     q: hash + eq,  

the problem here implement &q type such (1) (a, b): borrow<q>, , (2) q implements hash + eq.

to satisfy condition (1), need think of how write

fn borrow(self: &(a, b)) -> &q 

the trick &q does not need simple pointer, can trait object! idea create trait q, have 2 implementations:

impl q (a, b) impl q (&a, &b) 

so borrow implementation return self, meanwhile construct &q trait object 2 elements separately.


the full implementation this:

use std::collections::hashmap; use std::hash::{hash, hasher}; use std::borrow::borrow;  // see explanation (1). #[derive(partialeq, eq, hash)] struct pair<a, b>(a, b);  #[derive(partialeq, eq, hash)] struct borrowedpair<'a, 'b, a: 'a, b: 'b>(&'a a, &'b b);  // see explanation (2). trait keypair<a, b> {     /// obtains first element of pair.     fn a(&self) -> &a;     /// obtains second element of pair.     fn b(&self) -> &b;     /// checks if pair equal pair elementwise.     fn eq_pair(&self, a: &a, b: &b) -> bool;     /// computes hash of pair.     fn erased_hash(&self, state: erasedhasher); }  // see explanation (3). impl<'a, a, b> borrow<keypair<a, b> + 'a> pair<a, b>     a: eq + hash + 'a,     b: eq + hash + 'a, {     fn borrow(&self) -> &(keypair<a, b> + 'a) {         self     } }  // see explanation (4). impl<'a, a: hash, b: hash> hash (keypair<a, b> + 'a) {     fn hash<h: hasher>(&self, state: &mut h) {         self.erased_hash(erasedhasher(state));     } }  impl<'a, a: eq, b: eq> partialeq (keypair<a, b> + 'a) {     fn eq(&self, other: &self) -> bool {         self.eq_pair(other.a(), other.b())     } }  impl<'a, a: eq, b: eq> eq (keypair<a, b> + 'a) {}  pub struct table<a: eq + hash, b: eq + hash> {     map: hashmap<pair<a, b>, f64>, }  impl<a: eq + hash, b: eq + hash> table<a, b> {     fn new() -> self {         table { map: hashmap::new() }     }      fn get(&self, a: &a, b: &b) -> f64 {         *self.map.get(&borrowedpair(a, b) &keypair<a, b>).unwrap()     }      fn set(&mut self, a: a, b: b, v: f64) {         self.map.insert(pair(a, b), v);     } }  // boring stuff below.  impl<a, b> keypair<a, b> pair<a, b>     a: eq + hash,     b: eq + hash, {     fn a(&self) -> &a {         &self.0     }     fn b(&self) -> &b {         &self.1     }     fn eq_pair(&self, a: &a, b: &b) -> bool {         &self.0 == && &self.1 == b     }     fn erased_hash(&self, mut state: erasedhasher) {         self.0.hash(&mut state);         self.1.hash(&mut state);     } } impl<'a, 'b, a, b> keypair<a, b> borrowedpair<'a, 'b, a, b>     a: eq + hash + 'a,     b: eq + hash + 'a, {     fn a(&self) -> &a {         self.0     }     fn b(&self) -> &b {         self.1     }     fn eq_pair(&self, a: &a, b: &b) -> bool {         self.0 == && self.1 == b     }     fn erased_hash(&self, mut state: erasedhasher) {         self.0.hash(&mut state);         self.1.hash(&mut state);     } }  // needed because `&mut hasher` not `hasher`, // , `hash<h: hasher>(&self, &mut h)` means need sized `hasher`. struct erasedhasher<'a>(&'a mut hasher);  impl<'a> hasher erasedhasher<'a> {     fn finish(&self) -> u64 { self.0.finish() }     fn write(&mut self, bytes: &[u8]) { self.0.write(bytes) }     fn write_u8(&mut self, i: u8) { self.0.write_u8(i) }     fn write_u16(&mut self, i: u16) { self.0.write_u16(i) }     fn write_u32(&mut self, i: u32) { self.0.write_u32(i) }     fn write_u64(&mut self, i: u64) { self.0.write_u64(i) }     fn write_usize(&mut self, i: usize) { self.0.write_usize(i) }     fn write_i8(&mut self, i: i8) { self.0.write_i8(i) }     fn write_i16(&mut self, i: i16) { self.0.write_i16(i) }     fn write_i32(&mut self, i: i32) { self.0.write_i32(i) }     fn write_i64(&mut self, i: i64) { self.0.write_i64(i) }     fn write_isize(&mut self, i: isize) { self.0.write_isize(i) } } 

explanation:

  1. we introduced pair , borrowedpair types. can't use (a, b) directly due the orphan rule e0210. fine since map implementation detail.

  2. the keypair trait takes role of q mentioned above. we'd need impl eq + hash keypair, eq , hash both not object safe. added a(), b(), eq_pair() , erased_hash() methods implementing them manually.

  3. now implement borrow trait pair<a, b> keypair + 'a. note 'a — subtle bit needed make table::get work. arbitrary 'a allows say, pair<a, b> can borrowed trait object any lifetime. if don't specify 'a, unsized trait object default 'static, meaning borrow trait can applied when implementation borrowedpair outlives 'static, not case.

  4. finally implement eq , hash. above, implement keypair + 'a instead of keypair (which means keypair + 'static in context).


using trait objects incur indirection cost when computing hash , checking equality in get(). cost can eliminated if optimizer able devirtualize that, whether llvm unknown.

an alternative store map hashmap<(cow<a>, cow<b>), f64>. using requires less "clever code", there memory cost store owned/borrowed flag, runtime cost in both get() , set().

so, unfortunately, unless fork standard hashmap , adds method entry via hash + eq alone, there no guaranteed-zero-cost solution.


Comments

Popular posts from this blog

ubuntu - PHP script to find files of certain extensions in a directory, returns populated array when run in browser, but empty array when run from terminal -

php - How can i create a user dashboard -

javascript - How to detect toggling of the fullscreen-toolbar in jQuery Mobile? -