js_cols Class: RedBlackBag

new RedBlackBag(compare_func)

js_cols.RedBlackBag provides the implementation of a Red Black Tree multiset datastructure. The tree maintains a set of values in sorted order. A MultiSet allows dublicates. In case of dublicate values, the most recently inserted will be deleted when calling remove. The range function can be used to retrieve all equal values. The values 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

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.RedBlackSet

Extends

js_cols.RedBlackSet

Methods

clear()

Removes all elements from this set

Inherited From:

js_cols.RedBlackSet#clear

clone() → {js_cols.RedBlackBag}

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

Returns:

A new map with the same key-value pairs.

Type: js_cols.RedBlackBag

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.RedBlackSet#contains

Returns:

Type: Boolean

containsAll(col) → {Boolean}

Checks that all values contained in the collection are also contained in the tree. Checks that all values contained in the collection are also contained in the tree. If the collection has a notion of keys (i.e. an Array or a Set), the keys of the collection will be interpreted as values in this set.

Parameters:

Name	Type	Description
`col`

Inherited From:

js_cols.RedBlackSet#containsAll

Returns:

Type: Boolean

every(f, opt_obj) → {boolean}

Calls a function on each item in the RedBlackSet 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 RedBlackSet, and returns a boolean.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#every

Returns:

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

Type: boolean

filter(f, opt_obj) → {Array}

Calls a function on each item in the RedBlackSet, if the function returns true, the key/value pair is inserted into an object 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 RedBlackSet.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#filter

Returns:

The key / value pairs that evaluated to true in the function calls for each item in the RedBlackSet.

Type: Array

forEach(f, opt_obj)

Calls a function on each item in the RedBlackSet.

Parameters:

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

Inherited From:

js_cols.RedBlackSet#forEach

getCount() → {Integer}

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

Inherited From:

js_cols.RedBlackSet#getCount

Returns:

Type: Integer

getMax() → {*}

Returns the value associated with the maximum key in this tree

Inherited From:

js_cols.RedBlackSet#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.RedBlackSet#getMin

Returns:

the value associated with the minimum key in this tree

Type: *

getValues() → {Array}

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

Inherited From:

js_cols.RedBlackSet#getValues

Returns:

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

Type: Array

insertAll(element)

Inserts a collection of values into the tree

Parameters:

Name	Type	Description
`element`	*	the value

Inherited From:

js_cols.RedBlackSet#insertAll

intersection(col) → {js_cols.Set}

Finds all values that are present in both this set and the given collection. This operation is O(n O(col.contains)). WARNING: This operation is not guaranteed to work correctly if col is a Map. Example: if col is another RedBlackSet 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`	js_cols.Set \| Array \| Object	A collection.

Inherited From:

js_cols.RedBlackSet#intersection

Returns:

A new set containing all the values (primitives or objects) present in both this set and the given collection.

Type: js_cols.Set

isEmpty() → {Boolean}

Returns true if the current size of the tree is zero

Inherited From:

js_cols.RedBlackSet#isEmpty

Returns:

Type: Boolean

isSubsetOf(col) → {boolean}

Tests whether the given collection contains all the elements in this set. WARNING: This operation is not guaranteed to work correctly if col is a Map. Primitives are treated as equal if they have the same type and convert to the same string; objects are treated as equal if they are references to the same object.
This operation is O(n O(col.contains)). Example: if col is another RedBlackSet 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`	js_cols.Set \| Array \| Object	A collection.

Inherited From:

js_cols.RedBlackSet#isSubsetOf

Returns:

True if this set is a subset of the given collection.

Type: boolean

map(f, opt_obj) → {Array}

Calls a function on each item in the RedBlackSet 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 RedBlackSet.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#map

Returns:

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

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.RedBlackSet#predecessor

Returns:

the value associated with the preceeding key, or null if the supplied key was not in the set

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.RedBlackSet#range

Returns:

an array of values

Type: Array

remove(key)

Remove the key and the value associated with it

Parameters:

Name	Type	Description
`key`	*

Inherited From:

js_cols.RedBlackSet#remove

removeAll(col)

Removes a all values contained in the collection from the tree If the collection has a notion of keys (a Map), the keys will be treated as values in this set.

Parameters:

Name	Type	Description
`col`

Inherited From:

js_cols.RedBlackSet#removeAll

some(f, opt_obj) → {boolean}

Calls a function on each item in the RedBlackSet 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 RedBlackSet, and returns a boolean.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#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.RedBlackSet#successor

Returns:

the value associated with the succeeding key, or null if the supplied key was not in the set

Type: *

traverse(f, opt_obj)

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

Parameters:

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

Inherited From:

js_cols.RedBlackSet#traverse

traverseBackwards(f, opt_obj)

Performs a reverse-order traversal of the tree and calls {@code f} with 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		The function to call for each item. The function takes two arguments: the key, and the RedBlackSet.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#traverseBackwards

traverseFrom(f, fromKey, opt_obj)

Performs an in-order traversal of the tree and calls {@code f} with 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 f} returns a value that evaluates to true.

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes two arguments: the key, and the RedBlackSet.
`fromKey`	Object	<optional>	Traversal will begin on the node with key = fromKey.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#traverseFrom

traverseFromTo(f, fromKey, toKey, opt_obj)

Performs an in-order traversal of the tree and calls {@code f} with 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 f} returns a value that evaluates to true.

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes two arguments: the key, and the RedBlackSet.
`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.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#traverseFromTo

traverseTo(f, toKey, opt_obj)

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

Parameters:

Name	Type	Argument	Description
`f`	function		The function to call for each item. The function takes two arguments: the key, and the RedBlackSet.
`toKey`	Object	<optional>	Traversal will end before the node with the smallest key < toKey.
`opt_obj`	Object	<optional>	The object context to use as "this" for the function.

Inherited From:

js_cols.RedBlackSet#traverseTo