Skip to main content

TreeMultiMap

data-structure-typed

data-structure-typed / TreeMultiMap

Class: TreeMultiMap<K, V, R>

Defined in: data-structures/binary-tree/tree-multi-map.ts:28

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:45

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:4352

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:109

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:520

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:1677

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:1094

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:2556

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:440

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:4344

Creates a shallow clone of this map.

Returns​

TreeMultiMap<K, V, R>

Remarks​

Time O(n log n), Space O(n)

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:479

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:1528

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:1610

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:1657

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;

entriesOf()​

entriesOf(key): IterableIterator<[K, V]>;

Defined in: data-structures/binary-tree/tree-multi-map.ts:2055

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:3523

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:2216

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:2138

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:2731

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:3352

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:931

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'];

has()​

has(key): boolean;

Defined in: data-structures/binary-tree/tree-multi-map.ts:726

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:1568

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:2871

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:273

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:1847

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:2293

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:3011

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:3694

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:2338

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:2382

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:3183

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();

rangeSearch()​

rangeSearch<C>(range, callback?): ReturnType<C>[];

Defined in: data-structures/binary-tree/tree-multi-map.ts:4173

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:3868

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:1302

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:1303

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:4030

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:2014

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:2096

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'];