/*
 *  SPL - The SPL Programming Language
 *  Copyright (C) 2004, 2005  Clifford Wolf <clifford@clifford.at>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *  mod_array.spl: Array functions (SPL part)
 */

// simple bubble sort
function __array_sort_backend_bubble(array, order_function)
{
	// this is a simple bubblesort
	var keep_sorting = 1;
	while (keep_sorting) {
		keep_sorting = 0;
		var a = next array, undef;
		var b = next array, a;
		while (defined b) {
			if (order_function(a, b)) {
				array_switch(array, a, b);
				keep_sorting = 1;
				b = a;
			}
			b = next array, (a = b);
		}
	}
}

// a btree sort
function __array_sort_backend_btree(array, order_function)
{
	var tree = [ lc: 0, rc: 0 ];

	//       W              S
	//      / \            / \
	//     /   \          /   \
	//    S     Y  ===>  G     W
	//   / \                  / \
	//  /   \                /   \
	// G     U              U     Y
	//
	function rotate_right(t)
	{
		var W = t;
		var S = t.l;
		var Y = t.r;
		var G = S.l;
		var U = S.r;

		// unlink W and S
		delete W.l;
		delete W.r;
		delete S.l;
		delete S.r;

		// create new W in x
		var x;
		var x.k = W.k;
		var x.l = U;
		var x.r = Y;
		var x.lc = U.lc + U.rc + declared U.k;
		var x.rc = Y.lc + Y.rc + declared Y.k;

		// create new S in t
		var t.k = S.k;
		var t.l = G;
		var t.r = x;
		var t.lc = G.lc + G.rc + declared G.k;
		var t.rc = x.lc + x.rc + declared x.k;
	}

	//       W              S
	//      / \            / \
	//     /   \          /   \
	//    S     Y  <===  G     W
	//   / \                  / \
	//  /   \                /   \
	// G     U              U     Y
	//
	function rotate_left(t)
	{
		var S = t;
		var G = t.l;
		var W = t.r;
		var U = W.l;
		var Y = W.r;

		// unlink S and W
		delete S.l;
		delete S.r;
		delete W.l;
		delete W.r;

		// create new S in x
		var x;
		var x.k = S.k;
		var x.l = G;
		var x.r = U;
		var x.lc = G.lc + G.rc + declared G.k;
		var x.rc = U.lc + U.rc + declared U.k;

		// create new W in t
		var t.k = W.k;
		var t.l = x;
		var t.r = Y;
		var t.lc = x.lc + x.rc + declared x.k;
		var t.rc = Y.lc + Y.rc + declared Y.k;
	}

	function insert_tree(t, k)
	{
		if (not declared t.k) {
			var t.k = k;
			var t.l = [ lc: 0, rc: 0];
			var t.r = [ lc: 0, rc: 0];
			return;
		}

		if (order_function(t.k, k))
			{ insert_tree(t.l, k); t.lc++; }
		else
			{ insert_tree(t.r, k); t.rc++; }

		if (t.lc > t.rc+1)
			rotate_right(t);

		if (t.rc > t.lc+1)
			rotate_left(t);
	}

	function parse_tree(t)
	{
		if (not declared t.k)
			return;

		parse_tree(t.l);

		var temp = array[t.k];
		delete array[t.k];
		array[t.k] = temp;

		parse_tree(t.r);
	}

	foreach key (array)
		insert_tree(tree, key);
	
	parse_tree(tree);
}

// sort backend
function __array_sort_backend(array, order_function)
{
	if (elementsof array < 10)
		__array_sort_backend_bubble(array, order_function);
	else
	if (not __array_sort_backend_qsort(array, order_function))
		__array_sort_backend_btree(array, order_function);
}

/**
 * Sorting by keys
 *
 * This function sorts the passed array ussing the passed order function. The
 * order function is called whenever this function wants to compare two
 * elements. The key of the 1st element is passed as 1st parameter to the
 * order_function. The key of the 2nd element as 2nd parameter. The order
 * function must return 1 if the elements are in the wrong order.
 *
 * Example:
 *
 *	var a = [ 5 => 'a', '3' => 'b', '8' => 'c' ];
 *
 *	array_sort_by_keys(a, function(a,b) { return a > b; });
 *
 *	foreach i (a)
 *		debug "$i --> ${a[i]}";
 *
 * This creates the output:
 *
 *	SPL Debug: 3 --> b
 *	SPL Debug: 5 --> a
 *	SPL Debug: 8 --> c
 *
 * Small arrays (less then 10 elements) are sorted using a simple bubble sort.
 * Big arrays are sorted using the system qsort() function (if available) and
 * using a btree sort otherwise.
 */
function array_sort_by_keys(array, order_function)
{
	return __array_sort_backend(array, order_function);
}

/**
 * Sorting by values
 *
 * This function is pretty similar to [[array_sort_by_keys]]. The only
 * difference is that it passes references to the elements which should be
 * compared to the order function.
 */
function array_sort_by_values(array, order_function)
{
	return __array_sort_backend(array, function(a, b) { return order_function(array[a], array[b]); });
}

/**
 * Concatenate all array elements to a string
 */
function array_join(array, seperator)
{
	var ret, isfirst = 1;
	foreach[] v (array) {
		if (isfirst) isfirst = 0;
		else ret ~= seperator;
		ret ~= v;
	}
	return ret;
}