Home Reference Source 
import {TreeMultiMap} from 'jstreemap/src/public/tree-multimap.js'
public class | source

TreeMultiMap

TreeMultiMap is an associative container that stores elements formed by a combination of a key value and a mapped value, following a specific order, and where multiple elements can have equivalent keys.

In a TreeMultiMap, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key and mapped value may differ.

Container properties

  • Associative - Elements in associative containers are referenced by their key and not by their absolute position in the container.
  • Ordered - The elements in the container follow a strict order at all times. All inserted elements are given a position in this order.
  • Map - Each element associates a key to a mapped value. Keys are meant to identify the elements whose main content is the mapped value.
  • Multiple equivalent keys - Multiple elements in the container can have equivalent keys.

Example:

let map = new TreeMultiMap();
// add few values
map.set(1, 'a');
map.set(2, 'b');
map.set(2, 'c');
// find a value by key
let v = map.get(1); // << 'a'
find all values for a given key
// print all key-value pairs
let from = map.lowerBound(2);
let to = map.upperBound(2);
let it = from;
while (!it.equals(to)) {
  console.log(it.key);
  it.next();
}

Static Member Summary

Static Public Members
public static get

Allows to create programmatically an instance of the same class

Constructor Summary

Public Constructor
public

constructor(iterable: *)

Creates an empty, or a pre-initialized map.

Member Summary

Public Members
public get

String tag of this class
public set

Sets custom comparison function if key values are not of primitive types.
public get

size: Number: *

Number of key-value pairs in the map.

Method Summary

Public Methods
public

Forward ES6 iterator for all key-value pairs in ascending order of the keys.
public

ES6 reverse iterator for all key-value pairs in descending order of the keys.
public

Forward iterator to the first element
public

clear()

Removes all key-value pairs.
public

delete(key: *)

Removes key-value pair with the specified key if such entry exists.
public

Forward iterator to the element following the last element
public

Forward ES6 iterator for all key-value pairs in ascending order of the keys.
public

erase(iterator: Iterator)

Removes key-value pair for the specified iterator.
public

find(key: *): Iterator

Finds an element with key equivalent to the specified one.
public

first(): *

public

forEach(callback: *)

Iterates all key-value pairs using a callback in ascending order of the keys.
public

get(key: *): *

Finds value associated with the specified key.
public

has(key: *): Boolean

A boolean indicator whether map contains a key-value pair with the specified key
public

insertMulti(key: *, value: *): InsertionResult

Adds key-value pair.
public

insertOrReplace(key: *, value: *): InsertionResult

Adds key-value pair if such key does not exist in the map.
public

insertUnique(key: *, value: *): InsertionResult

Adds key-value pair if such key does not exist in the map
public

Forward ES6 iterator for all keys in ascending order of the keys.
public

last(): *

public

lowerBound(key: *): Iterator

Iterator pointing to the first element that is not less than specified key.
public

Reverse iterator to the last element.
public

Reverse iterator pointing to before the first element.
public

set(key: *, value: *)

Adds a key-value pair to the map.
public

Serializes contents of the map in the form {key1:value1,key2:value2,...}
public

upperBound(key: *): Iterator

Iterator pointing to the first element that is greater than key.
public

values(): JsITerator

Forward ES6 iterator for all values in ascending order of the keys.

Static Public Members

public static get [Symbol.species]: *: * source

Allows to create programmatically an instance of the same class

Return:

*

constructor object for this class.

Example:

let map = new TreeMultiMap();
let constrFunc = Object.getPrototypeOf(map).constructor[Symbol.species];
let map2 = new constrFunc();

Public Constructors

public constructor(iterable: *) source

Creates an empty, or a pre-initialized map.

Params:

NameTypeAttributeDescription
iterable *
  • optional

Another iterable object whose key-value pairs are added into the newly created map.

Example:

// Create an empty map
let map1 = new TreeMultiMap();
// Create and initialize map
let map2 = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);

Public Members

public get [Symbol.toStringTag]: String: string source

String tag of this class

Return:

String

Example:

Object.prototype.toString.call(new TreeMultiMap()); // "[object TreeMultiMap]"

public set compareFunc source

Sets custom comparison function if key values are not of primitive types. Callback is a 3-way comparison function accepts two key values (lhs, rhs). It is expected to return +1 if the value of rhs is greater than lhs -1 if the value of rhs is less than lhs 0 if values are the same

public get size: Number: * source

Number of key-value pairs in the map.

Return:

Number

Public Methods

public [Symbol.iterator](): JsIterator source

Forward ES6 iterator for all key-value pairs in ascending order of the keys. The same as entries() method

Return:

JsIterator

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let [key,value] of map) {
  console.log(`key: ${key}, value: ${value}`);
}

public backward(): JsReverseIterator source

ES6 reverse iterator for all key-value pairs in descending order of the keys.

Return:

JsReverseIterator

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let [key,value] of map.backwards()) {
  console.log(`key: ${key}, value: ${value}`);
}

public begin(): Iterator source

Forward iterator to the first element

Return:

Iterator

Example:

let m = new TreeMultiMap();
...
for (let it = m.begin(); !it.equals(m.end()); it.next()) {
  console.log(`key: ${it.key}, value: ${it.value}`);
}

public clear() source

Removes all key-value pairs.

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
map.clear();
console.log(map.size); // 0

public delete(key: *) source

Removes key-value pair with the specified key if such entry exists. Does nothing otherwise.

Params:

NameTypeAttributeDescription
key *

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
map.delete(2);
console.log(map.toString()); // {1:A,3:C}

public end(): Iterator source

Forward iterator to the element following the last element

Return:

Iterator

Example:

let m = new TreeMultiMap();
...
for (let it = m.begin(); !it.equals(m.end()); it.next()) {
  console.log(`key: ${it.key}, value: ${it.value}`);
}

public entries(): JsIterator source

Forward ES6 iterator for all key-value pairs in ascending order of the keys.

Return:

JsIterator

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let [key,value] of map.entries()) {
  console.log(`key: ${key}, value: ${value}`);
}

public erase(iterator: Iterator) source

Removes key-value pair for the specified iterator.

Params:

NameTypeAttributeDescription
iterator Iterator

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
let it = map.find(2);
it.prev();
map.erase(it); // removes a node with key 1
console.log(map.toString()); // {2:B,3:C}

public find(key: *): Iterator source

Finds an element with key equivalent to the specified one. If such key does not exist end() iterator is returned.

Params:

NameTypeAttributeDescription
key *

Return:

Iterator

Example:

let m = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
...
let it = m.find(1);
if (!it.equals(m.end())) {
  console.log(`key: ${it.key}, value: ${it.value}`); // 1, 'A'
}

public first(): * source

Return:

*

first key/value pair of the container, or undefined if container is empty

Example:

let m = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
let first = m.first();
if (first) {
  let key = first[0];   // 1
  let value = first[1]; // 'A'
}

public forEach(callback: *) source

Iterates all key-value pairs using a callback in ascending order of the keys. Note that ES6 specifies the order of key value parameters in the callback differently from for-of loop.

Params:

NameTypeAttributeDescription
callback *

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
map.forEach(function(value, key, container) {
  console.log(`key: ${key}, value: ${value}`);
});

public get(key: *): * source

Finds value associated with the specified key. If specified key does not exist then undefined is returned.

Params:

NameTypeAttributeDescription
key *

a value of any type that can be compared with a key

Return:

*

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
let v = map.get(3); // 'C'
* let v = map.get(4); // returns undefined

public has(key: *): Boolean source

A boolean indicator whether map contains a key-value pair with the specified key

Params:

NameTypeAttributeDescription
key *

a value of any type that can be compared with a key

Return:

Boolean

Example:

let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
let b = map.get(3); // true

public insertMulti(key: *, value: *): InsertionResult source

Adds key-value pair. If such key already exists in the map then adds another node with the same key and a new value.

Params:

NameTypeAttributeDescription
key *
value *

Return:

InsertionResult

indicates whether a node was added and provides iterator to it.

Example:

let m = new TreeMultiMap();
let res = m.insertMulti(1, 'A');
if (res.wasInserted) {
  console.log(`Inserted ${res.iterator.value}`); // prints A
}
res = m.insertMulti(1, 'B') // adds a new node
if (res.wasInserted) {
  console.log(`Inserted ${res.iterator.value}`); // prints B
  it.prev();
  console.log(`Previously inserted ${res.iterator.value}`); // prints A
}

public insertOrReplace(key: *, value: *): InsertionResult source

Adds key-value pair if such key does not exist in the map. Replaces value if such key exists

Params:

NameTypeAttributeDescription
key *
value *

Return:

InsertionResult

indicates whether a node was added and provides iterator to it.

Example:

let m = new TreeMultiMap();
let res = m.insertOrReplace(1, 'A');
if (res.wasInserted) {
  console.log(`Inserted ${res.iterator.value}`); // prints A
}
res = m.insertOrReplace(1, 'B') // replaces value on the existing node
if (res.wasInserted) {
  console.log(`Inserted ${res.iterator.key}`); // prints B
}

public insertUnique(key: *, value: *): InsertionResult source

Adds key-value pair if such key does not exist in the map

Params:

NameTypeAttributeDescription
key *
value *

Return:

InsertionResult

indicates whether a node was added and provides iterator to it.

Example:

let m = new TreeMultiMap();
let res = m.insertUnique(1, 'A');
if (res.wasInserted) {
  console.log(`Inserted ${res.iterator.value}`); // prints A
}
res = m.insertUnique(1, 'B') // this step has no effect on the map
if (res.wasInserted) {
  console.log(`Inserted ${res.iterator.key}`); // not executed
}

public keys(): JsIterator source

Forward ES6 iterator for all keys in ascending order of the keys.

Return:

JsIterator

Example:

// iterate all keys
let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let k of map.keys()) {
  console.log(k); // 1, 2, 3
}
// iterate all keys in reverse order
let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let k of map.keys().backward()) {
  console.log(k); // 3, 2, 1
}

public last(): * source

Return:

*

last key/value pair of the container, or undefined if container is empty

Example:

let m = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
let last = m.last();
if (last) {
  let key = last[0];   // 3
  let value = last[1]; // 'C'
}

public lowerBound(key: *): Iterator source

Iterator pointing to the first element that is not less than specified key. If no such element is found, see end() iterator is returned.

Params:

NameTypeAttributeDescription
key *

Return:

Iterator

Example:

let m = new TreeMultiMap();
... // add key-value pairs., using numbers as keys
// iterate through all key-value pairs with keys between 0 and 50 inclusive
let from = m.lowerBound(0);
let to = m.upperBound(50);
let it = from;
while (!it.equals(to)) {
  console.log(it.key);
  it.next();
}

let m = new TreeMultiMap();
... // add key-value pairs., using numbers as keys
// iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order
let from = new ReverseIterator(m.upperBound(50));
let to = new ReverseIterator(m.lowerBound(0));
let it = from;
while (!it.equals(to)) {
  console.log(it.key);
  it.next();
}

public rbegin(): ReverseIterator source

Reverse iterator to the last element.

Return:

ReverseIterator

Example:

let m = new TreeMultiMap();
...
for (let it = m.rbegin(); !it.equals(m.rend()); it.next()) {
  console.log(`key: ${it.key}, value: ${it.value}`);
}

public rend(): ReverseIterator source

Reverse iterator pointing to before the first element.

Return:

ReverseIterator

Example:

let m = new TreeMultiMap();
...
for (let it = m.rbegin(); !it.equals(m.rend()); it.next()) {
  console.log(`key: ${it.key}, value: ${it.value}`);
}

public set(key: *, value: *) source

Adds a key-value pair to the map. Multiple key-value pairs with the same key are allowed in TreeMultiMap.

Params:

NameTypeAttributeDescription
key *
value *

Example:

let map = new TreeMultiMap();
map.set(1, 'A');
map.set(1, 'B');
map.set(2, 'C');
for (let k of map.values()) {
  console.log(k); // A, B, C
}

public toString(): String source

Serializes contents of the map in the form {key1:value1,key2:value2,...}

Return:

String

public upperBound(key: *): Iterator source

Iterator pointing to the first element that is greater than key. If no such element is found end() iterator is returned.

Params:

NameTypeAttributeDescription
key *

Return:

Iterator

Example:

let m = new TreeMultiMap();
... // add key-value pairs., using numbers as keys
// iterate through all key-value pairs with keys between 0 and 50 inclusive
let from = m.lowerBound(0);
let to = m.upperBound(50);
let it = from;
while (!it.equals(to)) {
  console.log(it.key);
  it.next();
}

let m = new TreeMultiMap();
... // add key-value pairs., using numbers as keys
// iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order
let from = new ReverseIterator(m.upperBound(50));
let to = new ReverseIterator(m.lowerBound(0));
let it = from;
while (!it.equals(to)) {
  console.log(it.key);
  it.next();
}

public values(): JsITerator source

Forward ES6 iterator for all values in ascending order of the keys.

Return:

JsITerator

Example:

// iterate all values
let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let v of map.values()) {
  console.log(v); // 'A', 'B', 'C'
}
// iterate all values in reverse order
let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let v of map.values().backward()) {
  console.log(v); // 'C', 'B', 'A'
}