js_cols Class: RedBlackMultiMap

new RedBlackMultiMap(compare_func)

js_cols.RedBlackMultiMap provides the implementation of a Red Black Tree multi map datastructure. The tree maintains a set of values, sorted by their corresponding keys. A MultiMap allows key dublicates. In case of dublicate keys, the most recently inserted will be deleted when calling remove. The range function can be used to retrieve all values, mapped to a single key. Sample usage:

var mm = new js_cols.ABTreeMultiMap();
mm.insert('a', 'apple');
mm.insert('a', 'almond');
mm.insert('a', 'anaconda');
var aValues = mm.range('a','b'); // returns ['apple', 'almond', 'anaconda']

The key/value pairs can be inserted and deleted efficiently in their sorted order as the tree enforces a log(n) 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

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

See:

js_cols.RedBlackMap

Extends

js_cols.RedBlackMap

Members

intersection

this operation is not supported by Multi Maps

isSubmapOf

this opreation is not supported by Multi Maps

Methods

clear()

Removes all elements from this set

Inherited From:

js_cols.RedBlackMap#clear

clone() → {js_cols.RedBlackMultiMap}

Overriding RedBlackMaps clone method. Clones a set and returns a new set.

Returns:

A new map with the same key-value pairs.

Type: js_cols.RedBlackMultiMap

contains(key) → {Boolean}

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

Parameters:

Name	Type	Description
`key`	*

Inherited From:

js_cols.RedBlackMap#contains

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`

Inherited From:

js_cols.RedBlackMap#containsAll

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.

Inherited From:

js_cols.RedBlackMap#every

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.

Inherited From:

js_cols.RedBlackMap#filter

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.

Inherited From:

js_cols.RedBlackMap#forEach

get(key) → {*}

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

Parameters:

Name	Type	Description
`key`	*

Inherited From:

js_cols.RedBlackMap#get

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)

Inherited From:

js_cols.RedBlackMap#getCount

Returns:

Type: Integer

getKeys() → {Array}

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

Inherited From:

js_cols.RedBlackMap#getKeys

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

Inherited From:

js_cols.RedBlackMap#getMax

Returns:

the value associated with the maximum key in this tree

Type: *

getMin() → {*}

Returns the value associated with the minimum key in this tree

Inherited From:

js_cols.RedBlackMap#getMin

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.

Inherited From:

js_cols.RedBlackMap#getValues

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`

Inherited From:

js_cols.RedBlackMap#insertAll

isEmpty() → {Boolean}

Returns true current size of the tree is zero

Inherited From:

js_cols.RedBlackMap#isEmpty

Returns:

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.

Inherited From:

js_cols.RedBlackMap#map

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`	*

Inherited From:

js_cols.RedBlackMap#predecessor

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

Inherited From:

js_cols.RedBlackMap#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`	*

Inherited From:

js_cols.RedBlackMap#remove

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`

Inherited From:

js_cols.RedBlackMap#removeAll

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.

Inherited From:

js_cols.RedBlackMap#some

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`	*

Inherited From:

js_cols.RedBlackMap#successor

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.

Inherited From:

js_cols.RedBlackMap#traverse

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.

Inherited From:

js_cols.RedBlackMap#traverseBackwards

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.

Inherited From:

js_cols.RedBlackMap#traverseFrom

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.

Inherited From:

js_cols.RedBlackMap#traverseFromTo

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.

Inherited From:

js_cols.RedBlackMap#traverseTo