1import { Equal, Hash, HashMap, Option, Result } from "effect"
2import * as fc from "fast-check"
3import { describe, expect, it } from "vitest"
4
5describe("HashMap", () => {
6 describe("constructors", () => {
7 it("empty", () => {
8 const map = HashMap.empty<string, number>()
9 expect(HashMap.isEmpty(map)).toBe(true)
10 expect(HashMap.size(map)).toBe(0)
11 })
12
13 it("make", () => {
14 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
15 expect(HashMap.size(map)).toBe(3)
16 expect(HashMap.get(map, "a")).toEqual(Option.some(1))
17 expect(HashMap.get(map, "b")).toEqual(Option.some(2))
18 expect(HashMap.get(map, "c")).toEqual(Option.some(3))
19 })
20
21 it("fromIterable", () => {
22 const entries = [["a", 1], ["b", 2], ["c", 3]] as const
23 const map = HashMap.fromIterable(entries)
24 expect(HashMap.size(map)).toBe(3)
25 expect(HashMap.get(map, "a")).toEqual(Option.some(1))
26 expect(HashMap.get(map, "b")).toEqual(Option.some(2))
27 expect(HashMap.get(map, "c")).toEqual(Option.some(3))
28 })
29 })
30
31 describe("basic operations", () => {
32 it("modifyHash stores a new key under the supplied hash", () => {
33 const key = {}
34 const hash = 12345
35 const map = HashMap.modifyHash(HashMap.empty<object, string>(), key, hash, () => Option.some("value"))
36
37 expect(HashMap.getHash(map, key, hash)).toEqual(Option.some("value"))
38 })
39
40 it("modifyHash removes a key using the supplied hash", () => {
41 const key = {}
42 const hash = 12345
43 const map = HashMap.modifyHash(HashMap.empty<object, string>(), key, hash, () => Option.some("value"))
44 const removed = HashMap.modifyHash(map, key, hash, () => Option.none())
45
46 expect(HashMap.getHash(removed, key, hash)).toEqual(Option.none())
47 })
48
49 it("get - existing key", () => {
50 const map = HashMap.make(["a", 1], ["b", 2])
51 expect(HashMap.get(map, "a")).toEqual(Option.some(1))
52 expect(HashMap.get(map, "b")).toEqual(Option.some(2))
53 })
54
55 it("get - non-existing key", () => {
56 const map = HashMap.make(["a", 1], ["b", 2])
57 expect(HashMap.get(map, "c")).toEqual(Option.none())
58 })
59
60 it("has - existing key", () => {
61 const map = HashMap.make(["a", 1], ["b", 2])
62 expect(HashMap.has(map, "a")).toBe(true)
63 expect(HashMap.has(map, "b")).toBe(true)
64 })
65
66 it("has - non-existing key", () => {
67 const map = HashMap.make(["a", 1], ["b", 2])
68 expect(HashMap.has(map, "c")).toBe(false)
69 })
70
71 it("set - new key", () => {
72 const map1 = HashMap.make(["a", 1])
73 const map2 = HashMap.set(map1, "b", 2)
74 expect(HashMap.size(map2)).toBe(2)
75 expect(HashMap.get(map2, "a")).toEqual(Option.some(1))
76 expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
77 // Original should be unchanged
78 expect(HashMap.size(map1)).toBe(1)
79 expect(HashMap.has(map1, "b")).toBe(false)
80 })
81
82 it("set - existing key", () => {
83 const map1 = HashMap.make(["a", 1], ["b", 2])
84 const map2 = HashMap.set(map1, "a", 10)
85 expect(HashMap.size(map2)).toBe(2)
86 expect(HashMap.get(map2, "a")).toEqual(Option.some(10))
87 expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
88 // Original should be unchanged
89 expect(HashMap.get(map1, "a")).toEqual(Option.some(1))
90 })
91
92 it("remove - existing key", () => {
93 const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3])
94 const map2 = HashMap.remove(map1, "b")
95 expect(HashMap.size(map2)).toBe(2)
96 expect(HashMap.has(map2, "a")).toBe(true)
97 expect(HashMap.has(map2, "b")).toBe(false)
98 expect(HashMap.has(map2, "c")).toBe(true)
99 // Original should be unchanged
100 expect(HashMap.size(map1)).toBe(3)
101 expect(HashMap.has(map1, "b")).toBe(true)
102 })
103
104 it("remove - non-existing key", () => {
105 const map1 = HashMap.make(["a", 1], ["b", 2])
106 const map2 = HashMap.remove(map1, "c")
107 expect(map1).toBe(map2) // Should return same reference
108 expect(HashMap.size(map2)).toBe(2)
109 })
110
111 it("getUnsafe - existing key", () => {
112 const map = HashMap.make(["a", 1], ["b", 2])
113 expect(HashMap.getUnsafe(map, "a")).toBe(1)
114 expect(HashMap.getUnsafe(map, "b")).toBe(2)
115 })
116
117 it("getUnsafe - non-existing key", () => {
118 const map = HashMap.make(["a", 1])
119 expect(() => HashMap.getUnsafe(map, "b")).toThrow("HashMap.getUnsafe: key not found")
120 })
121 })
122
123 describe("iterators and getters", () => {
124 it("keys", () => {
125 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
126 const keys = Array.from(HashMap.keys(map)).sort()
127 expect(keys).toEqual(["a", "b", "c"])
128 })
129
130 it("values", () => {
131 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
132 const values = Array.from(HashMap.values(map)).sort()
133 expect(values).toEqual([1, 2, 3])
134 })
135
136 it("toValues", () => {
137 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
138 const values = HashMap.toValues(map).sort()
139 expect(values).toEqual([1, 2, 3])
140 })
141
142 it("entries", () => {
143 const map = HashMap.make(["a", 1], ["b", 2])
144 const entries = Array.from(HashMap.entries(map)).sort(([a], [b]) => a.localeCompare(b))
145 expect(entries).toEqual([["a", 1], ["b", 2]])
146 })
147
148 it("toEntries", () => {
149 const map = HashMap.make(["a", 1], ["b", 2])
150 const entries = HashMap.toEntries(map).sort(([a], [b]) => a.localeCompare(b))
151 expect(entries).toEqual([["a", 1], ["b", 2]])
152 })
153
154 it("Symbol.iterator", () => {
155 const map = HashMap.make(["a", 1], ["b", 2])
156 const entries = Array.from(map).sort(([a], [b]) => a.localeCompare(b))
157 expect(entries).toEqual([["a", 1], ["b", 2]])
158 })
159
160 it("preserves traversal order across every node kind", () => {
161 const expectIteration = <A>(iterator: Iterator<A>, expected: ReadonlyArray<A>) => {
162 for (const value of expected) {
163 expect(iterator.next()).toEqual({ done: false, value })
164 }
165 expect(iterator.next()).toEqual({ done: true, value: undefined })
166 expect(iterator.next()).toEqual({ done: true, value: undefined })
167 }
168
169 const empty = HashMap.empty<string, number>()
170 expectIteration(empty[Symbol.iterator](), [])
171 expectIteration(HashMap.entries(empty), [])
172 expectIteration(HashMap.keys(empty), [])
173 expectIteration(HashMap.values(empty), [])
174
175 const input = [
176 ...Array.from({ length: 16 }, (_, i) => [`leaf-${17 - i}`, 17 - i, 17 - i] as const),
177 ["nested-2", 65, 102] as const,
178 ["collision-first", 0, 1] as const,
179 ["nested-0", 1, 100] as const,
180 ["collision-second", 0, 2] as const,
181 ["nested-1", 33, 101] as const
182 ]
183 let map = empty
184 for (const [key, hash, value] of input) {
185 map = HashMap.modifyHash(map, key, hash, () => Option.some(value))
186 }
187
188 const expected: Array<[string, number]> = [
189 ["collision-first", 1],
190 ["collision-second", 2],
191 ["nested-0", 100],
192 ["nested-1", 101],
193 ["nested-2", 102],
194 ...Array.from({ length: 16 }, (_, i) => [`leaf-${i + 2}`, i + 2] as [string, number])
195 ]
196 expectIteration(map[Symbol.iterator](), expected)
197 expectIteration(HashMap.entries(map), expected)
198 expectIteration(HashMap.keys(map), expected.map(([key]) => key))
199 expectIteration(HashMap.values(map), expected.map(([, value]) => value))
200 })
201
202 it("does not expose mutable collision entries", () => {
203 const map = HashMap.make(["fF", 1], ["AA", 2])
204 const entry = Array.from(HashMap.entries(map)).find(([key]) => key === "fF")!
205
206 entry[1] = 99
207
208 expect(HashMap.getUnsafe(map, "fF")).toBe(1)
209 })
210 })
211
212 describe("bulk operations", () => {
213 it("removeMany", () => {
214 const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
215 const map2 = HashMap.removeMany(map1, ["b", "d"])
216 expect(HashMap.size(map2)).toBe(2)
217 expect(HashMap.has(map2, "a")).toBe(true)
218 expect(HashMap.has(map2, "b")).toBe(false)
219 expect(HashMap.has(map2, "c")).toBe(true)
220 expect(HashMap.has(map2, "d")).toBe(false)
221 })
222
223 it("setMany", () => {
224 const map1 = HashMap.make(["a", 1], ["b", 2])
225 const newEntries = [["c", 3], ["d", 4], ["a", 10]] as const // "a" should be overwritten
226 const map2 = HashMap.setMany(map1, newEntries)
227
228 expect(HashMap.size(map2)).toBe(4)
229 expect(HashMap.get(map2, "a")).toEqual(Option.some(10)) // overwritten
230 expect(HashMap.get(map2, "b")).toEqual(Option.some(2)) // preserved
231 expect(HashMap.get(map2, "c")).toEqual(Option.some(3)) // new
232 expect(HashMap.get(map2, "d")).toEqual(Option.some(4)) // new
233 })
234
235 it("setMany - pipe syntax", () => {
236 const map1 = HashMap.empty<string, number>()
237 const map2 = HashMap.setMany([["x", 100], ["y", 200]])(map1)
238
239 expect(HashMap.size(map2)).toBe(2)
240 expect(HashMap.get(map2, "x")).toEqual(Option.some(100))
241 expect(HashMap.get(map2, "y")).toEqual(Option.some(200))
242 })
243
244 it("setMany - different iterables", () => {
245 const map1 = HashMap.make(["existing", 1])
246
247 // Test with Map
248 const jsMap = new Map([["from-map", 2], ["another", 3]])
249 const map2 = HashMap.setMany(map1, jsMap)
250
251 expect(HashMap.size(map2)).toBe(3)
252 expect(HashMap.get(map2, "existing")).toEqual(Option.some(1))
253 expect(HashMap.get(map2, "from-map")).toEqual(Option.some(2))
254 expect(HashMap.get(map2, "another")).toEqual(Option.some(3))
255
256 // Test with Set of tuples
257 const setOfTuples = new Set([["from-set", 4]] as const)
258 const map3 = HashMap.setMany(map2, setOfTuples)
259
260 expect(HashMap.size(map3)).toBe(4)
261 expect(HashMap.get(map3, "from-set")).toEqual(Option.some(4))
262 })
263
264 it("union", () => {
265 const map1 = HashMap.make(["a", 1], ["b", 2])
266 const map2 = HashMap.make(["b", 20], ["c", 3])
267 const map3 = HashMap.union(map1, map2)
268 expect(HashMap.size(map3)).toBe(3)
269 expect(HashMap.get(map3, "a")).toEqual(Option.some(1))
270 expect(HashMap.get(map3, "b")).toEqual(Option.some(20)) // map2 wins
271 expect(HashMap.get(map3, "c")).toEqual(Option.some(3))
272 })
273 })
274
275 describe("mapping operations", () => {
276 it("map", () => {
277 const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3])
278 const map2 = HashMap.map(map1, (value, _key) => value * 2)
279 expect(HashMap.size(map2)).toBe(3)
280 expect(HashMap.get(map2, "a")).toEqual(Option.some(2))
281 expect(HashMap.get(map2, "b")).toEqual(Option.some(4))
282 expect(HashMap.get(map2, "c")).toEqual(Option.some(6))
283 })
284
285 it("flatMap", () => {
286 const map1 = HashMap.make(["a", 1], ["b", 2])
287 const map2 = HashMap.flatMap(map1, (value, key) => HashMap.make([key + "1", value], [key + "2", value * 2]))
288 expect(HashMap.size(map2)).toBe(4)
289 expect(HashMap.get(map2, "a1")).toEqual(Option.some(1))
290 expect(HashMap.get(map2, "a2")).toEqual(Option.some(2))
291 expect(HashMap.get(map2, "b1")).toEqual(Option.some(2))
292 expect(HashMap.get(map2, "b2")).toEqual(Option.some(4))
293 })
294 })
295
296 describe("filtering operations", () => {
297 it("filter", () => {
298 const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
299 const map2 = HashMap.filter(map1, (value) => value % 2 === 0)
300 expect(HashMap.size(map2)).toBe(2)
301 expect(HashMap.has(map2, "a")).toBe(false)
302 expect(HashMap.has(map2, "b")).toBe(true)
303 expect(HashMap.has(map2, "c")).toBe(false)
304 expect(HashMap.has(map2, "d")).toBe(true)
305 })
306
307 it("compact", () => {
308 const map1 = HashMap.make(
309 ["a", Option.some(1)],
310 ["b", Option.none()],
311 ["c", Option.some(3)]
312 )
313 const map2 = HashMap.compact(map1)
314 expect(HashMap.size(map2)).toBe(2)
315 expect(HashMap.get(map2, "a")).toEqual(Option.some(1))
316 expect(HashMap.has(map2, "b")).toBe(false)
317 expect(HashMap.get(map2, "c")).toEqual(Option.some(3))
318 })
319
320 it("filterMap", () => {
321 const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
322 const map2 = HashMap.filterMap(map1, (value) => value % 2 === 0 ? Result.succeed(value * 2) : Result.failVoid)
323 expect(HashMap.size(map2)).toBe(2)
324 expect(HashMap.get(map2, "b")).toEqual(Option.some(4))
325 expect(HashMap.get(map2, "d")).toEqual(Option.some(8))
326 expect(HashMap.has(map2, "a")).toBe(false)
327 expect(HashMap.has(map2, "c")).toBe(false)
328 })
329
330 it("filterMap - key argument", () => {
331 const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
332 const map2 = HashMap.filterMap(
333 map1,
334 (value, key) => key < "c" ? Result.succeed(`${key}:${value}`) : Result.failVoid
335 )
336
337 expect(HashMap.size(map2)).toBe(2)
338 expect(HashMap.get(map2, "a")).toEqual(Option.some("a:1"))
339 expect(HashMap.get(map2, "b")).toEqual(Option.some("b:2"))
340 expect(HashMap.has(map2, "c")).toBe(false)
341 expect(HashMap.has(map2, "d")).toBe(false)
342 })
343 })
344
345 describe("search operations", () => {
346 it("findFirst returns an entry matching both key and value", () => {
347 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
348 const result = HashMap.findFirst(map, (value) => value > 1)
349 expect(result).toEqual(Option.some(["c", 3]))
350 })
351
352 it("findFirst - not found", () => {
353 const map = HashMap.make(["a", 1], ["b", 2])
354 const result = HashMap.findFirst(map, (value) => value > 5)
355 expect(result).toEqual(Option.none())
356 })
357
358 it("some", () => {
359 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
360 expect(HashMap.some(map, (value) => value > 2)).toBe(true)
361 expect(HashMap.some(map, (value) => value > 5)).toBe(false)
362 })
363
364 it("every", () => {
365 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
366 expect(HashMap.every(map, (value) => value > 0)).toBe(true)
367 expect(HashMap.every(map, (value) => value > 1)).toBe(false)
368 })
369
370 it("hasBy", () => {
371 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
372 expect(HashMap.hasBy(map, (value, key) => key === "b" && value === 2)).toBe(true)
373 expect(HashMap.hasBy(map, (value, key) => key === "b" && value === 5)).toBe(false)
374 })
375 })
376
377 describe("modification operations", () => {
378 it("modifyAt - existing key", () => {
379 const map1 = HashMap.make(["a", 1], ["b", 2])
380 const map2 = HashMap.modifyAt(
381 map1,
382 "a",
383 (option) => Option.isSome(option) ? Option.some(option.value * 2) : Option.none()
384 )
385 expect(HashMap.get(map2, "a")).toEqual(Option.some(2))
386 })
387
388 it("modifyAt - non-existing key", () => {
389 const map1 = HashMap.make(["a", 1])
390 const map2 = HashMap.modifyAt(map1, "b", (option) => Option.isSome(option) ? option : Option.some(10))
391 expect(HashMap.get(map2, "b")).toEqual(Option.some(10))
392 })
393
394 it("modifyAt - remove via None", () => {
395 const map1 = HashMap.make(["a", 1], ["b", 2])
396 const map2 = HashMap.modifyAt(map1, "a", () => Option.none())
397 expect(HashMap.has(map2, "a")).toBe(false)
398 expect(HashMap.has(map2, "b")).toBe(true)
399 })
400
401 it("modify", () => {
402 const map1 = HashMap.make(["a", 1], ["b", 2])
403 const map2 = HashMap.modify(map1, "a", (value) => value * 3)
404 expect(HashMap.get(map2, "a")).toEqual(Option.some(3))
405 expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
406 })
407 })
408
409 describe("reduction operations", () => {
410 it("reduce", () => {
411 const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
412 const sum = HashMap.reduce(map, 0, (acc, value) => acc + value)
413 expect(sum).toBe(6)
414 })
415
416 it("forEach visits each key and value", () => {
417 const map = HashMap.make(["a", 1], ["b", 2])
418 const collected: Array<[string, number]> = []
419 HashMap.forEach(map, (value, key) => {
420 collected.push([key, value])
421 })
422 expect(collected.sort()).toEqual([["a", 1], ["b", 2]])
423 })
424 })
425
426 describe("mutation helpers", () => {
427 it("mutate allows in-place modifications", () => {
428 const map1 = HashMap.make(["a", 1])
429 const map2 = HashMap.mutate(map1, (mutable) => {
430 HashMap.set(mutable, "b", 2)
431 HashMap.set(mutable, "c", 3)
432 })
433 // Original should be unchanged
434 expect(HashMap.size(map1)).toBe(1)
435 // Mutated map should have all entries
436 expect(HashMap.size(map2)).toBe(3)
437 expect(HashMap.get(map2, "a")).toEqual(Option.some(1))
438 expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
439 expect(HashMap.get(map2, "c")).toEqual(Option.some(3))
440 })
441
442 it("beginMutation creates distinct mutable instance", () => {
443 const map1 = HashMap.make(["a", 1])
444 const mutable = HashMap.beginMutation(map1)
445
446 // Should be different instances
447 expect(map1).not.toBe(mutable)
448
449 // Mutations on mutable should not affect original
450 HashMap.set(mutable, "b", 2)
451 expect(HashMap.size(map1)).toBe(1)
452 expect(HashMap.size(mutable)).toBe(2)
453
454 // endMutation returns same instance
455 const immutable = HashMap.endMutation(mutable)
456 expect(mutable).toBe(immutable)
457 })
458
459 it("mutations are isolated from original", () => {
460 const original = HashMap.make(["a", 1], ["b", 2])
461 const mutated = HashMap.mutate(original, (m) => {
462 HashMap.set(m, "a", 100)
463 HashMap.remove(m, "b")
464 HashMap.set(m, "c", 3)
465 })
466
467 // Original unchanged
468 expect(HashMap.get(original, "a")).toEqual(Option.some(1))
469 expect(HashMap.get(original, "b")).toEqual(Option.some(2))
470 expect(HashMap.has(original, "c")).toBe(false)
471
472 // Mutated has changes
473 expect(HashMap.get(mutated, "a")).toEqual(Option.some(100))
474 expect(HashMap.has(mutated, "b")).toBe(false)
475 expect(HashMap.get(mutated, "c")).toEqual(Option.some(3))
476 })
477 })
478
479 describe("equality and hashing", () => {
480 it("Equal.equals", () => {
481 const map1 = HashMap.make(["a", 1], ["b", 2])
482 const map2 = HashMap.make(["b", 2], ["a", 1]) // Different order
483 const map3 = HashMap.make(["a", 1], ["b", 3]) // Different value
484
485 expect(Equal.equals(map1, map2)).toBe(true)
486 expect(Equal.equals(map1, map3)).toBe(false)
487 })
488
489 it("Hash.hash", () => {
490 const map1 = HashMap.make(["a", 1], ["b", 2])
491 const map2 = HashMap.make(["b", 2], ["a", 1]) // Different order
492
493 expect(Hash.hash(map1)).toBe(Hash.hash(map2))
494 })
495 })
496
497 describe("custom hash with Equal objects", () => {
498 class Person implements Equal.Equal {
499 constructor(readonly name: string, readonly age: number) {}
500
501 [Equal.symbol](that: Equal.Equal): boolean {
502 return that instanceof Person &&
503 this.name === that.name &&
504 this.age === that.age
505 }
506
507 [Hash.symbol](): number {
508 return Hash.string(this.name) ^ Hash.number(this.age)
509 }
510 }
511
512 it("should work with Equal objects as keys", () => {
513 const person1 = new Person("Alice", 25)
514 const person2 = new Person("Alice", 25) // Same data, different instance
515 const person3 = new Person("Bob", 30)
516
517 const map = HashMap.make([person1, "value1"], [person3, "value3"])
518
519 // Should find value using structurally equal key
520 expect(HashMap.get(map, person2)).toEqual(Option.some("value1"))
521 expect(HashMap.has(map, person2)).toBe(true)
522
523 // Should work with set operation
524 const map2 = HashMap.set(map, person2, "updated")
525 expect(HashMap.get(map2, person1)).toEqual(Option.some("updated"))
526 expect(HashMap.size(map2)).toBe(2) // Should not increase size
527 })
528 })
529
530 describe("regressions", () => {
531 class FixedHashKey implements Equal.Equal {
532 constructor(readonly id: string, readonly hash: number) {}
533
534 [Equal.symbol](that: Equal.Equal): boolean {
535 return that instanceof FixedHashKey && this.id === that.id
536 }
537
538 [Hash.symbol](): number {
539 return this.hash
540 }
541 }
542
543 it("keeps entries addressable when bit 31 is present in indexed leaf insert", () => {
544 const bit31Key = new FixedHashKey("bit31", 31)
545 const bit30Key = new FixedHashKey("bit30", 30)
546
547 let map = HashMap.empty<FixedHashKey, string>()
548 map = HashMap.set(map, bit31Key, "session1")
549 map = HashMap.set(map, bit30Key, "session2")
550
551 expect(HashMap.size(map)).toBe(2)
552 expect(HashMap.get(map, bit31Key)).toEqual(Option.some("session1"))
553 expect(HashMap.get(map, bit30Key)).toEqual(Option.some("session2"))
554 })
555
556 it("keeps entries addressable when mergeLeaves sees bit 31", () => {
557 const collisionA = new FixedHashKey("collisionA", 31)
558 const collisionB = new FixedHashKey("collisionB", 31)
559 const bit30Key = new FixedHashKey("bit30", 30)
560
561 let map = HashMap.empty<FixedHashKey, string>()
562 map = HashMap.set(map, collisionA, "a")
563 map = HashMap.set(map, collisionB, "b")
564 map = HashMap.set(map, bit30Key, "c")
565
566 expect(HashMap.size(map)).toBe(3)
567 expect(HashMap.get(map, collisionA)).toEqual(Option.some("a"))
568 expect(HashMap.get(map, collisionB)).toEqual(Option.some("b"))
569 expect(HashMap.get(map, bit30Key)).toEqual(Option.some("c"))
570 })
571
572 it("keeps all inserted entries addressable across random bit-31-heavy shapes", () => {
573 const entriesArbitrary = fc.array(fc.integer({ min: 0, max: 31 }), { minLength: 0, maxLength: 80 }).chain(
574 (hashes) => {
575 const allHashes = [31, 31, 30, ...hashes]
576 return fc.uniqueArray(fc.uuid(), { minLength: allHashes.length, maxLength: allHashes.length }).map((ids) =>
577 allHashes.map((hash, i) => ({ id: ids[i], hash }))
578 )
579 }
580 )
581
582 fc.assert(
583 fc.property(entriesArbitrary, (entries) => {
584 let map = HashMap.empty<FixedHashKey, string>()
585 const inserted: Array<readonly [FixedHashKey, string]> = []
586
587 for (const entry of entries) {
588 const key = new FixedHashKey(entry.id, entry.hash)
589 const value = `value-${entry.id}`
590 map = HashMap.set(map, key, value)
591 inserted.push([key, value])
592 }
593
594 expect(HashMap.size(map)).toBe(inserted.length)
595 for (const [key, value] of inserted) {
596 expect(HashMap.has(map, key)).toBe(true)
597 expect(HashMap.get(map, key)).toEqual(Option.some(value))
598 }
599 }),
600 { numRuns: 200 }
601 )
602 })
603 })
604
605 describe("type guards", () => {
606 it("isHashMap", () => {
607 const map = HashMap.make(["a", 1])
608 const notMap = { a: 1 }
609
610 expect(HashMap.isHashMap(map)).toBe(true)
611 expect(HashMap.isHashMap(notMap)).toBe(false)
612 expect(HashMap.isHashMap(null)).toBe(false)
613 expect(HashMap.isHashMap(undefined)).toBe(false)
614 })
615 })
616
617 describe("stress tests", () => {
618 it("handles many inserts, lookups, and removals", () => {
619 let map = HashMap.empty<number, string>()
620
621 // Add many entries
622 for (let i = 0; i < 1000; i++) {
623 map = HashMap.set(map, i, `value${i}`)
624 }
625
626 expect(HashMap.size(map)).toBe(1000)
627
628 // Check random entries
629 for (let i = 0; i < 100; i++) {
630 const key = Math.floor(Math.random() * 1000)
631 expect(HashMap.get(map, key)).toEqual(Option.some(`value${key}`))
632 }
633
634 // Remove half the entries
635 for (let i = 0; i < 500; i++) {
636 map = HashMap.remove(map, i)
637 }
638
639 expect(HashMap.size(map)).toBe(500)
640
641 // Verify removals
642 for (let i = 0; i < 500; i++) {
643 expect(HashMap.has(map, i)).toBe(false)
644 }
645 for (let i = 500; i < 1000; i++) {
646 expect(HashMap.has(map, i)).toBe(true)
647 }
648 })
649
650 it("should handle hash collisions", () => {
651 // Create objects with same hash but different equality
652 class CollidingKey implements Equal.Equal {
653 constructor(readonly id: number) {}
654
655 [Equal.symbol](that: Equal.Equal): boolean {
656 return that instanceof CollidingKey && this.id === that.id
657 }
658
659 [Hash.symbol](): number {
660 return 42 // Same hash for all instances
661 }
662 }
663
664 const key1 = new CollidingKey(1)
665 const key2 = new CollidingKey(2)
666 const key3 = new CollidingKey(3)
667
668 let map = HashMap.empty<CollidingKey, string>()
669 map = HashMap.set(map, key1, "value1")
670 map = HashMap.set(map, key2, "value2")
671 map = HashMap.set(map, key3, "value3")
672
673 expect(HashMap.size(map)).toBe(3)
674 expect(HashMap.get(map, key1)).toEqual(Option.some("value1"))
675 expect(HashMap.get(map, key2)).toEqual(Option.some("value2"))
676 expect(HashMap.get(map, key3)).toEqual(Option.some("value3"))
677
678 // Remove one
679 map = HashMap.remove(map, key2)
680 expect(HashMap.size(map)).toBe(2)
681 expect(HashMap.has(map, key1)).toBe(true)
682 expect(HashMap.has(map, key2)).toBe(false)
683 expect(HashMap.has(map, key3)).toBe(true)
684 })
685 })
686})