0
# Sets & Set Operations
1

2
Efficient set implementations including sparse sets for integer keys and functional set operations.
3

4
## Capabilities
5

6
### Set Operations (Functional)
7

8
Functional set operations for any iterable collections.
9

10
```typescript { .api }
11
/**
12
 * Functional set operations namespace
13
 */
14
namespace set {
15
  /** Create intersection of two iterables */
16
  function intersection<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
17
  
18
  /** Create union of two iterables */
19
  function union<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
20
  
21
  /** Create difference (a - b) of two iterables */
22
  function difference<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
23
  
24
  /** Create symmetric difference of two iterables */
25
  function symmetricDifference<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
26
  
27
  /** Check if a is subset of b */
28
  function isSubset<T>(a: Iterable<T>, b: Iterable<T>): boolean;
29
  
30
  /** Check if a is superset of b */
31
  function isSuperset<T>(a: Iterable<T>, b: Iterable<T>): boolean;
32
  
33
  /** Mutate set a to add all elements from b */
34
  function add<T>(a: Set<T>, b: Iterable<T>): Set<T>;
35
  
36
  /** Mutate set a to remove all elements in b */
37
  function subtract<T>(a: Set<T>, b: Iterable<T>): Set<T>;
38
  
39
  /** Mutate set a to keep only elements in b */
40
  function intersect<T>(a: Set<T>, b: Iterable<T>): Set<T>;
41
  
42
  /** Mutate set a to remove common elements with b */
43
  function disjunct<T>(a: Set<T>, b: Iterable<T>): Set<T>;
44
  
45
  /** Get size of intersection without creating it */
46
  function intersectionSize<T>(a: Iterable<T>, b: Iterable<T>): number;
47
  
48
  /** Get size of union without creating it */
49
  function unionSize<T>(a: Iterable<T>, b: Iterable<T>): number;
50
  
51
  /** Calculate Jaccard similarity coefficient */
52
  function jaccard<T>(a: Iterable<T>, b: Iterable<T>): number;
53
  
54
  /** Calculate overlap coefficient */
55
  function overlap<T>(a: Iterable<T>, b: Iterable<T>): number;
56
}
57
```
58

59
### SparseSet
60

61
Set optimized for sparse non-negative integer keys with O(1) operations.
62

63
```typescript { .api }
64
/**
65
 * Set optimized for sparse integer keys
66
 * @param capacity Maximum integer value that can be stored
67
 */
68
function SparseSet(capacity: number): SparseSet;
69

70
interface SparseSet {
71
  /** Maximum capacity */
72
  readonly capacity: number;
73
  
74
  /** Current number of elements */
75
  readonly size: number;
76
  
77
  /** Add integer to set */
78
  add(value: number): this;
79
  
80
  /** Remove integer from set */
81
  delete(value: number): boolean;
82
  
83
  /** Check if integer exists in set */
84
  has(value: number): boolean;
85
  
86
  /** Remove all elements */
87
  clear(): void;
88
  
89
  /** Iterate over values */
90
  values(): IterableIterator<number>;
91
  keys(): IterableIterator<number>;
92
  entries(): IterableIterator<[number, number]>;
93
  [Symbol.iterator](): IterableIterator<number>;
94
  forEach(callback: (value: number, key: number, set: this) => void): void;
95
  
96
  inspect(): any;
97
}
98
```
99

100
### SparseQueueSet
101

102
Queue-ordered sparse set combining queue operations with set membership.
103

104
```typescript { .api }
105
/**
106
 * Queue-ordered sparse set for integer values
107
 * @param capacity Maximum integer value that can be stored
108
 */
109
function SparseQueueSet(capacity: number): SparseQueueSet;
110

111
interface SparseQueueSet {
112
  readonly capacity: number;
113
  readonly size: number;
114
  
115
  /** Add integer to back of queue if not present */
116
  enqueue(value: number): this;
117
  
118
  /** Remove and return integer from front of queue */
119
  dequeue(): number | undefined;
120
  
121
  /** Check if integer exists in set */
122
  has(value: number): boolean;
123
  
124
  /** Remove all elements */
125
  clear(): void;
126
  
127
  values(): IterableIterator<number>;
128
  [Symbol.iterator](): IterableIterator<number>;
129
  
130
  inspect(): any;
131
}
132
```
133

134
### SparseMap
135

136
Map optimized for sparse non-negative integer keys.
137

138
```typescript { .api }
139
/**
140
 * Map optimized for sparse integer keys
141
 * @param capacity Maximum integer key that can be stored
142
 */
143
function SparseMap<V>(capacity: number): SparseMap<V>;
144

145
interface SparseMap<V> {
146
  readonly capacity: number;
147
  readonly size: number;
148
  
149
  /** Store key-value pair */
150
  set(key: number, value: V): this;
151
  
152
  /** Get value for key */
153
  get(key: number): V | undefined;
154
  
155
  /** Check if key exists */
156
  has(key: number): boolean;
157
  
158
  /** Remove key-value pair */
159
  delete(key: number): boolean;
160
  
161
  /** Remove all pairs */
162
  clear(): void;
163
  
164
  values(): IterableIterator<V>;
165
  keys(): IterableIterator<number>;
166
  entries(): IterableIterator<[number, V]>;
167
  [Symbol.iterator](): IterableIterator<[number, V]>;
168
  forEach(callback: (value: V, key: number, map: this) => void): void;
169
  
170
  inspect(): any;
171
}
172
```
173

174
### StaticDisjointSet
175

176
Union-find data structure for connectivity queries.
177

178
```typescript { .api }
179
/**
180
 * Union-find/disjoint-set data structure
181
 * @param size Number of elements (0 to size-1)
182
 */
183
function StaticDisjointSet(size: number): StaticDisjointSet;
184

185
interface StaticDisjointSet {
186
  readonly size: number;
187
  
188
  /** Union two elements */
189
  union(a: number, b: number): this;
190
  
191
  /** Check if two elements are connected */
192
  connected(a: number, b: number): boolean;
193
  
194
  /** Find root representative of element */
195
  find(node: number): number;
196
  
197
  inspect(): any;
198
}
199
```
200

201
## Usage Examples
202

203
### Set Operations Example
204

205
```typescript
206
import {set} from "mnemonist";
207

208
const setA = new Set([1, 2, 3, 4]);
209
const setB = new Set([3, 4, 5, 6]);
210
const arrayC = [2, 3, 7];
211

212
// Immutable operations (create new sets)
213
const intersect = set.intersection(setA, setB); // Set {3, 4}
214
const unite = set.union(setA, setB);            // Set {1, 2, 3, 4, 5, 6}
215
const diff = set.difference(setA, setB);        // Set {1, 2}
216
const symDiff = set.symmetricDifference(setA, setB); // Set {1, 2, 5, 6}
217

218
// Subset/superset checks
219
console.log(set.isSubset([1, 2], setA)); // true
220
console.log(set.isSuperset(setA, [1, 2])); // true
221

222
// Mutable operations (modify first set)
223
set.add(setA, arrayC);      // setA now includes 7
224
set.subtract(setA, setB);   // setA removes 3, 4, 5, 6
225
set.intersect(setA, setB);  // setA keeps only common elements
226

227
// Efficient size calculations
228
const intersectionCount = set.intersectionSize(setA, setB);
229
const unionCount = set.unionSize(setA, setB);
230

231
// Similarity metrics
232
const jaccardSim = set.jaccard(setA, setB);  // |A ∩ B| / |A ∪ B|
233
const overlapSim = set.overlap(setA, setB);  // |A ∩ B| / min(|A|, |B|)
234
```
235

236
### SparseSet Example
237

238
```typescript
239
import {SparseSet} from "mnemonist";
240

241
// For sparse integer sets (e.g., entity IDs, sparse indices)
242
const entities = new SparseSet(100000); // Can store 0-99999
243

244
entities.add(42);
245
entities.add(1337);
246
entities.add(99999);
247

248
console.log(entities.has(42));    // true
249
console.log(entities.has(43));    // false
250
console.log(entities.size);       // 3
251

252
// Efficient for sparse data
253
entities.delete(1337);
254
for (const id of entities) {
255
  console.log(`Entity ${id} is active`);
256
}
257
```
258

259
### SparseQueueSet Example
260

261
```typescript
262
import {SparseQueueSet} from "mnemonist";
263

264
// Task queue with deduplication
265
const taskQueue = new SparseQueueSet(10000);
266

267
// Enqueue tasks (duplicates ignored)
268
taskQueue.enqueue(101);
269
taskQueue.enqueue(205);
270
taskQueue.enqueue(101); // Ignored - already queued
271

272
console.log(taskQueue.size); // 2
273

274
// Process tasks in order
275
while (taskQueue.size > 0) {
276
  const taskId = taskQueue.dequeue();
277
  console.log(`Processing task ${taskId}`);
278
}
279
```
280

281
### StaticDisjointSet Example
282

283
```typescript
284
import {StaticDisjointSet} from "mnemonist";
285

286
// Network connectivity
287
const network = new StaticDisjointSet(10); // Nodes 0-9
288

289
// Connect nodes
290
network.union(0, 1);
291
network.union(1, 2);
292
network.union(3, 4);
293

294
// Check connectivity
295
console.log(network.connected(0, 2)); // true (0-1-2 path)
296
console.log(network.connected(0, 3)); // false (different components)
297

298
// Find representatives
299
console.log(network.find(0)); // Root of component containing 0
300
console.log(network.find(2)); // Same root as node 0
301
```
302

303
## Performance Characteristics
304

305
| Operation | Set Ops | SparseSet | SparseQueueSet | SparseMap | DisjointSet |
306
|-----------|---------|-----------|----------------|-----------|-------------|
307
| Add/Insert | O(n) | O(1) | O(1) | O(1) | N/A |
308
| Delete | O(n) | O(1) | N/A | O(1) | N/A |
309
| Has/Contains | O(n) | O(1) | O(1) | O(1) | N/A |
310
| Union | N/A | N/A | N/A | N/A | O(α(n)) |
311
| Find | N/A | N/A | N/A | N/A | O(α(n)) |
312
| Connected | N/A | N/A | N/A | N/A | O(α(n)) |
313
| Space | O(n+m) | O(capacity) | O(capacity) | O(capacity) | O(n) |
314
315
Where α(n) is the inverse Ackermann function (practically constant).
316

317
## Choosing the Right Set Structure
318

319
- **set operations**: For general set operations on any iterables
320
- **SparseSet**: For sparse integer sets with known maximum value
321
- **SparseQueueSet**: When you need FIFO ordering with deduplication
322
- **SparseMap**: For sparse integer-keyed mappings
323
- **StaticDisjointSet**: For connectivity/grouping problems with union-find