Sets & Set Operations

/**
 * Functional set operations namespace
 */
namespace set {
  /** Create intersection of two iterables */
  function intersection<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
  
  /** Create union of two iterables */
  function union<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
  
  /** Create difference (a - b) of two iterables */
  function difference<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
  
  /** Create symmetric difference of two iterables */
  function symmetricDifference<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
  
  /** Check if a is subset of b */
  function isSubset<T>(a: Iterable<T>, b: Iterable<T>): boolean;
  
  /** Check if a is superset of b */
  function isSuperset<T>(a: Iterable<T>, b: Iterable<T>): boolean;
  
  /** Mutate set a to add all elements from b */
  function add<T>(a: Set<T>, b: Iterable<T>): Set<T>;
  
  /** Mutate set a to remove all elements in b */
  function subtract<T>(a: Set<T>, b: Iterable<T>): Set<T>;
  
  /** Mutate set a to keep only elements in b */
  function intersect<T>(a: Set<T>, b: Iterable<T>): Set<T>;
  
  /** Mutate set a to remove common elements with b */
  function disjunct<T>(a: Set<T>, b: Iterable<T>): Set<T>;
  
  /** Get size of intersection without creating it */
  function intersectionSize<T>(a: Iterable<T>, b: Iterable<T>): number;
  
  /** Get size of union without creating it */
  function unionSize<T>(a: Iterable<T>, b: Iterable<T>): number;
  
  /** Calculate Jaccard similarity coefficient */
  function jaccard<T>(a: Iterable<T>, b: Iterable<T>): number;
  
  /** Calculate overlap coefficient */
  function overlap<T>(a: Iterable<T>, b: Iterable<T>): number;
}

/**
 * Set optimized for sparse integer keys
 * @param capacity Maximum integer value that can be stored
 */
function SparseSet(capacity: number): SparseSet;

interface SparseSet {
  /** Maximum capacity */
  readonly capacity: number;
  
  /** Current number of elements */
  readonly size: number;
  
  /** Add integer to set */
  add(value: number): this;
  
  /** Remove integer from set */
  delete(value: number): boolean;
  
  /** Check if integer exists in set */
  has(value: number): boolean;
  
  /** Remove all elements */
  clear(): void;
  
  /** Iterate over values */
  values(): IterableIterator<number>;
  keys(): IterableIterator<number>;
  entries(): IterableIterator<[number, number]>;
  [Symbol.iterator](): IterableIterator<number>;
  forEach(callback: (value: number, key: number, set: this) => void): void;
  
  inspect(): any;
}

/**
 * Queue-ordered sparse set for integer values
 * @param capacity Maximum integer value that can be stored
 */
function SparseQueueSet(capacity: number): SparseQueueSet;

interface SparseQueueSet {
  readonly capacity: number;
  readonly size: number;
  
  /** Add integer to back of queue if not present */
  enqueue(value: number): this;
  
  /** Remove and return integer from front of queue */
  dequeue(): number | undefined;
  
  /** Check if integer exists in set */
  has(value: number): boolean;
  
  /** Remove all elements */
  clear(): void;
  
  values(): IterableIterator<number>;
  [Symbol.iterator](): IterableIterator<number>;
  
  inspect(): any;
}

/**
 * Map optimized for sparse integer keys
 * @param capacity Maximum integer key that can be stored
 */
function SparseMap<V>(capacity: number): SparseMap<V>;

interface SparseMap<V> {
  readonly capacity: number;
  readonly size: number;
  
  /** Store key-value pair */
  set(key: number, value: V): this;
  
  /** Get value for key */
  get(key: number): V | undefined;
  
  /** Check if key exists */
  has(key: number): boolean;
  
  /** Remove key-value pair */
  delete(key: number): boolean;
  
  /** Remove all pairs */
  clear(): void;
  
  values(): IterableIterator<V>;
  keys(): IterableIterator<number>;
  entries(): IterableIterator<[number, V]>;
  [Symbol.iterator](): IterableIterator<[number, V]>;
  forEach(callback: (value: V, key: number, map: this) => void): void;
  
  inspect(): any;
}

/**
 * Union-find/disjoint-set data structure
 * @param size Number of elements (0 to size-1)
 */
function StaticDisjointSet(size: number): StaticDisjointSet;

interface StaticDisjointSet {
  readonly size: number;
  
  /** Union two elements */
  union(a: number, b: number): this;
  
  /** Check if two elements are connected */
  connected(a: number, b: number): boolean;
  
  /** Find root representative of element */
  find(node: number): number;
  
  inspect(): any;
}

import {set} from "mnemonist";

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

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

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

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

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

// Similarity metrics
const jaccardSim = set.jaccard(setA, setB);  // |A ∩ B| / |A ∪ B|
const overlapSim = set.overlap(setA, setB);  // |A ∩ B| / min(|A|, |B|)

import {SparseSet} from "mnemonist";

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

entities.add(42);
entities.add(1337);
entities.add(99999);

console.log(entities.has(42));    // true
console.log(entities.has(43));    // false
console.log(entities.size);       // 3

// Efficient for sparse data
entities.delete(1337);
for (const id of entities) {
  console.log(`Entity ${id} is active`);
}

import {SparseQueueSet} from "mnemonist";

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

// Enqueue tasks (duplicates ignored)
taskQueue.enqueue(101);
taskQueue.enqueue(205);
taskQueue.enqueue(101); // Ignored - already queued

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

// Process tasks in order
while (taskQueue.size > 0) {
  const taskId = taskQueue.dequeue();
  console.log(`Processing task ${taskId}`);
}

import {StaticDisjointSet} from "mnemonist";

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

// Connect nodes
network.union(0, 1);
network.union(1, 2);
network.union(3, 4);

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

// Find representatives
console.log(network.find(0)); // Root of component containing 0
console.log(network.find(2)); // Same root as node 0