TreeMultiMap
data-structure-typed / TreeMultiMap
Class: TreeMultiMap<K, V, R>
Defined in: data-structures/binary-tree/tree-multi-map.ts:27
TreeMultiMap (ordered MultiMap) — key → bucket (Array of values).
Semantics (RFC):
- Bucketed design: each key appears once; duplicates live in the bucket.
get(key)returns a live bucket reference.- Default iteration yields bucket entries:
[K, V[]]. - Navigable operations (
first/last/ceiling/...) return entry tuples like TreeMap.
Example
// Morris traversal (O(1) space)
const tmm = new TreeMultiMap<number>([5, 3, 7]);
const result = tmm.morris(n => n.key, 'IN');
console.log(result.length); // > 0;
Type Parameters
K
K = any
V
V = any
R
R = any
Implements
Iterable<[K,V[]]>
Constructors
Constructor
new TreeMultiMap<K, V, R>(keysNodesEntriesOrRaws?, options?): TreeMultiMap<K, V, R>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:44
Creates a new TreeMultiMap.
Parameters
keysNodesEntriesOrRaws?
Iterable<
| K
| R
| [K | null | undefined, V[] | undefined]
| null
| undefined> = []
Initial entries, or raw elements if toEntryFn is provided.
options?
TreeMultiMapOptions<K, V[], R> = {}
Configuration options including optional toEntryFn to transform raw elements.
Returns
TreeMultiMap<K, V, R>
Remarks
Time O(m log m), Space O(m) where m is the number of initial entries
Example
// Standard usage with entries
const mmap = new TreeMultiMap([['a', ['x', 'y']], ['b', ['z']]]);
// Using toEntryFn to transform raw objects
const players = [{ score: 100, items: ['sword'] }, { score: 200, items: ['shield', 'bow'] }];
const mmap = new TreeMultiMap(players, { toEntryFn: p => [p.score, p.items] });
Accessors
comparator
Get Signature
get comparator(): Comparator<K>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:115
Expose comparator for advanced usage/testing (read-only).
Remarks
Time O(1), Space O(1)
Returns
Comparator<K>
size
Get Signature
get size(): number;
Defined in: data-structures/binary-tree/tree-multi-map.ts:90
Number of distinct keys.
Remarks
Time O(1), Space O(1)
Returns
number
totalSize
Get Signature
get totalSize(): number;
Defined in: data-structures/binary-tree/tree-multi-map.ts:105
Total number of values across all buckets (Σ bucket.length).
Remarks
Time O(n), Space O(1)
Example
// Total number of values
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
mm.add(2, 'c');
console.log(mm.totalSize); // 3;
Returns
number
Methods
[iterator]()
iterator: Iterator<[K, V[]]>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:330
Iterates over all entries as [key, bucket] pairs.
Returns
Iterator<[K, V[]]>
Remarks
Time O(n), Space O(1)
Implementation of
Iterable.[iterator]
add()
add(key, value): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:200
Append a single value.
Parameters
key
K
value
V
Returns
boolean
Remarks
Time O(log n), Space O(1)
Example
// Add key-value pair
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
mm.add(2, 'c');
console.log(mm.get(1)); // ['a', 'b'];
ceiling()
ceiling(key): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:525
Returns the entry with the smallest key >= given key.
Parameters
key
K
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Least key ≥ target
const mm = new TreeMultiMap<number, string>();
mm.add(10, 'a');
mm.add(20, 'b');
mm.add(30, 'c');
console.log(mm.ceiling(15)?.[0]); // 20;
clear()
clear(): void;
Defined in: data-structures/binary-tree/tree-multi-map.ts:140
Removes all entries from the map.
Returns
void
Remarks
Time O(1), Space O(1)
Example
// Remove all entries
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.clear();
console.log(mm.isEmpty()); // true;
clone()
clone(): TreeMultiMap<K, V, R>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:781
Deep copy
Returns
TreeMultiMap<K, V, R>
Example
// Deep clone
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
const copy = mm.clone();
copy.delete(1);
console.log(mm.has(1)); // true;
count()
count(key): number;
Defined in: data-structures/binary-tree/tree-multi-map.ts:154
Bucket length for a key (missing => 0).
Parameters
key
K
Returns
number
Remarks
Time O(log n), Space O(1)
Example
// Count values for key
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
console.log(mm.count(1)); // 2;
delete()
delete(key): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:256
Deletes a key and its entire bucket.
Parameters
key
K
Returns
boolean
Remarks
Time O(log n), Space O(1)
Example
// Remove key
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(2, 'b');
mm.delete(1);
console.log(mm.has(1)); // false;
deleteValue()
deleteValue(
key,
value,
eq?): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:288
Delete a single occurrence of a value from a key's bucket.
Parameters
key
K
value
V
eq?
(a, b) => boolean
Returns
boolean
Remarks
Time O(log n + m), Space O(1) where m is bucket size
Example
// Delete specific value
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
mm.deleteValue(1, 'a');
console.log(mm.get(1)); // ['b'];
deleteValues()
deleteValues(
key,
value,
eq?): number;
Defined in: data-structures/binary-tree/tree-multi-map.ts:310
Delete all occurrences of a value from a key's bucket.
Parameters
key
K
value
V
eq?
(a, b) => boolean
Returns
number
Remarks
Time O(log n + m), Space O(1) where m is bucket size
Example
// Delete all matching values
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'a');
mm.add(1, 'b');
const count = mm.deleteValues(1, 'a');
console.log(count); // 2;
entries()
entries(): IterableIterator<[K, V[]]>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:379
Iterate over all [key, values[]] entries (Map-compatible).
Returns
IterableIterator<[K, V[]]>
Remarks
Time O(n), Space O(1) per step.
Example
// Iterate over entries
const mm = new TreeMultiMap<number, string>();
mm.set(1, 'a');
mm.set(1, 'b');
mm.set(2, 'c');
console.log([...mm.entries()]); // [
// [1, ['a', 'b']],
// [2, ['c']]
// ];
entriesOf()
entriesOf(key): IterableIterator<[K, V]>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:398
Iterates over all entries for a specific key.
Parameters
key
K
Returns
IterableIterator<[K, V]>
Remarks
Time O(log n + m), Space O(1) where m is bucket size
Example
// Get entries for key
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
console.log([...mm.entriesOf(1)]); // [
// [1, 'a'],
// [1, 'b']
// ];
filter()
filter(predicate): TreeMultiMap<K, V, R>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:633
Creates a new map with entries that pass the predicate.
Parameters
predicate
(value, key, map) => boolean
Returns
TreeMultiMap<K, V, R>
Remarks
Time O(n), Space O(n)
Example
// Filter entries
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(2, 'b');
mm.add(3, 'c');
const filtered = mm.filter((v, k) => k > 1);
console.log([...filtered.keys()]); // [2, 3];
first()
first(): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:453
Returns the entry with the smallest key.
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// First entry
const mm = new TreeMultiMap<number, string>();
mm.add(3, 'c');
mm.add(1, 'a');
console.log(mm.first()?.[0]); // 1;
flatEntries()
flatEntries(): IterableIterator<[K, V]>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:435
Iterates over all [key, value] pairs (flattened from buckets).
Returns
IterableIterator<[K, V]>
Remarks
Time O(T), Space O(1) where T is totalSize
Example
// All key-value pairs flattened
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
mm.add(2, 'c');
console.log([...mm.flatEntries()]); // [
// [1, 'a'],
// [1, 'b'],
// [2, 'c']
// ];
floor()
floor(key): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:544
Returns the entry with the largest key <= given key.
Parameters
key
K
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Greatest key ≤ target
const mm = new TreeMultiMap<number, string>();
mm.add(10, 'a');
mm.add(20, 'b');
mm.add(30, 'c');
console.log(mm.floor(25)?.[0]); // 20;
forEach()
forEach(callback): void;
Defined in: data-structures/binary-tree/tree-multi-map.ts:615
Executes a callback for each entry.
Parameters
callback
(value, key, map) => void
Returns
void
Remarks
Time O(n), Space O(1)
Example
// Iterate entries
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(2, 'b');
const keys: number[] = [];
mm.forEach((v, k) => keys.push(k));
console.log(keys); // [1, 2];
get()
get(key): V[] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:184
Live bucket reference (do not auto-delete key if bucket becomes empty via mutation).
Parameters
key
K
Returns
V[] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Get values for key
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
console.log(mm.get(1)); // ['a', 'b'];
getByRank()
getByRank(k): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:729
Creates a shallow clone of this map.
Parameters
k
number
Returns
[K, V[]] | undefined
Remarks
Time O(n log n), Space O(n)
Example
// Order-statistic on BST
const tree = new TreeMultiMap<number>([30, 10, 50, 20, 40], { enableOrderStatistic: true });
console.log(tree.getByRank(0)); // 10;
console.log(tree.getByRank(4)); // 50;
console.log(tree.getRank(30)); // 2;
getRank()
getRank(key): number;
Defined in: data-structures/binary-tree/tree-multi-map.ts:748
Get the rank of a key in sorted order
Parameters
key
K
Returns
number
Example
// Get the rank of a key in sorted order
const tree = new TreeMultiMap<number>(
[10, 20, 30, 40, 50],
{ enableOrderStatistic: true }
);
console.log(tree.getRank(10)); // 0; // smallest → rank 0
console.log(tree.getRank(30)); // 2; // 2 elements before 30 in tree order
console.log(tree.getRank(50)); // 4; // largest → rank 4
console.log(tree.getRank(25)); // 2;
has()
has(key): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:169
Whether the map contains the given key.
Parameters
key
K
Returns
boolean
Remarks
Time O(log n), Space O(1)
Example
// Check key existence
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
console.log(mm.has(1)); // true;
console.log(mm.has(2)); // false;
hasEntry()
hasEntry(
key,
value,
eq?): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:271
Check if a specific value exists in a key's bucket.
Parameters
key
K
value
V
eq?
(a, b) => boolean
Returns
boolean
Remarks
Time O(log n + m), Space O(1) where m is bucket size
Example
// Check specific key-value
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
console.log(mm.hasEntry(1, 'a')); // true;
console.log(mm.hasEntry(1, 'z')); // false;
higher()
higher(key): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:562
Returns the entry with the smallest key > given key.
Parameters
key
K
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Least key > target
const mm = new TreeMultiMap<number, string>();
mm.add(10, 'a');
mm.add(20, 'b');
console.log(mm.higher(10)?.[0]); // 20;
isEmpty()
isEmpty(): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:126
Whether the map is empty.
Returns
boolean
Remarks
Time O(1), Space O(1)
Example
// Check if empty
console.log(new TreeMultiMap().isEmpty()); // true;
keys()
keys(): IterableIterator<K>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:347
Iterates over all keys.
Returns
IterableIterator<K>
Remarks
Time O(n), Space O(1)
Example
// Iterate keys
const mm = new TreeMultiMap<number, string>();
mm.add(3, 'c');
mm.add(1, 'a');
console.log([...mm.keys()]); // [1, 3];
last()
last(): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:470
Returns the entry with the largest key.
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Last entry
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(3, 'c');
console.log(mm.last()?.[0]); // 3;
lower()
lower(key): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:580
Returns the entry with the largest key < given key.
Parameters
key
K
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Greatest key < target
const mm = new TreeMultiMap<number, string>();
mm.add(10, 'a');
mm.add(20, 'b');
console.log(mm.lower(20)?.[0]); // 10;
map()
map<V2>(mapper): TreeMultiMap<K, V2, R>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:651
Creates a new map by transforming each entry.
Type Parameters
V2
V2
Parameters
mapper
(value, key, map) => [K, V2[]]
Returns
TreeMultiMap<K, V2, R>
Remarks
Time O(n log n), Space O(n)
Example
// Transform values
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
const mapped = mm.map((v, k) => [k, v.map(s => s.toUpperCase())] as [number, string[]]);
console.log(mapped.get(1)); // ['A'];
pollFirst()
pollFirst(): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:489
Removes and returns the entry with the smallest key.
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Remove and return first
const mm = new TreeMultiMap<number, string>();
mm.add(2, 'b');
mm.add(1, 'a');
const first = mm.pollFirst();
console.log(first?.[0]); // 1;
console.log(mm.has(1)); // false;
pollLast()
pollLast(): [K, V[]] | undefined;
Defined in: data-structures/binary-tree/tree-multi-map.ts:507
Removes and returns the entry with the largest key.
Returns
[K, V[]] | undefined
Remarks
Time O(log n), Space O(1)
Example
// Remove and return last
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(3, 'c');
const last = mm.pollLast();
console.log(last?.[0]); // 3;
print()
print(): void;
Defined in: data-structures/binary-tree/tree-multi-map.ts:599
Prints the internal tree structure (for debugging).
Returns
void
Remarks
Time O(n), Space O(n)
Example
// Display tree
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
expect(() => mm.print()).not.toThrow();
rangeByRank()
rangeByRank(start, end): [K, V[]][];
Defined in: data-structures/binary-tree/tree-multi-map.ts:766
Get elements by rank range
Parameters
start
number
end
number
Returns
[K, V[]][]
Example
// Pagination by position in tree order
const tree = new TreeMultiMap<number>([10, 20, 30, 40, 50, 60, 70, 80, 90], { enableOrderStatistic: true });
const pageSize = 3;
// Page 1
console.log(tree.rangeByRank(0, pageSize - 1)); // [10, 20, 30];
// Page 2
console.log(tree.rangeByRank(pageSize, 2 * pageSize - 1)); // [40, 50, 60];
// Page 3
console.log(tree.rangeByRank(2 * pageSize, 3 * pageSize - 1)); // [70, 80, 90];
rangeSearch()
rangeSearch<C>(range, callback?): ReturnType<C>[];
Defined in: data-structures/binary-tree/tree-multi-map.ts:711
Searches for entries within a key range.
Type Parameters
C
C extends (node) => unknown
Parameters
range
Range<K> | [K, K]
callback?
C
Returns
ReturnType<C>[]
Remarks
Time O(log n + k), Space O(k) where k is result size
Example
// Find keys in range
const mm = new TreeMultiMap<number, string>();
mm.add(10, 'a');
mm.add(20, 'b');
mm.add(30, 'c');
const result = mm.rangeSearch([15, 25]);
console.log(result.length); // 1;
reduce()
reduce<U>(callback, initialValue): U;
Defined in: data-structures/binary-tree/tree-multi-map.ts:670
Reduces all entries to a single value.
Type Parameters
U
U
Parameters
callback
(accumulator, value, key, map) => U
initialValue
U
Returns
U
Remarks
Time O(n), Space O(1)
Example
// Aggregate
const mm = new TreeMultiMap<number, number>();
mm.add(1, 10);
mm.add(2, 20);
const sum = mm.reduce((acc, v) => acc + v.reduce((a, b) => a + b, 0), 0);
console.log(sum); // 30;
set()
Call Signature
set(entry, value?): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:220
Alias for compatibility with existing TreeMultiMap semantics.
Parameters
entry
| K
| [K | null | undefined, V[] | undefined]
| null
| undefined
value?
V
Returns
boolean
Remarks
Time O(log n), Space O(1) for single value; O(log n + m) for bucket append
Example
// Set values for key
const mm = new TreeMultiMap<number, string>();
mm.set(1, 'a');
mm.set(1, 'b');
console.log(mm.get(1)); // ['a', 'b'];
Call Signature
set(key, value): boolean;
Defined in: data-structures/binary-tree/tree-multi-map.ts:221
Alias for compatibility with existing TreeMultiMap semantics.
Parameters
key
K
value
V
Returns
boolean
Remarks
Time O(log n), Space O(1) for single value; O(log n + m) for bucket append
Example
// Set values for key
const mm = new TreeMultiMap<number, string>();
mm.set(1, 'a');
mm.set(1, 'b');
console.log(mm.get(1)); // ['a', 'b'];
setMany()
setMany(keysNodesEntriesOrRaws): boolean[];
Defined in: data-structures/binary-tree/tree-multi-map.ts:690
Sets multiple entries at once.
Parameters
keysNodesEntriesOrRaws
Iterable<K | [K | null | undefined, V[] | undefined]>
Returns
boolean[]
Remarks
Time O(m log n), Space O(m) where m is input size
Example
// Set multiple entries
const mm = new TreeMultiMap<number, string>();
mm.setMany([
[1, ['a']],
[2, ['b']]
]);
console.log(mm.size); // 2;
values()
values(): IterableIterator<V[]>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:361
Iterates over all buckets.
Returns
IterableIterator<V[]>
Remarks
Time O(n), Space O(1)
Example
// Iterate value arrays
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
console.log([...mm.values()]); // [['a', 'b']];
valuesOf()
valuesOf(key): IterableIterator<V>;
Defined in: data-structures/binary-tree/tree-multi-map.ts:414
Iterates over all values for a specific key.
Parameters
key
K
Returns
IterableIterator<V>
Remarks
Time O(log n + m), Space O(1) where m is bucket size
Example
// Get flat values for key
const mm = new TreeMultiMap<number, string>();
mm.add(1, 'a');
mm.add(1, 'b');
console.log([...mm.valuesOf(1)]); // ['a', 'b'];