1/**
2 * @since 2.0.0
3 */
4
5import * as Equal from "../Equal.ts"
6import { format } from "../Formatter.ts"
7import * as Hash from "../Hash.ts"
8import type { Inspectable } from "../Inspectable.ts"
9import { NodeInspectSymbol, toJson } from "../Inspectable.ts"
10import type { Pipeable } from "../Pipeable.ts"
11import { pipeArguments } from "../Pipeable.ts"
12import { hasProperty } from "../Predicate.ts"
13import * as HashMap from "./hashMap.ts"
14
15/** @internal */
16export const HashSetTypeId = "~effect/HashSet"
17
18/** @internal */
19export type HashSetTypeId = typeof HashSetTypeId
20
21/** @internal */
22export interface HashSet<out V> extends Iterable<V>, Equal.Equal, Pipeable, Inspectable {
23 readonly [HashSetTypeId]: HashSetTypeId
24}
25
26const hashSetSeed = Hash.string(HashSetTypeId)
27
28const HashSetProto: Omit<HashSet<unknown>, HashSetTypeId> = {
29 [Hash.symbol]<V>(this: HashSet<V>): number {
30 return Hash.optimize(Hash.combine(hashSetSeed, Hash.hash(keyMap(this))))
31 },
32 [Equal.symbol]<V>(this: HashSet<V>, that: unknown): boolean {
33 return isHashSet(that) && size(this) === size(that) && every(this, (value) => has(that, value))
34 },
35 [Symbol.iterator]<V>(this: HashSet<V>): Iterator<V> {
36 return HashMap.keys(keyMap(this))
37 },
38 toString() {
39 return `HashSet(${format(Array.from(this))})`
40 },
41 toJSON() {
42 return {
43 _id: "HashSet",
44 values: toJson(Array.from(this))
45 }
46 },
47 [NodeInspectSymbol]() {
48 return this.toJSON()
49 },
50 pipe() {
51 return pipeArguments(this, arguments)
52 }
53}
54
55const makeImpl = <V>(keyMap: HashMap.HashMap<V, boolean>): HashSet<V> => {
56 const set = Object.create(HashSetProto)
57 set[HashSetTypeId] = HashSetTypeId
58 set.keyMap = keyMap
59 return set
60}
61
62/** @internal */
63export const isHashSet = (u: unknown): u is HashSet<unknown> => hasProperty(u, HashSetTypeId)
64
65/** @internal */
66export const keyMap = <V>(self: HashSet<V>): HashMap.HashMap<V, boolean> => (self as any).keyMap
67
68/** @internal */
69export const empty = <V = never>(): HashSet<V> => makeImpl(HashMap.empty<V, boolean>())
70
71/** @internal */
72export const make = <Values extends ReadonlyArray<any>>(
73 ...values: Values
74): HashSet<Values[number]> => fromIterable(values)
75
76/** @internal */
77export const fromIterable = <V>(values: Iterable<V>): HashSet<V> => {
78 let map = HashMap.empty<V, boolean>()
79 for (const value of values) {
80 map = HashMap.set(map, value, true)
81 }
82 return makeImpl(map)
83}
84
85/** @internal */
86export const has = <V>(self: HashSet<V>, value: V): boolean => HashMap.has(keyMap(self), value)
87
88/** @internal */
89export const add = <V>(self: HashSet<V>, value: V): HashSet<V> => {
90 const map = keyMap(self)
91 return HashMap.has(map, value) ? self : makeImpl(HashMap.set(map, value, true))
92}
93
94/** @internal */
95export const remove = <V>(self: HashSet<V>, value: V): HashSet<V> => {
96 const map = keyMap(self)
97 return HashMap.has(map, value) ? makeImpl(HashMap.remove(map, value)) : self
98}
99
100/** @internal */
101export const size = <V>(self: HashSet<V>): number => HashMap.size(keyMap(self))
102
103/** @internal */
104export const isEmpty = <V>(self: HashSet<V>): boolean => HashMap.isEmpty(keyMap(self))
105
106// Helper function for building new HashSets from iteration
107const fromPredicate = <V>(self: HashSet<V>, predicate: (value: V) => boolean): HashSet<V> => {
108 let result = HashMap.empty<V, boolean>()
109 for (const value of self) {
110 if (predicate(value)) {
111 result = HashMap.set(result, value, true)
112 }
113 }
114 return makeImpl(result)
115}
116
117/** @internal */
118export const union = <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): HashSet<V0 | V1> => {
119 const map = keyMap(self)
120 let result = map as HashMap.HashMap<V0 | V1, boolean>
121 for (const value of that) {
122 result = HashMap.set(result, value, true)
123 }
124 return makeImpl(result)
125}
126
127/** @internal */
128export const intersection = <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): HashSet<V0 & V1> => {
129 let result = HashMap.empty<V0 & V1, boolean>()
130 for (const value of self) {
131 if (has(that, value as any)) {
132 result = HashMap.set(result, value as V0 & V1, true)
133 }
134 }
135 return makeImpl(result)
136}
137
138/** @internal */
139export const difference = <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): HashSet<V0> =>
140 fromPredicate(self, (value) => !has(that, value as any))
141
142/** @internal */
143export const isSubset = <V0, V1>(self: HashSet<V0>, that: HashSet<V1>): boolean => {
144 for (const value of self) {
145 if (!has(that, value as any)) {
146 return false
147 }
148 }
149 return true
150}
151
152/** @internal */
153export const map = <V, U>(self: HashSet<V>, f: (value: V) => U): HashSet<U> => {
154 let result = HashMap.empty<U, boolean>()
155 for (const value of self) {
156 result = HashMap.set(result, f(value), true)
157 }
158 return makeImpl(result)
159}
160
161/** @internal */
162export const filter = <V>(self: HashSet<V>, predicate: (value: V) => boolean): HashSet<V> =>
163 fromPredicate(self, predicate)
164
165/** @internal */
166export const some = <V>(self: HashSet<V>, predicate: (value: V) => boolean): boolean => {
167 for (const value of self) {
168 if (predicate(value)) {
169 return true
170 }
171 }
172 return false
173}
174
175/** @internal */
176export const every = <V>(self: HashSet<V>, predicate: (value: V) => boolean): boolean => {
177 for (const value of self) {
178 if (!predicate(value)) {
179 return false
180 }
181 }
182 return true
183}
184
185/** @internal */
186export const reduce = <V, U>(self: HashSet<V>, zero: U, f: (accumulator: U, value: V) => U): U => {
187 let result = zero
188 for (const value of self) {
189 result = f(result, value)
190 }
191 return result
192}