A powerful toolkit for data structures and algorithms in TypeScript, designed for optimal performance and versatility. The toolkit provides implementations of various data structures and algorithms, with a focus on search and sort operations, caching, and
npm install dsa-toolboxWelcome to DSA Toolbox, a comprehensive library of data structures and algorithms designed to streamline your development process! This library is built for JavaScript and TypeScript, offering both fundamental and advanced data structures, search algorithms, sort algorithms, and more.
Whether you're building a lightweight application or handling large datasets, DSA Toolbox provides an optimized library to make your coding journey efficient and fun.
DSA Toolbox offers a variety of powerful toolbox:
- Composition: Function composition for declarative programming
- Currying: Transforming functions into unary functions
- Functors: CanApply for safe function application
- Monads:
- Option
- Result
- Effect
- Pattern Matching: Expressive control flow using Match (matcher, case-of)
- Lenses & Optics: Immutable state manipulation (Lens, Prism, Traversal)
- Trampoline: Converts deep recursion into iteration to prevent stack overflows
- Transducers: Composable data transformations with high performance (map, filter, reduce fused)
---
| (index) | dataStructure | operation | size | time (ms) |
|---------|----------------------|-------------------|---------|--------------------|
| 0 | Native Array | Insert | 1000 | 0.0042 |
| 1 | Native Array | Search | 1000 | 0.0015 |
| 2 | Native Array | Delete | 1000 | 0.0008 |
| 3 | Queue | Insert (Enqueue) | 1000 | 0.1306 |
| 4 | Queue | Delete (Dequeue) | 1000 | 0.1355 |
| 5 | Stack | Insert (Push) | 1000 | 0.1216 |
| 6 | Stack | Delete (Pop) | 1000 | 0.1128 |
| 7 | Binary Search Tree | Insert | 1000 | 0.3302 |
| 8 | Binary Search Tree | Search | 1000 | 0.0431 |
| 9 | Binary Search Tree | Delete | 1000 | 0.0308 |
| 10 | Red-Black Tree | Insert | 1000 | 0.8018 |
| 11 | Red-Black Tree | Search | 1000 | 0.0202 |
| 12 | Red-Black Tree | Delete | 1000 | 0.0791 |
| 13 | AVL Tree | Insert | 1000 | 0.6278 |
| 14 | AVL Tree | Search | 1000 | 0.0117 |
| 15 | AVL Tree | Delete | 1000 | 0.0189 |
| 16 | Trie | Insert | 1000 | 0.3451 |
| 17 | Trie | Search | 1000 | 0.0157 |
| 18 | Trie | Delete | 1000 | 0.0184 |
| 19 | Min Heap | Insert | 1000 | 0.1854 |
| 20 | Min Heap | Extract | 1000 | 0.3252 |
| 21 | Max Heap | Insert | 1000 | 0.1810 |
| 22 | Max Heap | Extract | 1000 | 0.3187 |
| 23 | B-Tree | Insert | 1000 | 0.4755 |
| 24 | B-Tree | Search | 1000 | 0.0155 |
| 25 | B-Tree | Delete | 1000 | 0.0783 |
| 26 | Native Array | Insert | 10000 | 0.1975 |
| 27 | Native Array | Search | 10000 | 0.0025 |
| 28 | Native Array | Delete | 10000 | 0.0007 |
| 29 | Queue | Insert (Enqueue) | 10000 | 0.2820 |
| 30 | Queue | Delete (Dequeue) | 10000 | 0.1872 |
| 31 | Stack | Insert (Push) | 10000 | 0.1817 |
| 32 | Stack | Delete (Pop) | 10000 | 0.1647 |
| 33 | Binary Search Tree | Insert | 10000 | 1.6758 |
| 34 | Binary Search Tree | Search | 10000 | 0.0039 |
| 35 | Binary Search Tree | Delete | 10000 | 0.0036 |
| 36 | Red-Black Tree | Insert | 10000 | 3.0843 |
| 37 | Red-Black Tree | Search | 10000 | 0.0051 |
| 38 | Red-Black Tree | Delete | 10000 | 0.0178 |
| 39 | AVL Tree | Insert | 10000 | 1.7637 |
| 40 | AVL Tree | Search | 10000 | 0.0028 |
| 41 | AVL Tree | Delete | 10000 | 0.0040 |
| 42 | Trie | Insert | 10000 | 1.2017 |
| 43 | Trie | Search | 10000 | 0.0059 |
| 44 | Trie | Delete | 10000 | 0.0045 |
| 45 | Min Heap | Insert | 10000 | 0.4538 |
| 46 | Min Heap | Extract | 10000 | 0.8098 |
| 47 | Max Heap | Insert | 10000 | 0.3135 |
| 48 | Max Heap | Extract | 10000 | 0.7455 |
| 49 | B-Tree | Insert | 10000 | 2.5483 |
| 50 | B-Tree | Search | 10000 | 0.0098 |
| 51 | B-Tree | Delete | 10000 | 0.0772 |
| 52 | Native Array | Insert | 100000 | 0.1380 |
| 53 | Native Array | Search | 100000 | 0.0166 |
| 54 | Native Array | Delete | 100000 | 0.0010 |
| 55 | Queue | Insert (Enqueue) | 100000 | 1.9742 |
| 56 | Queue | Delete (Dequeue) | 100000 | 0.3029 |
| 57 | Stack | Insert (Push) | 100000 | 0.7822 |
| 58 | Stack | Delete (Pop) | 100000 | 0.1848 |
| 59 | Binary Search Tree | Insert | 100000 | 20.2091 |
| 60 | Binary Search Tree | Search | 100000 | 0.0126 |
| 61 | Binary Search Tree | Delete | 100000 | 0.0031 |
| 62 | Red-Black Tree | Insert | 100000 | 95.1039 |
| 63 | Red-Black Tree | Search | 100000 | 0.0193 |
| 64 | Red-Black Tree | Delete | 100000 | 0.0112 |
| 65 | AVL Tree | Insert | 100000 | 29.1355 |
| 66 | AVL Tree | Search | 100000 | 0.0110 |
| 67 | AVL Tree | Delete | 100000 | 0.0036 |
| 68 | Trie | Insert | 100000 | 33.3004 |
| 69 | Trie | Search | 100000 | 0.0455 |
| 70 | Trie | Delete | 100000 | 0.0880 |
| 71 | Min Heap | Insert | 100000 | 4.6971 |
| 72 | Min Heap | Extract | 100000 | 9.8937 |
| 73 | Max Heap | Insert | 100000 | 3.2794 |
| 74 | Max Heap | Extract | 100000 | 9.2720 |
| 75 | B-Tree | Insert | 100000 | 50.4755 |
| 76 | B-Tree | Search | 100000 | 0.0125 |
| 77 | B-Tree | Delete | 100000 | 0.0196 |
Suggested Applications:
- Small Data: For datasets around 1,000 elements, Native Arrays, Queues, and Stacks provide excellent performance.
- Medium Data: Up to 10,000 elements, use AVL Tree for balanced tree operations and Min/Max Heap for priority-based insert/extract operations.
- Large Data: At 100,000 elements, consider using B-Trees or Red-Black Trees for optimized insertion and search performance.
- Extra Large Data: Beyond 1,000,000 elements, B-Trees, with their balanced and efficient nature, are superior for handling large datasets, especially for search and delete operations.
| (index) | algorithm | operation | size | time (ms) |
|---------|----------------------|-----------|----------|---------------|
| 0 | Heap Sort | Sort | 1000 | 1.1344 |
| 1 | Merge Sort | Sort | 1000 | 0.6770 |
| 2 | Tim Sort | Sort | 1000 | 0.5847 |
| 3 | Native Sort | Sort | 1000 | 0.1421 |
| 4 | Binary Search | Search | 1000 | 0.0278 |
| 5 | Exponential Search | Search | 1000 | 0.0265 |
| 6 | Hybrid Search | Search | 1000 | 0.0377 |
| 7 | Linear Search | Search | 1000 | 0.0218 |
| 8 | Ternary Search | Search | 1000 | 0.0259 |
| 9 | Heap Sort | Sort | 10000 | 2.6921 |
| 10 | Merge Sort | Sort | 10000 | 3.4185 |
| 11 | Tim Sort | Sort | 10000 | 2.1583 |
| 12 | Native Sort | Sort | 10000 | 1.2181 |
| 13 | Binary Search | Search | 10000 | 0.0050 |
| 14 | Exponential Search | Search | 10000 | 0.0062 |
| 15 | Hybrid Search | Search | 10000 | 3.5105 |
| 16 | Linear Search | Search | 10000 | 0.0740 |
| 17 | Ternary Search | Search | 10000 | 0.0067 |
| 18 | Heap Sort | Sort | 100000 | 18.3146 |
| 19 | Merge Sort | Sort | 100000 | 24.6636 |
| 20 | Tim Sort | Sort | 100000 | 12.3915 |
| 21 | Native Sort | Sort | 100000 | 15.6272 |
| 22 | Binary Search | Search | 100000 | 0.0200 |
| 23 | Exponential Search | Search | 100000 | 0.1084 |
| 24 | Hybrid Search | Search | 100000 | 30.4123 |
| 25 | Linear Search | Search | 100000 | 0.6435 |
| 26 | Ternary Search | Search | 100000 | 0.0108 |
| 27 | Heap Sort | Sort | 1000000 | 272.6623 |
| 28 | Merge Sort | Sort | 1000000 | 246.9195 |
| 29 | Tim Sort | Sort | 1000000 | 140.5443 |
| 30 | Native Sort | Sort | 1000000 | 184.8578 |
| 31 | Binary Search | Search | 1000000 | 0.0271 |
| 32 | Exponential Search | Search | 1000000 | 0.7834 |
| 33 | Hybrid Search | Search | 1000000 | 375.9163 |
| 34 | Linear Search | Search | 1000000 | 0.6445 |
| 35 | Ternary Search | Search | 1000000 | 0.0094 |
Sorting Algorithms:
- Heap Sort: Ideal for priority queues and constrained memory environments.
- Merge Sort: Best for linked lists and large datasets on disk where stable sorting is needed.
- Tim Sort: Great for real-time systems and partially sorted data, widely used in production environments.
- Native Sort: Versatile for general-purpose sorting with built-in optimization.
Searching Algorithms:
- Binary Search: Perfect for quick lookups in large, sorted datasets (e.g., databases).
- Exponential Search: Useful for unbounded or sparse datasets to find a starting range for binary search.
- Hybrid Search: Adapts well to changing dataset sizes, ideal for large applications and databases.
- Linear Search: Suited for small, unsorted datasets where search is infrequent.
- Ternary Search: Good for distinct, ordered data ranges, often in optimization or game algorithms.
Functional programming utilities are designed for safe, composable, and efficient function transformations.
| Function | Operation | Time (ms) |
|------------------|--------------------------------|----------------------|
| compose | Function composition | 0.0565 |
| pipe | Function piping | 0.0371 |
| curry | Currying | 0.0508 |
| partial | Partial Application | 0.0302 |
| partialRight | Partial Right Application | 0.0352 |
| uncurry | Uncurrying | 0.0591 |
| CanApply | Functor Mapping | 0.0694 |
| Option | Option Mapping (Monad) | 0.0767 |
| Result | Result Mapping (Monad) | 0.0649 |
| Effect | Effect Execution (Monad) | 0.0578 |
- Function composition (compose, pipe) is highly efficient, enabling declarative and reusable transformations.
- Currying (curry, uncurry) and partial application (partial, partialRight) improve function modularity while maintaining performance.
- Functors and Monads (CanApply, Option, Result, Effect) ensure safety and composability, with reasonable execution times.
- Effect handling (Effect) provides error resilience, making it ideal for managing side effects safely.
---
To install the DSA Toolbox:
``bash`
pnpm add dsa-toolbox
Then you can import the Data Structure or the Algorithm you want to use:
`typescript
import {
binarySearch,
exponentialSearch,
hybridSearch,
linearSearch,
ternarySearch,
heapSort,
mergeSort,
timSort,
LFUCache,
LRUCache,
MaxHeap,
MinHeap,
DoublyLinkedList,
LinkedList,
HyperLogLog,
CountMinSketch,
BloomFilter,
SkipList,
TDigest,
MinHash,
SimHash,
Queue,
Stack,
Treap,
AVLTree,
BTree,
BinarySearchTree,
RedBlackTree,
Trie,
Option,
Effect,
compose,
curry,
CanApply
} from 'dsa-toolbox';
binarySearch(sortedData, target, { compareFn: (a, b) => a - b, isSorted: true });
ternarySearch(data, target, 0, sortedData.length - 1, {
compareFn: (a, b) => a - b,
isSorted: false,
});
const queue = new Queue
data.forEach((item) => queue.enqueue(item));
const avlTree = new AVLTree
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(5);
avlTree.insert(4);
avlTree.insert(15);
avlTree.search(10);
const double = (x: number) => x * 2;
const increment = (x: number) => x + 1;
const doubleThenIncrement = compose(increment, double);
console.log(doubleThenIncrement(3)); // 7
const safeValue = CanApply(10)
.map((x) => x * 2)
.map((x) => Result: ${x})
.getValue();
console.log(safeValue); // "Result: 20"
`
More usage examples can be found here:
- https://github.com/helabenkhalfallah/dsa-toolbox/blob/main/benchmark-algo.ts
- https://github.com/helabenkhalfallah/dsa-toolbox/blob/main/benchmark-ds.ts
- In tests files, for example:
- https://github.com/helabenkhalfallah/dsa-toolbox/blob/main/src/data-structures/trees/avl/AVLTree-test.ts
- https://github.com/helabenkhalfallah/dsa-toolbox/blob/main/src/data-structures/trees/b-tree/BTree-test.ts
---
For detailed explanations of each data structure and algorithm, please visit:
- Trees in Data Structures: More than Just Wood
- Heaps: Beyond First-Come-First-Served Queue Wizard
- Yet Another Way to Balance BSTs: The Treaps Approach
- The Secret Life of Caches: A Deep Dive into LRU and LFU
- Probabilistic Data Structures for Large Data Challenges
---
| Metric | Coverage |
|------------|-------------|
| Statements | 91.38% |
| Branches | 91.11% |
| Functions | 96.03% |
| Lines | 91.38% |
| File/Module | % Stmts | % Branch | % Funcs | % Lines | Uncovered Line #s |
|--------------------------------------|------------|-------------|------------|------------|----------------------|
| All files | 91.38 | 91.11 | 96.03 | 91.38 | |
| Algorithms / Search | 96.9 | 92.85 | 100 | 96.9 | |
| BinarySearch.ts | 100 | 100 | 100 | 100 | |ExponentialSearch.ts
| | 100 | 87.5 | 100 | 100 | 70 |HybridSearch.ts
| | 93.33 | 87.5 | 100 | 93.33 | 121-122 |LinearSearch.ts
| | 100 | 100 | 100 | 100 | |TernarySearch.ts
| | 96 | 92.3 | 100 | 96 | 82 |HeapSort.ts
| Algorithms / Sort | 99.44 | 95.23 | 100 | 99.44 | |
| | 100 | 100 | 100 | 100 | |MergeSort.ts
| | 100 | 100 | 100 | 100 | |TimSort.ts
| | 99.24 | 93.47 | 100 | 99.24 | 128 |ComparableNode.ts
| Common Utilities | 85.71 | 100 | 75 | 85.71 | |
| | 85.71 | 100 | 75 | 85.71 | 50-51 |LFU.ts
| Data Structures / Caching | 100 | 94.59 | 100 | 100 | |
| | 100 | 90.9 | 100 | 100 | 75,148 |LRU.ts
| | 100 | 100 | 100 | 100 | |MaxHeap.ts
| Data Structures / Heaps | 97.14 | 93.87 | 88.88 | 97.14 | |
| | 97.14 | 96 | 88.88 | 97.14 | 138-139 |MinHeap.ts
| | 97.14 | 91.66 | 88.88 | 97.14 | 139-140 |DoublyLinkedList.ts
| Data Structures / Linked Lists | 97.04 | 89.06 | 100 | 97.04 | |
| | 95.65 | 88.57 | 100 | 95.65 | 87-89,91 |LinkedList.ts
| | 98.7 | 89.65 | 100 | 98.7 | 75 |Composition.ts
| Functional Programming (FP) | 96.38 | 100 | 93.61 | 96.38 | |
| | 77.77 | 87.5 | 100 | 77.77 | 18-19 |Curry.ts
| | 91.3 | 88.88 | 100 | 91.3 | 49-50 |CanApply.ts
| | 100 | 85.71 | 100 | 100 | 29 |Effect.ts
| | 100 | 100 | 100 | 100 | |Option.ts
| | 96.87 | 100 | 95 | 96.87 | 15-16 |Result.ts
| | 94.44 | 100 | 90.9 | 94.44 | 16-17,26-27 |Partial.ts` | 100 | 100 | 100 | 100 | |
|
---
For contributions, we invite you to read our Contributing Guide to get started and ensure a smooth process.
---
Happy coding with the DSA Toolbox! 🎉