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        for i = 0 until primes.size do
11            let prime = primes[i]
12            if prime >= capacity then
13                return prime
14    
15        fail "capacity exceeds largest prime"
16    
17    type Entry<K> = struct
18        is_occupied : bool
19        prev : i32
20        next : i32
21        key : K
22    
23    mixin HashCollection<K, T> where T : Entry<K> =
24        var array = Array<T> 0
25        var first : i32 = -1
26        let mut last : i32 = -1
27    
28        def find_index (k : K) =
29            let hash = Kd.hash_of k
30            let mut i = hash % array.size as u64 |> as<u32>
31            while array[i].is_occupied && array[i].key <> k do
32                i = (i + 1) % array.size
33    
34            i
35    
36        def contains (k : K) =
37            if first == -1 then
38                false
39            else
40                let i = find_index k
41                array[i].is_occupied
42    
43        def put (entry : T) =
44            let i = find_index entry.key
45            assert not array[i].is_occupied
46    
47            if last <> -1 then
48                array[last].next = i as i32
49    
50            array[i] = T is_occupied = true
51                         prev = last
52                         next = -1
53                         f@ entry
54    
55            if first == -1 then
56                first = i as i32
57    
58            last = i as i32
59    
60        def rebuild =
61            let capacity = if array.size == 0
62                           then 17
63                           else get_prime (array.size * 2)
64    
65            let prev_array = array
66            let prev_first = first
67            array = Array capacity
68            first = -1
69            last = -1
70    
71            let mut i = prev_first
72            while i <> -1 do
73                let entry = prev_array[i]
74                put entry
75                i = entry.next
76    
77            prev_array.discard
78    
79        def remove_key (k : K) =
80            let mut i = find_index k
81            if not array[i].is_occupied then
82                fail "key is not present"
83    
84            array[i].is_occupied = false
85            if array[i].prev <> -1 then
86                array[array[i].prev].next = array[i].next
87            else
88                first = array[i].next
89    
90            if array[i].next <> -1 then
91                array[array[i].next].prev = array[i].prev
92            else
93                last = array[i].prev
94    
95            let mut j = i
96            repeat
97                j = (j + 1) % array.size
98                if not array[j].is_occupied then
99                    break
100   
101               let hash = Kd.hash_of array[j].key
102               let l = hash % array.size as u64 |> as<u32>
103               if i <= j then
104                   if i < l && l <= j then
105                       continue
106               else
107                   if l <= j || i < l then
108                       continue
109   
110               array[i] = array[j]
111   
112               if array[j].prev == -1 then
113                   first = i as i32
114               else
115                   array[array[j].prev].next = i as i32
116   
117               if array[j].next == -1 then
118                   last = i as i32
119               else
120                   array[array[j].next].prev = i as i32
121   
122               array[j].is_occupied = false
123               i = j
124   
125       def remove_all =
126           let mut index = first
127           while index <> -1 do
128               array[index].is_occupied = false
129               index = array[index].next
130   
131           first = -1
132           last = -1
133