1/**
2 * @since 2.0.0
3 */
4
5import * as Equal_ from "../Equal.ts"
6import { format } from "../Formatter.ts"
7import { dual, identity, pipe } from "../Function.ts"
8import * as Hash from "../Hash.ts"
9import type { Inspectable } from "../Inspectable.ts"
10import { NodeInspectSymbol, toJson } from "../Inspectable.ts"
11import * as Option from "../Option.ts"
12import type { Pipeable } from "../Pipeable.ts"
13import { pipeArguments } from "../Pipeable.ts"
14import { hasProperty } from "../Predicate.ts"
15import * as Result from "../Result.ts"
16import type { NoInfer } from "../Types.ts"
17import { backEdges } from "./hash.ts"
18
19/** @internal */
20export const HashMapTypeId = "~effect/HashMap"
21
22/** @internal */
23export type HashMapTypeId = typeof HashMapTypeId
24
25/** @internal */
26export interface HashMap<out Key, out Value> extends Iterable<[Key, Value]>, Equal_.Equal, Pipeable, Inspectable {
27 readonly [HashMapTypeId]: HashMapTypeId
28}
29
30/** @internal */
31export declare namespace HashMap {
32 export type UpdateFn<V> = (option: Option.Option<V>) => Option.Option<V>
33}
34
35// HAMT Implementation
36
37/** @internal */
38const SHIFT = 5
39/** @internal */
40const BUCKET_SIZE = 1 << SHIFT // 32
41/** @internal */
42// const BITMAP_SIZE = 1 << SHIFT // 32
43/** @internal */
44const MIN_ARRAY_NODE = BUCKET_SIZE / 4 // 8
45/** @internal */
46const MAX_INDEX_NODE = BUCKET_SIZE / 2 // 16
47/** @internal */
48const BITMAP_INDEX_MASK = BUCKET_SIZE - 1 // 31
49
50/** @internal */
51const popcount = (n: number): number => {
52 n = n - ((n >>> 1) & 0x55555555)
53 n = (n & 0x33333333) + ((n >>> 2) & 0x33333333)
54 return (((n + (n >>> 4)) & 0xF0F0F0F) * 0x1010101) >>> 24
55}
56
57/** @internal */
58const mask = (hash: number, shift: number): number => (hash >>> shift) & BITMAP_INDEX_MASK
59
60/** @internal */
61const bitpos = (hash: number, shift: number): number => 1 << mask(hash, shift)
62
63/** @internal */
64const index = (bitmap: number, bit: number): number => popcount(bitmap & (bit - 1))
65
66/** @internal */
67function mergeLeaves<K, V>(
68 edit: number,
69 shift: number,
70 hash1: number,
71 node1: Node<K, V>,
72 hash2: number,
73 node2: Node<K, V>
74): Node<K, V> {
75 if (shift > 32) {
76 throw new Error("HashMap: max depth exceeded")
77 }
78
79 const bit1 = bitpos(hash1, shift)
80 const bit2 = bitpos(hash2, shift)
81
82 if (bit1 === bit2) {
83 const child = mergeLeaves(edit, shift + SHIFT, hash1, node1, hash2, node2)
84 return new IndexedNode(edit, bit1, [child])
85 }
86
87 const bitmap = bit1 | bit2
88 const children: Array<Node<K, V>> = (bit1 >>> 0) < (bit2 >>> 0)
89 ? [node1, node2]
90 : [node2, node1]
91
92 return new IndexedNode(edit, bitmap, children)
93}
94
95const hashMapSeed = Hash.string("HashMap")
96
97const entryHash = (key: unknown, value: unknown): number => Hash.combine(Hash.hash(key), Hash.hash(value))
98
99const childrenHash = <K, V>(children: ReadonlyArray<Node<K, V> | undefined>): number => {
100 let h = 0
101 for (let i = 0; i < children.length; i++) {
102 const child = children[i]
103 if (child) h ^= child.subtreeHash()
104 }
105 return h
106}
107
108/** @internal */
109abstract class Node<K, V> {
110 abstract readonly _tag: "EmptyNode" | "LeafNode" | "IndexedNode" | "CollisionNode" | "ArrayNode"
111 abstract readonly edit: number
112 abstract get size(): number
113 abstract get(shift: number, hash: number, key: K): Option.Option<V>
114 abstract has(shift: number, hash: number, key: K): boolean
115 abstract set(
116 edit: number,
117 shift: number,
118 hash: number,
119 key: K,
120 value: V,
121 added: { value: boolean }
122 ): Node<K, V>
123 abstract remove(
124 edit: number,
125 shift: number,
126 hash: number,
127 key: K,
128 removed: { value: boolean }
129 ): Node<K, V> | undefined
130
131 canEdit(edit: number): boolean {
132 return this.edit === edit
133 }
134
135 /** Cached XOR of this subtree's entry hashes. Cleared by in-place edits. */
136 declare _hash: number | undefined
137
138 abstract computeHash(): number
139
140 subtreeHash(): number {
141 let h = this._hash
142 if (h === undefined) {
143 const seen = backEdges
144 h = this.computeHash()
145 // Cycle hashes depend on the entry point.
146 if (seen === backEdges) {
147 this._hash = h
148 }
149 }
150 return h
151 }
152}
153
154/** @internal */
155class EmptyNode<K, V> extends Node<K, V> {
156 readonly _tag = "EmptyNode"
157
158 readonly edit = 0
159
160 get size(): number {
161 return 0
162 }
163
164 get(_shift: number, _hash: number, _key: K): Option.Option<V> {
165 return Option.none()
166 }
167
168 has(_shift: number, _hash: number, _key: K): boolean {
169 return false
170 }
171
172 set(
173 edit: number,
174 _shift: number,
175 hash: number,
176 key: K,
177 value: V,
178 added: { value: boolean }
179 ): Node<K, V> {
180 added.value = true
181 return new LeafNode(edit, hash, key, value)
182 }
183
184 remove(
185 _edit: number,
186 _shift: number,
187 _hash: number,
188 _key: K,
189 _removed: { value: boolean }
190 ): Node<K, V> | undefined {
191 return this
192 }
193
194 override canEdit(_edit: number): boolean {
195 return false
196 }
197
198 computeHash(): number {
199 return 0
200 }
201}
202
203/** @internal */
204class LeafNode<K, V> extends Node<K, V> {
205 readonly _tag = "LeafNode"
206
207 edit: number
208 readonly hash: number
209 key: K
210 value: V
211
212 constructor(
213 edit: number,
214 hash: number,
215 key: K,
216 value: V
217 ) {
218 super()
219 this.edit = edit
220 this.hash = hash
221 this.key = key
222 this.value = value
223 }
224
225 get size(): number {
226 return 1
227 }
228
229 get(_shift: number, hash: number, key: K): Option.Option<V> {
230 if (this.hash === hash && Equal_.equals(this.key, key)) {
231 return Option.some(this.value)
232 }
233 return Option.none()
234 }
235
236 has(_shift: number, hash: number, key: K): boolean {
237 return this.hash === hash && Equal_.equals(this.key, key)
238 }
239
240 set(
241 edit: number,
242 shift: number,
243 hash: number,
244 key: K,
245 value: V,
246 added: { value: boolean }
247 ): Node<K, V> {
248 if (this.canEdit(edit)) this._hash = undefined
249 if (this.hash === hash && Equal_.equals(this.key, key)) {
250 if (Equal_.equals(this.value, value)) {
251 return this
252 }
253 // Can mutate in-place if edit matches
254 if (this.canEdit(edit)) {
255 this.value = value
256 return this
257 }
258 return new LeafNode(edit, hash, key, value)
259 }
260
261 added.value = true
262
263 if (this.hash === hash) {
264 return new CollisionNode(edit, hash, [[this.key, this.value], [key, value]])
265 }
266
267 const newBit = bitpos(hash, shift)
268 const existingBit = bitpos(this.hash, shift)
269
270 if (newBit === existingBit) {
271 return new IndexedNode(
272 edit,
273 newBit,
274 [this.set(edit, shift + SHIFT, hash, key, value, added)]
275 )
276 }
277
278 const bitmap = newBit | existingBit
279 const nodes: Array<Node<K, V>> = (newBit >>> 0) < (existingBit >>> 0)
280 ? [new LeafNode(edit, hash, key, value), this]
281 : [this, new LeafNode(edit, hash, key, value)]
282
283 return new IndexedNode(edit, bitmap, nodes)
284 }
285
286 remove(
287 _edit: number,
288 _shift: number,
289 hash: number,
290 key: K,
291 removed: { value: boolean }
292 ): Node<K, V> | undefined {
293 if (this.hash === hash && Equal_.equals(this.key, key)) {
294 removed.value = true
295 return undefined
296 }
297 return this
298 }
299
300 computeHash(): number {
301 // `setHash` allows the stored hash to differ from `Hash.hash(key)`.
302 return entryHash(this.key, this.value)
303 }
304}
305
306/** @internal */
307class CollisionNode<K, V> extends Node<K, V> {
308 readonly _tag = "CollisionNode"
309
310 edit: number
311 readonly hash: number
312 entries: Array<[K, V]>
313
314 constructor(
315 edit: number,
316 hash: number,
317 entries: Array<[K, V]>
318 ) {
319 super()
320 this.edit = edit
321 this.hash = hash
322 this.entries = entries
323 }
324
325 get size(): number {
326 return this.entries.length
327 }
328
329 get(_shift: number, hash: number, key: K): Option.Option<V> {
330 if (this.hash !== hash) {
331 return Option.none()
332 }
333
334 for (const [k, v] of this.entries) {
335 if (Equal_.equals(k, key)) {
336 return Option.some(v)
337 }
338 }
339 return Option.none()
340 }
341
342 has(_shift: number, hash: number, key: K): boolean {
343 if (this.hash !== hash) {
344 return false
345 }
346
347 for (const [k] of this.entries) {
348 if (Equal_.equals(k, key)) {
349 return true
350 }
351 }
352 return false
353 }
354
355 set(
356 edit: number,
357 shift: number,
358 hash: number,
359 key: K,
360 value: V,
361 added: { value: boolean }
362 ): Node<K, V> {
363 if (this.canEdit(edit)) this._hash = undefined
364 if (this.hash !== hash) {
365 added.value = true
366 // Need to merge this collision node with new leaf
367 return mergeLeaves(
368 edit,
369 shift,
370 this.hash,
371 this,
372 hash,
373 new LeafNode(edit, hash, key, value)
374 )
375 }
376
377 // Same hash - update or add to collision list
378 for (let i = 0; i < this.entries.length; i++) {
379 if (Equal_.equals(this.entries[i][0], key)) {
380 if (Equal_.equals(this.entries[i][1], value)) {
381 return this
382 }
383 if (this.canEdit(edit)) {
384 this.entries[i] = [key, value]
385 return this
386 }
387 const newEntries = [...this.entries]
388 newEntries[i] = [key, value]
389 return new CollisionNode(edit, this.hash, newEntries)
390 }
391 }
392
393 added.value = true
394 if (this.canEdit(edit)) {
395 this.entries.push([key, value])
396 return this
397 }
398 return new CollisionNode(edit, this.hash, [...this.entries, [key, value]])
399 }
400
401 remove(
402 edit: number,
403 _shift: number,
404 hash: number,
405 key: K,
406 removed: { value: boolean }
407 ): Node<K, V> | undefined {
408 if (this.canEdit(edit)) this._hash = undefined
409 if (this.hash !== hash) {
410 return this
411 }
412
413 const idx = this.entries.findIndex(([k]) => Equal_.equals(k, key))
414 if (idx === -1) {
415 return this
416 }
417
418 removed.value = true
419
420 if (this.entries.length === 1) {
421 return undefined
422 }
423
424 if (this.entries.length === 2) {
425 const remaining = this.entries[idx === 0 ? 1 : 0]
426 return new LeafNode(edit, this.hash, remaining[0], remaining[1])
427 }
428
429 if (this.canEdit(edit)) {
430 this.entries.splice(idx, 1)
431 return this
432 }
433
434 const newEntries = [...this.entries]
435 newEntries.splice(idx, 1)
436 return new CollisionNode(edit, this.hash, newEntries)
437 }
438
439 computeHash(): number {
440 let h = 0
441 const entries = this.entries
442 for (let i = 0; i < entries.length; i++) {
443 h ^= entryHash(entries[i][0], entries[i][1])
444 }
445 return h
446 }
447}
448
449/** @internal */
450class IndexedNode<K, V> extends Node<K, V> {
451 readonly _tag = "IndexedNode"
452
453 edit: number
454 private _size: number | undefined
455 bitmap: number
456 children: Array<Node<K, V>>
457
458 constructor(
459 edit: number,
460 bitmap: number,
461 children: Array<Node<K, V>>
462 ) {
463 super()
464 this.edit = edit
465 this.bitmap = bitmap
466 this.children = children
467 }
468
469 get size(): number {
470 if (this._size === undefined) {
471 this._size = this.children.reduce((acc, child) => acc + child.size, 0)
472 }
473 return this._size
474 }
475
476 get(shift: number, hash: number, key: K): Option.Option<V> {
477 const bit = bitpos(hash, shift)
478 if ((this.bitmap & bit) === 0) {
479 return Option.none()
480 }
481 const idx = index(this.bitmap, bit)
482 return this.children[idx].get(shift + SHIFT, hash, key)
483 }
484
485 has(shift: number, hash: number, key: K): boolean {
486 const bit = bitpos(hash, shift)
487 if ((this.bitmap & bit) === 0) {
488 return false
489 }
490 const idx = index(this.bitmap, bit)
491 return this.children[idx].has(shift + SHIFT, hash, key)
492 }
493
494 set(
495 edit: number,
496 shift: number,
497 hash: number,
498 key: K,
499 value: V,
500 added: { value: boolean }
501 ): Node<K, V> {
502 if (this.canEdit(edit)) this._hash = undefined
503 const bit = bitpos(hash, shift)
504 const idx = index(this.bitmap, bit)
505
506 if ((this.bitmap & bit) !== 0) {
507 // Existing child - update it
508 const child = this.children[idx]
509 const newChild = child.set(edit, shift + SHIFT, hash, key, value, added)
510 if (child === newChild) {
511 return this
512 }
513
514 if (this.canEdit(edit)) {
515 this.children[idx] = newChild
516 return this
517 }
518
519 const newChildren = [...this.children]
520 newChildren[idx] = newChild
521 return new IndexedNode(edit, this.bitmap, newChildren)
522 } else {
523 // New child - insert
524 added.value = true
525 const newChild = new LeafNode(edit, hash, key, value)
526 const newBitmap = this.bitmap | bit
527
528 if (this.canEdit(edit)) {
529 this.children.splice(idx, 0, newChild)
530 this.bitmap = newBitmap
531 this._size = undefined
532
533 if (this.children.length > MAX_INDEX_NODE) {
534 return this.expand(edit, newBitmap, this.children)
535 }
536 return this
537 }
538
539 const newChildren = [...this.children]
540 newChildren.splice(idx, 0, newChild)
541
542 if (newChildren.length > MAX_INDEX_NODE) {
543 return this.expand(edit, newBitmap, newChildren)
544 }
545
546 return new IndexedNode(edit, newBitmap, newChildren)
547 }
548 }
549
550 remove(
551 edit: number,
552 shift: number,
553 hash: number,
554 key: K,
555 removed: { value: boolean }
556 ): Node<K, V> | undefined {
557 if (this.canEdit(edit)) this._hash = undefined
558 const bit = bitpos(hash, shift)
559 if ((this.bitmap & bit) === 0) {
560 return this
561 }
562
563 const idx = index(this.bitmap, bit)
564 const child = this.children[idx]
565 const newChild = child.remove(edit, shift + SHIFT, hash, key, removed)
566
567 if (!removed.value) {
568 return this
569 }
570
571 if (newChild === undefined) {
572 const newBitmap = this.bitmap ^ bit
573 if (newBitmap === 0) {
574 return undefined
575 }
576
577 if (this.children.length === 2) {
578 const remaining = this.children[idx === 0 ? 1 : 0]
579 if (remaining._tag === "LeafNode") {
580 return remaining
581 }
582 }
583
584 if (this.canEdit(edit)) {
585 this.children.splice(idx, 1)
586 this.bitmap = newBitmap
587 this._size = undefined
588 return this
589 }
590
591 const newChildren = [...this.children]
592 newChildren.splice(idx, 1)
593 return new IndexedNode(edit, newBitmap, newChildren)
594 }
595
596 if (child === newChild) {
597 return this
598 }
599
600 if (this.canEdit(edit)) {
601 this.children[idx] = newChild
602 return this
603 }
604
605 const newChildren = [...this.children]
606 newChildren[idx] = newChild
607 return new IndexedNode(edit, this.bitmap, newChildren)
608 }
609
610 private expand(edit: number, bitmap: number, children: Array<Node<K, V>>): ArrayNode<K, V> {
611 const nodes: Array<Node<K, V> | undefined> = new globalThis.Array(BUCKET_SIZE)
612 let j = 0
613 for (let i = 0; i < BUCKET_SIZE; i++) {
614 if ((bitmap & (1 << i)) !== 0) {
615 nodes[i] = children[j++]
616 }
617 }
618 return new ArrayNode(edit, children.length, nodes)
619 }
620
621 computeHash(): number {
622 return childrenHash(this.children)
623 }
624}
625
626/** @internal */
627class ArrayNode<K, V> extends Node<K, V> {
628 readonly _tag = "ArrayNode"
629
630 edit: number
631 private _size: number | undefined
632 count: number
633 children: Array<Node<K, V> | undefined>
634
635 constructor(
636 edit: number,
637 count: number,
638 children: Array<Node<K, V> | undefined>
639 ) {
640 super()
641 this.edit = edit
642 this.count = count
643 this.children = children
644 }
645
646 get size(): number {
647 if (this._size === undefined) {
648 this._size = this.children.reduce<number>((acc, child) => acc + (child?.size ?? 0), 0)
649 }
650 return this._size
651 }
652
653 get(shift: number, hash: number, key: K): Option.Option<V> {
654 const idx = mask(hash, shift)
655 const child = this.children[idx]
656 return child ? child.get(shift + SHIFT, hash, key) : Option.none()
657 }
658
659 has(shift: number, hash: number, key: K): boolean {
660 const idx = mask(hash, shift)
661 const child = this.children[idx]
662 return child ? child.has(shift + SHIFT, hash, key) : false
663 }
664
665 set(
666 edit: number,
667 shift: number,
668 hash: number,
669 key: K,
670 value: V,
671 added: { value: boolean }
672 ): Node<K, V> {
673 if (this.canEdit(edit)) this._hash = undefined
674 const idx = mask(hash, shift)
675 const child = this.children[idx]
676
677 if (child) {
678 const newChild = child.set(edit, shift + SHIFT, hash, key, value, added)
679 if (child === newChild) {
680 return this
681 }
682
683 if (this.canEdit(edit)) {
684 this.children[idx] = newChild
685 return this
686 }
687
688 const newChildren = [...this.children]
689 newChildren[idx] = newChild
690 return new ArrayNode(edit, this.count, newChildren)
691 } else {
692 added.value = true
693 const newChild = new LeafNode(edit, hash, key, value)
694
695 if (this.canEdit(edit)) {
696 this.children[idx] = newChild
697 this.count++
698 this._size = undefined
699 return this
700 }
701
702 const newChildren = [...this.children]
703 newChildren[idx] = newChild
704 return new ArrayNode(edit, this.count + 1, newChildren)
705 }
706 }
707
708 remove(
709 edit: number,
710 shift: number,
711 hash: number,
712 key: K,
713 removed: { value: boolean }
714 ): Node<K, V> | undefined {
715 if (this.canEdit(edit)) this._hash = undefined
716 const idx = mask(hash, shift)
717 const child = this.children[idx]
718
719 if (!child) {
720 return this
721 }
722
723 const newChild = child.remove(edit, shift + SHIFT, hash, key, removed)
724
725 if (!removed.value) {
726 return this
727 }
728
729 const newCount = this.count - (newChild ? 0 : 1)
730
731 if (newCount < MIN_ARRAY_NODE) {
732 return this.pack(edit, idx, newChild)
733 }
734
735 if (child === newChild) {
736 return this
737 }
738
739 if (this.canEdit(edit)) {
740 this.children[idx] = newChild
741 if (!newChild) {
742 this.count = newCount
743 }
744 this._size = undefined
745 return this
746 }
747
748 const newChildren = [...this.children]
749 newChildren[idx] = newChild
750 return new ArrayNode(edit, newCount, newChildren)
751 }
752
753 private pack(
754 edit: number,
755 excludeIdx: number,
756 newChild: Node<K, V> | undefined
757 ): IndexedNode<K, V> {
758 const children: Array<Node<K, V>> = []
759 let bitmap = 0
760 let bit = 1
761
762 for (let i = 0; i < this.children.length; i++) {
763 const child = i === excludeIdx ? newChild : this.children[i]
764 if (child) {
765 children.push(child)
766 bitmap |= bit
767 }
768 bit <<= 1
769 }
770
771 return new IndexedNode(edit, bitmap, children)
772 }
773
774 computeHash(): number {
775 return childrenHash(this.children)
776 }
777}
778
779class HashMapIterator<K, V, A> implements IterableIterator<A> {
780 readonly stack: Array<Node<K, V>>
781 readonly project: (key: K, value: V) => A
782 entries: Array<[K, V]> = []
783 index = 0
784
785 constructor(root: Node<K, V>, project: (key: K, value: V) => A) {
786 this.stack = [root]
787 this.project = project
788 }
789
790 next(): IteratorResult<A> {
791 while (true) {
792 if (this.index < this.entries.length) {
793 const entry = this.entries[this.index++]
794 return { done: false, value: this.project(entry[0], entry[1]) }
795 }
796 if (this.stack.length === 0) {
797 return { done: true, value: undefined }
798 }
799 const node = this.stack.pop()!
800 switch (node._tag) {
801 case "LeafNode": {
802 const leaf = node as LeafNode<K, V>
803 return { done: false, value: this.project(leaf.key, leaf.value) }
804 }
805 case "CollisionNode": {
806 this.entries = (node as CollisionNode<K, V>).entries
807 this.index = 0
808 break
809 }
810 case "IndexedNode":
811 case "ArrayNode": {
812 const children = (node as IndexedNode<K, V> | ArrayNode<K, V>).children
813 for (let i = children.length - 1; i >= 0; i--) {
814 const child = children[i]
815 if (child) this.stack.push(child)
816 }
817 }
818 }
819 }
820 }
821
822 [Symbol.iterator](): IterableIterator<A> {
823 return this
824 }
825}
826
827const toEntry = <K, V>(key: K, value: V): [K, V] => [key, value]
828const toValue = <V>(_: unknown, value: V): V => value
829
830/** @internal */
831class HashMapImpl<K, V> implements HashMap<K, V> {
832 readonly [HashMapTypeId]: HashMapTypeId = HashMapTypeId
833
834 _editable: boolean
835 _edit: number
836 _root: Node<K, V>
837 _size: number
838
839 constructor(
840 editable: boolean,
841 edit: number,
842 root: Node<K, V>,
843 size: number
844 ) {
845 this._editable = editable
846 this._edit = edit
847 this._root = root
848 this._size = size
849 }
850
851 get size(): number {
852 return this._size
853 }
854
855 [Symbol.iterator](): IterableIterator<[K, V]> {
856 return new HashMapIterator(this._root, toEntry)
857 }
858
859 [Equal_.symbol](that: Equal_.Equal): boolean {
860 if (isHashMap(that)) {
861 const thatImpl = that as HashMapImpl<K, V>
862 if (this.size !== thatImpl.size) {
863 return false
864 }
865 for (const [key, value] of this) {
866 const otherValue = pipe(that, get(key))
867 if (Option.isNone(otherValue) || !Equal_.equals(value, otherValue.value)) {
868 return false
869 }
870 }
871 return true
872 }
873 return false
874 }
875
876 [Hash.symbol](): number {
877 return Hash.optimize(hashMapSeed ^ this._root.subtreeHash())
878 }
879
880 [NodeInspectSymbol](): unknown {
881 return toJson(this)
882 }
883
884 toString(): string {
885 return `HashMap(${format(Array.from(this))})`
886 }
887
888 toJSON(): unknown {
889 return {
890 _id: "HashMap",
891 values: Array.from(this).map(([k, v]) => [toJson(k), toJson(v)])
892 }
893 }
894
895 pipe() {
896 return pipeArguments(this, arguments)
897 }
898}
899
900/** @internal */
901const emptyNode = new EmptyNode<any, any>()
902
903/** @internal */
904export const isHashMap: {
905 <K, V>(u: Iterable<readonly [K, V]>): u is HashMap<K, V>
906 (u: unknown): u is HashMap<unknown, unknown>
907} = (u: unknown): u is HashMap<unknown, unknown> => hasProperty(u, HashMapTypeId)
908
909/** @internal */
910export const empty = <K = never, V = never>(): HashMap<K, V> => new HashMapImpl(false, 0, emptyNode, 0)
911
912/** @internal */
913export const make = <Entries extends ReadonlyArray<readonly [any, any]>>(
914 ...entries: Entries
915): HashMap<
916 Entries[number] extends readonly [infer K, any] ? K : never,
917 Entries[number] extends readonly [any, infer V] ? V : never
918> => fromIterable(entries)
919
920/** @internal */
921export const fromIterable = <K, V>(entries: Iterable<readonly [K, V]>): HashMap<K, V> => {
922 let root: Node<K, V> = emptyNode
923 let size = 0
924 const added = { value: false }
925
926 for (const [key, value] of entries) {
927 const hash = Hash.hash(key)
928 added.value = false
929 root = root.set(NaN, 0, hash, key, value, added)
930 if (added.value) {
931 size++
932 }
933 }
934
935 return new HashMapImpl(false, 0, root, size)
936}
937
938/** @internal */
939export const isEmpty = <K, V>(self: HashMap<K, V>): boolean => (self as HashMapImpl<K, V>).size === 0
940
941/** @internal */
942export const get = dual<
943 <K1 extends K, K>(key: K1) => <V>(self: HashMap<K, V>) => Option.Option<V>,
944 <K1 extends K, K, V>(self: HashMap<K, V>, key: K1) => Option.Option<V>
945>(2, <K, V>(self: HashMap<K, V>, key: K): Option.Option<V> => {
946 const impl = self as HashMapImpl<K, V>
947 return impl._root.get(0, Hash.hash(key), key)
948})
949
950/** @internal */
951export const getHash = dual<
952 <K1 extends K, K>(key: K1, hash: number) => <V>(self: HashMap<K, V>) => Option.Option<V>,
953 <K1 extends K, K, V>(self: HashMap<K, V>, key: K1, hash: number) => Option.Option<V>
954>(3, <K, V>(self: HashMap<K, V>, key: K, hash: number): Option.Option<V> => {
955 const impl = self as HashMapImpl<K, V>
956 return impl._root.get(0, hash, key)
957})
958
959/** @internal */
960export const getUnsafe = dual<
961 <K1 extends K, K>(key: K1) => <V>(self: HashMap<K, V>) => V,
962 <K1 extends K, K, V>(self: HashMap<K, V>, key: K1) => V
963>(2, <K, V>(self: HashMap<K, V>, key: K): V => {
964 const result = get(self, key)
965 if (Option.isSome(result)) {
966 return result.value
967 }
968 throw new Error(`HashMap.getUnsafe: key not found: ${key}`)
969})
970
971/** @internal */
972export const has = dual<
973 <K1 extends K, K>(key: K1) => <V>(self: HashMap<K, V>) => boolean,
974 <K1 extends K, K, V>(self: HashMap<K, V>, key: K1) => boolean
975>(2, <K, V>(self: HashMap<K, V>, key: K): boolean => {
976 const impl = self as HashMapImpl<K, V>
977 return impl._root.has(0, Hash.hash(key), key)
978})
979
980/** @internal */
981export const hasHash = dual<
982 <K1 extends K, K>(key: K1, hash: number) => <V>(self: HashMap<K, V>) => boolean,
983 <K1 extends K, K, V>(self: HashMap<K, V>, key: K1, hash: number) => boolean
984>(3, <K, V>(self: HashMap<K, V>, key: K, hash: number): boolean => {
985 const impl = self as HashMapImpl<K, V>
986 return impl._root.has(0, hash, key)
987})
988
989/** @internal */
990export const hasBy = dual<
991 <K, V>(predicate: (value: NoInfer<V>, key: NoInfer<K>) => boolean) => (self: HashMap<K, V>) => boolean,
992 <K, V>(self: HashMap<K, V>, predicate: (value: NoInfer<V>, key: NoInfer<K>) => boolean) => boolean
993>(2, <K, V>(self: HashMap<K, V>, predicate: (value: V, key: K) => boolean): boolean => {
994 for (const [key, value] of self) {
995 if (predicate(value, key)) {
996 return true
997 }
998 }
999 return false
1000})
1001
1002const setHash = <K, V>(self: HashMap<K, V>, key: K, hash: number, value: V): HashMap<K, V> => {
1003 const impl = self as HashMapImpl<K, V>
1004 const added = { value: false }
1005
1006 // Pass edit context: use current edit if editable, otherwise NaN (never matches any edit)
1007 const edit = impl._editable ? impl._edit : NaN
1008 const newRoot = impl._root.set(edit, 0, hash, key, value, added)
1009
1010 if (impl._editable) {
1011 // In-place mutation
1012 impl._root = newRoot
1013 if (added.value) {
1014 impl._size++
1015 }
1016 return self
1017 }
1018
1019 // Immutable: create new instance if changed
1020 if (impl._root === newRoot) {
1021 return self
1022 }
1023
1024 return new HashMapImpl(false, impl._edit, newRoot, impl._size + (added.value ? 1 : 0))
1025}
1026
1027/** @internal */
1028export const set = dual<
1029 <K, V>(key: K, value: V) => (self: HashMap<K, V>) => HashMap<K, V>,
1030 <K, V>(self: HashMap<K, V>, key: K, value: V) => HashMap<K, V>
1031>(3, <K, V>(self: HashMap<K, V>, key: K, value: V): HashMap<K, V> => {
1032 return setHash(self, key, Hash.hash(key), value)
1033})
1034
1035/** @internal */
1036export const keys = <K, V>(self: HashMap<K, V>): IterableIterator<K> =>
1037 new HashMapIterator((self as HashMapImpl<K, V>)._root, identity)
1038
1039/** @internal */
1040export const values = <K, V>(self: HashMap<K, V>): IterableIterator<V> =>
1041 new HashMapIterator((self as HashMapImpl<K, V>)._root, toValue)
1042
1043/** @internal */
1044export const entries = <K, V>(self: HashMap<K, V>): IterableIterator<[K, V]> =>
1045 (self as HashMapImpl<K, V>)[Symbol.iterator]()
1046
1047/** @internal */
1048export const size = <K, V>(self: HashMap<K, V>): number => (self as HashMapImpl<K, V>).size
1049
1050/** @internal */
1051export const beginMutation = <K, V>(self: HashMap<K, V>): HashMap<K, V> => {
1052 const impl = self as HashMapImpl<K, V>
1053 return new HashMapImpl(true, impl._edit + 1, impl._root, impl._size)
1054}
1055
1056/** @internal */
1057export const endMutation = <K, V>(self: HashMap<K, V>): HashMap<K, V> => {
1058 const impl = self as HashMapImpl<K, V>
1059 impl._editable = false
1060 return self
1061}
1062
1063/** @internal */
1064export const mutate = dual<
1065 <K, V>(f: (self: HashMap<K, V>) => void) => (self: HashMap<K, V>) => HashMap<K, V>,
1066 <K, V>(self: HashMap<K, V>, f: (self: HashMap<K, V>) => void) => HashMap<K, V>
1067>(2, <K, V>(self: HashMap<K, V>, f: (self: HashMap<K, V>) => void): HashMap<K, V> => {
1068 const mutable = beginMutation(self)
1069 f(mutable)
1070 return endMutation(mutable)
1071})
1072
1073/** @internal */
1074export const modifyAt = dual<
1075 <K, V>(key: K, f: HashMap.UpdateFn<V>) => (self: HashMap<K, V>) => HashMap<K, V>,
1076 <K, V>(self: HashMap<K, V>, key: K, f: HashMap.UpdateFn<V>) => HashMap<K, V>
1077>(3, <K, V>(self: HashMap<K, V>, key: K, f: HashMap.UpdateFn<V>): HashMap<K, V> => {
1078 const current = get(self, key)
1079 const updated = f(current)
1080
1081 if (Option.isNone(updated)) {
1082 return has(self, key) ? remove(self, key) : self
1083 }
1084
1085 return set(self, key, updated.value)
1086})
1087
1088/** @internal */
1089export const modifyHash = dual<
1090 <K, V>(key: K, hash: number, f: HashMap.UpdateFn<V>) => (self: HashMap<K, V>) => HashMap<K, V>,
1091 <K, V>(self: HashMap<K, V>, key: K, hash: number, f: HashMap.UpdateFn<V>) => HashMap<K, V>
1092>(4, <K, V>(self: HashMap<K, V>, key: K, hash: number, f: HashMap.UpdateFn<V>): HashMap<K, V> => {
1093 const current = getHash(self, key, hash)
1094 const updated = f(current)
1095
1096 if (Option.isNone(updated)) {
1097 return hasHash(self, key, hash) ? removeHash(self, key, hash) : self
1098 }
1099
1100 return setHash(self, key, hash, updated.value)
1101})
1102
1103/** @internal */
1104export const modify = dual<
1105 <K, V>(key: K, f: (v: V) => V) => (self: HashMap<K, V>) => HashMap<K, V>,
1106 <K, V>(self: HashMap<K, V>, key: K, f: (v: V) => V) => HashMap<K, V>
1107>(3, <K, V>(self: HashMap<K, V>, key: K, f: (v: V) => V): HashMap<K, V> => {
1108 return modifyAt(self, key, Option.map(f))
1109})
1110
1111/** @internal */
1112export const union = dual<
1113 <K1, V1>(that: HashMap<K1, V1>) => <K0, V0>(self: HashMap<K0, V0>) => HashMap<K1 | K0, V1 | V0>,
1114 <K0, V0, K1, V1>(self: HashMap<K0, V0>, that: HashMap<K1, V1>) => HashMap<K0 | K1, V0 | V1>
1115>(2, <K0, V0, K1, V1>(self: HashMap<K0, V0>, that: HashMap<K1, V1>): HashMap<K0 | K1, V0 | V1> => {
1116 let result = self as HashMap<K0 | K1, V0 | V1>
1117 for (const [key, value] of that) {
1118 result = set(result, key, value)
1119 }
1120 return result
1121})
1122
1123const removeHash = <K, V>(self: HashMap<K, V>, key: K, hash: number): HashMap<K, V> => {
1124 const impl = self as HashMapImpl<K, V>
1125 const removed = { value: false }
1126
1127 const edit = impl._editable ? impl._edit : NaN
1128 const newRoot = impl._root.remove(edit, 0, hash, key, removed)
1129
1130 if (!removed.value) {
1131 return self
1132 }
1133
1134 if (impl._editable) {
1135 impl._root = newRoot ?? emptyNode
1136 impl._size--
1137 return self
1138 }
1139
1140 if (newRoot === undefined) {
1141 return empty()
1142 }
1143
1144 return new HashMapImpl(false, impl._edit, newRoot, impl._size - 1)
1145}
1146
1147/** @internal */
1148export const remove = dual<
1149 <K>(key: K) => <V>(self: HashMap<K, V>) => HashMap<K, V>,
1150 <K, V>(self: HashMap<K, V>, key: K) => HashMap<K, V>
1151>(2, <K, V>(self: HashMap<K, V>, key: K): HashMap<K, V> => {
1152 return removeHash(self, key, Hash.hash(key))
1153})
1154
1155/** @internal */
1156export const removeMany = dual<
1157 <K>(keys: Iterable<K>) => <V>(self: HashMap<K, V>) => HashMap<K, V>,
1158 <K, V>(self: HashMap<K, V>, keys: Iterable<K>) => HashMap<K, V>
1159>(2, <K, V>(self: HashMap<K, V>, keys: Iterable<K>): HashMap<K, V> => {
1160 let result = self
1161 for (const key of keys) {
1162 result = remove(result, key)
1163 }
1164 return result
1165})
1166
1167/** @internal */
1168export const setMany = dual<
1169 <K, V>(entries: Iterable<readonly [K, V]>) => (self: HashMap<K, V>) => HashMap<K, V>,
1170 <K, V>(self: HashMap<K, V>, entries: Iterable<readonly [K, V]>) => HashMap<K, V>
1171>(2, <K, V>(self: HashMap<K, V>, entries: Iterable<readonly [K, V]>): HashMap<K, V> => {
1172 let result = self
1173 for (const [key, value] of entries) {
1174 result = set(result, key, value)
1175 }
1176 return result
1177})
1178
1179/** @internal */
1180export const map = dual<
1181 <A, V, K>(f: (value: V, key: K) => A) => (self: HashMap<K, V>) => HashMap<K, A>,
1182 <K, V, A>(self: HashMap<K, V>, f: (value: V, key: K) => A) => HashMap<K, A>
1183>(2, <K, V, A>(self: HashMap<K, V>, f: (value: V, key: K) => A): HashMap<K, A> => {
1184 let result = empty<K, A>()
1185 for (const [key, value] of self) {
1186 result = set(result, key, f(value, key))
1187 }
1188 return result
1189})
1190
1191/** @internal */
1192export const flatMap = dual<
1193 <A, K, B>(f: (value: A, key: K) => HashMap<K, B>) => (self: HashMap<K, A>) => HashMap<K, B>,
1194 <K, A, B>(self: HashMap<K, A>, f: (value: A, key: K) => HashMap<K, B>) => HashMap<K, B>
1195>(2, <K, A, B>(self: HashMap<K, A>, f: (value: A, key: K) => HashMap<K, B>): HashMap<K, B> => {
1196 let result = empty<K, B>()
1197 for (const [key, value] of self) {
1198 result = union(result, f(value, key))
1199 }
1200 return result
1201})
1202
1203/** @internal */
1204export const forEach = dual<
1205 <V, K>(f: (value: V, key: K) => void) => (self: HashMap<K, V>) => void,
1206 <V, K>(self: HashMap<K, V>, f: (value: V, key: K) => void) => void
1207>(2, <V, K>(self: HashMap<K, V>, f: (value: V, key: K) => void): void => {
1208 for (const [key, value] of self) {
1209 f(value, key)
1210 }
1211})
1212
1213/** @internal */
1214export const reduce = dual<
1215 <Z, V, K>(zero: Z, f: (accumulator: Z, value: V, key: K) => Z) => (self: HashMap<K, V>) => Z,
1216 <K, V, Z>(self: HashMap<K, V>, zero: Z, f: (accumulator: Z, value: V, key: K) => Z) => Z
1217>(3, <K, V, Z>(self: HashMap<K, V>, zero: Z, f: (accumulator: Z, value: V, key: K) => Z): Z => {
1218 let result = zero
1219 for (const [key, value] of self) {
1220 result = f(result, value, key)
1221 }
1222 return result
1223})
1224
1225/** @internal */
1226export const filter = dual<
1227 <K, A>(f: (a: NoInfer<A>, k: K) => boolean) => (self: HashMap<K, A>) => HashMap<K, A>,
1228 <K, A>(self: HashMap<K, A>, f: (a: A, k: K) => boolean) => HashMap<K, A>
1229>(2, <K, A>(self: HashMap<K, A>, f: (a: A, k: K) => boolean) => {
1230 let result = empty<K, A>()
1231 for (const [key, value] of self) {
1232 if (f(value, key)) {
1233 result = set(result, key, value)
1234 }
1235 }
1236 return result
1237})
1238
1239/** @internal */
1240export const compact = <K, A>(self: HashMap<K, Option.Option<A>>): HashMap<K, A> => {
1241 let result = empty<K, A>()
1242 for (const [key, value] of self) {
1243 if (Option.isSome(value)) {
1244 result = set(result, key, value.value)
1245 }
1246 }
1247 return result
1248}
1249
1250/** @internal */
1251export const filterMap = dual<
1252 <A, K, B, X>(f: (input: A, key: K) => Result.Result<B, X>) => (self: HashMap<K, A>) => HashMap<K, B>,
1253 <K, A, B, X>(self: HashMap<K, A>, f: (input: A, key: K) => Result.Result<B, X>) => HashMap<K, B>
1254>(2, <K, A, B, X>(self: HashMap<K, A>, f: (input: A, key: K) => Result.Result<B, X>): HashMap<K, B> => {
1255 let result = empty<K, B>()
1256 for (const [key, value] of self) {
1257 const mapped = f(value, key)
1258 if (Result.isSuccess(mapped)) {
1259 result = set(result, key, mapped.success)
1260 }
1261 }
1262 return result
1263})
1264
1265/** @internal */
1266export const findFirst = dual<
1267 <K, A>(predicate: (a: NoInfer<A>, k: K) => boolean) => (self: HashMap<K, A>) => Option.Option<[K, A]>,
1268 <K, A>(self: HashMap<K, A>, predicate: (a: A, k: K) => boolean) => Option.Option<[K, A]>
1269>(2, <K, A>(self: HashMap<K, A>, predicate: (a: A, k: K) => boolean) => {
1270 for (const [key, value] of self) {
1271 if (predicate(value, key)) {
1272 return Option.some([key, value])
1273 }
1274 }
1275 return Option.none()
1276})
1277
1278/** @internal */
1279export const some = dual<
1280 <K, A>(predicate: (a: NoInfer<A>, k: K) => boolean) => (self: HashMap<K, A>) => boolean,
1281 <K, A>(self: HashMap<K, A>, predicate: (a: A, k: K) => boolean) => boolean
1282>(2, <K, A>(self: HashMap<K, A>, predicate: (a: A, k: K) => boolean): boolean => {
1283 for (const [key, value] of self) {
1284 if (predicate(value, key)) {
1285 return true
1286 }
1287 }
1288 return false
1289})
1290
1291/** @internal */
1292export const every = dual<
1293 <K, A>(predicate: (a: NoInfer<A>, k: K) => boolean) => (self: HashMap<K, A>) => boolean,
1294 <K, A>(self: HashMap<K, A>, predicate: (a: A, k: K) => boolean) => boolean
1295>(2, <K, A>(self: HashMap<K, A>, predicate: (a: A, k: K) => boolean): boolean => {
1296 for (const [key, value] of self) {
1297 if (!predicate(value, key)) {
1298 return false
1299 }
1300 }
1301 return true
1302})