Class TreeMultiMap<K, V, R>

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

// players ranked by score with their equipment
 type Equipment = {
      name: string; // Equipment name
      quality: 'legendary' | 'epic' | 'rare' | 'common';
      level: number;
    };

    type Player = {
      name: string;
      score: number;
      equipments: Equipment[];
    };

    // Mock player data with their scores and equipment
    const players: Player[] = [
      {
        name: 'DragonSlayer',
        score: 8750,
        equipments: [
          { name: 'AWM', quality: 'legendary', level: 85 },
          { name: 'Level 3 Helmet', quality: 'epic', level: 80 },
          { name: 'Extended Quickdraw Mag', quality: 'rare', level: 75 },
          { name: 'Compensator', quality: 'epic', level: 78 },
          { name: 'Vertical Grip', quality: 'rare', level: 72 }
        ]
      },
      {
        name: 'ShadowNinja',
        score: 7200,
        equipments: [
          { name: 'M416', quality: 'epic', level: 75 },
          { name: 'Ghillie Suit', quality: 'rare', level: 70 },
          { name: 'Red Dot Sight', quality: 'common', level: 65 },
          { name: 'Extended QuickDraw Mag', quality: 'rare', level: 68 }
        ]
      },
      {
        name: 'RuneMaster',
        score: 9100,
        equipments: [
          { name: 'KAR98K', quality: 'legendary', level: 90 },
          { name: 'Level 3 Vest', quality: 'legendary', level: 85 },
          { name: 'Holographic Sight', quality: 'epic', level: 82 },
          { name: 'Suppressor', quality: 'legendary', level: 88 },
          { name: 'Level 3 Backpack', quality: 'epic', level: 80 }
        ]
      },
      {
        name: 'BattleKing',
        score: 8500,
        equipments: [
          { name: 'AUG', quality: 'epic', level: 82 },
          { name: 'Red Dot Sight', quality: 'rare', level: 75 },
          { name: 'Extended Mag', quality: 'common', level: 70 },
          { name: 'Tactical Stock', quality: 'rare', level: 76 }
        ]
      },
      {
        name: 'SniperElite',
        score: 7800,
        equipments: [
          { name: 'M24', quality: 'legendary', level: 88 },
          { name: 'Compensator', quality: 'epic', level: 80 },
          { name: 'Scope 8x', quality: 'legendary', level: 85 },
          { name: 'Level 2 Helmet', quality: 'rare', level: 75 }
        ]
      },
      {
        name: 'RushMaster',
        score: 7500,
        equipments: [
          { name: 'Vector', quality: 'rare', level: 72 },
          { name: 'Level 2 Helmet', quality: 'common', level: 65 },
          { name: 'Quickdraw Mag', quality: 'common', level: 60 },
          { name: 'Laser Sight', quality: 'rare', level: 68 }
        ]
      },
      {
        name: 'GhostWarrior',
        score: 8200,
        equipments: [
          { name: 'SCAR-L', quality: 'epic', level: 78 },
          { name: 'Extended Quickdraw Mag', quality: 'rare', level: 70 },
          { name: 'Holographic Sight', quality: 'epic', level: 75 },
          { name: 'Suppressor', quality: 'rare', level: 72 },
          { name: 'Vertical Grip', quality: 'common', level: 65 }
        ]
      },
      {
        name: 'DeathDealer',
        score: 7300,
        equipments: [
          { name: 'SKS', quality: 'epic', level: 76 },
          { name: 'Holographic Sight', quality: 'rare', level: 68 },
          { name: 'Extended Mag', quality: 'common', level: 65 }
        ]
      },
      {
        name: 'StormRider',
        score: 8900,
        equipments: [
          { name: 'MK14', quality: 'legendary', level: 92 },
          { name: 'Level 3 Backpack', quality: 'legendary', level: 85 },
          { name: 'Scope 8x', quality: 'epic', level: 80 },
          { name: 'Suppressor', quality: 'legendary', level: 88 },
          { name: 'Tactical Stock', quality: 'rare', level: 75 }
        ]
      },
      {
        name: 'CombatLegend',
        score: 7600,
        equipments: [
          { name: 'UMP45', quality: 'rare', level: 74 },
          { name: 'Level 2 Vest', quality: 'common', level: 67 },
          { name: 'Red Dot Sight', quality: 'common', level: 62 },
          { name: 'Extended Mag', quality: 'rare', level: 70 }
        ]
      }
    ];

    // Create a TreeMultiMap for player rankings
    const playerRankings = new TreeMultiMap<number, Equipment, Player>(players, {
      toEntryFn: ({ score, equipments }) => [score, equipments],
      isMapMode: false
    });

    const topPlayersEquipments = playerRankings.rangeSearch([8900, 10000], node => playerRankings.get(node.key));
    console.log(topPlayersEquipments); // [
 //      [
 //        {
 //          name: 'MK14',
 //          quality: 'legendary',
 //          level: 92
 //        },
 //        { name: 'Level 3 Backpack', quality: 'legendary', level: 85 },
 //        {
 //          name: 'Scope 8x',
 //          quality: 'epic',
 //          level: 80
 //        },
 //        { name: 'Suppressor', quality: 'legendary', level: 88 },
 //        {
 //          name: 'Tactical Stock',
 //          quality: 'rare',
 //          level: 75
 //        }
 //      ],
 //      [
 //        { name: 'KAR98K', quality: 'legendary', level: 90 },
 //        {
 //          name: 'Level 3 Vest',
 //          quality: 'legendary',
 //          level: 85
 //        },
 //        { name: 'Holographic Sight', quality: 'epic', level: 82 },
 //        {
 //          name: 'Suppressor',
 //          quality: 'legendary',
 //          level: 88
 //        },
 //        { name: 'Level 3 Backpack', quality: 'epic', level: 80 }
 //      ]
 //    ];

Type Parameters

K = any
V = any
R = any

Implements

Iterable<[K, V[]]>

Index

Constructors

constructor

Accessors

comparator size totalSize

Constructors

constructor

new TreeMultiMap<K, V, R>(keysNodesEntriesOrRaws?, options?): TreeMultiMap<K, V, R>
Creates a new TreeMultiMap.
Type Parameters
- K = any
- V = any
- R = any
Parameters
- keysNodesEntriesOrRaws: Iterable<
      | undefined
      | null
      | K
      | R
      | [undefined | null | K, undefined | V[]], any, any> = []
  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] });
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:215

Accessors

comparator

get comparator(): Comparator<K>
Expose comparator for advanced usage/testing (read-only).

Returns Comparator<K>
Remarks
Time O(1), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:709

size

get size(): number
Number of distinct keys.

Returns number
Remarks
Time O(1), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:279

totalSize

get totalSize(): number
Total number of values across all buckets (Σ bucket.length).

Returns number
Remarks
Time O(n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:312

Methods

[iterator]

[iterator](): Iterator<[K, V[]], any, any>
Iterates over all entries as [key, bucket] pairs.

Returns Iterator<[K, V[]], any, any>
Remarks
Time O(n), Space O(1)
Implementation of Iterable.[iterator]
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:436

add

add(key, value): boolean
Append a single value.
Parameters
- key: K
- value: V
Returns boolean
Remarks
Time O(log n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:340

ceiling

ceiling(key): undefined | [K, V[]]
Returns the entry with the smallest key >= given key.
Parameters
- key: K
Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[10, ['a']], [20, ['b']], [30, ['c']]]);
map.ceiling(15);  // [20, ['b']]
map.ceiling(20);  // [20, ['b']]
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:559

clear

clear(): void
Removes all entries from the map.

Returns void
Remarks
Time O(1), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:295

clone

clone(): TreeMultiMap<K, V, R>
Creates a shallow clone of this map.

Returns TreeMultiMap<K, V, R>
Remarks
Time O(n log n), Space O(n)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:701

count

count(key): number
Bucket length for a key (missing => 0).
Parameters
- key: K
Returns number
Remarks
Time O(log n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:303

delete

delete(key): boolean
Deletes a key and its entire bucket.
Parameters
- key: K
Returns boolean
Remarks
Time O(log n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:383

deleteValue

deleteValue(key, value, eq?): boolean
Delete a single occurrence of a value from a key's bucket.
Parameters
- key: K
- value: V
- eq: ((a: V, b: V) => boolean) = Object.is
  - - (a, b): boolean
    - Parameters
      a: V
      b: V
      Returns boolean
Returns boolean
Remarks
Time O(log n + m), Space O(1) where m is bucket size
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:402

deleteValues

deleteValues(key, value, eq?): number
Delete all occurrences of a value from a key's bucket.
Parameters
- key: K
- value: V
- eq: ((a: V, b: V) => boolean) = Object.is
  - - (a, b): boolean
    - Parameters
      a: V
      b: V
      Returns boolean
Returns number
Remarks
Time O(log n + m), Space O(1) where m is bucket size
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:416

entriesOf

entriesOf(key): IterableIterator<[K, V], any, any>
Iterates over all entries for a specific key.
Parameters
- key: K
Returns IterableIterator<[K, V], any, any>
Remarks
Time O(log n + m), Space O(1) where m is bucket size
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:465

filter

filter(predicate): TreeMultiMap<K, V, R>
Creates a new map with entries that pass the predicate.
Parameters
- predicate: ((value: V[], key: K, map: this) => boolean)
  - - (value, key, map): boolean
    - Parameters
      value: V[]
      key: K
      map: this
      Returns boolean
Returns TreeMultiMap<K, V, R>
Remarks
Time O(n), Space O(n)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:639

first

first(): undefined | [K, V[]]
Returns the entry with the smallest key.

Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[1, ['a']], [2, ['b']]]);
map.first();  // [1, ['a']]
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:500

flatEntries

flatEntries(): IterableIterator<[K, V], any, any>
Iterates over all [key, value] pairs (flattened from buckets).

Returns IterableIterator<[K, V], any, any>
Remarks
Time O(T), Space O(1) where T is totalSize
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:485

floor

floor(key): undefined | [K, V[]]
Returns the entry with the largest key <= given key.
Parameters
- key: K
Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[10, ['a']], [20, ['b']], [30, ['c']]]);
map.floor(25);  // [20, ['b']]
map.floor(20);  // [20, ['b']]
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:575

forEach

forEach(callback): void
Executes a callback for each entry.
Parameters
- callback: ((value: V[], key: K, map: this) => void)
  - - (value, key, map): void
    - Parameters
      value: V[]
      key: K
      map: this
      Returns void
Returns void
Remarks
Time O(n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:629

get

get(key): undefined | V[]
Live bucket reference (do not auto-delete key if bucket becomes empty via mutation).
Parameters
- key: K
Returns undefined | V[]
Remarks
Time O(log n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:331

has

has(key): boolean
Whether the map contains the given key.
Parameters
- key: K
Returns boolean
Remarks
Time O(log n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:322

hasEntry

hasEntry(key, value, eq?): boolean
Check if a specific value exists in a key's bucket.
Parameters
- key: K
- value: V
- eq: ((a: V, b: V) => boolean) = Object.is
  - - (a, b): boolean
    - Parameters
      a: V
      b: V
      Returns boolean
Returns boolean
Remarks
Time O(log n + m), Space O(1) where m is bucket size
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:392

higher

higher(key): undefined | [K, V[]]
Returns the entry with the smallest key > given key.
Parameters
- key: K
Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[10, ['a']], [20, ['b']], [30, ['c']]]);
map.higher(10);  // [20, ['b']]
map.higher(15);  // [20, ['b']]
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:591

isEmpty

isEmpty(): boolean
Whether the map is empty.

Returns boolean
Remarks
Time O(1), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:287

keys

keys(): IterableIterator<K, any, any>
Iterates over all keys.

Returns IterableIterator<K, any, any>
Remarks
Time O(n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:447

last

last(): undefined | [K, V[]]
Returns the entry with the largest key.

Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[1, ['a']], [2, ['b']]]);
map.last();  // [2, ['b']]
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:514

lower

lower(key): undefined | [K, V[]]
Returns the entry with the largest key < given key.
Parameters
- key: K
Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[10, ['a']], [20, ['b']], [30, ['c']]]);
map.lower(20);  // [10, ['a']]
map.lower(15);  // [10, ['a']]
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:607

map

map<V2>(mapper): TreeMultiMap<K, V2, R>
Creates a new map by transforming each entry.
Type Parameters
- V2
Parameters
- mapper: ((value: V[], key: K, map: this) => [K, V2[]])
  - - (value, key, map): [K, V2[]]
    - Parameters
      value: V[]
      key: K
      map: this
      Returns [K, V2[]]
Returns TreeMultiMap<K, V2, R>
Remarks
Time O(n log n), Space O(n)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:651

pollFirst

pollFirst(): undefined | [K, V[]]
Removes and returns the entry with the smallest key.

Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[1, ['a']], [2, ['b']]]);
map.pollFirst();  // [1, ['a']]
map.has(1);       // false
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:529

pollLast

pollLast(): undefined | [K, V[]]
Removes and returns the entry with the largest key.

Returns undefined | [K, V[]]
Remarks
Time O(log n), Space O(1)
Example
```
const map = new TreeMultiMap([[1, ['a']], [2, ['b']]]);
map.pollLast();  // [2, ['b']]
map.has(2);      // false
```
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:544

print

print(): void
Prints the internal tree structure (for debugging).

Returns void
Remarks
Time O(n), Space O(n)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:621

rangeSearch

rangeSearch<C>(range, callback?): ReturnType<C>[]
Searches for entries within a key range.
Type Parameters
- C extends ((node: RedBlackTreeNode<K, V[]>) => unknown)
Parameters
- range: Range<K> | [K, K]
- Optionalcallback: C
Returns ReturnType<C>[]
Remarks
Time O(log n + k), Space O(k) where k is result size
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:690

reduce

reduce<U>(callback, initialValue): U
Reduces all entries to a single value.
Type Parameters
- U
Parameters
- callback: ((accumulator: U, value: V[], key: K, map: this) => U)
  - - (accumulator, value, key, map): U
    - Parameters
      accumulator: U
      value: V[]
      key: K
      map: this
      Returns U
- initialValue: U
Returns U
Remarks
Time O(n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:665

set

set(entry, value?): boolean
Alias for compatibility with existing TreeMultiMap semantics.
Parameters
- entry:
      | undefined
      | null
      | K
      | [undefined | null | K, undefined | V[]]
- Optionalvalue: V
Returns boolean
Remarks
Time O(log n), Space O(1) for single value; O(log n + m) for bucket append
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:354

setMany

setMany(keysNodesEntriesOrRaws): boolean[]
Sets multiple entries at once.
Parameters
- keysNodesEntriesOrRaws: Iterable<K | [undefined | null | K, undefined | V[]], any, any>
Returns boolean[]
Remarks
Time O(m log n), Space O(m) where m is input size
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:677

values

values(): IterableIterator<V[], any, any>
Iterates over all buckets.

Returns IterableIterator<V[], any, any>
Remarks
Time O(n), Space O(1)
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:455

valuesOf

valuesOf(key): IterableIterator<V, any, any>
Iterates over all values for a specific key.
Parameters
- key: K
Returns IterableIterator<V, any, any>
Remarks
Time O(log n + m), Space O(1) where m is bucket size
- Defined in src/data-structures/binary-tree/tree-multi-map.ts:475

Class TreeMultiMap<K, V, R>

Example

Type Parameters

Implements

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns TreeMultiMap<K, V, R>

Remarks

Example

Accessors

comparator

Returns Comparator<K>

Remarks

size

Returns number

Remarks

totalSize

Returns number

Remarks

Methods

[iterator]

Returns Iterator<[K, V[]], any, any>

Remarks

add

Parameters

Returns boolean

Remarks

ceiling

Parameters

Returns undefined | [K, V[]]

Remarks

Example

clear

Returns void

Remarks

clone

Returns TreeMultiMap<K, V, R>

Remarks

count

Parameters

Returns number

Remarks

delete

Parameters

Returns boolean

Remarks

deleteValue

Parameters

Parameters

Returns boolean

Returns boolean

Remarks

deleteValues

Parameters

Parameters

Returns boolean

Returns number

Remarks

entriesOf

Parameters

Returns IterableIterator<[K, V], any, any>

Remarks

filter

Parameters

Parameters

Returns boolean

Returns TreeMultiMap<K, V, R>

Remarks

first

Returns undefined | [K, V[]]

Remarks

Example

flatEntries

Returns IterableIterator<[K, V], any, any>