GpsGate Server JavaScript API

/**
 * <p>
 * Copyright Franson Technology AB, Sweden, 2009 <br />
 * http://gpsgate.com, http://franson.com <br />
 * <br />
 * author Fredrik Blomqvist
 * </p>
 * <p>
 * <a href="http://en.wikipedia.org/wiki/Iterator">Iterator</a> module<br />
 * Compatible with <a href="http://mochikit.com/doc/html/MochiKit/Iter.html">MochiKit.Iter</a> protocol (will be added to JavaScript in <a href="https://developer.mozilla.org/en/New_in_JavaScript_1.7#Iterators">v1.7</a>) basically same as the Python <a href="http://docs.python.org/library/itertools.html">itertools</a> module.<br />
 * </p>
 * note that iterators are not cloneable (in general) since they are (allowed to be) implemented using closures.
 * <p>
 * tree Iters can be easily be adapted to traverse any tree structure like html-DOM, SVG/VML, quadtrees etc.
 * (for structures supporting getNextSibling also (like DOM..) you can create completely stack-less iterators but I doubt it would be worth it unless you have very large graphs)
 * </p>
 * todo: flattenIter, bidirectionalIter (also see Python::itertools combinatoric generators) etc
 *
 * @module Iter
 *
 */
var Franson = Franson || {};
/**
 * namespace
 * @class Franson.Iter
 * @static
 */
Franson.Iter = Franson.Iter || {};


/**
 * parent->child order (depth-first, preorder)
 * ref <a href="http://en.wikipedia.org/wiki/Tree_traversal">tree traversal</a>
 * @method treePreOrderIter
 * @param {object} rootNode
 * @param {function} getChildNodes  (ex: for dom traversal use <code>treePreOrderIter(dom, methodcaller('childNodes'));</code>)
 * @return {Iterable}
 */
Franson.Iter.treePreOrderIter = function(rootNode, getChildNodes)
{
	var stack = [ rootNode ];

	return {
		next: function()
		{
			if (stack.length == 0)
				throw MochiKit.Iter.StopIteration;

			var node = stack.pop();

			// note: this should rather set a state and iterate this level instead of filling stack for less mem (stack) usage and "true" iterator behaviour.
			MochiKit.Iter.iextend(stack, getChildNodes(node));

			return node;
		}
	};
};


/**
 * top-down, breadth-first, level-order traversal (parent->siblings order)
 * ref <a href="http://en.wikipedia.org/wiki/Tree_traversal">tree traversal</a>
 * (could be seen as an iterator version of <a href="http://mochikit.com/doc/html/MochiKit/Base.html#fn-nodewalk">MochiKit.Base.nodeWalk()</a>)
 * useful for searching and culling
 * todo: create version taking a descend-predicate if used for culling
 * todo: hmm, would be nice to have some version that would indicate each level (useful when doing searches for example)
 * @method treeLevelOrderIter
 * @param {object} rootNode
 * @param {function(node)} getChildNodes should return an empty array if no children
 * @return {Iterable}
 */
Franson.Iter.treeLevelOrderIter = function(rootNode, getChildNodes)
{
	var queue = [ rootNode ];

	return {
		next: function()
		{
			if (queue.length == 0)
				throw MochiKit.Iter.StopIteration;

			var node = queue.shift();

			// note: this should rather set a state and iterate this level instead of filling stack for less mem usage and "true" iterator behaviour.
			MochiKit.Iter.iextend(queue, getChildNodes(node));

			return node;
		}
	};
};


/**
 * bottom-up iteration
 * ref <a href="http://en.wikipedia.org/wiki/Tree_traversal">tree traversal</a>
 * useful for pruning for example.
 * @method treePostOrderIter
 * @param {object} rootNode
 * @param {function(node)} getChildNodes should return an empty array if no children
 * @return {Iterable}
 */
Franson.Iter.treePostOrderIter = function(rootNode, getChildNodes)
{
	var stack = [ [rootNode, false] ]; // [node, visited] (could use a queue also)

	return {
		next: function()
		{
			while (true) // loop until a visited node is returned or end of iteration
			{
				if (stack.length == 0)
					throw MochiKit.Iter.StopIteration;

				var n = stack.pop();
				if (n[1]) // visited?
					return n[0];
				// else
				n[1] = true;
				stack.push(n);

				MochiKit.Iter.iextend(stack, MochiKit.Iter.imap(
					function(node) { return [node, false]; },
					getChildNodes(n[0])
				));
			}
		}
	};
};


/**
 * predicate decides if the branch will be descended into
 * todo: this could be done using any depth-first iter (preOrderIter) also.
 * todo: create tri-state version. i.e a path where it descends into subtree but stops checking if parent was flagged (completely) visible.
 * rename cullingIter?
 * @method treeLevelOrderIterIf
 * @param {object} rootNode
 * @param {function} getChildNodes
 * @param {function} predicate (unary)
 */
Franson.Iter.treeLevelOrderIterIf = function(rootNode, getChildNodes, predicate)
{
	var queue = [ rootNode ];

	return {
		next: function()
		{
			while (true) // loop until end or node passed predicate
			{
				if (queue.length == 0)
					throw MochiKit.Iter.StopIteration;

				var node = queue.shift();
				if (predicate(node))
				{
					MochiKit.Iter.iextend(queue, getChildNodes(node));
					return node;
				}
			}
		}
	};
};



/**
 * iterates child->parent
 * todo: hmm, should or should not the initial node be part of the iteration?
 * @method leafParentIter
 * @param {object} node
 * @param {function} getParentNode
 * @return {Iterable}
 */
Franson.Iter.leafParentIter = function(node, getParentNode)
{
	return {
		next: function()
		{
			node = getParentNode(node);

			if (node == null)
				throw MochiKit.Iter.StopIteration;

			return node;
		}
	};
};


/**
 * Pairwise view of an iterable (overlapping)
 * <tt>[a, b, c, d, ..] -> [[a,b],[b,c],[c,d], ..]</tt>
 *
 * todo: generalize to full n-tuples (fifo queue) and configurable start and end logic (offset, clamp, wraparound etc) (windowIter?)
 * @method pairIter
 * @param {Iterable} iterable
 * @return {Iterable}
 */
Franson.Iter.pairIter = function(iterable)
{
	var it = MochiKit.Iter.iter(iterable);
	var elem0 = it.next();

	return {
		next: function()
		{
			var elem1 = it.next();
			var pair = [ elem0, elem1 ];
			elem0 = elem1;
			return pair;
		}
	};
};