1import { Equal, Hash, HashSet } from "effect"
2import { describe, expect, it } from "vitest"
3
4describe("HashSet", () => {
5 describe("constructors", () => {
6 it("empty creates an empty set", () => {
7 const set = HashSet.empty<string>()
8 expect(HashSet.size(set)).toBe(0)
9 expect(HashSet.isEmpty(set)).toBe(true)
10 })
11
12 it("make creates a set from distinct values", () => {
13 const set = HashSet.make("a", "b", "c")
14 expect(HashSet.size(set)).toBe(3)
15 expect(HashSet.has(set, "a")).toBe(true)
16 expect(HashSet.has(set, "b")).toBe(true)
17 expect(HashSet.has(set, "c")).toBe(true)
18 expect(HashSet.has(set, "d")).toBe(false)
19 })
20
21 it("make removes duplicate values", () => {
22 const set = HashSet.make("a", "b", "a", "c", "b")
23 expect(HashSet.size(set)).toBe(3)
24 expect(HashSet.has(set, "a")).toBe(true)
25 expect(HashSet.has(set, "b")).toBe(true)
26 expect(HashSet.has(set, "c")).toBe(true)
27 })
28
29 it("fromIterable removes duplicate values from an iterable", () => {
30 const set = HashSet.fromIterable(["a", "b", "c", "b", "a"])
31 expect(HashSet.size(set)).toBe(3)
32 expect(HashSet.has(set, "a")).toBe(true)
33 expect(HashSet.has(set, "b")).toBe(true)
34 expect(HashSet.has(set, "c")).toBe(true)
35 })
36 })
37
38 describe("basic operations", () => {
39 it("add returns a new set without mutating the original", () => {
40 const original = HashSet.make("a", "b")
41 const updated = HashSet.add(original, "c")
42
43 // Original unchanged
44 expect(HashSet.size(original)).toBe(2)
45 expect(HashSet.has(original, "c")).toBe(false)
46
47 // Updated has new element
48 expect(HashSet.size(updated)).toBe(3)
49 expect(HashSet.has(updated, "c")).toBe(true)
50 expect(HashSet.has(updated, "a")).toBe(true)
51 expect(HashSet.has(updated, "b")).toBe(true)
52 })
53
54 it("add returns the same set when the value already exists", () => {
55 const original = HashSet.make("a", "b")
56 const same = HashSet.add(original, "a")
57
58 expect(HashSet.size(same)).toBe(2)
59 expect(same).toBe(original) // Should return same reference
60 })
61
62 it("remove returns a new set without mutating the original", () => {
63 const original = HashSet.make("a", "b", "c")
64 const updated = HashSet.remove(original, "b")
65
66 // Original unchanged
67 expect(HashSet.size(original)).toBe(3)
68 expect(HashSet.has(original, "b")).toBe(true)
69
70 // Updated has element removed
71 expect(HashSet.size(updated)).toBe(2)
72 expect(HashSet.has(updated, "b")).toBe(false)
73 expect(HashSet.has(updated, "a")).toBe(true)
74 expect(HashSet.has(updated, "c")).toBe(true)
75 })
76
77 it("remove returns the same set when the value is absent", () => {
78 const original = HashSet.make("a", "b")
79 const same = HashSet.remove(original, "c")
80
81 expect(HashSet.size(same)).toBe(2)
82 expect(same).toBe(original) // Should return same reference
83 })
84
85 it("has checks membership for present and absent values", () => {
86 const set = HashSet.make("a", "b", "c")
87
88 expect(HashSet.has(set, "a")).toBe(true)
89 expect(HashSet.has(set, "b")).toBe(true)
90 expect(HashSet.has(set, "c")).toBe(true)
91 expect(HashSet.has(set, "d")).toBe(false)
92 })
93
94 it("size and isEmpty reflect set cardinality", () => {
95 const empty = HashSet.empty<string>()
96 expect(HashSet.size(empty)).toBe(0)
97 expect(HashSet.isEmpty(empty)).toBe(true)
98
99 const single = HashSet.make("a")
100 expect(HashSet.size(single)).toBe(1)
101 expect(HashSet.isEmpty(single)).toBe(false)
102
103 const multiple = HashSet.make("a", "b", "c")
104 expect(HashSet.size(multiple)).toBe(3)
105 expect(HashSet.isEmpty(multiple)).toBe(false)
106 })
107 })
108
109 describe("set operations", () => {
110 it("union keeps values from both sets", () => {
111 const set1 = HashSet.make("a", "b")
112 const set2 = HashSet.make("b", "c")
113 const result = HashSet.union(set1, set2)
114
115 expect(HashSet.size(result)).toBe(3)
116 expect(HashSet.has(result, "a")).toBe(true)
117 expect(HashSet.has(result, "b")).toBe(true)
118 expect(HashSet.has(result, "c")).toBe(true)
119 })
120
121 it("intersection keeps only values present in both sets", () => {
122 const set1 = HashSet.make("a", "b", "c")
123 const set2 = HashSet.make("b", "c", "d")
124 const result = HashSet.intersection(set1, set2)
125
126 expect(HashSet.size(result)).toBe(2)
127 expect(HashSet.has(result, "b")).toBe(true)
128 expect(HashSet.has(result, "c")).toBe(true)
129 expect(HashSet.has(result, "a")).toBe(false)
130 expect(HashSet.has(result, "d")).toBe(false)
131 })
132
133 it("difference removes values found in the second set", () => {
134 const set1 = HashSet.make("a", "b", "c")
135 const set2 = HashSet.make("b", "d")
136 const result = HashSet.difference(set1, set2)
137
138 expect(HashSet.size(result)).toBe(2)
139 expect(HashSet.has(result, "a")).toBe(true)
140 expect(HashSet.has(result, "c")).toBe(true)
141 expect(HashSet.has(result, "b")).toBe(false)
142 })
143
144 it("isSubset checks whether all values exist in another set", () => {
145 const small = HashSet.make("a", "b")
146 const large = HashSet.make("a", "b", "c", "d")
147 const other = HashSet.make("x", "y")
148
149 expect(HashSet.isSubset(small, large)).toBe(true)
150 expect(HashSet.isSubset(large, small)).toBe(false)
151 expect(HashSet.isSubset(small, other)).toBe(false)
152 expect(HashSet.isSubset(small, small)).toBe(true)
153 })
154 })
155
156 describe("functional operations", () => {
157 it("map transforms every value", () => {
158 const numbers = HashSet.make(1, 2, 3)
159 const doubled = HashSet.map(numbers, (n) => n * 2)
160
161 expect(HashSet.size(doubled)).toBe(3)
162 expect(HashSet.has(doubled, 2)).toBe(true)
163 expect(HashSet.has(doubled, 4)).toBe(true)
164 expect(HashSet.has(doubled, 6)).toBe(true)
165 })
166
167 it("map removes duplicate transformed values", () => {
168 const strings = HashSet.make("apple", "banana", "cherry")
169 const lengths = HashSet.map(strings, (s) => s.length)
170
171 expect(HashSet.size(lengths)).toBe(2) // 5 and 6 (apple=5, banana=6, cherry=6)
172 expect(HashSet.has(lengths, 5)).toBe(true)
173 expect(HashSet.has(lengths, 6)).toBe(true)
174 })
175
176 it("filter keeps values that satisfy the predicate", () => {
177 const numbers = HashSet.make(1, 2, 3, 4, 5, 6)
178 const evens = HashSet.filter(numbers, (n) => n % 2 === 0)
179
180 expect(HashSet.size(evens)).toBe(3)
181 expect(HashSet.has(evens, 2)).toBe(true)
182 expect(HashSet.has(evens, 4)).toBe(true)
183 expect(HashSet.has(evens, 6)).toBe(true)
184 expect(HashSet.has(evens, 1)).toBe(false)
185 })
186
187 it("some returns true when any value satisfies the predicate", () => {
188 const numbers = HashSet.make(1, 2, 3, 4, 5)
189
190 expect(HashSet.some(numbers, (n) => n > 3)).toBe(true)
191 expect(HashSet.some(numbers, (n) => n > 10)).toBe(false)
192
193 const empty = HashSet.empty<number>()
194 expect(HashSet.some(empty, (n) => n > 0)).toBe(false)
195 })
196
197 it("every returns true when all values satisfy the predicate", () => {
198 const evens = HashSet.make(2, 4, 6, 8)
199
200 expect(HashSet.every(evens, (n) => n % 2 === 0)).toBe(true)
201 expect(HashSet.every(evens, (n) => n > 5)).toBe(false)
202
203 const empty = HashSet.empty<number>()
204 expect(HashSet.every(empty, (n) => n > 0)).toBe(true) // vacuously true
205 })
206
207 it("reduce folds every value into an accumulator", () => {
208 const numbers = HashSet.make(1, 2, 3, 4, 5)
209 const sum = HashSet.reduce(numbers, 0, (acc, n) => acc + n)
210
211 expect(sum).toBe(15)
212
213 const empty = HashSet.empty<number>()
214 const zeroSum = HashSet.reduce(empty, 0, (acc, n) => acc + n)
215 expect(zeroSum).toBe(0)
216 })
217 })
218
219 describe("iteration", () => {
220 it("Symbol.iterator iterates over the set values", () => {
221 const set = HashSet.make("a", "b", "c")
222 const values = Array.from(set).sort()
223
224 expect(values).toEqual(["a", "b", "c"])
225 })
226
227 it("supports for...of iteration", () => {
228 const set = HashSet.make("x", "y", "z")
229 const collected = []
230
231 for (const value of set) {
232 collected.push(value)
233 }
234
235 expect(collected.sort()).toEqual(["x", "y", "z"])
236 })
237 })
238
239 describe("equality and hashing", () => {
240 it("structural equality ignores insertion order", () => {
241 const set1 = HashSet.make("a", "b", "c")
242 const set2 = HashSet.make("c", "b", "a") // Different order
243 const set3 = HashSet.make("a", "b", "d") // Different content
244
245 expect(Equal.equals(set1, set2)).toBe(true)
246 expect(Equal.equals(set1, set3)).toBe(false)
247 })
248
249 it("hash is consistent for sets with the same values", () => {
250 const set1 = HashSet.make("a", "b", "c")
251 const set2 = HashSet.make("c", "b", "a") // Same content, different order
252
253 expect(Hash.hash(set1)).toBe(Hash.hash(set2))
254 })
255 })
256
257 describe("custom Equal objects", () => {
258 class Person implements Equal.Equal {
259 constructor(readonly id: string, readonly name: string) {}
260
261 [Equal.symbol](other: unknown): boolean {
262 return other instanceof Person && this.id === other.id
263 }
264
265 [Hash.symbol](): number {
266 return Hash.string(this.id)
267 }
268 }
269
270 it("uses Equal and Hash implementations for membership and uniqueness", () => {
271 const alice1 = new Person("1", "Alice")
272 const alice2 = new Person("1", "Alice") // Same ID
273 const bob = new Person("2", "Bob")
274
275 const people = HashSet.make(alice1, bob)
276
277 expect(HashSet.has(people, alice2)).toBe(true) // Should find by ID
278 expect(HashSet.size(people)).toBe(2)
279
280 const withDuplicate = HashSet.add(people, alice2)
281 expect(HashSet.size(withDuplicate)).toBe(2) // Should not add duplicate
282 })
283 })
284
285 describe("type guards", () => {
286 it("isHashSet identifies HashSet values", () => {
287 const set = HashSet.make("a", "b", "c")
288 const array = ["a", "b", "c"]
289 const object = { a: 1, b: 2 }
290
291 expect(HashSet.isHashSet(set)).toBe(true)
292 expect(HashSet.isHashSet(array)).toBe(false)
293 expect(HashSet.isHashSet(object)).toBe(false)
294 expect(HashSet.isHashSet(null)).toBe(false)
295 expect(HashSet.isHashSet(undefined)).toBe(false)
296 })
297 })
298})