burst.Alg Class Reference

Detailed Description

Scoping class to hold static collection utility functions.

These utilities are loosely inspired by the STL: http://www.sgi.com/tech/stl/stl_index.html

No attempt is made at genericity. When we do support different types of collections, it is with different function names. Genericity is not natively supported by ECMAScript, nor is multi-dispatch, and while emulating it would be possible, we deem it not worth it. Another approach would be to introduce iterator objects for each underlying collection object, but that too is a bit heavy weight in both API complexity and overhead.

The collection types which have at least some algorithm functions available are:

Array
Arguments (sadly not a real Array in ECMAScript)
Object (also called a "map" here, for its associative character)
DOM Collection
DOM Node (these algorithms are mostly found in the burst.xml.DomUtil static methods)

Todo:

Investigate any speed improvement from hoisting arr.length into a constant outside of loop.

perhaps use Duff's Device http://home.earthlink.net/~kendrasg/info/js_opt/jsOptMain.html#duffsdevice

Document which algorithms allow mutating function arguments.

Static Public Member Functions

void for_map (Object map, Function binary_func)

Iterate through the properties of Object map calling the binary function binary_func with the two arguments of property name and value.

Array transform_map (Object map, Function binary_func, Array arr)

Similar to for_map, except that the return values of binary_func are collected into the Array arr.

void for_each (Array arr, Function unary_func)

Call unary_func on each Array element.

void for_each_call (Array arr, Object obj, Function unary_func)

Unlike for_each, use obj.call to invoke the member function func on each Array element.

void for_each_call2 (Array arr, Object obj, Function binary_func, Object arg2)

Just like for_each_call, but a binary function, and the second argument is the fixed arg2.

Number find (Array arr, Object val)

Returns index of first element that is == val.

Object find_value (Array arr, Object val)

Like find, but returns the matching value rather than the index.

Number find_if (Array arr, Function unary_predicate)

Returns index of first element for which unary_predicate is true.

Object find_if_value (Array arr, Function unary_func)

Like find_if, but rather than returning an index, it returns the first return value from unary_func that tests as true.

Object find_if_nth_value (Array arr, Number n, Function unary_func)

Like find_if_value, but returns the nth (zero-based) value returned from unary_func that tests as true.

Object find_if_specified (Array arr, Function unary_func)

Like find_if_value, but returns the first first value that is not null or undefined (vs.

Number count_if (Array arr, Function unary_predicate)

Counts elements for which unary_predicate is true.

Array generate (Array arr, Function zeroary_func)

Set all Array members with the result from calling the generator (with no arguments).

Array generate_n (Array arr, Number n, Function zeroary_func)

Set the first n members of the Array by calling the generator.

Number lower_bound (Array arr, Object val, Function less)

Return index of first element not less than val.

Number upper_bound (Array arr, Object val, Function less)

Returns index of first element for which val is less than the element.

Array transform (Array arr, Function unary_func, Array dest)

Collection the results of invoking unary_func on each element.

Object toMap (Array arr, Function unary_func, Object map)

Initialize a map with keys being the results of calling unary_func on each element.

Object toSet (Array arr, Object map)

Initialize a map with keys taken from arr, and the value true.

Array copy (Array arr, Array dest)

Copy arr into dest.

Member Function Documentation

Array burst.Alg.copy ( Array arr,

Array dest

) [static]

Copy arr into dest.
The same indexes are used (versus doing a push).
Parameters:

arr The Array to copy.

dest Optional. The destination Array. If not specified, one is created.

Returns:
dest

Number burst.Alg.count_if ( Array arr,

Function unary_predicate

) [static]

Counts elements for which unary_predicate is true.

Parameters:

arr the Array to iterate through.

unary_predicate the function to call on each element.

Returns:
the count of elements for which unary_predicate returned a true value.

Number burst.Alg.find ( Array arr,

Object val

) [static]

Returns index of first element that is == val.
Returns -1 if none.
Parameters:

arr the Array to look through.

val the value to look for

Returns:
the index of the first matching element, or -1 if none.

Number burst.Alg.find_if ( Array arr,

Function unary_predicate

) [static]

Returns index of first element for which unary_predicate is true.
Returns -1 if none.
Parameters:

arr the Array to look through.

unary_predicate the function to call on each element.

Returns:
the index of the first matching element, or -1 if none.

Object burst.Alg.find_if_nth_value ( Array arr,

Number n,

Function unary_func

) [static]

Like find_if_value, but returns the nth (zero-based) value returned from unary_func that tests as true.

Parameters:

arr the Array to iterate through.

n The number of the match to return (zero-based).

unary_func the function to call on each element.

Returns:
the nth true value returned, or undefined if none.

Object burst.Alg.find_if_specified ( Array arr,

Function unary_func

) [static]

Like find_if_value, but returns the first first value that is not null or undefined (vs.
testing for true).
Parameters:

arr the Array to iterate through.

unary_func the function to call on each element.

Returns:
the first not-null, not-undefined value returned, or undefined if none.

Object burst.Alg.find_if_value ( Array arr,

Function unary_func

) [static]

Like find_if, but rather than returning an index, it returns the first return value from unary_func that tests as true.

Parameters:

arr the Array to iterate through.

unary_func the function to call on each element.

Returns:
the first true value returned, or undefined if none.

Object burst.Alg.find_value ( Array arr,

Object val

) [static]

Like find, but returns the matching value rather than the index.
Returns undefined if none match.
Parameters:

arr the Array to look through.

val the value to look for

Returns:
the matching value in the array, or undefined if none.

void burst.Alg.for_each ( Array arr,

Function unary_func

) [static]

Call unary_func on each Array element.
No return value.
Parameters:

arr The Array to iterate over.

unary_func The function to call on each element.

void burst.Alg.for_each_call ( Array arr,

Object obj,

Function unary_func

) [static]

Unlike for_each, use obj.call to invoke the member function func on each Array element.

Parameters:

arr The Array to iterate over.

obj The object to invoke unary_func.call(obj, val) on.

unary_func The function to call on each element.

void burst.Alg.for_map ( Object map,

Function binary_func

) [static]

Iterate through the properties of Object map calling the binary function binary_func with the two arguments of property name and value.
Note that it is assumed that the caller has not added any extraneous properties or will filter those out in func. This does no filtering.

Todo:
consider filtering by "k in obj.prototype", etc.

Parameters:

map The object to iterate over.

binary_func a binary function

Array burst.Alg.generate ( Array arr,

Function zeroary_func

) [static]

Set all Array members with the result from calling the generator (with no arguments).
Assumes the Array length has already been set.
Parameters:

arr The Array to set values of (up to its existing length)

zeroary_func The function to call to generate each value

Returns:
arr

Array burst.Alg.generate_n ( Array arr,

Number n,

Function zeroary_func

) [static]

Set the first n members of the Array by calling the generator.

Parameters:

arr The Array to set values of.

n The number of array members to set or add.

zeroary_func The function to call to generate each value.

Returns:
arr

Number burst.Alg.lower_bound ( Array arr,

Object val,

Function less

) [static]

Return index of first element not less than val.
This is the first position where val could be inserted in a way preserving the order imposed by the "less" comparator. Returns length if val is greater than all elements.
Parameters:

arr The Array to iterate through.

val The value to pass into the less function

less Optional. A binary predicate defaulting to function(a,b) {return a<b;}

Returns:
The first index i for which !less(arr[i],val)

Object burst.Alg.toMap ( Array arr,

Function unary_func,

Object map

) [static]

Initialize a map with keys being the results of calling unary_func on each element.
The corresponding map values are the element values used to produce those keys.
Parameters:

arr The Array to iterate over, which also has the eventual map values.

unary_func The function to call on each element to produce a key.

map Optional. If not specified a new Object is created.

Returns:
map.

Object burst.Alg.toSet ( Array arr,

Object map

) [static]

Initialize a map with keys taken from arr, and the value true.

Parameters:

arr The Array of keys to iterate over.

map Optional. If not specified a new Object is created.

Returns:
map.

Array burst.Alg.transform ( Array arr,

Function unary_func,

Array dest

) [static]

Collection the results of invoking unary_func on each element.
Note that the same index is used in dest and arr; the results are not just push'd onto dest.
Parameters:

arr The Array to iterate over.

unary_func The function to call on each element (actually called with both value and index).

dest Optional. If not provided, a new Array is created.

Returns:
dest

Array burst.Alg.transform_map ( Object map,

Function binary_func,

Array arr

) [static]

Similar to for_map, except that the return values of binary_func are collected into the Array arr.

Parameters:

map The object to iterate over.

binary_func A binary function.

arr Optional. If specified, the array to push onto. Otherwise a new Array is made.

Returns:
arr

Number burst.Alg.upper_bound ( Array arr,

Object val,

Function less

) [static]

Returns index of first element for which val is less than the element.
This is the highest index where val could be inserted preserving the order imposed by the "less" comparator. Returns length if none.
If val does not exist in the container, lower_bound and upper_bound are the same. If val exists exactly once in the container, then lower_bound returns the index of that val, and upper_bound returns the index of that val. Take a look at your favorite C++ text for more information.

Parameters:

arr The Array to iterate through.

val The value to pass into the less function

less Optional. A binary predicate defaulting to function(a,b) {return a<b;}

Returns:
The first index i for which less(val,arr[i])

The documentation for this class was generated from the following file:

Alg.java

Generated on Tue Nov 30 04:03:08 2004 for BurstProject by

1.3.4


Static Public Member Functions
void	for_map (Object map, Function binary_func)
	Iterate through the properties of Object map calling the binary function binary_func with the two arguments of property name and value.
Array	transform_map (Object map, Function binary_func, Array arr)
	Similar to for_map, except that the return values of binary_func are collected into the Array arr.
void	for_each (Array arr, Function unary_func)
	Call unary_func on each Array element.
void	for_each_call (Array arr, Object obj, Function unary_func)
	Unlike for_each, use obj.call to invoke the member function func on each Array element.
void	for_each_call2 (Array arr, Object obj, Function binary_func, Object arg2)
	Just like for_each_call, but a binary function, and the second argument is the fixed arg2.
Number	find (Array arr, Object val)
	Returns index of first element that is == val.
Object	find_value (Array arr, Object val)
	Like find, but returns the matching value rather than the index.
Number	find_if (Array arr, Function unary_predicate)
	Returns index of first element for which unary_predicate is true.
Object	find_if_value (Array arr, Function unary_func)
	Like find_if, but rather than returning an index, it returns the first return value from unary_func that tests as true.
Object	find_if_nth_value (Array arr, Number n, Function unary_func)
	Like find_if_value, but returns the nth (zero-based) value returned from unary_func that tests as true.
Object	find_if_specified (Array arr, Function unary_func)
	Like find_if_value, but returns the first first value that is not null or undefined (vs.
Number	count_if (Array arr, Function unary_predicate)
	Counts elements for which unary_predicate is true.
Array	generate (Array arr, Function zeroary_func)
	Set all Array members with the result from calling the generator (with no arguments).
Array	generate_n (Array arr, Number n, Function zeroary_func)
	Set the first n members of the Array by calling the generator.
Number	lower_bound (Array arr, Object val, Function less)
	Return index of first element not less than val.
Number	upper_bound (Array arr, Object val, Function less)
	Returns index of first element for which val is less than the element.
Array	transform (Array arr, Function unary_func, Array dest)
	Collection the results of invoking unary_func on each element.
Object	toMap (Array arr, Function unary_func, Object map)
	Initialize a map with keys being the results of calling unary_func on each element.
Object	toSet (Array arr, Object map)
	Initialize a map with keys taken from arr, and the value true.
Array	copy (Array arr, Array dest)
	Copy arr into dest.