1import { describe, it } from "@effect/vitest"
2import { assertNone, assertSome, deepStrictEqual, strictEqual, throws } from "@effect/vitest/utils"
3import * as Equal from "effect/Equal"
4import { pipe } from "effect/Function"
5import * as Hash from "effect/Hash"
6import * as Option from "effect/Option"
7import * as Result from "effect/Result"
8import * as Trie from "effect/Trie"
9
10describe("Trie", () => {
11 it("equality rejects tries with different numbers of entries after a hash collision", () => {
12 // Makes the "a" entry collide with the empty trie.
13 const value = {
14 [Hash.symbol]: () => -1520130700
15 }
16 const empty = Trie.empty<typeof value>()
17 const nonEmpty = Trie.make(["a", value])
18
19 strictEqual(Hash.hash(empty), Hash.hash(nonEmpty))
20 strictEqual(Equal.equals(empty, nonEmpty), false, "tries with different sizes must not be equal")
21 })
22
23 it("toString renders entries in iteration order", () => {
24 const trie = pipe(
25 Trie.empty<number>(),
26 Trie.insert("a", 0),
27 Trie.insert("b", 1)
28 )
29
30 strictEqual(
31 String(trie),
32 `Trie([["a",0],["b",1]])`
33 )
34 })
35
36 it("toJSON renders tagged entries", () => {
37 const trie = pipe(
38 Trie.empty<number>(),
39 Trie.insert("a", 0),
40 Trie.insert("b", 1)
41 )
42
43 deepStrictEqual(trie.toJSON(), { _id: "Trie", values: [["a", 0], ["b", 1]] })
44 })
45
46 it("inspect renders the JSON representation", () => {
47 if (typeof window !== "undefined") {
48 return
49 }
50 // oxlint-disable-next-line @typescript-eslint/no-require-imports
51 const { inspect } = require("node:util")
52
53 const trie = pipe(
54 Trie.empty<number>(),
55 Trie.insert("a", 0),
56 Trie.insert("b", 1)
57 )
58
59 deepStrictEqual(inspect(trie), inspect({ _id: "Trie", values: [["a", 0], ["b", 1]] }))
60 })
61
62 it("iterates no entries for an empty trie", () => {
63 const trie = Trie.empty<string>()
64
65 strictEqual(Trie.size(trie), 0)
66 deepStrictEqual(Array.from(trie), [])
67 })
68
69 it("insert returns new tries and orders entries by key", () => {
70 const trie1 = Trie.empty<number>().pipe(
71 Trie.insert("call", 0)
72 )
73
74 const trie2 = trie1.pipe(Trie.insert("me", 1))
75 const trie3 = trie2.pipe(Trie.insert("mind", 2))
76 const trie4 = trie3.pipe(Trie.insert("mid", 3))
77
78 deepStrictEqual(Array.from(trie1), [["call", 0]])
79 deepStrictEqual(Array.from(trie2), [["call", 0], ["me", 1]])
80 deepStrictEqual(Array.from(trie3), [["call", 0], ["me", 1], ["mind", 2]])
81 deepStrictEqual(Array.from(trie4), [["call", 0], ["me", 1], ["mid", 3], ["mind", 2]])
82 })
83
84 it("insert replaces a key without mutating or growing the original", () => {
85 const before = Trie.make(["a", 1])
86 const after = Trie.insert(before, "a", 2)
87
88 deepStrictEqual(
89 [Array.from(before), Trie.size(before), Array.from(after), Trie.size(after)],
90 [[["a", 1]], 1, [["a", 2]], 1],
91 "replacement must be immutable and preserve size"
92 )
93 })
94
95 it("fromIterable preserves an empty iterable", () => {
96 const iterable: Array<[string, number]> = []
97 const trie = Trie.fromIterable(iterable)
98 deepStrictEqual(Array.from(trie), iterable)
99 })
100
101 it("make builds a trie from entry pairs", () => {
102 const trie = Trie.make(["ca", 0], ["me", 1])
103 deepStrictEqual(Array.from(trie), [["ca", 0], ["me", 1]])
104 strictEqual(Equal.equals(Trie.fromIterable([["ca", 0], ["me", 1]]), trie), true)
105 })
106
107 it("fromIterable builds the same trie as make", () => {
108 const iterable: Array<[string, number]> = [["ca", 0], ["me", 1]]
109 const trie = Trie.fromIterable(iterable)
110 deepStrictEqual(Array.from(trie), iterable)
111 strictEqual(Equal.equals(Trie.make(["ca", 0], ["me", 1]), trie), true)
112 })
113
114 it("fromIterable orders entries by key", () => {
115 const iterable: Array<readonly [string, number]> = [["call", 0], ["me", 1], ["mind", 2], ["mid", 3]]
116 const trie = Trie.fromIterable(iterable)
117 deepStrictEqual(Array.from(trie), [["call", 0], ["me", 1], ["mid", 3], ["mind", 2]])
118 })
119
120 it("fromIterable preserves already sorted entries", () => {
121 const iterable: Array<[string, number]> = [["a", 0], ["b", 1]]
122 const trie = Trie.fromIterable(iterable)
123 deepStrictEqual(Array.from(trie), iterable)
124 })
125
126 it("fromIterable accepts a single entry", () => {
127 const iterable: Array<[string, number]> = [["a", 0]]
128 const trie = Trie.fromIterable(iterable)
129 deepStrictEqual(Array.from(trie), iterable)
130 })
131
132 it("fromIterable orders keys when one key is a prefix", () => {
133 const iterable: Array<[string, number]> = [["shells", 0], ["she", 1]]
134 const trie = Trie.fromIterable(iterable)
135 deepStrictEqual(Array.from(trie), [["she", 1], ["shells", 0]])
136 })
137
138 it("size counts stored keys", () => {
139 const trie = Trie.empty<number>().pipe(
140 Trie.insert("a", 0),
141 Trie.insert("b", 1)
142 )
143
144 strictEqual(Trie.size(trie), 2)
145 })
146
147 it("isEmpty distinguishes empty and populated tries", () => {
148 const trie = Trie.empty<number>()
149 const trie1 = trie.pipe(Trie.insert("ma", 0))
150 strictEqual(Trie.isEmpty(trie), true)
151 strictEqual(Trie.isEmpty(trie1), false)
152 })
153
154 it("get returns Some only for exact keys", () => {
155 const trie = Trie.empty<number>().pipe(
156 Trie.insert("call", 0),
157 Trie.insert("me", 1),
158 Trie.insert("mind", 2),
159 Trie.insert("mid", 3)
160 )
161 assertSome(Trie.get(trie, "call"), 0)
162 assertSome(Trie.get(trie, "me"), 1)
163 assertSome(Trie.get(trie, "mind"), 2)
164 assertSome(Trie.get(trie, "mid"), 3)
165 assertNone(Trie.get(trie, "cale"))
166 assertNone(Trie.get(trie, "ma"))
167 assertNone(Trie.get(trie, "midn"))
168 assertNone(Trie.get(trie, "mea"))
169 })
170
171 it("stores undefined values", () => {
172 const trie = Trie.make(["a", undefined])
173
174 strictEqual(Trie.size(trie), 1)
175 strictEqual(Option.isSome(Trie.get(trie, "a")), true, "an inserted undefined value must remain present")
176 deepStrictEqual(Array.from(trie), [["a", undefined]])
177 })
178
179 it("get distinguishes complete keys from prefixes", () => {
180 const trie = Trie.empty<number>().pipe(
181 Trie.insert("shells", 0),
182 Trie.insert("sells", 1),
183 Trie.insert("she", 2)
184 )
185
186 assertNone(Trie.get(trie, "sell"))
187 assertSome(Trie.get(trie, "sells"), 1)
188 assertNone(Trie.get(trie, "shell"))
189 assertSome(Trie.get(trie, "she"), 2)
190 })
191
192 it("has returns true only for exact keys", () => {
193 const trie = Trie.empty<number>().pipe(
194 Trie.insert("call", 0),
195 Trie.insert("me", 1),
196 Trie.insert("mind", 2),
197 Trie.insert("mid", 3)
198 )
199 strictEqual(Trie.has(trie, "call"), true)
200 strictEqual(Trie.has(trie, "me"), true)
201 strictEqual(Trie.has(trie, "mind"), true)
202 strictEqual(Trie.has(trie, "mid"), true)
203 strictEqual(Trie.has(trie, "cale"), false)
204 strictEqual(Trie.has(trie, "ma"), false)
205 strictEqual(Trie.has(trie, "midn"), false)
206 strictEqual(Trie.has(trie, "mea"), false)
207 })
208
209 it("getUnsafe returns the value or throws when the key is missing", () => {
210 const trie = Trie.empty<number>().pipe(
211 Trie.insert("call", 0),
212 Trie.insert("me", 1)
213 )
214 throws(() => Trie.getUnsafe(trie, "mae"))
215 })
216
217 it("remove deletes a key without mutating the original trie", () => {
218 const trie = Trie.empty<number>().pipe(
219 Trie.insert("call", 0),
220 Trie.insert("me", 1),
221 Trie.insert("mind", 2),
222 Trie.insert("mid", 3)
223 )
224
225 const trie1 = trie.pipe(Trie.remove("call"))
226 const trie2 = trie1.pipe(Trie.remove("mea"))
227
228 deepStrictEqual(Trie.get(trie, "call"), Option.some(0))
229 deepStrictEqual(Trie.get(trie1, "call"), Option.none())
230 deepStrictEqual(Trie.get(trie2, "call"), Option.none())
231
232 deepStrictEqual(Array.from(trie), [["call", 0], ["me", 1], ["mid", 3], ["mind", 2]])
233 deepStrictEqual(Array.from(trie1), [["me", 1], ["mid", 3], ["mind", 2]])
234 deepStrictEqual(Array.from(trie2), [["me", 1], ["mid", 3], ["mind", 2]])
235 })
236
237 it("remove preserves a valued prefix", () => {
238 const trie = Trie.make(["ab", 1], ["abc", 2]).pipe(Trie.remove("abc"))
239
240 deepStrictEqual(Array.from(trie), [["ab", 1]], "valued prefix should remain after removing its extension")
241 })
242
243 it("keys returns keys in sorted order", () => {
244 const trie = Trie.empty<number>().pipe(
245 Trie.insert("cab", 0),
246 Trie.insert("abc", 1),
247 Trie.insert("bca", 2)
248 )
249
250 const result = Array.from(Trie.keys(trie))
251 deepStrictEqual(result, ["abc", "bca", "cab"])
252 })
253
254 it("keys orders nested prefixes alphabetically", () => {
255 const trie = Trie.make(
256 ["abc", 0],
257 ["bac", 0],
258 ["b", 0],
259 ["ca", 0],
260 ["cac", 0],
261 ["c", 0],
262 ["abb", 0],
263 ["ba", 0],
264 ["a", 0],
265 ["bca", 0],
266 ["cab", 0],
267 ["dca", 0],
268 ["ab", 0],
269 ["adc", 0]
270 )
271
272 const result = Array.from(Trie.keys(trie))
273 deepStrictEqual(result, [
274 "a",
275 "ab",
276 "abb",
277 "abc",
278 "adc",
279 "b",
280 "ba",
281 "bac",
282 "bca",
283 "c",
284 "ca",
285 "cab",
286 "cac",
287 "dca"
288 ])
289 })
290
291 it("values follow key iteration order", () => {
292 const trie = Trie.empty<number>().pipe(
293 Trie.insert("call", 0),
294 Trie.insert("me", 1),
295 Trie.insert("and", 2)
296 )
297
298 const result = Array.from(Trie.values(trie))
299 deepStrictEqual(result, [2, 0, 1])
300 })
301
302 it("entries iterates key-value pairs in sorted order", () => {
303 const trie = Trie.empty<number>().pipe(
304 Trie.insert("call", 0),
305 Trie.insert("me", 1)
306 )
307
308 const result = Array.from(Trie.entries(trie))
309 deepStrictEqual(result, [["call", 0], ["me", 1]])
310 })
311
312 it("toEntries returns a sorted entry array", () => {
313 const trie = Trie.empty<number>().pipe(
314 Trie.insert("call", 0),
315 Trie.insert("me", 1)
316 )
317
318 const result = Trie.toEntries(trie)
319 deepStrictEqual(result, [["call", 0], ["me", 1]])
320 })
321
322 it("keysWithPrefix returns matching keys in sorted order", () => {
323 const trie = Trie.empty<number>().pipe(
324 Trie.insert("she", 0),
325 Trie.insert("shells", 1),
326 Trie.insert("sea", 2),
327 Trie.insert("sells", 3),
328 Trie.insert("by", 4),
329 Trie.insert("the", 5),
330 Trie.insert("sea", 6),
331 Trie.insert("shore", 7)
332 )
333
334 const result = Array.from(Trie.keysWithPrefix(trie, "she"))
335 deepStrictEqual(result, ["she", "shells"])
336 })
337
338 it("valuesWithPrefix returns matching values in key order", () => {
339 const trie = pipe(
340 Trie.empty<number>(),
341 Trie.insert("shells", 0),
342 Trie.insert("sells", 1),
343 Trie.insert("sea", 2),
344 Trie.insert("she", 3)
345 )
346
347 const result = Array.from(Trie.valuesWithPrefix(trie, "she"))
348 deepStrictEqual(result, [3, 0])
349 })
350
351 it("entriesWithPrefix returns matching entries in key order", () => {
352 const trie = pipe(
353 Trie.empty<number>(),
354 Trie.insert("shells", 0),
355 Trie.insert("sells", 1),
356 Trie.insert("sea", 2),
357 Trie.insert("she", 3)
358 )
359
360 const result = Array.from(Trie.entriesWithPrefix(trie, "she"))
361 deepStrictEqual(result, [["she", 3], ["shells", 0]])
362 })
363
364 it("toEntriesWithPrefix returns matching entries as an array", () => {
365 const trie = Trie.empty<number>().pipe(
366 Trie.insert("shells", 0),
367 Trie.insert("sells", 1),
368 Trie.insert("sea", 2),
369 Trie.insert("she", 3)
370 )
371
372 const result = Trie.toEntriesWithPrefix(trie, "she")
373 deepStrictEqual(result, [["she", 3], ["shells", 0]])
374 })
375
376 it("longestPrefixOf returns the longest stored key that prefixes the input", () => {
377 const trie = Trie.empty<number>().pipe(
378 Trie.insert("shells", 0),
379 Trie.insert("sells", 1),
380 Trie.insert("she", 2)
381 )
382
383 assertNone(Trie.longestPrefixOf(trie, "sell"))
384 assertSome(Trie.longestPrefixOf(trie, "sells"), ["sells", 1])
385 assertSome(Trie.longestPrefixOf(trie, "shell"), ["she", 2])
386 assertSome(Trie.longestPrefixOf(trie, "shellsort"), ["shells", 0])
387 })
388
389 it("longestPrefixOf ignores valued sibling nodes that do not match the input", () => {
390 const trie = Trie.make(["a", 1], ["b", 2])
391
392 strictEqual(
393 Option.isNone(Trie.longestPrefixOf(trie, "c")),
394 true,
395 "a non-matching sibling must not be reported as a prefix"
396 )
397 })
398
399 it("map transforms values and can use keys", () => {
400 const trie = Trie.empty<number>().pipe(
401 Trie.insert("shells", 0),
402 Trie.insert("sells", 1),
403 Trie.insert("she", 2)
404 )
405
406 const trieMapV = Trie.empty<number>().pipe(
407 Trie.insert("shells", 1),
408 Trie.insert("sells", 2),
409 Trie.insert("she", 3)
410 )
411
412 const trieMapK = Trie.empty<number>().pipe(
413 Trie.insert("shells", 6),
414 Trie.insert("sells", 5),
415 Trie.insert("she", 3)
416 )
417
418 strictEqual(Equal.equals(Trie.map(trie, (v) => v + 1), trieMapV), true)
419 strictEqual(Equal.equals(Trie.map(trie, (_, k) => k.length), trieMapK), true)
420 })
421
422 it("filter keeps entries by value or key", () => {
423 const trie = Trie.empty<number>().pipe(
424 Trie.insert("shells", 0),
425 Trie.insert("sells", 1),
426 Trie.insert("she", 2)
427 )
428
429 const trieMapV = Trie.empty<number>().pipe(
430 Trie.insert("she", 2)
431 )
432
433 const trieMapK = Trie.empty<number>().pipe(
434 Trie.insert("shells", 0),
435 Trie.insert("sells", 1)
436 )
437
438 strictEqual(Equal.equals(Trie.filter(trie, (v) => v > 1), trieMapV), true)
439 strictEqual(Equal.equals(Trie.filter(trie, (_, k) => k.length > 3), trieMapK), true)
440 })
441
442 it("filterMap keeps Result successes and can use keys", () => {
443 const trie = Trie.empty<number>().pipe(
444 Trie.insert("shells", 0),
445 Trie.insert("sells", 1),
446 Trie.insert("she", 2)
447 )
448
449 const trieMapV = Trie.empty<number>().pipe(
450 Trie.insert("she", 2)
451 )
452
453 const trieMapK = Trie.empty<number>().pipe(
454 Trie.insert("shells", 0),
455 Trie.insert("sells", 1)
456 )
457
458 strictEqual(Equal.equals(Trie.filterMap(trie, (v) => v > 1 ? Result.succeed(v) : Result.failVoid), trieMapV), true)
459 strictEqual(
460 Equal.equals(Trie.filterMap(trie, (v, k) => k.length > 3 ? Result.succeed(v) : Result.failVoid), trieMapK),
461 true
462 )
463 })
464
465 it("compact keeps Some values", () => {
466 const trie = Trie.empty<Option.Option<number>>().pipe(
467 Trie.insert("shells", Option.some(0)),
468 Trie.insert("sells", Option.none()),
469 Trie.insert("she", Option.some(2))
470 )
471
472 const trieMapV = Trie.empty<number>().pipe(
473 Trie.insert("shells", 0),
474 Trie.insert("she", 2)
475 )
476
477 strictEqual(Equal.equals(Trie.compact(trie), trieMapV), true)
478 })
479
480 it("modify updates an existing key and ignores a missing key", () => {
481 const trie = Trie.empty<number>().pipe(
482 Trie.insert("shells", 0),
483 Trie.insert("sells", 1),
484 Trie.insert("she", 2)
485 )
486
487 deepStrictEqual(trie.pipe(Trie.modify("she", (v) => v + 10), Trie.get("she")), Option.some(12))
488 strictEqual(Equal.equals(trie.pipe(Trie.modify("me", (v) => v)), trie), true)
489 })
490
491 it("removeMany deletes all matching keys", () => {
492 const trie = Trie.empty<number>().pipe(
493 Trie.insert("shells", 0),
494 Trie.insert("sells", 1),
495 Trie.insert("she", 2)
496 )
497
498 strictEqual(
499 Equal.equals(trie.pipe(Trie.removeMany(["she", "sells"])), Trie.empty<number>().pipe(Trie.insert("shells", 0))),
500 true
501 )
502 })
503
504 it("insertMany inserts all entries", () => {
505 const trie = Trie.empty<number>().pipe(
506 Trie.insert("shells", 0),
507 Trie.insert("sells", 1),
508 Trie.insert("she", 2)
509 )
510
511 const trieInsert = Trie.empty<number>().pipe(
512 Trie.insert("shells", 0),
513 Trie.insertMany(
514 [["sells", 1], ["she", 2]]
515 )
516 )
517
518 strictEqual(
519 Equal.equals(trie, trieInsert),
520 true
521 )
522 })
523
524 it("reduce visits entries in key order", () => {
525 const trie = Trie.empty<number>().pipe(
526 Trie.insert("shells", 0),
527 Trie.insert("sells", 1),
528 Trie.insert("she", 2)
529 )
530
531 strictEqual(
532 trie.pipe(
533 Trie.reduce(0, (acc, n) => acc + n)
534 ),
535 3
536 )
537 strictEqual(
538 trie.pipe(
539 Trie.reduce(10, (acc, n) => acc + n)
540 ),
541 13
542 )
543 strictEqual(
544 trie.pipe(
545 Trie.reduce("", (acc, _, key) => acc + key)
546 ),
547 "sellssheshells"
548 )
549 })
550
551 it("forEach", () => {
552 let value = 0
553
554 Trie.empty<number>().pipe(
555 Trie.insert("shells", 0),
556 Trie.insert("sells", 1),
557 Trie.insert("she", 2),
558 Trie.forEach((n, key) => {
559 value += n + key.length
560 })
561 )
562
563 strictEqual(value, 17)
564 })
565
566 it("Equal compares tries by entries", () => {
567 strictEqual(
568 Equal.equals(Trie.empty<number>(), Trie.empty<number>()),
569 true
570 )
571 strictEqual(
572 Equal.equals(
573 Trie.make(["call", 0], ["me", 1]),
574 Trie.make(["call", 0], ["me", 1])
575 ),
576 true
577 )
578 })
579})