1     let primes = array@<u32>
2         3 7 11 17 23 29 37 47 59 71 89 107 131 163 197 239 293 353 431 521 631 761
3         919 1103 1327 1597 1931 2333 2801 3371 4049 4861 5839 7013 8419 10103 12143
4         14591 17519 21023 25229 30293 36353 43627 52361 62851 75431 90523 108631
5         130363 156437 187751 225307 270371 324449 389357 467237 560689 672827 807403
6         968897 1162687 1395263 1674319 2009191 2411033 2893249 3471899 4166287
7         4999559 5999471 7199369
8     
9     let get_prime (capacity : u32) =
10        let mut index = 0
11        for i = 0 until primes.size do
12            let prime = primes[i]
13            if prime >= capacity then
14                return prime
15    
16        fail "capacity exceeds largest prime"
17    
18    type Entry<K> = struct
19        is_occupied : bool
20        prev : i32
21        next : i32
22        key : K
23    
24    mixin HashCollection<K, T> where T : Entry<K> =
25        var array = Array<T> 0
26        var first : i32 = -1
27        let mut last : i32 = -1
28    
29        def find_index (k : K) =
30            let hash = Kd.hash_of k
31            let mut i = hash % array.size as u64 |> as<u32>
32            while array[i].is_occupied && array[i].key <> k do
33                i = (i + 1) % array.size
34    
35            i
36    
37        def contains (k : K) =
38            if first == -1 then
39                false
40            else
41                let i = find_index k
42                array[i].is_occupied
43    
44        def put (entry : T) =
45            let i = find_index entry.key
46            assert not array[i].is_occupied
47    
48            if last <> -1 then
49                array[last].next = i as i32
50    
51            array[i] = T is_occupied = true
52                         prev = last
53                         next = -1
54                         f@ entry
55    
56            if first == -1 then
57                first = i as i32
58    
59            last = i as i32
60    
61        def rebuild =
62            let capacity = if array.size == 0
63                           then 17
64                           else get_prime (array.size * 2)
65    
66            let prev_array = array
67            let prev_first = first
68            array = Array capacity
69            first = -1
70            last = -1
71    
72            let mut i = prev_first
73            while i <> -1 do
74                let entry = prev_array[i]
75                put entry
76                i = entry.next
77    
78            prev_array.discard
79    
80        def remove_key (k : K) =
81            let mut i = find_index k
82            if not array[i].is_occupied then
83                fail "key is not present"
84    
85            array[i].is_occupied = false
86            if array[i].prev <> -1 then
87                array[array[i].prev].next = array[i].next
88            else
89                first = array[i].next
90    
91            if array[i].next <> -1 then
92                array[array[i].next].prev = array[i].prev
93            else
94                last = array[i].prev
95    
96            let mut j = i
97            repeat
98                j = (j + 1) % array.size
99                if not array[j].is_occupied then
100                   break
101   
102               let hash = Kd.hash_of array[j].key
103               let l = hash % array.size as u64 |> as<u32>
104               if i <= j then
105                   if i < l && l <= j then
106                       continue
107               else
108                   if l <= j || i < l then
109                       continue
110   
111               array[i] = array[j]
112   
113               if array[j].prev == -1 then
114                   first = i as i32
115               else
116                   array[array[j].prev].next = i as i32
117   
118               if array[j].next == -1 then
119                   last = i as i32
120               else
121                   array[array[j].next].prev = i as i32
122   
123               array[j].is_occupied = false
124               i = j
125   
126       def remove_all =
127           let mut index = first
128           while index <> -1 do
129               array[index].is_occupied = false
130               index = array[index].next
131   
132           first = -1
133           last = -1
134