// 1041: Multimap — HashMap<K, Vec<V>> with Helpers
// A map where each key can have multiple values
use std::collections::HashMap;
/// A multimap: each key maps to a Vec of values
struct MultiMap<K, V> {
inner: HashMap<K, Vec<V>>,
}
impl<K: std::hash::Hash + Eq, V> MultiMap<K, V> {
fn new() -> Self {
MultiMap { inner: HashMap::new() }
}
fn insert(&mut self, key: K, value: V) {
self.inner.entry(key).or_default().push(value);
}
fn get(&self, key: &K) -> &[V] {
self.inner.get(key).map_or(&[], |v| v.as_slice())
}
fn remove_key(&mut self, key: &K) -> Option<Vec<V>> {
self.inner.remove(key)
}
fn count_values(&self, key: &K) -> usize {
self.get(key).len()
}
fn total_values(&self) -> usize {
self.inner.values().map(|v| v.len()).sum()
}
fn keys(&self) -> impl Iterator<Item = &K> {
self.inner.keys()
}
fn contains_key(&self, key: &K) -> bool {
self.inner.contains_key(key)
}
}
impl<K: std::hash::Hash + Eq, V: PartialEq> MultiMap<K, V> {
fn remove_value(&mut self, key: &K, value: &V) -> bool {
if let Some(values) = self.inner.get_mut(key) {
if let Some(pos) = values.iter().position(|v| v == value) {
values.remove(pos);
if values.is_empty() {
self.inner.remove(key);
}
return true;
}
}
false
}
fn contains_value(&self, key: &K, value: &V) -> bool {
self.get(key).contains(value)
}
}
fn basic_ops() {
let mut mm = MultiMap::new();
mm.insert("fruits", "apple");
mm.insert("fruits", "banana");
mm.insert("fruits", "cherry");
mm.insert("vegs", "carrot");
mm.insert("vegs", "pea");
assert_eq!(mm.get(&"fruits"), &["apple", "banana", "cherry"]);
assert_eq!(mm.get(&"vegs"), &["carrot", "pea"]);
assert_eq!(mm.count_values(&"fruits"), 3);
assert_eq!(mm.total_values(), 5);
}
fn remove_ops() {
let mut mm = MultiMap::new();
mm.insert("tags", "rust");
mm.insert("tags", "ocaml");
mm.insert("tags", "haskell");
assert!(mm.remove_value(&"tags", &"ocaml"));
assert_eq!(mm.get(&"tags"), &["rust", "haskell"]);
mm.remove_key(&"tags");
assert_eq!(mm.get(&"tags"), &[] as &[&str]);
}
fn build_index() {
let data = vec![
("lang", "Rust"), ("lang", "OCaml"), ("lang", "Haskell"),
("paradigm", "functional"), ("paradigm", "imperative"),
];
let mut mm = MultiMap::new();
for (key, value) in data {
mm.insert(key, value);
}
assert_eq!(mm.get(&"lang"), &["Rust", "OCaml", "Haskell"]);
assert_eq!(mm.get(&"paradigm"), &["functional", "imperative"]);
assert!(mm.contains_value(&"lang", &"Rust"));
assert!(!mm.contains_value(&"lang", &"Python"));
}
fn main() {
basic_ops();
remove_ops();
build_index();
println!("✓ All tests passed");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_basic() { basic_ops(); }
#[test]
fn test_remove() { remove_ops(); }
#[test]
fn test_index() { build_index(); }
#[test]
fn test_empty_get() {
let mm: MultiMap<&str, i32> = MultiMap::new();
assert_eq!(mm.get(&"missing"), &[] as &[i32]);
assert_eq!(mm.count_values(&"missing"), 0);
}
}
(* 1041: Multimap — HashMap<K, Vec<V>> with Helpers *)
(* A map where each key maps to multiple values *)
module StringMap = Map.Make(String)
type 'a multimap = 'a list StringMap.t
let empty : 'a multimap = StringMap.empty
let add key value (mm : 'a multimap) : 'a multimap =
let current = match StringMap.find_opt key mm with
| Some vs -> vs
| None -> []
in
StringMap.add key (current @ [value]) mm
let get key (mm : 'a multimap) : 'a list =
match StringMap.find_opt key mm with
| Some vs -> vs
| None -> []
let remove_key key (mm : 'a multimap) : 'a multimap =
StringMap.remove key mm
let remove_value key value (mm : 'a multimap) : 'a multimap =
match StringMap.find_opt key mm with
| None -> mm
| Some vs ->
let filtered = List.filter (fun v -> v <> value) vs in
if filtered = [] then StringMap.remove key mm
else StringMap.add key filtered mm
let count_values key (mm : 'a multimap) : int =
List.length (get key mm)
let total_values (mm : 'a multimap) : int =
StringMap.fold (fun _ vs acc -> acc + List.length vs) mm 0
(* Approach 1: Basic multimap operations *)
let basic_ops () =
let mm = empty
|> add "fruits" "apple"
|> add "fruits" "banana"
|> add "fruits" "cherry"
|> add "vegs" "carrot"
|> add "vegs" "pea"
in
assert (get "fruits" mm = ["apple"; "banana"; "cherry"]);
assert (get "vegs" mm = ["carrot"; "pea"]);
assert (count_values "fruits" mm = 3);
assert (total_values mm = 5)
(* Approach 2: Remove operations *)
let remove_ops () =
let mm = empty
|> add "tags" "rust"
|> add "tags" "ocaml"
|> add "tags" "haskell"
in
let mm = remove_value "tags" "ocaml" mm in
assert (get "tags" mm = ["rust"; "haskell"]);
let mm = remove_key "tags" mm in
assert (get "tags" mm = [])
(* Approach 3: Index building *)
let build_index items =
List.fold_left (fun mm (key, value) ->
add key value mm
) empty items
let index_test () =
let data = [
("lang", "Rust"); ("lang", "OCaml"); ("lang", "Haskell");
("paradigm", "functional"); ("paradigm", "imperative");
] in
let mm = build_index data in
assert (get "lang" mm = ["Rust"; "OCaml"; "Haskell"]);
assert (get "paradigm" mm = ["functional"; "imperative"])
let () =
basic_ops ();
remove_ops ();
index_test ();
Printf.printf "✓ All tests passed\n"