Mnemonist

https://github.com/yomguithereal/mnemonist
Admin
Mnemonist is a curated collection of data structures for JavaScript and TypeScript, including...
Tokens:13,953
Snippets:79
Trust Score:9.5
License:MIT
Update:6 months ago
Show doc for...
Tokens:
Raw
### Setup and Test Mnemonist Development Environment

Source: https://github.com/yomguithereal/mnemonist/blob/master/README.md

These commands clone the repository, install dependencies, lint the source code, and execute the unit test suite.

```bash
git clone git@github.com:Yomguithereal/mnemonist.git
cd mnemonist
npm install
npm run lint
npm test
```

--------------------------------

### LRU Cache Implementation in JavaScript

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Shows how to use the LRUCache from mnemonist, including setting capacity, getting and checking for items, eviction policies, and using typed arrays for keys and values. Demonstrates setpop and iteration.

```javascript
const LRUCache = require('mnemonist/lru-cache');

// Create cache with capacity
const cache = new LRUCache(3);

cache.set('a', 1);
cache.set('b', 2);
cache.set('c', 3);

console.log(cache.get('a')); // 1 (moves 'a' to front)
console.log(cache.has('b')); // true

// Adding new item evicts least recently used
cache.set('d', 4);
console.log(cache.has('b')); // false ('b' was evicted)

// Peek without affecting order
console.log(cache.peek('c')); // 3 (doesn't move 'c' to front)

// setpop: set and return evicted item info
cache.clear();
cache.set('x', 10);
cache.set('y', 20);
cache.set('z', 30);

const evicted = cache.setpop('w', 40);
console.log(evicted); // { evicted: true, key: 'x', value: 10 }

// Iterate over entries (most to least recently used)
for (const [key, value] of cache) {
  console.log(key, value);
}

// Use typed arrays for keys/values
const TypedLRUCache = require('mnemonist/lru-cache');
const typedCache = new TypedLRUCache(Uint32Array, Float64Array, 1000);
typedCache.set(1, 3.14);
typedCache.set(2, 2.71);

```

--------------------------------

### Implement Singly Linked List with Mnemonist

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Provides examples for managing a singly linked list, including adding elements to the front or end and removing them. It also demonstrates iteration and conversion to arrays.

```javascript
const LinkedList = require('mnemonist/linked-list');

const list = new LinkedList();

list.push('a');    // Add to end
list.push('b');
list.unshift('z'); // Add to beginning

console.log(list.size);    // 3
console.log(list.first()); // 'z' (or use list.peek())
console.log(list.last());  // 'b'

console.log(list.shift()); // 'z' (removes and returns first)
console.log(list.first()); // 'a'

// Convert to array
console.log(list.toArray()); // ['a', 'b']

// Build from iterable
const list2 = LinkedList.from([1, 2, 3, 4, 5]);

// Iterate
for (const item of list2) {
  console.log(item);
}

list2.forEach((value, index) => {
  console.log(`Index ${index}: ${value}`);
});
```

--------------------------------

### Install Mnemonist via NPM

Source: https://github.com/yomguithereal/mnemonist/blob/master/README.md

This command installs the Mnemonist library as a dependency in your project using the Node Package Manager.

```bash
npm install --save mnemonist
```

--------------------------------

### KD-Tree for Nearest Neighbor Search in JavaScript

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Explains how to use a KD-Tree for efficient nearest neighbor queries in multi-dimensional space. It covers creating a tree from labeled points with specified dimensions, finding the single nearest neighbor, and retrieving multiple nearest neighbors (k-NN). Examples include 2D and 3D points, and building a tree from pre-organized axes.

```javascript
const KDTree = require('mnemonist/kd-tree');

// Create from labeled points: [label, [coordinates]]
const points = [
  ['A', [2, 3]],
  ['B', [5, 4]],
  ['C', [9, 6]],
  ['D', [4, 7]],
  ['E', [8, 1]],
  ['F', [7, 2]]
];

const tree = KDTree.from(points, 2); // 2 dimensions

console.log(tree.size); // 6

// Find nearest neighbor
const nearest = tree.nearestNeighbor([3, 4]);
console.log(nearest); // 'A' or 'B' (closest to [3, 4])

// Find k nearest neighbors
const kNearest = tree.kNearestNeighbors(3, [5, 5]);
console.log(kNearest); // Array of 3 closest labels

// 3D example
const points3D = [
  ['origin', [0, 0, 0]],
  ['point1', [1, 1, 1]],
  ['point2', [2, 2, 2]],
  ['point3', [5, 5, 5]]
];

const tree3D = KDTree.from(points3D, 3);
console.log(tree3D.nearestNeighbor([1.5, 1.5, 1.5])); // 'point1' or 'point2'

// Build from axes (for pre-organized data)
const xAxis = new Float64Array([2, 5, 9, 4, 8, 7]);
const yAxis = new Float64Array([3, 4, 6, 7, 1, 2]);
const labels = ['A', 'B', 'C', 'D', 'E', 'F'];

const treeFromAxes = KDTree.fromAxes([xAxis, yAxis], labels);
console.log(treeFromAxes.nearestNeighbor([6, 3])); // Label of nearest point
```

--------------------------------

### Optimizing Regex Usage in JavaScript

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Demonstrates the performance benefit of pre-compiling regular expressions instead of creating them within functions. The 'BAD' example shows repeated regex creation, while the 'GOOD' example uses a pre-defined constant.

```javascript
// BAD!
const test = x => /regex/.test(x);

// GOOD!
const REGEX = /regex/;
const test = x => REGEX.test(x);
```

--------------------------------

### BK-Tree for Fuzzy String Matching in JavaScript

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Illustrates the use of a BK-Tree for efficient fuzzy string matching, utilizing a provided distance metric like Levenshtein distance. The example includes a Levenshtein distance function implementation, adding words to the tree, and searching for words within a specified distance. It also shows how to build a BK-Tree from an array of words.

```javascript
const BKTree = require('mnemonist/bk-tree');

// Simple Levenshtein distance function
function levenshtein(a, b) {
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  const matrix = [];
  for (let i = 0; i <= b.length; i++) matrix[i] = [i];
  for (let j = 0; j <= a.length; j++) matrix[0][j] = j;

  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      matrix[i][j] = b.charAt(i - 1) === a.charAt(j - 1)
        ? matrix[i - 1][j - 1]
        : Math.min(
            matrix[i - 1][j - 1] + 1,
            matrix[i][j - 1] + 1,
            matrix[i - 1][j] + 1
          );
    }
  }
  return matrix[b.length][a.length];
}

const tree = new BKTree(levenshtein);

tree.add('cat');
tree.add('car');
tree.add('cart');
tree.add('dog');
tree.add('bat');

// Search for words within distance 1 of 'cat'
const results = tree.search(1, 'cat');
console.log(results);
// [ 
//   { item: 'cat', distance: 0 },
//   { item: 'car', distance: 1 },
//   { item: 'bat', distance: 1 }
// ]

// Search with larger tolerance
const results2 = tree.search(2, 'cart');
console.log(results2);
// Includes words within distance 2 of 'cart'

// Build from iterable
const dictionary = ['hello', 'help', 'held', 'world', 'word'];
const spellTree = BKTree.from(dictionary, levenshtein);

const suggestions = spellTree.search(2, 'helo');
console.log(suggestions.map(r => r.item)); // ['hello', 'help', 'held']
```

--------------------------------

### DefaultMap: Automatic Default Value Creation (JavaScript)

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates DefaultMap, which automatically assigns a default value to a key upon its first access if it doesn't exist. Examples include counting occurrences, grouping items into arrays, and generating auto-incrementing IDs.

```javascript
const DefaultMap = require('mnemonist/default-map');

// Factory function receives (key, currentSize)
const counts = new DefaultMap(() => 0);

// Auto-creates default on first access
counts.get('apple');
console.log(counts.get('apple')); // 0

// Common pattern: counting
const wordCounts = new DefaultMap(() => 0);
const words = ['cat', 'dog', 'cat', 'bird', 'cat', 'dog'];
words.forEach(word => {
  wordCounts.set(word, wordCounts.get(word) + 1);
});
console.log(wordCounts.get('cat')); // 3

// Grouping with arrays
const grouped = new DefaultMap(() => []);
const items = [
  { type: 'fruit', name: 'apple' },
  { type: 'vegetable', name: 'carrot' },
  { type: 'fruit', name: 'banana' }
];
items.forEach(item => {
  grouped.get(item.type).push(item.name);
});
console.log(grouped.get('fruit')); // ['apple', 'banana']

// Auto-incrementing IDs
const ids = new DefaultMap(DefaultMap.autoIncrement());
console.log(ids.get('first'));  // 0
console.log(ids.get('second')); // 1
console.log(ids.get('first'));  // 0 (same key returns same ID)

// Peek without creating default
const map = new DefaultMap(() => []);
console.log(map.peek('nonexistent')); // undefined
console.log(map.has('nonexistent')); // false
```

--------------------------------

### Efficient LRU Cache Data Structures (JavaScript)

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Illustrates the underlying data structures for an efficient LRU (Least Recently Used) cache. It involves a doubly linked list to manage the order of usage and a map to store items and their corresponding pointers in the list. This allows for O(1) complexity for set, get, and evict operations.

```javascript
// A ~doubly~ linked list:
// head     = 0
// tail     = 2
// next     = [1, 2, 0]
// prev     = [0, 1, 2]

// Same as (with pointers):
// head -> (a) <-> (b) <-> (c) <- tail

// A map to pointers & values:
// items  = {a: 0, b: 1, c: 2}
// values = [a, b, c]
```

--------------------------------

### Illustrating Mixed Type Arrays in JavaScript

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

This snippet shows an example of an array containing elements of various data types. While JavaScript allows this, it's often considered bad practice in performance-critical code due to potential type coercion issues and reduced optimization opportunities.

```javascript
// Why do you do that?
// If you are this kind of person, can we meet?
// I really want to understand.
const array = [1, 'two', '3', /four/, {five: new Date()}];
```

--------------------------------

### Implement FIFO Queue with Mnemonist

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates how to initialize, populate, and manipulate a high-performance FIFO queue. It covers enqueueing, dequeueing, peeking, and converting the queue to an array or building it from iterables.

```javascript
const Queue = require('mnemonist/queue');

const queue = new Queue();

queue.enqueue('first');
queue.enqueue('second');
queue.enqueue('third');

console.log(queue.size);    // 3
console.log(queue.peek());  // 'first' (doesn't remove)
console.log(queue.dequeue()); // 'first' (removes and returns)
console.log(queue.dequeue()); // 'second'

// Convert to array
console.log(queue.toArray()); // ['third']

// Build from iterable
const queue2 = Queue.from([1, 2, 3, 4, 5]);
console.log(queue2.dequeue()); // 1

// Build from arguments
const queue3 = Queue.of('a', 'b', 'c');
console.log(queue3.dequeue()); // 'a'

// Iterate over queue
for (const item of queue2) {
  console.log(item);
}
```

--------------------------------

### Heap Implementation in JavaScript

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates the usage of Heap, MinHeap, and MaxHeap from the mnemonist library. Supports custom comparators, building from iterables, and finding n-smallest/largest elements. It also shows pushpop and replace operations.

```javascript
const { Heap, MinHeap, MaxHeap } = require('mnemonist/heap');

// Create a min-heap (default)
const minHeap = new Heap();
minHeap.push(5);
minHeap.push(1);
minHeap.push(3);

console.log(minHeap.peek()); // 1 (smallest element)
console.log(minHeap.pop());  // 1 (removes and returns smallest)
console.log(minHeap.size);   // 2

// Create a max-heap
const maxHeap = new MaxHeap();
maxHeap.push(5);
maxHeap.push(1);
maxHeap.push(3);

console.log(maxHeap.peek()); // 5 (largest element)
console.log(maxHeap.pop());  // 5

// Custom comparator for objects
const taskHeap = new Heap((a, b) => a.priority - b.priority);
taskHeap.push({ name: 'Task A', priority: 3 });
taskHeap.push({ name: 'Task B', priority: 1 });
taskHeap.push({ name: 'Task C', priority: 2 });

console.log(taskHeap.pop()); // { name: 'Task B', priority: 1 }

// Build heap from iterable (linear time)
const heap = Heap.from([5, 2, 8, 1, 9]);
console.log(heap.consume()); // [1, 2, 5, 8, 9] - sorted array

// Get n smallest/largest from iterable
const smallest = Heap.nsmallest(3, [5, 2, 8, 1, 9, 4]);
console.log(smallest); // [1, 2, 4]

const largest = Heap.nlargest(3, [5, 2, 8, 1, 9, 4]);
console.log(largest); // [9, 8, 5]

// Replace: pop then push in single operation
const replaced = heap.replace(3);
console.log(replaced); // returns old top element

// Pushpop: push then pop in single operation
const popped = heap.pushpop(0);
console.log(popped); // returns smallest after push

```

--------------------------------

### Implement LIFO Stack with Mnemonist

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Shows the usage of a LIFO stack, including pushing, popping, and peeking at the top element. It also demonstrates stack initialization from iterables and arguments.

```javascript
const Stack = require('mnemonist/stack');

const stack = new Stack();

stack.push('first');
stack.push('second');
stack.push('third');

console.log(stack.size);   // 3
console.log(stack.peek()); // 'third' (top element)
console.log(stack.pop());  // 'third' (removes and returns top)
console.log(stack.pop());  // 'second'

// Convert to array (top to bottom)
console.log(stack.toArray()); // ['first']

// Build from iterable
const stack2 = Stack.from([1, 2, 3]);
console.log(stack2.pop()); // 3

// Build from arguments
const stack3 = Stack.of('a', 'b', 'c');
console.log(stack3.pop()); // 'c'
```

--------------------------------

### Implementing a Linked List with Object References (JavaScript)

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Demonstrates a basic implementation of a linked list using JavaScript object references to simulate pointers. Each node contains a value and a reference to the next node. This approach is intuitive but can be less memory-efficient than array-based methods.

```javascript
// Using object references as pointers
function LinkedListNode(value) {
  this.next = null;
  this.value = value;
}
// Changing a pointer
node.next = otherNode;
```

--------------------------------

### Implement JSON Serialization and String Representation

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Demonstrates how to implement the toJSON and toString methods to allow custom data structures to be serialized by JSON.stringify and represented as strings.

```javascript
Structure.prototype.toJSON = function() {
  return this.items;
};

Structure.prototype.toString = function() {
  return somethingUsefulForOnce;
};
```

--------------------------------

### Bloom Filter Implementation in JavaScript

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates creating and using a Bloom Filter for efficient, albeit probabilistic, membership testing. It shows initialization with capacity or error rate, adding elements, and testing for their presence, noting the possibility of false positives but no false negatives. It also covers building a filter from an iterable.

```javascript
const BloomFilter = require('mnemonist/bloom-filter');

// Create with expected capacity
const filter = new BloomFilter(1000);

filter.add('hello');
filter.add('world');
filter.add('foo');

// Test membership (may have false positives, never false negatives)
console.log(filter.test('hello')); // true
console.log(filter.test('world')); // true
console.log(filter.test('bar'));   // false (probably)

// Create with custom error rate
const preciseFilter = new BloomFilter({
  capacity: 1000,
  errorRate: 0.001  // 0.1% false positive rate
});

// Build from iterable
const words = ['cat', 'dog', 'bird', 'fish'];
const wordFilter = BloomFilter.from(words, words.length);

console.log(wordFilter.test('cat'));   // true
console.log(wordFilter.test('snake')); // false (probably)
```

--------------------------------

### Implement Prefix Trie with Mnemonist

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates using a Trie for efficient string storage and prefix-based lookups. Includes adding, deleting, and searching for words based on prefixes.

```javascript
const Trie = require('mnemonist/trie');

const trie = new Trie();

trie.add('cat');
trie.add('car');
trie.add('card');
trie.add('cart');
trie.add('dog');

console.log(trie.size);       // 5
console.log(trie.has('car')); // true
console.log(trie.has('ca'));  // false (not a complete word)

// Find all words with prefix
const matches = trie.find('car');
console.log(matches); // ['car', 'card', 'cart']

const catMatches = trie.find('cat');
console.log(catMatches); // ['cat']

// Delete a word
trie.delete('card');
console.log(trie.find('car')); // ['car', 'cart']

// Build from iterable
const trie2 = Trie.from(['apple', 'application', 'apply', 'banana']);
console.log(trie2.find('app')); // ['apple', 'application', 'apply']

// Iterate over all keys
for (const word of trie) {
  console.log(word);
}
```

--------------------------------

### Implement TrieMap with Mnemonist

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Shows how to use a TrieMap to associate values with string keys. It includes setting values, retrieving them, finding entries by prefix, and updating values using callbacks.

```javascript
const TrieMap = require('mnemonist/trie-map');

const trieMap = new TrieMap();

trieMap.set('cat', { type: 'animal', legs: 4 });
trieMap.set('car', { type: 'vehicle', wheels: 4 });
trieMap.set('card', { type: 'object', material: 'paper' });

console.log(trieMap.size);       // 3
console.log(trieMap.get('cat')); // { type: 'animal', legs: 4 }
console.log(trieMap.has('car')); // true

// Find all entries with prefix
const results = trieMap.find('car');
console.log(results);

// Update value using callback
trieMap.update('cat', (oldValue) => ({ ...oldValue, sound: 'meow' }));
console.log(trieMap.get('cat')); // { type: 'animal', legs: 4, sound: 'meow' }

// Iterate over entries
for (const [key, value] of trieMap) {
  console.log(key, value);
}

// Iterate over keys only
for (const key of trieMap.keys()) {
  console.log(key);
}
```

--------------------------------

### Fibonacci Heap Implementation in JavaScript

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Illustrates the use of FibonacciHeap, MinFibonacciHeap, and MaxFibonacciHeap from mnemonist. It covers basic operations like push, peek, pop, and building from an iterable.

```javascript
const { FibonacciHeap, MinFibonacciHeap, MaxFibonacciHeap } = require('mnemonist/fibonacci-heap');

// Create a min fibonacci heap
const heap = new FibonacciHeap();

heap.push(10);
heap.push(5);
heap.push(15);

console.log(heap.peek()); // 5 (minimum element)
console.log(heap.size);   // 3

console.log(heap.pop());  // 5
console.log(heap.pop());  // 10
console.log(heap.pop());  // 15

// Max fibonacci heap
const maxHeap = new MaxFibonacciHeap();
maxHeap.push(10);
maxHeap.push(5);
maxHeap.push(15);

console.log(maxHeap.pop()); // 15

// Build from iterable
const fheap = FibonacciHeap.from([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(fheap.pop()); // 1

```

--------------------------------

### Implementing a MultiSet in JavaScript

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Demonstrates the simplification of counting occurrences by replacing manual object-based bookkeeping with a dedicated MultiSet structure.

```javascript
// How about changing this:
const counts = {};

for (const item in something) {
  if (!(item in counts))
    counts[item] = 0;

  counts[item]++;
}

// Into this:
const counts = new MultiSet();

for (const item in something)
  counts.add(item);
```

--------------------------------

### Using Graph Data Structures

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Shows how a dedicated graph library provides a cleaner, more legible interface for common graph operations compared to manual array/object implementations.

```javascript
const graph = new Graph();

// Finding specific neighbors
const neighbors = graph.outNeighbors(node);

// Iterating over a node's edges
graph.forEachEdge(node, (edge, attributes) => {
  console.log(attributes.weight);
});
```

--------------------------------

### Linked List API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Shows how to use the Linked List for efficient insertions and deletions at both ends, along with sequential access.

```APIDOC
## Linked List

A singly linked list implementation optimized for sequential access and insertions at both ends.

### Usage Example
```javascript
const LinkedList = require('mnemonist/linked-list');

const list = new LinkedList();

list.push('a');    // Add to end
list.push('b');
list.unshift('z'); // Add to beginning

console.log(list.size);    // 3
console.log(list.first()); // 'z' (or use list.peek())
console.log(list.last());  // 'b'

console.log(list.shift()); // 'z' (removes and returns first)
console.log(list.first()); // 'a'

// Convert to array
console.log(list.toArray()); // ['a', 'b']

// Build from iterable
const list2 = LinkedList.from([1, 2, 3, 4, 5]);

// Iterate
for (const item of list2) {
  console.log(item);
}

list2.forEach((value, index) => {
  console.log(`Index ${index}: ${value}`);
});
```
```

--------------------------------

### BK-Tree API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Illustrates the implementation and application of the BK-Tree for fuzzy string matching using distance metrics like Levenshtein distance.

```APIDOC
## BK-Tree

A Burkhard-Keller tree for efficient fuzzy string matching using a distance metric like Levenshtein distance.

### Usage

```javascript
const BKTree = require('mnemonist/bk-tree');

// Simple Levenshtein distance function
function levenshtein(a, b) {
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  const matrix = [];
  for (let i = 0; i <= b.length; i++) matrix[i] = [i];
  for (let j = 0; j <= a.length; j++) matrix[0][j] = j;

  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      matrix[i][j] = b.charAt(i - 1) === a.charAt(j - 1)
        ? matrix[i - 1][j - 1]
        : Math.min(
            matrix[i - 1][j - 1] + 1,
            matrix[i][j - 1] + 1,
            matrix[i - 1][j] + 1
          );
    }
  }
  return matrix[b.length][a.length];
}

const tree = new BKTree(levenshtein);

tree.add('cat');
tree.add('car');
tree.add('cart');
tree.add('dog');
tree.add('bat');

// Search for words within distance 1 of 'cat'
const results = tree.search(1, 'cat');
console.log(results);
// [
//   { item: 'cat', distance: 0 },
//   { item: 'car', distance: 1 },
//   { item: 'bat', distance: 1 }
// ]

// Search with larger tolerance
const results2 = tree.search(2, 'cart');
console.log(results2); // Includes words within distance 2 of 'cart'

// Build from iterable
const dictionary = ['hello', 'help', 'held', 'world', 'word'];
const spellTree = BKTree.from(dictionary, levenshtein);

const suggestions = spellTree.search(2, 'helo');
console.log(suggestions.map(r => r.item)); // ['hello', 'help', 'held']
```
```

--------------------------------

### MultiMap: Key-Value with Multiple Values (JavaScript)

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates how to use MultiMap to store multiple values associated with a single key. It shows default Array container usage, custom Set container for uniqueness, and methods for adding, retrieving, and removing elements.

```javascript
const MultiMap = require('mnemonist/multi-map');

// Default uses Array as container
const multimap = new MultiMap();

multimap.set('colors', 'red');
multimap.set('colors', 'blue');
multimap.set('colors', 'green');
multimap.set('fruits', 'apple');

console.log(multimap.size);      // 4 (total values)
console.log(multimap.dimension); // 2 (number of keys)
console.log(multimap.get('colors')); // ['red', 'blue', 'green']

// Check multiplicity (count of values for a key)
console.log(multimap.multiplicity('colors')); // 3
console.log(multimap.count('fruits'));        // 1 (alias)

// Remove specific value from key
multimap.remove('colors', 'blue');
console.log(multimap.get('colors')); // ['red', 'green']

// Delete entire key
multimap.delete('fruits');
console.log(multimap.has('fruits')); // false

// Use Set as container (prevents duplicates)
const setMultimap = new MultiMap(Set);
setMultimap.set('tags', 'javascript');
setMultimap.set('tags', 'javascript'); // Duplicate ignored
setMultimap.set('tags', 'nodejs');
console.log(setMultimap.multiplicity('tags')); // 2

// Iterate over all key-value pairs
for (const [key, value] of multimap) {
  console.log(key, value);
}

// Iterate over associations (key -> container)
multimap.forEachAssociation((container, key) => {
  console.log(`${key}: ${container.join(', ')}`);
});
```

--------------------------------

### Optimizing Map Lookups

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Illustrates a performance optimization technique by reducing the number of map lookups in a getter method from two to one.

```javascript
// You made 2 lookups
Graph.prototype.getNodeAttribute = function(node, data) {
  if (this._nodes.has(node))
    throw Error(...);

  const data = this._nodes.get(node);

  return data[name];
};

// You made only one
Graph.prototype.getNodeAttribute = function(node, data) {
  const data = this._nodes.get(node);

  if (typeof data === 'undefined')
    throw Error(...);

  return data[name];
};
```

--------------------------------

### Stack API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Illustrates the Stack data structure for LIFO operations, including push, pop, and peeking at the top element.

```APIDOC
## Stack

A LIFO stack implementation with optimal push/pop performance.

### Usage Example
```javascript
const Stack = require('mnemonist/stack');

const stack = new Stack();

stack.push('first');
stack.push('second');
stack.push('third');

console.log(stack.size);   // 3
console.log(stack.peek()); // 'third' (top element)
console.log(stack.pop());  // 'third' (removes and returns top)
console.log(stack.pop());  // 'second'

// Convert to array (top to bottom)
console.log(stack.toArray()); // ['first']

// Build from iterable
const stack2 = Stack.from([1, 2, 3]);
console.log(stack2.pop()); // 3

// Build from arguments
const stack3 = Stack.of('a', 'b', 'c');
console.log(stack3.pop()); // 'c'
```
```

--------------------------------

### BiMap: Bidirectional Key-Value Mapping (JavaScript)

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Explains the BiMap data structure, which allows for one-to-one mappings that can be traversed in both forward and reverse directions. It covers setting pairs, forward/reverse lookups, handling duplicate values, and deletion.

```javascript
const BiMap = require('mnemonist/bi-map');

const bimap = new BiMap();

bimap.set('a', 1);
bimap.set('b', 2);
bimap.set('c', 3);

// Forward lookup
console.log(bimap.get('a')); // 1
console.log(bimap.has('b')); // true

// Reverse lookup via inverse
console.log(bimap.inverse.get(2)); // 'b'
console.log(bimap.inverse.has(3)); // true

// Setting existing value removes old key
bimap.set('d', 1); // 'a' -> 1 is now replaced by 'd' -> 1
console.log(bimap.has('a')); // false
console.log(bimap.get('d')); // 1

// Delete from either direction
bimap.delete('b');
console.log(bimap.inverse.has(2)); // false

// Build from iterable
const bimap2 = BiMap.from(new Map([['x', 10], ['y', 20]]));
console.log(bimap2.inverse.get(10)); // 'x'
```

--------------------------------

### Implementing a Linked List with Byte Arrays (JavaScript)

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Presents an alternative linked list implementation using byte arrays (`Uint16Array` for indices and a standard array for values) to manage nodes and pointers. This method offers more control over memory and can be more performant for large datasets, akin to manual memory allocation in C.

```javascript
// Using byte arrays (capacity is fixed)
function LinkedList(capacity) {
  this.head = 0;
  this.next = new Uint16Array(capacity);
  this.values = new Array(capacity);
}
// Changing a pointer;
this.next[nodeIndex] = otherNodeIndex;
```

--------------------------------

### Queue API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates the usage of the Queue data structure for FIFO operations, including enqueue, dequeue, and peeking.

```APIDOC
## Queue

A high-performance FIFO queue implementation optimized for enqueue/dequeue operations.

### Usage Example
```javascript
const Queue = require('mnemonist/queue');

const queue = new Queue();

queue.enqueue('first');
queue.enqueue('second');
queue.enqueue('third');

console.log(queue.size);    // 3
console.log(queue.peek());  // 'first' (doesn't remove)
console.log(queue.dequeue()); // 'first' (removes and returns)
console.log(queue.dequeue()); // 'second'

// Convert to array
console.log(queue.toArray()); // ['third']

// Build from iterable
const queue2 = Queue.from([1, 2, 3, 4, 5]);
console.log(queue2.dequeue()); // 1

// Build from arguments
const queue3 = Queue.of('a', 'b', 'c');
console.log(queue3.dequeue()); // 'a'

// Iterate over queue
for (const item of queue) {
  console.log(item);
}
```
```

--------------------------------

### TrieMap API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Explains the TrieMap, a prefix tree that associates values with string keys, supporting efficient lookups and updates.

```APIDOC
## TrieMap

A prefix tree that associates values with string keys, combining trie efficiency with map functionality.

### Usage Example
```javascript
const TrieMap = require('mnemonist/trie-map');

const trieMap = new TrieMap();

trieMap.set('cat', { type: 'animal', legs: 4 });
trieMap.set('car', { type: 'vehicle', wheels: 4 });
trieMap.set('card', { type: 'object', material: 'paper' });

console.log(trieMap.size);       // 3
console.log(trieMap.get('cat')); // { type: 'animal', legs: 4 }
console.log(trieMap.has('car')); // true

// Find all entries with prefix
const results = trieMap.find('car');
console.log(results);
// [
//   ['car', { type: 'vehicle', wheels: 4 }],
//   ['card', { type: 'object', material: 'paper' }]
// ]

// Update value using callback
trieMap.update('cat', (oldValue) => ({ ...oldValue, sound: 'meow' }));
console.log(trieMap.get('cat')); // { type: 'animal', legs: 4, sound: 'meow' }

// Iterate over entries
for (const [key, value] of trieMap) {
  console.log(key, value);
}

// Iterate over keys only
for (const key of trieMap.keys()) {
  console.log(key);
}
```
```

--------------------------------

### Implement Iteration Protocols

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Shows how to make custom data structures iterable by implementing the iterator protocol and the Symbol.iterator property, enabling the use of for...of loops.

```javascript
Queue.prototype.values = function() {
  return {
    next: function() {
      return {
        done: false,
        value: whatever
      };
    }
  };
};

Queue.prototype[Symbol.iterator] = Queue.prototype.values;
```

--------------------------------

### Trie API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Details the Trie (prefix tree) for efficient string storage and prefix-based lookups, including adding, checking, finding, and deleting words.

```APIDOC
## Trie

A prefix tree for efficient string storage and prefix-based lookups.

### Usage Example
```javascript
const Trie = require('mnemonist/trie');

const trie = new Trie();

trie.add('cat');
trie.add('car');
trie.add('card');
trie.add('cart');
trie.add('dog');

console.log(trie.size);       // 5
console.log(trie.has('car')); // true
console.log(trie.has('ca'));  // false (not a complete word)

// Find all words with prefix
const matches = trie.find('car');
console.log(matches); // ['car', 'card', 'cart']

const catMatches = trie.find('cat');
console.log(catMatches); // ['cat']

// Delete a word
trie.delete('card');
console.log(trie.find('car')); // ['car', 'cart']

// Build from iterable
const trie2 = Trie.from(['apple', 'application', 'apply', 'banana']);
console.log(trie2.find('app')); // ['apple', 'application', 'apply']

// Iterate over all keys
for (const word of trie) {
  console.log(word);
}
```
```

--------------------------------

### MultiSet: Tracking Element Multiplicity (JavaScript)

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Illustrates the use of MultiSet, also known as a bag, for tracking the count of each element. It covers adding elements, checking multiplicity, calculating frequency, and building MultiSets from iterables.

```javascript
const MultiSet = require('mnemonist/multi-set');

const multiset = new MultiSet();

multiset.add('apple');
multiset.add('apple');
multiset.add('banana');
multiset.add('apple', 3); // Add 3 more apples

console.log(multiset.size);      // 6 (total count)
console.log(multiset.dimension); // 2 (unique elements)

console.log(multiset.multiplicity('apple')); // 5
console.log(multiset.count('banana'));       // 1 (alias)

// Get frequency (proportion)
console.log(multiset.frequency('apple')); // 0.833...

// Remove some occurrences
multiset.remove('apple', 2);
console.log(multiset.multiplicity('apple')); // 3

// Set exact multiplicity
multiset.set('orange', 10);
console.log(multiset.multiplicity('orange')); // 10

// Get top n elements
const top = multiset.top(2);
console.log(top); // [['orange', 10], ['apple', 3]]

// Build from iterable
const words = MultiSet.from(['the', 'cat', 'sat', 'on', 'the', 'mat', 'the']);
console.log(words.multiplicity('the')); // 3

// Check subset/superset relations
const setA = MultiSet.from(['a', 'a', 'b']);
const setB = MultiSet.from(['a', 'a', 'b', 'c']);
console.log(MultiSet.isSubset(setA, setB)); // true
```

--------------------------------

### KD-Tree API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Explains the functionality of the KD-Tree for performing efficient nearest neighbor queries in multi-dimensional spaces.

```APIDOC
## KD-Tree

A k-dimensional tree for efficient nearest neighbor queries in multi-dimensional space.

### Usage

```javascript
const KDTree = require('mnemonist/kd-tree');

// Create from labeled points: [label, [coordinates]]
const points = [
  ['A', [2, 3]],
  ['B', [5, 4]],
  ['C', [9, 6]],
  ['D', [4, 7]],
  ['E', [8, 1]],
  ['F', [7, 2]]
];

const tree = KDTree.from(points, 2); // 2 dimensions

console.log(tree.size); // 6

// Find nearest neighbor
const nearest = tree.nearestNeighbor([3, 4]);
console.log(nearest); // 'A' or 'B' (closest to [3, 4])

// Find k nearest neighbors
const kNearest = tree.kNearestNeighbors(3, [5, 5]);
console.log(kNearest); // Array of 3 closest labels

// 3D example
const points3D = [
  ['origin', [0, 0, 0]],
  ['point1', [1, 1, 1]],
  ['point2', [2, 2, 2]],
  ['point3', [5, 5, 5]]
];

const tree3D = KDTree.from(points3D, 3);
console.log(tree3D.nearestNeighbor([1.5, 1.5, 1.5])); // 'point1' or 'point2'

// Build from axes (for pre-organized data)
const xAxis = new Float64Array([2, 5, 9, 4, 8, 7]);
const yAxis = new Float64Array([3, 4, 6, 7, 1, 2]);
const labels = ['A', 'B', 'C', 'D', 'E', 'F'];

const treeFromAxes = KDTree.fromAxes([xAxis, yAxis], labels);
console.log(treeFromAxes.nearestNeighbor([6, 3])); // Label of nearest point
```
```

--------------------------------

### Bloom Filter API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

Demonstrates the creation and usage of the Bloom Filter for efficient membership testing with configurable error rates.

```APIDOC
## Bloom Filter

A space-efficient probabilistic data structure for membership testing with configurable error rate.

### Usage

```javascript
const BloomFilter = require('mnemonist/bloom-filter');

// Create with expected capacity
const filter = new BloomFilter(1000);

filter.add('hello');
filter.add('world');
filter.add('foo');

// Test membership (may have false positives, never false negatives)
console.log(filter.test('hello')); // true
console.log(filter.test('world')); // true
console.log(filter.test('bar'));   // false (probably)

// Create with custom error rate
const preciseFilter = new BloomFilter({
  capacity: 1000,
  errorRate: 0.001  // 0.1% false positive rate
});

// Build from iterable
const words = ['cat', 'dog', 'bird', 'fish'];
const wordFilter = BloomFilter.from(words, words.length);

console.log(wordFilter.test('cat'));   // true
console.log(wordFilter.test('snake')); // false (probably)
```
```

--------------------------------

### JavaScript Sparse Set for Efficient Integer Operations

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

An optimized set implementation for integer members using sparse and dense arrays, offering O(1) average time complexity for add, delete, and has operations. Supports efficient iteration over members. Dependencies: 'mnemonist/sparse-set'.

```javascript
const SparseSet = require('mnemonist/sparse-set');

// Create with maximum possible value
const set = new SparseSet(100);

set.add(5);
set.add(42);
set.add(17);

console.log(set.size);    // 3
console.log(set.has(42)); // true
console.log(set.has(99)); // false

set.delete(42);
console.log(set.has(42)); // false

// Clear is O(1)
set.clear();
console.log(set.size); // 0

// Efficient iteration
const sparseSet = new SparseSet(1000);
sparseSet.add(100);
sparseSet.add(500);
sparseSet.add(200);

for (const member of sparseSet) {
  console.log(member); // 100, 500, 200 (insertion order)
}

sparseSet.forEach((value) => {
  console.log(value);
});
```

--------------------------------

### DefaultMap API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

A map that automatically creates default values for missing keys, similar to Python's defaultdict.

```APIDOC
## DefaultMap

### Description
A map that initializes missing keys with a value returned by a provided factory function.

### Methods
- **constructor(factory)**: Initializes the map with a function to generate default values.
- **get(key)**: Returns the value, or creates it using the factory if it doesn't exist.
- **peek(key)**: Returns the value without triggering the factory function if the key is missing.

### Request Example
const counts = new DefaultMap(() => 0);
counts.get('apple'); // Returns 0 and sets it in the map
```

--------------------------------

### Recursive vs. Iterative Binary Search Tree Traversal (JavaScript)

Source: https://github.com/yomguithereal/mnemonist/blob/master/docs/fosdem2019/presentation.mdx

Compares a recursive implementation of a binary search tree traversal with an iterative one using a stack. The iterative approach is generally faster and more memory-efficient as it avoids function call overhead and potential stack overflow issues inherent in deep recursion.

```javascript
// Recursive version - "easy"
function recurse(node, key) {
  if (key < node.value) {
    if (node.left)
      return recurse(node.left, key);

    return false;
  }
  else if (key > node.value) {
    if (node.right)
      return recurse(node.right, key);

    return false;
  }

  return true;
}
```

```javascript
// Iterative version - more alien but faster, mileage may vary
function iterative(root, key) {
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    if (key < node.value) {
      if (node.left)
        stack.push(node.left);
      else
        break;
    }
    else if (key > node.value) {
      if (node.right)
        stack.push(node.right);
      else
        break;
    }
    return true;
  }
  return false;
}
```

--------------------------------

### Implement Mnemonist Structure Boilerplate

Source: https://github.com/yomguithereal/mnemonist/blob/master/ADD_TODO_LIST.md

A standard JavaScript template for creating new data structures in Mnemonist. It includes the constructor, essential prototype methods like clear and inspect, and a static from method for iterable conversion.

```javascript
var forEach = require('obliterator/foreach');

function Structure() {
  this.clear();
}

Structure.prototype.clear = function() {
  // Properties
};

Structure.prototype.inspect = function() {
  return this;
};

if (typeof Symbol !== 'undefined')
  Structure.prototype[Symbol.for('nodejs.util.inspect.custom')] = Structure.prototype.inspect;

Structure.from = function(iterable) {

};

module.exports = Structure;
```

--------------------------------

### MultiMap API

Source: https://context7.com/yomguithereal/mnemonist/llms.txt

A map that allows multiple values per key, with customizable container types like Array or Set.

```APIDOC
## MultiMap

### Description
A map that allows multiple values per key. It supports customizable container types (default is Array) to manage values associated with a single key.

### Methods
- **set(key, value)**: Adds a value to the key's container.
- **get(key)**: Returns the container of values for the key.
- **multiplicity(key)**: Returns the number of values for a given key.
- **remove(key, value)**: Removes a specific value from the key's container.
- **delete(key)**: Removes the entire key and its associated values.

### Request Example
const multimap = new MultiMap();
multimap.set('colors', 'red');
multimap.set('colors', 'blue');

### Response
- **size** (number): Total number of values across all keys.
- **dimension** (number): Total number of unique keys.
```
Tokens:
Raw