tobogganSe connecter

packages

The Louise packages, each released on its own

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

251 lignes · 6595 octetsBrut · Historique
1// The containers switch between list and bitmap at 4,096 values, and the
2// set operations agree with naive ones on random sets.
3
4import bitmap
5import gen
6import gen/check
7import std/list
8import std/random.{type random}
9import std/test.{assert, assert_equal}
10
11@test
12fn an_empty_bitmap_has_nothing ::
13{
14 let b = bitmap.empty ()
15 assert_equal (bitmap.size b) 0
16 assert (bitmap.is_empty b) "empty"
17 assert_equal (bitmap.to_list b) []
18 assert (!bitmap.contains b 0) "contains nothing"
19}
20
21@test
22fn added_ids_are_contained_in_order ::
23{
24 let b = bitmap.from_list [5, 1, 5, 70000, 3]
25 assert_equal (bitmap.to_list b) [1, 3, 5, 70000]
26 assert_equal (bitmap.size b) 4
27 assert (bitmap.contains b 70000) "70000"
28 assert (!bitmap.contains b 69999) "not 69999"
29 // Two high bits: two sparse containers.
30 assert_equal (bitmap.stats b) (2, 0)
31}
32
33@test
34fn a_container_becomes_a_bitmap_past_4096 ::
35{
36 let b = bitmap.from_list (list.range 0 4095)
37 assert_equal (bitmap.stats b) (1, 0)
38 let b = bitmap.add b 4096
39 assert_equal (bitmap.stats b) (0, 1)
40 assert_equal (bitmap.size b) 4097
41 assert (bitmap.contains b 4096) "4096"
42 let b = bitmap.add b 5000
43 assert_equal (bitmap.to_list b) (list.range 0 4096 <> [5000])
44}
45
46@test
47fn a_bitmap_drops_back_to_a_list_at_4096 ::
48{
49 let b = bitmap.from_list (list.range 0 4100)
50 assert_equal (bitmap.stats b) (0, 1)
51 let b =
52 list.fold [4100, 4099, 4098, 4097, 4096] b fn b id { bitmap.remove b id }
53 assert_equal (bitmap.stats b) (1, 0)
54 assert_equal (bitmap.to_list b) (list.range 0 4095)
55}
56
57@test
58fn removing_the_last_value_drops_the_container ::
59{
60 let b = bitmap.remove (bitmap.from_list [5, 70000]) 5
61 assert_equal (bitmap.to_list b) [70000]
62 assert_equal (bitmap.stats b) (1, 0)
63 assert (bitmap.is_empty (bitmap.remove b 70000)) "empty"
64}
65
66@test
67fn a_dense_intersection_stays_a_bitmap ::
68{
69 let a = bitmap.from_list (list.range 0 6000)
70 let b = bitmap.from_list (list.range 1000 9000)
71 let both = bitmap.intersect a b
72 assert_equal (bitmap.to_list both) (list.range 1000 6000)
73 assert_equal (bitmap.stats both) (0, 1)
74}
75
76@test
77fn a_sparse_intersection_drops_to_a_list ::
78{
79 let a = bitmap.from_list (list.range 0 6000)
80 let b = bitmap.from_list (list.range 3000 9000)
81 let both = bitmap.intersect a b
82 assert_equal (bitmap.to_list both) (list.range 3000 6000)
83 assert_equal (bitmap.stats both) (1, 0)
84}
85
86@test
87@should_panic "negative id"
88fn adding_a_negative_id_panics ::
89{
90 let _ = bitmap.add (bitmap.empty ()) (0 - 1)
91 ()
92}
93
94@test
95@should_panic "negative id"
96fn from_list_with_a_negative_id_panics ::
97{
98 let _ = bitmap.from_list [0 - 1]
99 ()
100}
101
102// ---- against naive sets -----------------------------------------------------
103
104/// The distinct values of `xs`, ascending.
105fn sorted_unique :: xs: List<Int> -> List<Int>
106{
107 dedupe (list.sort xs)
108}
109
110fn dedupe :: xs: List<Int> -> List<Int>
111{
112 match xs
113 { [x, y, ..rest] -> if x == y
114 {
115 dedupe [y, ..rest]
116 }
117 else
118 {
119 [x, ..dedupe [y, ..rest]]
120 }
121 , _ -> xs
122 }
123}
124
125/// The values in both, ascending.
126fn naive_intersect :: xs: List<Int> ys: List<Int> -> List<Int>
127{
128 let ys = sorted_unique ys
129 list.filter (sorted_unique xs) fn x { list.any ys fn y { y == x } }
130}
131
132/// Two random sets in a small range: sparse list containers.
133fn small_sets :: -> (List<Int>, List<Int>) / <random>
134{
135 let a = gen.list ~min: 0 ~max: 120 fn { gen.int ~low: 0 ~high: 300 }
136 let b = gen.list ~min: 0 ~max: 120 fn { gen.int ~low: 0 ~high: 300 }
137 (a, b)
138}
139
140/// Two random sets spread over several containers.
141fn wide_sets :: -> (List<Int>, List<Int>) / <random>
142{
143 let a = gen.list ~min: 0 ~max: 60 fn { gen.int ~low: 0 ~high: 200000 }
144 let b = gen.list ~min: 0 ~max: 60 fn { gen.int ~low: 0 ~high: 200000 }
145 (a, b)
146}
147
148fn sets_agree_with_the_naive_ones :: pair: (List<Int>, List<Int>) -> Bool
149{
150 let (a, b) = pair
151 let x = bitmap.from_list a
152 let y = bitmap.from_list b
153 bitmap.to_list x == sorted_unique a && bitmap.to_list y == sorted_unique b
154 && bitmap.size x == list.length (sorted_unique a)
155 && bitmap.to_list (bitmap.intersect x y) == naive_intersect a b
156 && list.all a fn id { bitmap.contains x id }
157 && list.all (naive_intersect a b) fn id { bitmap.contains y id }
158}
159
160@test
161fn small_sets_agree_with_the_naive_ones ::
162{
163 check.seeded ~seed: 101 ~runs: 100 small_sets sets_agree_with_the_naive_ones
164}
165
166@test
167fn wide_sets_agree_with_the_naive_ones ::
168{
169 check.seeded ~seed: 102 ~runs: 100 wide_sets sets_agree_with_the_naive_ones
170}
171
172/// A range of more than 4,096 values, at a random offset.
173fn dense_set :: -> (Int, Int) / <random>
174{
175 let lo = gen.int ~low: 0 ~high: 1000
176 let hi = lo + 4200 + gen.int ~low: 0 ~high: 800
177 (lo, hi)
178}
179
180fn dense_ranges_use_bitmaps :: bounds: (Int, Int) -> Bool
181{
182 let (lo, hi) = bounds
183 let b = bitmap.from_list (list.range lo hi)
184 bitmap.stats b == (0, 1) && bitmap.size b == hi - lo + 1
185 && bitmap.to_list b == list.range lo hi
186 && bitmap.contains b lo
187 && bitmap.contains b hi
188 && !bitmap.contains b (hi + 1)
189}
190
191@test
192fn dense_ranges_use_bitmap_containers ::
193{
194 check.seeded ~seed: 103 ~runs: 20 dense_set dense_ranges_use_bitmaps
195}
196
197/// Two overlapping dense ranges: their intersection is dense too.
198fn dense_pair :: -> (Int, Int, Int) / <random>
199{
200 let lo = gen.int ~low: 0 ~high: 500
201 let mid = lo + 3000 + gen.int ~low: 0 ~high: 1000
202 let hi = mid + 3000 + gen.int ~low: 0 ~high: 1000
203 (lo, mid, hi)
204}
205
206fn dense_intersections_agree :: bounds: (Int, Int, Int) -> Bool
207{
208 let (lo, mid, hi) = bounds
209 let a = bitmap.from_list (list.range lo (mid + 2500))
210 let b = bitmap.from_list (list.range mid hi)
211 bitmap.to_list (bitmap.intersect a b) == list.range mid (mid + 2500)
212}
213
214@test
215fn dense_intersections_agree_with_the_ranges ::
216{
217 check.seeded ~seed: 104 ~runs: 20 dense_pair dense_intersections_agree
218}
219
220@test
221fn adds_and_removes_keep_a_random_set ::
222{
223 check.seeded
224 ~seed: 105
225 ~runs: 50
226 fn
227 {
228 let ids = gen.list ~min: 1 ~max: 200 fn { gen.int ~low: 0 ~high: 400 }
229 // An id's operation is fixed: a multiple of 3 removes it, anything
230 // else adds it.
231 let b =
232 list.fold
233 ids
234 (bitmap.empty ())
235 fn b id
236 {
237 if id % 3 == 0
238 {
239 bitmap.remove b id
240 }
241 else
242 {
243 bitmap.add b id
244 }
245 }
246 let expected = sorted_unique (list.filter ids fn id { id % 3 != 0 })
247 bitmap.to_list b == expected
248 && list.all ids fn id { bitmap.contains b id == (id % 3 != 0) }
249 }
250 fn ok { ok }
251}