js_cols Class: RedBlackSet

new RedBlackSet(compare_func)

js_cols.RedBlackSet provides the implementation of a Red Black Tree Set datastructure. The tree maintains a set of values in sorted order. 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
- 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

Methods

clear()

Removes all elements from this set

clone() → {js_cols.RedBlackSet}

Clones a set and returns a new set.

Returns:

A new map with the same key-value pairs.

Type: js_cols.RedBlackSet

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

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.

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.

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.

getCount() → {Integer}

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

Returns:

Type: Integer

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 elements stored in the tree into a new Array and returns the Array.

Returns:

An array containing all of the trees elements 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(element)

Inserts a collection of values into the tree

Parameters:

Name	Type	Description
`element`	*	the value

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.

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

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.

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.

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

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

Returns:

an array of values

Type: Array

remove(key)

Remove the key and the value associated with it

Parameters:

Name	Type	Description
`key`	*

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`

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.

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

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.

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.

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.

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.