0
# Mnemonist
1
2
Mnemonist is a comprehensive JavaScript data structures library providing efficient implementations of 40+ data structures for JavaScript and TypeScript applications. It features classic structures like heaps, tries, linked lists, LRU caches, alongside specialized implementations including Fibonacci heaps, K-D trees, bloom filters, bit vectors, sparse sets, and metric space indexation structures.
3
4
## Package Information
5
6
- **Package Name**: mnemonist
7
- **Package Type**: npm
8
- **Language**: JavaScript with TypeScript definitions
9
- **Installation**: `npm install mnemonist`
10
- **Repository**: https://github.com/yomguithereal/mnemonist
11
- **Version**: 0.40.3
12
13
## Core Imports
14
15
### ES Modules (Recommended)
16
17
```typescript
18
// Import specific data structures
19
import {Heap, LRUCache, BitSet, Trie} from "mnemonist";
20
21
// Import with types
22
import {Heap, MinHeap, MaxHeap} from "mnemonist";
23
24
// Import utility functions
25
import {nsmallest, nlargest} from "mnemonist";
26
27
// Import individual modules
28
import Heap from "mnemonist/heap";
29
import LRUCache from "mnemonist/lru-cache";
30
```
31
32
### CommonJS
33
34
```javascript
35
// Import specific data structures
36
const {Heap, LRUCache, BitSet, Trie} = require("mnemonist");
37
38
// Import utility functions
39
const {nsmallest, nlargest} = require("mnemonist");
40
41
// Import individual modules
42
const Heap = require("mnemonist/heap");
43
const LRUCache = require("mnemonist/lru-cache");
44
```
45
46
### Full Library Import (Not Recommended for Production)
47
48
```javascript
49
import * as mnemonist from "mnemonist";
50
const heap = new mnemonist.Heap();
51
```
52
53
## Basic Usage
54
55
```typescript
56
import {Heap, LRUCache, BitSet, Trie} from "mnemonist";
57
58
// Priority queue with heap
59
const minHeap = new Heap();
60
minHeap.push(5, 2, 8, 1);
61
console.log(minHeap.pop()); // 1
62
63
// LRU Cache
64
const cache = new LRUCache(100);
65
cache.set("key", "value");
66
console.log(cache.get("key")); // "value"
67
68
// Bit operations
69
const bitSet = new BitSet(32);
70
bitSet.set(5, 1);
71
console.log(bitSet.test(5)); // true
72
73
// Prefix tree
74
const trie = new Trie();
75
trie.add("hello");
76
trie.add("help");
77
console.log(trie.has("help")); // true
78
```
79
80
## Architecture
81
82
Mnemonist is designed with several key principles:
83
84
- **Memory Efficiency**: Optimized implementations using typed arrays and minimal object allocations
85
- **Performance**: O(1), O(log n), and other optimal time complexities for core operations
86
- **Type Safety**: Complete TypeScript definitions with generic type parameters
87
- **Modularity**: Individual imports available for optimal bundle size
88
- **Consistency**: Common method patterns across all data structures
89
90
### Common Interface Patterns
91
92
Most data structures in mnemonist follow consistent patterns:
93
94
```typescript { .api }
95
interface CommonMethods<T> {
96
// Core operations
97
clear(): void;
98
size: number;
99
100
// Iteration support
101
values(): Iterator<T>;
102
entries(): Iterator<[any, T]>;
103
keys(): Iterator<any>;
104
forEach(callback: (value: T, key?: any) => void): void;
105
[Symbol.iterator](): Iterator<T>;
106
107
// Debugging
108
inspect(): any;
109
}
110
```
111
112
## Capabilities
113
114
### Heaps & Priority Queues
115
116
High-performance priority queues for efficient minimum/maximum element access with logarithmic insertion and removal.
117
118
```typescript { .api }
119
// Basic heap operations
120
function Heap<T>(comparator?: (a: T, b: T) => number): Heap<T>;
121
function MinHeap<T>(comparator?: (a: T, b: T) => number): MinHeap<T>;
122
function MaxHeap<T>(comparator?: (a: T, b: T) => number): MaxHeap<T>;
123
function FibonacciHeap<T>(comparator?: (a: T, b: T) => number): FibonacciHeap<T>;
124
```
125
126
[Heaps & Priority Queues](./heaps.md)
127
128
### Vectors & Arrays
129
130
Memory-efficient resizable arrays with typed backing storage and bit-packed boolean arrays for space optimization.
131
132
```typescript { .api }
133
// Vector constructors
134
function Vector<T>(ArrayClass: ArrayConstructor, capacity?: number): Vector<T>;
135
function BitVector(length: number): BitVector;
136
function BitSet(length: number): BitSet;
137
138
// Typed vector variants
139
function Uint8Vector(capacity?: number): Uint8Vector;
140
function Float32Vector(capacity?: number): Float32Vector;
141
function PointerVector(capacity?: number): PointerVector;
142
```
143
144
[Vectors & Arrays](./vectors.md)
145
146
### Caches
147
148
LRU (Least Recently Used) caches with configurable capacity and efficient eviction policies for memory management.
149
150
```typescript { .api }
151
// Cache constructors
152
function LRUCache<K, V>(capacity: number): LRUCache<K, V>;
153
function LRUCacheWithDelete<K, V>(capacity: number): LRUCacheWithDelete<K, V>;
154
function LRUMap<K, V>(capacity: number): LRUMap<K, V>;
155
```
156
157
[Caches](./caches.md)
158
159
### Maps & Associative Collections
160
161
Advanced mapping structures including bidirectional maps, multi-value maps, and fuzzy matching capabilities.
162
163
```typescript { .api }
164
// Map constructors
165
function BiMap<K, V>(): BiMap<K, V>;
166
function MultiMap<K, V>(container?: ArrayConstructor | SetConstructor): MultiMap<K, V>;
167
function DefaultMap<K, V>(factory: () => V): DefaultMap<K, V>;
168
function FuzzyMap<V>(distance: DistanceFunction, tolerance: number): FuzzyMap<V>;
169
```
170
171
[Maps & Associative Collections](./maps.md)
172
173
### Sets & Set Operations
174
175
Efficient set implementations including sparse sets for integer keys and functional set operations.
176
177
```typescript { .api }
178
// Set constructors
179
function SparseSet(capacity: number): SparseSet;
180
function SparseQueueSet(capacity: number): SparseQueueSet;
181
function StaticDisjointSet(size: number): StaticDisjointSet;
182
183
// Set operations namespace
184
namespace set {
185
function intersection<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
186
function union<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
187
function difference<T>(a: Iterable<T>, b: Iterable<T>): Set<T>;
188
}
189
```
190
191
[Sets & Set Operations](./sets.md)
192
193
### Trees & Hierarchical Structures
194
195
Tree data structures for prefix matching, spatial queries, fuzzy search, and range operations.
196
197
```typescript { .api }
198
// Tree constructors
199
function Trie<T>(Token?: new () => T): Trie<T>;
200
function TrieMap<T, V>(Token?: new () => T): TrieMap<T, V>;
201
function BKTree(distance: DistanceFunction): BKTree;
202
function KDTree(dimensions: number, distance?: DistanceFunction): KDTree;
203
function VPTree(distance: DistanceFunction, items?: any[]): VPTree;
204
```
205
206
[Trees & Hierarchical Structures](./trees.md)
207
208
### Linear Data Structures
209
210
Classic linear data structures including queues, stacks, linked lists, and circular buffers.
211
212
```typescript { .api }
213
// Linear structure constructors
214
function Queue<T>(): Queue<T>;
215
function Stack<T>(): Stack<T>;
216
function LinkedList<T>(): LinkedList<T>;
217
function CircularBuffer<T>(ArrayClass: ArrayConstructor, capacity: number): CircularBuffer<T>;
218
function FixedDeque<T>(ArrayClass: ArrayConstructor, capacity: number): FixedDeque<T>;
219
```
220
221
[Linear Data Structures](./linear.md)
222
223
### Specialized Algorithms & Structures
224
225
Advanced data structures for specific algorithmic applications including bloom filters, suffix arrays, and search indexes.
226
227
```typescript { .api }
228
// Specialized structure constructors
229
function BloomFilter(capacity: number, errorRate?: number): BloomFilter;
230
function SuffixArray(string: string | string[]): SuffixArray;
231
function InvertedIndex(tokenizer?: TokenizerFunction): InvertedIndex;
232
function SymSpell(options?: SymSpellOptions): SymSpell;
233
function PassjoinIndex(options: PassjoinOptions): PassjoinIndex;
234
```
235
236
[Specialized Algorithms & Structures](./specialized.md)
237
238
## Type Definitions
239
240
### Common Types
241
242
```typescript { .api }
243
// Comparison function used by heaps and sorted structures
244
type ComparatorFunction<T> = (a: T, b: T) => number;
245
246
// Distance function used by metric trees and fuzzy structures
247
type DistanceFunction<T = string> = (a: T, b: T) => number;
248
249
// Tokenizer function for text processing
250
type TokenizerFunction = (text: string) => string[];
251
252
// Array constructor types for typed backing storage
253
type ArrayConstructor =
254
| Uint8ArrayConstructor
255
| Uint16ArrayConstructor
256
| Uint32ArrayConstructor
257
| Int8ArrayConstructor
258
| Int16ArrayConstructor
259
| Int32ArrayConstructor
260
| Float32ArrayConstructor
261
| Float64ArrayConstructor;
262
```
263
264
### Iterator Types
265
266
```typescript { .api }
267
// Standard iteration interfaces implemented by most structures
268
interface Iterator<T> {
269
next(): IteratorResult<T>;
270
[Symbol.iterator](): Iterator<T>;
271
}
272
273
interface IteratorResult<T> {
274
done: boolean;
275
value: T;
276
}
277
```
278
279
## Performance Characteristics
280
281
Mnemonist data structures are optimized for performance with the following general characteristics:
282
283
- **Heap operations**: O(log n) insertion/deletion, O(1) peek
284
- **Cache operations**: O(1) get/set/delete with LRU eviction
285
- **Vector operations**: O(1) amortized append, O(1) random access
286
- **Trie operations**: O(k) where k is key length
287
- **Spatial tree queries**: O(log n) average case for nearest neighbor
288
- **Set operations**: O(1) for sparse integer sets, O(n) for functional operations
289
290
## Dependencies
291
292
- **obliterator** (^2.0.4): Iterator utilities and functional programming helpers used internally by some data structures
293
294
The library is designed to minimize external dependencies while providing comprehensive functionality.