1    type MapEntry<K, V> = struct
2        inherit Entry<K>
3    
4        value : V
5    
6    type Map<K, V> @abstract =
7        include HashCollection<K, MapEntry<K, V>>
8            private all@
9            public contains
10           internal first
11                    array
12   
13       var size : u32 = 0
14       var version : u32 = 0
15   
16       def is_empty = size == 0
17       def is_not_empty = size <> 0
18   
19       def try_get k =
20           if size == 0 then
21               None
22           else
23               let i = find_index k
24               if array[i].is_occupied
25               then Some array[i].value
26               else None
27   
28       fun get k = try_get k |> unwrap
29   
30       let get_mut_ptr k =
31           let i = find_index k
32           if array[i].is_occupied
33           then array[i].value@mut_ptr
34           else fail "key is not present"
35   
36       fun get_ptr k = get_mut_ptr k as Ptr<V>
37   
38   type MutMap<K, V> @[mut_of Map] =
39       inherit Map<K, V>
40   
41       let put k v =
42           let i = find_index k
43           if array[i].is_occupied then
44               let prev_v = array[i].value
45               array[i].value = v
46               Some prev_v
47           else
48               let entry = MapEntry<K, V> key = k
49                                          value = v
50                                          f@ struct@zero
51               put entry
52               None
53   
54       fun get_mut_ptr k = get_mut_ptr k
55   
56       def insert k v =
57           if array.size == 0 || size as f32 / array.size as f32 >= 0.7 then
58               rebuild
59   
60           let result = put k v
61           if result.is_none then
62               size += 1
63   
64           version += 1
65   
66           result
67   
68       def add k v =
69           let result = insert k v
70           assert result.is_none
71   
72       fun set k v =
73           let i = find_index k
74           if array[i].is_occupied then
75               array[i].value = v
76               version += 1
77           else
78               insert k v |> ignore
79   
80       def remove k =
81           remove_key k
82           size -= 1
83           version += 1
84   
85       def retain (f : K * V -> bool) : Unit =
86           fail
87   
88       def clear =
89           remove_all
90           size = 0
91           version += 1
92   
93       def as_readonly = self as Map<K, V>
94   
95   object Map<K, V> =
96       val empty = Map<K, V>.new |> as_readonly
97