npm package: @frontendxlab/dsa-js
Description: Tree-shakable DSA runtime library for coding platforms - algorithms, data structures, and utilities
Latest version: 1.0.7

# @frontendxlab/dsa-js

A tree-shakable, production-grade DSA (Data Structures & Algorithms) runtime library for coding platforms like LeetCode, with CDN + ESM compatibility.

## Features

- **Fully Tree-shakable**: Import only what you need
- **CDN Compatible**: Use directly from esm.sh or unpkg
- **TypeScript**: Full type definitions included
- **Performance Optimized**: Competitive programming algorithms
- **Comprehensive Tests**: 95%+ code coverage

## Installation

```bash
npm install @frontendxlab/dsa-js
```

Or via CDN:

```typescript
import { toBinary } from "https://esm.sh/@frontendxlab/dsa-js/bits/toBinary";
```

## Quick Usage

### Algorithms

```typescript
import { lowerBound } from "@frontendxlab/dsa-js/algorithms/lowerBound";
import { binarySearch } from "@frontendxlab/dsa-js/algorithms/binarySearch";
import { gcd, lcm } from "@frontendxlab/dsa-js/algorithms/gcd";
import { prefixSum, rangeSum } from "@frontendxlab/dsa-js/algorithms/prefixSum";
import { nextPermutation } from "@frontendxlab/dsa-js/algorithms/nextPermutation";

// Binary search
const arr = [1, 3, 5, 7, 9];
const index = binarySearch(arr, 5); // 2

// GCD and LCM
gcd(12, 8);  // 4
lcm(4, 6);  // 12

// Prefix sum
const ps = prefixSum([1, 2, 3, 4]); // [1, 3, 6, 10]
rangeSum(ps, 1, 3); // 9
```

### Bit Operations

```typescript
import { setBit, clearBit, toggleBit } from "@frontendxlab/dsa-js/bits/bitwise";
import { popcount } from "@frontendxlab/dsa-js/bits/popcount";
import { isPowerOfTwo } from "@frontendxlab/dsa-js/bits/isPowerOfTwo";
import { toBinary, fromBinary } from "@frontendxlab/dsa-js/bits/toBinary";

// Set/clear/toggle bits
setBit(0b0000, 2);      // 0b0100
clearBit(0b1111, 0);     // 0b1110
toggleBit(0b0000, 1);    // 0b0010

// Popcount (Brian Kernighan's algorithm)
popcount(0b1111);  // 4

// Power of two check
isPowerOfTwo(8);  // true

// Binary conversions
toBinary(10);   // "1010"
fromBinary("1010"); // 10
```

### Data Structures

```typescript
import { MinHeap, MaxHeap } from "@frontendxlab/dsa-js/data-structures/heap/MinHeap";
import { UnionFind } from "@frontendxlab/dsa-js/data-structures/union-find/UnionFind";
import { SegmentTree } from "@frontendxlab/dsa-js/data-structures/segment-tree/SegmentTree";
import { FenwickTree } from "@frontendxlab/dsa-js/data-structures/fenwick-tree/FenwickTree";
import { LinkedList } from "@frontendxlab/dsa-js/data-structures/linked-list/LinkedList";
import { Stack } from "@frontendxlab/dsa-js/data-structures/stack/Stack";
import { Queue, Deque } from "@frontendxlab/dsa-js/data-structures/queue/Queue";
import { BST } from "@frontendxlab/dsa-js/data-structures/tree/BST";
import { Trie } from "@frontendxlab/dsa-js/data-structures/tree/Trie";
import { Graph } from "@frontendxlab/dsa-js/data-structures/graph/Graph";
import { HashMap, HashSet } from "@frontendxlab/dsa-js/data-structures/hash/HashMap";

// Heaps
const minHeap = new MinHeap<number>();
minHeap.push(5); minHeap.push(3); minHeap.push(7);
minHeap.peek(); // 3
minHeap.pop();  // 3

// Union-Find
const uf = new UnionFind(5);
uf.union(0, 1);
uf.connected(0, 1); // true

// Segment Tree
const seg = new SegmentTree([1, 3, 5, 7, 9], (a, b) => a + b, 0);
seg.query(0, 4); // 25

// Fenwick Tree
const ft = FenwickTree.from([1, 2, 3, 4, 5]);
ft.prefixSum(4);  // 15

// BST
const bst = new BST<number>();
bst.insert(5); bst.insert(3); bst.insert(7);
bst.search(5);  // true
bst.inOrder();  // [3, 5, 7]

// Trie
const trie = new Trie();
trie.insert("hello");
trie.search("hello");     // true
trie.startsWith("hel");  // true

// Graph
const graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.bfs(1); // [1, 2, 3]
```

### Utilities

```typescript
import { cloneDeep } from "@frontendxlab/dsa-js/utils/cloneDeep";
import { memoize } from "@frontendxlab/dsa-js/utils/memoize";

// Deep clone
const obj = { a: 1, b: { c: 2 } };
const cloned = cloneDeep(obj);

// Memoization
const fib = memoize((n: number): number => {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
});
```

## Algorithms

| Function | Description | Time Complexity |
|----------|-------------|----------------|
| `lowerBound` | Find first index where arr[i] >= target | O(log n) |
| `upperBound` | Find first index where arr[i] > target | O(log n) |
| `binarySearch` | Find target index or -1 | O(log n) |
| `nextPermutation` | Generate next permutation in-place | O(n) |
| `gcd` | Greatest common divisor | O(log min(a,b)) |
| `lcm` | Least common multiple | O(log min(a,b)) |
| `prefixSum` | Compute prefix sum array | O(n) |
| `rangeSum` | Query sum in range | O(1) |

## Data Structures

### Heaps
- `MinHeap<T>` - Min-heap with O(log n) insert/extract
- `MaxHeap<T>` - Max-heap with O(log n) insert/extract

### Union-Find
- `UnionFind` - Disjoint set with path compression and union by rank

### Trees
- `SegmentTree<T>` - Range queries with O(log n) updates
- `FenwickTree` - Binary indexed tree for prefix sums
- `BST<T>` - Binary search tree with O(log n) operations
- `Trie` - Prefix tree for string operations

### Graphs
- `Graph` - Adjacency list representation with BFS/DFS

### Hash
- `HashMap<K, V>` - Hash map with auto-resize
- `HashSet<T>` - Hash set implementation

### Lists & Collections
- `LinkedList<T>` - Doubly-linked list
- `Stack<T>` - LIFO stack
- `Queue<T>` - FIFO queue
- `Deque<T>` - Double-ended queue

## Bit Operations

| Function | Description |
|----------|-------------|
| `setBit(n, i)` | Set i-th bit to 1 |
| `clearBit(n, i)` | Set i-th bit to 0 |
| `toggleBit(n, i)` | Flip i-th bit |
| `isBitSet(n, i)` | Check if i-th bit is 1 |
| `popcount(n)` | Count set bits (Brian Kernighan) |
| `countTrailingZeros(n)` | Count trailing zeros |
| `countLeadingZeros(n)` | Count leading zeros |
| `isPowerOfTwo(n)` | Check if power of 2 |
| `nextPowerOfTwo(n)` | Smallest power of 2 >= n |
| `xorRange(n)` | XOR of 1 to n (O(1)) |
| `findSingleNumber(arr)` | Find element appearing once |
| `toGray(n)` | Convert to Gray code |
| `fromGray(g)` | Convert from Gray code |

## CDN Usage

```typescript
// esm.sh
import { lowerBound } from "https://esm.sh/@frontendxlab/dsa-js/algorithms/lowerBound";

// unpkg
import { toBinary } from "https://unpkg.com/@frontendxlab/dsa-js/bits/toBinary.js";
```

## Build

```bash
# Build for production
pnpm build

# Run tests
pnpm test

# Generate docs
pnpm docs
```

## License

MIT