1    begin@ multimap
2    
3    type Multimap<K, V> =
4        let map = Map<K, mut Set<V>>.new
5        let empty = Set<V>.new
6        var version : u32 = 0
7        var size : u32 = 0
8    
9        def contains k =
10           map.contains k
11   
12       def contains k v =
13           map.contains k && map[k].contains v
14   
15       def get k =
16           map[k].as_readonly
17   
18       fun get k = get k
19   
20       def try_get k = map.try_get k |> map { _.as_readonly }
21   
22       def as_map = map.as_readonly
23   
24       def insert k v =
25           let result = case map.try_get k of
26               None ->
27                   let set = Set<V>.new
28                   set.insert v
29                   map.insert k set
30                   true
31   
32               Some set ->
33                   set.insert v
34   
35           if result then
36               size += 1
37               version += 1
38   
39           result
40   
41       def add k v =
42           let result = insert k v
43           assert result
44   
45       def remove k v =
46           let set = map[k]
47           set.remove v
48           size -= 1
49           version += 1
50   
51       def remove_all k =
52           let set = map[k]
53           size -= set.size
54           set.clear
55           version += 1
56   
57       def trim =
58           map.retain { _ set -> set.is_not_empty }
59           version += 1
60   
61       def clear =
62           map.clear
63           size = 0
64           version += 1
65