A basic multimap prototype in Rust


Recently, I have been working on a couple of projects, and in one of them, the logic required the use of a multimap. Now, this project is in Rust, and the standard Rust map types, `HashMap` and `BTreeMap` do not support duplicate keys.
Of course, there are full-blown crates available that provide multimap functionality.

However, this being a dead simple project, I decided to roll one out myself. This version simply wraps a `HashMap<K, Vec>` instance inside the custom data structure, but the advantage is that the client API remains consistent and never the wiser about the innards of the actual multimap type. Since I just needed `insert`, `get`, and `iter`, I implemented those for the custom multimap. If needed, the entire API of the `HashMap` type could be implemented for `MHashMap` as well.

Here is the code. It is simple enough that no explanation is really required:

#![allow(dead_code)]

/// A simple wrapper around a HashMap to simulate the basic functionality
/// of a multimap.

use std::collections::HashMap;
use std::hash::Hash;
use std::collections::hash_map::Iter;


#[derive(Debug)]
struct MHashMap<K: Eq + PartialEq + Hash, V>{
    map: HashMap<K, Vec<V>>,
}

impl<K, V> MHashMap<K, V> 
    where K : Eq + PartialEq + Hash
{
    fn new() -> Self {
        MHashMap {
            map: HashMap::new(),
        }
    }

    fn iter(&self) -> Iter<K, Vec<V>> {
        self.map.iter()
        
    }

    fn insert(&mut self, k: K, v: V) {
        if self.map.contains_key(&k) {
                self.map.get_mut(&k).unwrap().push(v);
        } else {
            self.map.insert(k, vec![v]);
        }
    }

    fn get(&self, k: &K) -> Option<&Vec<V>> {
        self.map.get(&k)
    }

    fn get_mut(&mut self, k: &K) -> Option<&mut Vec<V>> {
        self.map.get_mut(&k)
    }
}


fn main() {
    let mut mmap = MHashMap::new();

    mmap.insert(1, "One");
    mmap.insert(1, "Uno");
    mmap.insert(1, "Ein");
    mmap.insert(2, "Two");
    mmap.insert(3, "Three");

    println!("{:?}", mmap);

    let key = 1;

    match mmap.get(&key) {
        Some(vals) => println!("Got {:?} for key {}", vals, key),
        None => println!("Key {} not found!", key),
    }

    for entry in mmap.iter() {
        println!("{} = {:?}", entry.0, entry.1);
    }
}

A small test run:

Macushla:tcp_study z0ltan$ rustc mhash.rs
Macushla:tcp_study z0ltan$ ./mhash
MHashMap { map: {3: ["Three"], 1: ["One", "Uno", "Ein"], 2: ["Two"]} }
Got ["One", "Uno", "Ein"] for key 1
3 = ["Three"]
1 = ["One", "Uno", "Ein"]
2 = ["Two"]

Short and simple!

Advertisements
A basic multimap prototype in Rust

Speak your mind!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s