GpsGate Server JavaScript API

/**
 *
 * Various generic algorithms, Set handling etc.
 * @module Algorithm
 */

/**
 * namespace
 * @class Franson.Algorithm
 * @static
 */
Franson.Algorithm = Franson.Algorithm || {};


/**
 * <tt>O(N)</tt> <br />
 * note: see the overloads also
 * rename findDeltaSegments?
 * todo: change to iter interface or mapped cursor
 * @method findSegments
 * @param {object[]} data
 * @param {integer} [startIndex=0]
 * @param {integer} [length=data.length]
 * @param {bool function(lhs, rhs)} [binaryPredicate=MochiKit.Base.operator.ceq] logic is compare(a, b) == 0 (equal)
 * @return {integer[]} Array of indices, the indices will be index + startIndex (i.e absolute)
 */
Franson.Algorithm.findSegments = function(data, startIndex, length, binaryPredicate)
{
	// handle overloads

	// findSegments(data, [binaryPredicate])
	if (arguments.length == 1 || (arguments.length == 2 && typeof(arguments[1]) == 'function'))
	{
		binaryPredicate = arguments[1];
		startIndex = 0;
		length = data.length;
	}
	else
	// findSegments(data, startIndex, [binaryPredicate])
	if (arguments.length == 2 || (arguments.length == 3 && typeof(arguments[2]) == 'function'))
	{
		binaryPredicate = arguments[2];
		length = data.length;
	}
	// else same signature as declared at top
	binaryPredicate = binaryPredicate || MochiKit.Base.operator.ceq;

	if (length == 0)
		return [];

	var segments = [startIndex];
	for (var i = startIndex; i < startIndex + length - 1; ++i) // todo: could use Franson.Iter.pairIter here
	{
		if (!binaryPredicate(data[i], data[i+1]))
		{
			segments.push(i+1);
		}
	}
	segments.push(startIndex + length); // always store last index

	return segments;
};

/**
 * set subtraction, assuming unordered input: <tt>O(N^2)</tt> <br />
 * ref <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/difference.html">difference</a>
 * todo: hmm, rename "setComplement"? (not same?)
 * todo: implement this method as an Iterable?
 * todo: create versions assuming ordered input (bin-search impl.) and perhaps version assuming unordered but hashable elems?
 * todo: create a Set datastructure and more algorithms (union, sum, intersection etc)
 * todo: move to separate algorithm module
 * todo: support multiple arguments?
 * @method setDifference
 * @param {Iterable} setA
 * @param {Iterable} setB
 * @param {BinaryPredicate} [cmp=MochiKit.Base.eq (==)]
 * @return {object[]} D = A - B
 */
Franson.Algorithm.setDifference = function(setA, setB, cmp)
{
	cmp = cmp || MochiKit.Base.operator.eq; // ok? or ceq. I'd say objEqual (compare==0) is unnecessarily demanding as a default(?)

	var result = [];
	forEach(setA, function(a)
	{
		var exists = false;
		forEach(setB, function(b)
		{
			if (cmp(a, b))
			{
				exists = true;
				throw MochiKit.Iter.StopIteration; // break
			}
		});
		if (!exists)
		{
			result.push(a);
		}
	});

	return result;
};

/**
 * Assumes unordered input: <tt>O(N^2)</tt> <br />
 * ref <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/intersection.html">intersection</a>
 * see also <a href="#method_setDifference">setDifference</a>
 * @method setIntersection
 * @param {Iterable} setA
 * @param {Iterable} setB
 * @param {BinaryComparator} [cmp=eq]
 * @return {object[]}
 */
Franson.Algorithm.setIntersection = function(setA, setB, cmp)
{
	cmp = cmp || MochiKit.Base.operator.eq;

	var result = [];
	forEach(setA, function(a)
	{
		forEach(setB, function(b)
		{
			if (cmp(a, b))
			{
				result.push(a);
			}
		});
	});

	return result;
};

/**
 * Assumes unordered input: <tt>O(N^2)</tt> <br />
 * ref <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/union.html">union</a>
 * todo: support multiple arguments?
 * @method setUnion
 * @param {Iterable} setA
 * @param {Iterable} setB
 * @param {BinaryComparator} [cmp=eq]
 * @return {object[]} A u B
 */
Franson.Algorithm.setUnion = function(setA, setB, cmp)
{
	return MochiKit.Base.extend(setA, Franson.Algorithm.setDifference(setB, setA, cmp));
};


/**
 * Assumes unordered input: <tt>O(N^2)</tt> <br />
 * ref <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/symmetricSetDiff.html">symmetricSetDiff</a>
 * @method setSymmetricDifference
 * @param {Iterable} setA
 * @param {Iterable} setB
 * @param {BinaryComparator} [cmp=eq]
 * @return {object[]}
 */
Franson.Algorithm.setSymmetricDifference = function(setA, setB, cmp)
{
	var intersection = Franson.Algorithm.setIntersection(setA, setB, cmp);
	var union = Franson.Algorithm.setUnion(setA, setB, cmp);
	return Franson.Algorithm.setDifference(union, intersection);
};