js_cols Class: RedBlackMap

new RedBlackMap(compare_func)

js_cols.RedBlackMap provides the implementation of a Red Black Tree map datastructure. The tree maintains a set of values, sorted by their corresponding keys. The key/value pairs can be inserted and deleted efficiently in their sorted order as the tree enforces a logn maximum height. This implementation provides guaranteed log(n) time cost for the

contains, insert and remove operations. Algorithms are adaptations of those in Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms, second edition.

The assymptotic running time for important operations are below:

  Method                 big-O
----------------------------------------------------------------------------
- clear                  O(1)
- clone                  O(n logn)
- contains               O(logn)
- containsAll            O(m logn) m is the cardinality of the supplied collection
- every                  O(n * O(f)) f is the function supplied as argument
- filter                 O(n * O(f)) f is the function supplied as argument
- forEach                O(n * O(f)) f is the function supplied as argument
- get                    O(logn)
- getValues              O(n)
- insert                 O(logn)
- insertAll              O(m logn) m is the cardinality of the supplied collection
- map                    O(n * O(f)) f is the function supplied as argument
- remove                 O(logn)
- removeAll              O(m logn) m is the cardinality of the supplied collection
- some                   O(n * O(f)) f is the function supplied as argument
- contains               O(n * O(f)) f is the function supplied as argument

Constructs a new Red Black map

Parameters:

Name	Type	Argument	Description
`compare_func`	function	<optional>	an optional compare function to compare the keys. This function should take two values, a and b, and return x where: x < 0 if a < b, x > 0 if a > b, x = 0 otherwise if not defined, a default compare function for `numbers` will be used

Methods

clear()

Removes all elements from this set

clone() → {js_cols.RedBlackMap}

Clones a set and returns a new set.

Returns:

A new map with the same key-value pairs.

Type: js_cols.RedBlackMap

contains(key) → {Boolean}

Returns true if the key is associated with a value in this tree

Parameters:

Name	Type	Description
`key`	*

Returns:

Type: Boolean

containsAll(col) → {Boolean}

Checks that all values contained in the collection are also contained as keys in the tree

Parameters:

Name	Type	Description
`col`

Returns:

Type: Boolean

every(f, opt_obj) → {boolean}

Calls a function on each item in the RedBlackMap and returns true only if every function call returns a true-like value.

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes three arguments: the value, the key, and the RedBlackMap, and returns a boolean.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Returns:

Whether f evaluates to true for every item in the RedBlackMap.

Type: boolean

filter(f, opt_obj) → {js_cols.RedBlackMap}

Calls a function on each item in the RedBlackMap, if the function returns true, the key/value pair is inserted into a new RedBlackMap that is returned when the tree is fully traversed

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes three arguments: the value, the key, and the RedBlackMap.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Returns:

The key / value pairs that evaluated to true in the function calls are returned in a new RedBlackMap.

Type: js_cols.RedBlackMap

forEach(f, opt_obj)

Calls a function on each item in the RedBlackMap.

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes three arguments: tha value, the key, and the RedBlackMap.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

get(key) → {*}

Finds and returns the value associated with the key that is passed to the function

Parameters:

Name	Type	Description
`key`	*

Returns:

the value associated with the key if it exists in this tree, otherwise null

Type: *

getCount() → {Integer}

Returns the current size of the tree (number of elements)

Returns:

Type: Integer

getKeys() → {Array}

Inserts the keys stored in the tree into a new Array and returns the Array.

Returns:

An array containing all of the trees values in sorted order.

Type: Array

getMax() → {*}

Returns the value associated with the maximum key in this tree

Returns:

the value associated with the maximum key in this tree

Type: *

getMin() → {*}

Returns the value associated with the minimum key in this tree

Returns:

the value associated with the minimum key in this tree

Type: *

getValues() → {Array}

Inserts the values stored in the tree into a new Array and returns the Array.

Returns:

An array containing all of the trees values in sorted order.

Type: Array

insert(key, element)

Inserts a key/value pair into the tree

Parameters:

Name	Type	Description
`key`	*	the key used for ordering and location
`element`	*	the value associated with the key

insertAll(col)

Inserts a collection of key/value pairs into the map If the collection has no notion of keys (i.e. an Array or Set) each element is inserted as both key and value (mapping to it self)

Parameters:

Name	Type	Description
`col`

intersection(col) → {js_cols.RedBlackMap}

Finds all key/value pairs that are present in both this map and the given collection. If the collection has no notion of keys (i.e. a Set or an Array), each element of the collection will be treated as key, and it will be inserted to the returned map with its corresponding value from this map. This operation is O(n O(col.contains)). Example: if col is another RedBlackMap of size m, running time is O(n log(m)), if col is an Array or LinkedList, running time is O(n m), if col is a HashSet, running time is O(n).

Parameters:

Name	Type	Description
`col`

Returns:

A new set containing all the key/value pairs (primitives or objects) present in both this set and the given collection.

Type: js_cols.RedBlackMap

isEmpty() → {Boolean}

Returns true current size of the tree is zero

Returns:

Type: Boolean

isSubmapOf(col) → {Boolean}

Detects wheter all key/value pairs present in this map are also present in the given collection. If the collection has no notion of keys (i.e. a Set or an Array), the result will be whether the keys in this map is a subset of the elements in the collection. This operation is O(n O(col.contains)). Example: if col is another RedBlackMap of size m, running time is O(n log(m)), if col is an Array or LinkedList, running time is O(n m), if col is a HashSet, running time is O(n).

Parameters:

Name	Type	Description
`col`

Returns:

wheter this map is a submap of col

Type: Boolean

map(f, opt_obj) → {Array}

Calls a function on each item in the RedBlackMap and returns the results of those calls in an array.

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes three arguments: the value, the key, and the RedBlackMap.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Returns:

The results of the function calls for each item in the RedBlackMap.

Type: Array

predecessor(key) → {*}

Finds and returns the value associated with the preceeding key to that passed to the function

Parameters:

Name	Type	Description
`key`	*

Returns:

the value associated with the preceeding key, or null if the tree is not in the map

Type: *

range(from, to) → {Array}

Returns an array of the values in a given key range in this tree. The 'from' key is inclusive, the 'to' key exclusive

Parameters:

Name	Type	Description
`from`	*	the smallest key in the range
`to`	*	the successor of the largest key in the range

Returns:

an array of values

Type: Array

remove(key) → {*}

Remove the key and the value associated with it, and returns the value

Parameters:

Name	Type	Description
`key`	*

Returns:

the value

Type: *

removeAll(col)

Removes a all values contained in the collection from the tree The values in the collection are treated as keys in the tree, and the values associated with those keys are removed.

Parameters:

Name	Type	Description
`col`

some(f, opt_obj) → {boolean}

Calls a function on each item in the RedBlackMap and returns true if any of those function calls returns a true-like value.

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes three arguments: the value, the key and the RedBlackMap, and returns a boolean.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Returns:

Whether f evaluates to true for at least one item in the RedBlackSet.

Type: boolean

successor(key) → {*}

Finds and returns the value associated with the succeeding key to that passed to the function

Parameters:

Name	Type	Description
`key`	*

Returns:

the value associated with the succeeding key

Type: *

traverse(func)

Performs an in-order traversal of the tree and calls {@code func} with the value of each traversed node. The traversal ends after traversing the tree's maximum node or when {@code func} returns a value that evaluates to true.

Parameters:

Name	Type	Description
`func`	function	Function to call on the value of each traversed node.

traverseBackwards(f, opt_startValue)

Performs a reverse-order traversal of the tree and calls {@code f} with the value of each traversed node, optionally starting from the largest node with a value <= to the specified start value. The traversal ends after traversing the tree's minimum node or when func returns a value that evaluates to true.

Parameters:

Name	Type	Argument	Description
`f`	function		Function to call on the value of each traversed node.
`opt_startValue`	Object	<optional>	If specified, traversal will begin on the node with the largest value <= opt_startValue.

traverseFrom(func, fromKey)

Performs an in-order traversal of the tree and calls {@code func} with the value of each traversed node, starting on the node with a key = to the specified start key. The traversal ends after traversing the tree's maximum node or when {@code func} returns a value that evaluates to true.

Parameters:

Name	Type	Argument	Description
`func`	function		Function to call on the value of each traversed node.
`fromKey`	Object	<optional>	Traversal will begin on the node with key = fromKey.

traverseFromTo(func, fromKey, toKey)

Performs an in-order traversal of the tree and calls {@code func} with the value of each traversed node, starting on the node with a key = to the specified start key. The traversal ends before the node with key = toKey or when {@code func} returns a value that evaluates to true.

Parameters:

Name	Type	Argument	Description
`func`	function		Function to call on the value of each traversed node.
`fromKey`	Object	<optional>	Traversal will begin on the node with key = fromKey.
`toKey`	Object	<optional>	Traversal will end before the node with the smallest key < toKey.

traverseTo(func, toKey)

Performs an in-order traversal of the tree and calls {@code func} with the value of each traversed node. The traversal ends before the node with key = toKey or when {@code func} returns a value that evaluates to true.

Parameters:

Name	Type	Argument	Description
`func`	function		Function to call the value of on each traversed node.
`toKey`	Object	<optional>	Traversal will end before the node with the smallest key < toKey.