1/**
2 * Stores unique values in an immutable hash set.
3 *
4 * A `HashSet<A>` contains at most one value for each equality class according
5 * to Effect's `Equal` and `Hash` rules. Membership checks, additions, removals,
6 * and set operations return new sets. This module also includes constructors,
7 * union, intersection, difference, subset checks, mapping, filtering, and
8 * reducing helpers.
9 *
10 * @since 2.0.0
11 */
12
13import type { Equal } from "./Equal.ts"
14import * as Dual from "./Function.ts"
15import type { Inspectable } from "./Inspectable.ts"
16import * as internal from "./internal/hashSet.ts"
17import type { Pipeable } from "./Pipeable.ts"
18import type { Predicate, Refinement } from "./Predicate.ts"
19import type { NoInfer } from "./Types.ts"
20
21const TypeId = internal.HashSetTypeId
22
23/**
24 * A HashSet is an immutable set data structure that provides efficient storage
25 * and retrieval of unique values. It uses a HashMap internally for optimal performance.
26 *
27 * **Example** (Creating and updating a HashSet)
28 *
29 * ```ts import.meta.vitest
30 * import { HashSet } from "effect"
31 *
32 * // Create a HashSet
33 * const set = HashSet.make("apple", "banana", "cherry")
34 *
35 * // Check membership
36 * HashSet.has(set, "apple") // => true
37 * HashSet.has(set, "grape") // => false
38 *
39 * // Add values (returns new HashSet)
40 * const updated = HashSet.add(set, "grape")
41 * updated // => HashSet.make("apple", "banana", "cherry", "grape")
42 *
43 * // Remove values (returns new HashSet)
44 * const smaller = HashSet.remove(set, "banana")
45 * smaller // => HashSet.make("apple", "cherry")
46 * ```
47 *
48 * @category models
49 * @since 2.0.0
50 */
51export interface HashSet<out Value> extends Iterable<Value>, Equal, Pipeable, Inspectable {
52 readonly [TypeId]: typeof TypeId
53}
54
55/**
56 * The HashSet namespace contains type-level utilities and helper types
57 * for working with HashSet instances.
58 *
59 * **Example** (Extracting value types from a HashSet)
60 *
61 * ```ts import.meta.vitest
62 * import { HashSet } from "effect"
63 *
64 * // Create a concrete HashSet for type extraction
65 * const fruits = HashSet.make("apple", "banana", "cherry")
66 *
67 * // Extract the value type for reuse
68 * type Fruit = HashSet.HashSet.Value<typeof fruits> // string
69 *
70 * // Use extracted type in functions
71 * const processFruit = (fruit: Fruit) => {
72 * return `Processing ${fruit}`
73 * }
74 * processFruit("apple") // => "Processing apple"
75 * ```
76 *
77 * @since 2.0.0
78 */
79export declare namespace HashSet {
80 /**
81 * Extracts the element type from a `HashSet`.
82 *
83 * **Details**
84 *
85 * For `HashSet.HashSet<A>`, `HashSet.Value<...>` resolves to `A`.
86 *
87 * **Example** (Extracting a HashSet value type)
88 *
89 * ```ts import.meta.vitest
90 * import { HashSet } from "effect"
91 *
92 * const numbers = HashSet.make(1, 2, 3, 4, 5)
93 *
94 * // Extract the value type
95 * type NumberType = HashSet.HashSet.Value<typeof numbers> // number
96 *
97 * const processNumber = (n: NumberType) => n * 2
98 * processNumber(3) // => 6
99 * ```
100 *
101 * @category utility types
102 * @since 4.0.0
103 */
104 export type Value<T> = T extends HashSet<infer V> ? V : never
105}
106
107/**
108 * Creates an empty HashSet.
109 *
110 * **Example** (Creating an empty HashSet)
111 *
112 * ```ts import.meta.vitest
113 * import { HashSet } from "effect"
114 *
115 * const set = HashSet.empty<string>()
116 *
117 * HashSet.size(set) // => 0
118 * HashSet.isEmpty(set) // => true
119 *
120 * // Add some values
121 * const withValues = HashSet.add(HashSet.add(set, "hello"), "world")
122 * withValues // => HashSet.make("hello", "world")
123 * ```
124 *
125 * @category constructors
126 * @since 2.0.0
127 */
128export const empty: <V = never>() => HashSet<V> = internal.empty
129
130/**
131 * Creates a HashSet from a variable number of values.
132 *
133 * **Example** (Creating a HashSet from values)
134 *
135 * ```ts import.meta.vitest
136 * import { HashSet } from "effect"
137 *
138 * HashSet.make("apple", "banana", "cherry") // => HashSet.make("apple", "banana", "cherry")
139 *
140 * HashSet.make(1, 2, 3, 2, 1) // => HashSet.make(1, 2, 3)
141 *
142 * HashSet.make("hello", 42, true) // => HashSet.make("hello", 42, true)
143 * ```
144 *
145 * @category constructors
146 * @since 2.0.0
147 */
148export const make: <Values extends ReadonlyArray<any>>(
149 ...values: Values
150) => HashSet<Values[number]> = internal.make
151
152/**
153 * Creates a HashSet from an iterable collection of values.
154 *
155 * **Example** (Creating a HashSet from an iterable)
156 *
157 * ```ts import.meta.vitest
158 * import { HashSet } from "effect"
159 *
160 * HashSet.fromIterable(["a", "b", "c", "b", "a"]) // => HashSet.make("a", "b", "c")
161 *
162 * HashSet.fromIterable(new Set([1, 2, 3])) // => HashSet.make(1, 2, 3)
163 *
164 * HashSet.fromIterable("hello") // => HashSet.make("h", "e", "l", "o")
165 * ```
166 *
167 * @category constructors
168 * @since 2.0.0
169 */
170export const fromIterable: <V>(values: Iterable<V>) => HashSet<V> = internal.fromIterable
171
172/**
173 * Checks whether a value is a HashSet.
174 *
175 * **Example** (Checking for a HashSet)
176 *
177 * ```ts import.meta.vitest
178 * import { HashSet } from "effect"
179 *
180 * const set = HashSet.make(1, 2, 3)
181 * const array = [1, 2, 3]
182 *
183 * HashSet.isHashSet(set) // => true
184 * HashSet.isHashSet(array) // => false
185 * HashSet.isHashSet(null) // => false
186 * ```
187 *
188 * @category guards
189 * @since 2.0.0
190 */
191export const isHashSet: {
192 <V>(u: Iterable<V>): u is HashSet<V>
193 (u: unknown): u is HashSet<unknown>
194} = internal.isHashSet
195
196/**
197 * Adds a value to the HashSet, returning a new HashSet.
198 *
199 * **Example** (Adding values to a HashSet)
200 *
201 * ```ts import.meta.vitest
202 * import { HashSet } from "effect"
203 *
204 * const set = HashSet.make("a", "b")
205 * const withC = HashSet.add(set, "c")
206 *
207 * set // => HashSet.make("a", "b")
208 * withC // => HashSet.make("a", "b", "c")
209 * HashSet.has(withC, "c") // => true
210 *
211 * // Adding existing value has no effect
212 * HashSet.add(set, "a") // => HashSet.make("a", "b")
213 * ```
214 *
215 * @category mutations
216 * @since 2.0.0
217 */
218export const add: {
219 <V>(value: V): (self: HashSet<V>) => HashSet<V>
220 <V>(self: HashSet<V>, value: V): HashSet<V>
221} = Dual.dual<
222 <V>(value: V) => (self: HashSet<V>) => HashSet<V>,
223 <V>(self: HashSet<V>, value: V) => HashSet<V>
224>(2, internal.add)
225
226/**
227 * Checks whether the HashSet contains the specified value.
228 *
229 * **Example** (Checking HashSet membership)
230 *
231 * ```ts import.meta.vitest
232 * import { Equal, Hash, HashSet } from "effect"
233 *
234 * // Works with any type that implements Equal
235 *
236 * const set = HashSet.make("apple", "banana", "cherry")
237 *
238 * HashSet.has(set, "apple") // => true
239 * HashSet.has(set, "grape") // => false
240 *
241 * class Person implements Equal.Equal {
242 * constructor(readonly name: string) {}
243 *
244 * [Equal.symbol](other: unknown) {
245 * return other instanceof Person && this.name === other.name
246 * }
247 *
248 * [Hash.symbol](): number {
249 * return Hash.string(this.name)
250 * }
251 * }
252 *
253 * const people = HashSet.make(new Person("Alice"), new Person("Bob"))
254 * HashSet.has(people, new Person("Alice")) // => true
255 * ```
256 *
257 * @category predicates
258 * @since 2.0.0
259 */
260export const has: {
261 <V>(value: V): (self: HashSet<V>) => boolean
262 <V>(self: HashSet<V>, value: V): boolean
263} = Dual.dual<
264 <V>(value: V) => (self: HashSet<V>) => boolean,
265 <V>(self: HashSet<V>, value: V) => boolean
266>(2, internal.has)
267
268/**
269 * Removes a value from the HashSet, returning a new HashSet.
270 *
271 * **Example** (Removing values from a HashSet)
272 *
273 * ```ts import.meta.vitest
274 * import { HashSet } from "effect"
275 *
276 * const set = HashSet.make("a", "b", "c")
277 * const withoutB = HashSet.remove(set, "b")
278 *
279 * set // => HashSet.make("a", "b", "c")
280 * withoutB // => HashSet.make("a", "c")
281 * HashSet.has(withoutB, "b") // => false
282 *
283 * // Removing non-existent value has no effect
284 * HashSet.remove(set, "d") // => HashSet.make("a", "b", "c")
285 * ```
286 *
287 * @category mutations
288 * @since 2.0.0
289 */
290export const remove: {
291 <V>(value: V): (self: HashSet<V>) => HashSet<V>
292 <V>(self: HashSet<V>, value: V): HashSet<V>
293} = Dual.dual<
294 <V>(value: V) => (self: HashSet<V>) => HashSet<V>,
295 <V>(self: HashSet<V>, value: V) => HashSet<V>
296>(2, internal.remove)
297
298/**
299 * Returns the number of values in the HashSet.
300 *
301 * **Example** (Getting the HashSet size)
302 *
303 * ```ts import.meta.vitest
304 * import { HashSet } from "effect"
305 *
306 * HashSet.size(HashSet.empty<string>()) // => 0
307 *
308 * HashSet.size(HashSet.make("a", "b")) // => 2
309 *
310 * HashSet.size(HashSet.fromIterable(["x", "y", "z", "x", "y"])) // => 3
311 * ```
312 *
313 * @category getters
314 * @since 2.0.0
315 */
316export const size: <V>(self: HashSet<V>) => number = internal.size
317
318/**
319 * Checks whether the HashSet is empty.
320 *
321 * **Example** (Checking whether a HashSet is empty)
322 *
323 * ```ts import.meta.vitest
324 * import { HashSet } from "effect"
325 *
326 * HashSet.isEmpty(HashSet.empty<string>()) // => true
327 *
328 * HashSet.isEmpty(HashSet.make("a")) // => false
329 * ```
330 *
331 * @category predicates
332 * @since 4.0.0
333 */
334export const isEmpty: <V>(self: HashSet<V>) => boolean = internal.isEmpty
335
336/**
337 * Creates the union of two HashSets.
338 *
339 * **Example** (Combining HashSets)
340 *
341 * ```ts import.meta.vitest
342 * import { HashSet } from "effect"
343 *
344 * HashSet.union(HashSet.make("a", "b"), HashSet.make("b", "c")) // => HashSet.make("a", "b", "c")
345 * ```
346 *
347 * @category combinators
348 * @since 2.0.0
349 */
350export const union: {
351 <V1>(that: HashSet<V1>): <V0>(self: HashSet<V0>) => HashSet<V1 | V0>
352 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): HashSet<V0 | V1>
353} = Dual.dual<
354 <V1>(that: HashSet<V1>) => <V0>(self: HashSet<V0>) => HashSet<V1 | V0>,
355 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>) => HashSet<V0 | V1>
356>(2, internal.union)
357
358/**
359 * Creates the intersection of two HashSets.
360 *
361 * **Example** (Finding common HashSet values)
362 *
363 * ```ts import.meta.vitest
364 * import { HashSet } from "effect"
365 *
366 * HashSet.intersection(HashSet.make("a", "b", "c"), HashSet.make("b", "c", "d")) // => HashSet.make("b", "c")
367 * ```
368 *
369 * @category combinators
370 * @since 2.0.0
371 */
372export const intersection: {
373 <V1>(that: HashSet<V1>): <V0>(self: HashSet<V0>) => HashSet<V1 & V0>
374 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): HashSet<V0 & V1>
375} = Dual.dual<
376 <V1>(that: HashSet<V1>) => <V0>(self: HashSet<V0>) => HashSet<V1 & V0>,
377 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>) => HashSet<V0 & V1>
378>(2, internal.intersection)
379
380/**
381 * Creates the difference of two HashSets (elements in the first set that are not in the second).
382 *
383 * **Example** (Finding HashSet differences)
384 *
385 * ```ts import.meta.vitest
386 * import { HashSet } from "effect"
387 *
388 * HashSet.difference(HashSet.make("a", "b", "c"), HashSet.make("b", "d")) // => HashSet.make("a", "c")
389 * ```
390 *
391 * @category combinators
392 * @since 2.0.0
393 */
394export const difference: {
395 <V1>(that: HashSet<V1>): <V0>(self: HashSet<V0>) => HashSet<V0>
396 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): HashSet<V0>
397} = Dual.dual<
398 <V1>(that: HashSet<V1>) => <V0>(self: HashSet<V0>) => HashSet<V0>,
399 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>) => HashSet<V0>
400>(2, internal.difference)
401
402/**
403 * Checks whether a HashSet is a subset of another HashSet.
404 *
405 * **Example** (Checking subset relationships)
406 *
407 * ```ts import.meta.vitest
408 * import { HashSet } from "effect"
409 *
410 * const small = HashSet.make("a", "b")
411 * const large = HashSet.make("a", "b", "c", "d")
412 * const other = HashSet.make("x", "y")
413 *
414 * HashSet.isSubset(small, large) // => true
415 * HashSet.isSubset(large, small) // => false
416 * HashSet.isSubset(small, other) // => false
417 * HashSet.isSubset(small, small) // => true
418 * ```
419 *
420 * @category predicates
421 * @since 2.0.0
422 */
423export const isSubset: {
424 <V1>(that: HashSet<V1>): <V0>(self: HashSet<V0>) => boolean
425 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): boolean
426} = Dual.dual<
427 <V1>(that: HashSet<V1>) => <V0>(self: HashSet<V0>) => boolean,
428 <V0, V1>(self: HashSet<V0>, that: HashSet<V1>) => boolean
429>(2, internal.isSubset)
430
431/**
432 * Maps each value in the HashSet using the provided function.
433 *
434 * **Example** (Mapping HashSet values)
435 *
436 * ```ts import.meta.vitest
437 * import { HashSet } from "effect"
438 *
439 * const numbers = HashSet.make(1, 2, 3)
440 * const doubled = HashSet.map(numbers, (n) => n * 2)
441 *
442 * doubled // => HashSet.make(2, 4, 6)
443 *
444 * // Mapping can reduce size if function produces duplicates
445 * const strings = HashSet.make("apple", "banana", "cherry")
446 * const lengths = HashSet.map(strings, (s) => s.length)
447 * lengths // => HashSet.make(5, 6)
448 * ```
449 *
450 * @category mapping
451 * @since 2.0.0
452 */
453export const map: {
454 <V, U>(f: (value: V) => U): (self: HashSet<V>) => HashSet<U>
455 <V, U>(self: HashSet<V>, f: (value: V) => U): HashSet<U>
456} = Dual.dual<
457 <V, U>(f: (value: V) => U) => (self: HashSet<V>) => HashSet<U>,
458 <V, U>(self: HashSet<V>, f: (value: V) => U) => HashSet<U>
459>(2, internal.map)
460
461/**
462 * Filters the HashSet keeping only values that satisfy the predicate.
463 *
464 * **Example** (Filtering HashSet values)
465 *
466 * ```ts import.meta.vitest
467 * import { HashSet } from "effect"
468 *
469 * HashSet.filter(HashSet.make(1, 2, 3, 4, 5, 6), (n) => n % 2 === 0) // => HashSet.make(2, 4, 6)
470 * ```
471 *
472 * @category filtering
473 * @since 2.0.0
474 */
475export const filter: {
476 <V, U extends V>(refinement: Refinement<NoInfer<V>, U>): (self: HashSet<V>) => HashSet<U>
477 <V>(predicate: Predicate<NoInfer<V>>): (self: HashSet<V>) => HashSet<V>
478 <V, U extends V>(self: HashSet<V>, refinement: Refinement<V, U>): HashSet<U>
479 <V>(self: HashSet<V>, predicate: Predicate<V>): HashSet<V>
480} = Dual.dual<
481 {
482 <V, U extends V>(refinement: Refinement<NoInfer<V>, U>): (self: HashSet<V>) => HashSet<U>
483 <V>(predicate: Predicate<NoInfer<V>>): (self: HashSet<V>) => HashSet<V>
484 },
485 {
486 <V, U extends V>(self: HashSet<V>, refinement: Refinement<V, U>): HashSet<U>
487 <V>(self: HashSet<V>, predicate: Predicate<V>): HashSet<V>
488 }
489>(2, internal.filter)
490
491/**
492 * Checks whether at least one value in the HashSet satisfies the predicate.
493 *
494 * **Example** (Testing whether some values match)
495 *
496 * ```ts import.meta.vitest
497 * import { HashSet } from "effect"
498 *
499 * const numbers = HashSet.make(1, 2, 3, 4, 5)
500 *
501 * HashSet.some(numbers, (n) => n > 3) // => true
502 * HashSet.some(numbers, (n) => n > 10) // => false
503 *
504 * HashSet.some(HashSet.empty<number>(), (n) => n > 0) // => false
505 * ```
506 *
507 * @category predicates
508 * @since 2.0.0
509 */
510export const some: {
511 <V>(predicate: Predicate<V>): (self: HashSet<V>) => boolean
512 <V>(self: HashSet<V>, predicate: Predicate<V>): boolean
513} = Dual.dual<
514 <V>(predicate: Predicate<V>) => (self: HashSet<V>) => boolean,
515 <V>(self: HashSet<V>, predicate: Predicate<V>) => boolean
516>(2, internal.some)
517
518/**
519 * Checks whether all values in the HashSet satisfy the predicate.
520 *
521 * **Example** (Testing whether every value matches)
522 *
523 * ```ts import.meta.vitest
524 * import { HashSet } from "effect"
525 *
526 * const numbers = HashSet.make(2, 4, 6, 8)
527 *
528 * HashSet.every(numbers, (n) => n % 2 === 0) // => true
529 * HashSet.every(numbers, (n) => n > 5) // => false
530 *
531 * HashSet.every(HashSet.empty<number>(), (n) => n > 0) // => true
532 * ```
533 *
534 * @category predicates
535 * @since 2.0.0
536 */
537export const every: {
538 <V>(predicate: Predicate<V>): (self: HashSet<V>) => boolean
539 <V>(self: HashSet<V>, predicate: Predicate<V>): boolean
540} = Dual.dual<
541 <V>(predicate: Predicate<V>) => (self: HashSet<V>) => boolean,
542 <V>(self: HashSet<V>, predicate: Predicate<V>) => boolean
543>(2, internal.every)
544
545/**
546 * Reduces the HashSet to a single value by iterating through the values and applying an accumulator function.
547 *
548 * **Example** (Reducing HashSet values)
549 *
550 * ```ts import.meta.vitest
551 * import { HashSet } from "effect"
552 *
553 * const numbers = HashSet.make(1, 2, 3, 4, 5)
554 * HashSet.reduce(numbers, 0, (acc, n) => acc + n) // => 15
555 * ```
556 *
557 * @category folding
558 * @since 2.0.0
559 */
560export const reduce: {
561 <V, U>(zero: U, f: (accumulator: U, value: V) => U): (self: HashSet<V>) => U
562 <V, U>(self: HashSet<V>, zero: U, f: (accumulator: U, value: V) => U): U
563} = Dual.dual<
564 <V, U>(zero: U, f: (accumulator: U, value: V) => U) => (self: HashSet<V>) => U,
565 <V, U>(self: HashSet<V>, zero: U, f: (accumulator: U, value: V) => U) => U
566>(3, internal.reduce)