1    type MultisetEntry<T> = struct
2        inherit Entry<T>
3    
4        count : u32
5    
6    type Multiset<T> @abstract =
7        include HashCollection<T, MultisetEntry<T>>
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 multiplicity x =
20           let i = find_index x
21           assert array[i].is_occupied
22           array[i].count
23   
24   type MutMultiset<T> @[mut_of Multiset] =
25       inherit Multiset<T>
26   
27       let put (x : T) =
28           let i = find_index x
29           if array[i].is_occupied then
30               array[i].count += 1
31               false
32           else
33               let entry = MultisetEntry<T> key = x
34                                            count = 1
35                                            f@ struct@zero
36               put entry
37               true
38   
39       def add (x : T) =
40           if array.size == 0 || size as f32 / array.size as f32 >= 0.7 then
41               rebuild
42   
43           let result = put x
44           if result then
45               size += 1
46   
47           version += 1
48   
49       def remove x =
50           let i = find_index x
51           assert array[i].is_occupied
52   
53           if array[i].count == 1 then
54               remove_key x
55               size -= 1
56           else
57               array[i].count -= 1
58   
59           version += 1
60   
61       def as_readonly = self as Multiset<T>
62