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

TreeMap

TreeMap is an associative container that stores elements formed by a combination of a key value and a mapped value, following a specific order.

In a TreeMap, 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.
  • Unique keys - No two elements in the container can have equivalent keys.

Example:

let map = new TreeMap();
// add few values
map.set(1, 'a');
map.set(2, 'b');
// find a value by key
let v = map.get(1); // << 'a'
// print all key-value pairs
for (let [key, value] of map) {
  console.log(`key: ${key}, value: ${value}`);
}

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

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 or updates 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 TreeMap();
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 TreeMap();
// Create and initialize map
let map2 = new TreeMap([[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 TreeMap()); // "[object TreeMap]"

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 TreeMap([[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 TreeMap([[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 TreeMap();
...
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 TreeMap([[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 TreeMap([[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 TreeMap();
...
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 TreeMap([[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 TreeMap([[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 TreeMap([[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 TreeMap([[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 TreeMap([[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 TreeMap([[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 TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]);
let b = map.get(3); // true

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 TreeMap();
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 TreeMap();
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 TreeMap([[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 TreeMap([[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 TreeMap([[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 TreeMap();
... // 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 TreeMap();
... // 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 TreeMap();
...
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 TreeMap();
...
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 or updates key-value pair to the map.

Params:

NameTypeAttributeDescription
key *
value *

Example:

let map = new TreeMap();
map.set(1, 'A');

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 TreeMap();
... // 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 TreeMap();
... // 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 TreeMap([[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 TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]);
for (let v of map.values().backward()) {
  console.log(v); // 'C', 'B', 'A'
}