# AVSLib :: 'array' package :: 'transforms' module
# Copyright (c) 2005 George Zarkadas (gzarkadas@users.sourceforge.net)

# 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"

DefineModule("avslib", "array", "transforms")

global __load__ = Eval("""
	LoadModule("avslib", "base", "core")
	LoadModule("avslib", "string", "core")
	LoadModule("avslib", "numeric", "statistics")
	""")
global __load__ = IsPackageLoaded("avslib", "array") ? NOP : Eval("""
	LoadModule("avslib", "array", "core")
	LoadModule("avslib", "array", "operators")
	LoadModule("avslib", "array", "slices")
	""")

# Returns the array inversed (eg. ArrayInvert("1,2,3") = "3,2,1"
#
Function ArrayInvert(string array)
{
	arrlen = array.ArrayLen()
	_ret = (arrlen > 0) ? array.ArrayGetString(-1) : ""
	return (arrlen > 1) \
		? _ret + __ARRAY_DLM + ArrayInvert(array.ArrayDelete(-1)) \
		: _ret
}

# Rotates all array elements by 'num_indexes' positions.
# 'num_indexes' > 0 : rotates towards the end of the array (ie a right shift).
# 'num_indexes' < 0 : rotates towards the start of the array (ie a left shift).
# Abs(num_indexes) can be greater than ArrayLen(array); the modulo of division 
# with ArrayLen(array) is used.
#
Function ArrayRotate(string array, int num_indexes)
{
	arrlen = array.ArrayLen()
	num = Sign(num_indexes) * (arrlen > 0 ? Abs(num_indexes) % arrlen : 0)
	return (num != 0) \
		? ArrayGetRange(array, -num, arrlen) + __ARRAY_DLM + \
			ArrayGetRange(array, 0, -num) \
		: array
}

# Swaps the positions (indexes) of two array elements 
# (ie a[i] becomes a[j] and a[j] becomes a[i])
#
Function ArrayElmSwap(string array, int index1, int index2)
{
	arrlen = ArrayLen(array)
	index1 = __bound_array_index(array, index1)
	index2 = __bound_array_index(array, index2)
	i1 = __min2(index1, index2)
	i2 = __max2(index1, index2)
	return index1 != index2 \
		? ArrayJoin( \
			array.ArrayGetRange(0, i1), array.ArrayGetString(i2), \
			array.ArrayGetRange(i1 + 1, i2), array.ArrayGetString(i1), \
			array.ArrayGetRange(i2 + 1) ) \
		: array 
}

# Sorts an array in ascending or descending order. Implements the "quick sort"
# algorigthm.
# Optional 'cmp_func' must accept two val arguments at the start of its list 
# and return -1, 0, 1 if arg1 < ar2, ar1 == arg2, arg1 > arg2 respectively.
# If 'cmp_func' needs extra arguments, these should be provided in 'cmp_args' 
# just like in the array operator functions.
# Optional 'avg_func' must accept two val arguments at the start of its list
# and return the mean value of them. If 'avg_func' needs extra arguments, 
# these should be provided in 'avg_args' just like in the array operator functions.

	# default comparison function
	#
	Function __array_cmp_default(val v1, val v2)
	{
		return (v1 < v2) ? -1 : ((v1 > v2) ? 1 : 0)
	}

	# inner-inner loop of i counter
	#
	Function __array_sort_newi(string array, int i, val mean)
	{
		# note that mean is in local scope
		cmp = Eval(__array_sort_cmp_func + "(" \
			+ QuoteNoexpr(array.ArrayGetString(i)) + ",mean" \
			+ __array_sort_cmp_args + ")")
		return (cmp < 0) ? __array_sort_newi(array, i + 1, mean) : i
	}
	
	# inner-inner loop of j counter
	#
	Function __array_sort_newj(string array, int j, val mean)
	{
		# note that mean is in local scope
		cmp = Eval(__array_sort_cmp_func + "(" \
			+ QuoteNoexpr(array.ArrayGetString(j)) + ",mean" \
			+ __array_sort_cmp_args + ")")
		return (cmp > 0) ? __array_sort_newj(array, j - 1, mean) : j
	}
	
	# inner loop of counters and elements switching
	# __aso_x are needed in order to return to caller
	# i,j information in addition to the array itself
	#
	Function __array_sort_loop(string array, int i, int j, val mean)
	{
		# get the new counters' values
		global __aso_i = __array_sort_newi(array, i, mean)
		global __aso_j = __array_sort_newj(array, j, mean)
		# emulate an if check then {multi-statements} block
		check = (__aso_i <= __aso_j)
		array = check ? array.ArrayElmSwap(__aso_i, __aso_j) : array
		global __aso_i = __aso_i + (check ?  1 : 0)
		global __aso_j = __aso_j + (check ? -1 : 0)
		# test for loop termination
		# here do NOT use check; __aso_i,j may have 
		# been modified at the previous step
		return (__aso_i <= __aso_j) \
			? __array_sort_loop(array, __aso_i, __aso_j, mean) \
			: array
	}
	
	# quick-sort core function; performs always an ascending order sort
	#
	Function __array_sort_core(string array, int left, int right)
	{
		# calculate ends' average; array,left,right 
		# are in local scope and thus can be used
		mean = Eval( __array_sort_avg_func + \
			"(array.ArrayGet(left), array.ArrayGet(right)" \
			+ __array_sort_avg_args + ")" )
		# initiate global counters
		global __aso_i = left
		global __aso_j = right
		# perform an inner loop and then branch left,right if needed
		array = __array_sort_loop(array, left, right, mean)
		array = (left < __aso_j) \
			? __array_sort_core(array, left, __aso_j) \
			: array
		array = (__aso_i < right) \
			? __array_sort_core(array, __aso_i, right) \
			: array
		# return the final result (ascending sorted array)
		return array
	}

# top-level wrapper; process arguments and transforms the result 
# in case a descending sort was requested
#
Function ArraySort(string array, bool "ascending", string "cmp_func", \
	string "cmp_args", string "avg_func", string "avg_args")
{
	ascending = Default(ascending, true)
	# assign to globals to avoid overloading the stack with parameters
	global __array_sort_cmp_func = Default(cmp_func, "__array_cmp_default")
	global __array_sort_cmp_args = Defined(cmp_args) ? "," + cmp_args : "" 
	global __array_sort_avg_func = Default(avg_func, "Average")
	global __array_sort_avg_args = Defined(avg_args) ? "," + avg_args : "" 
	array = __array_sort_core(array, 0, array.ArrayLen() - 1)
	return ascending \
		? array \
		: array.ArrayInvert()
}

# Removes elements from 'array', wherever the 'flags' array has a zero value.
#
Function ArrayReduce(string array, string flags)
{
	arrlen = array.ArrayLen()
	Assert(arrlen == flags.ArrayLen(), \
		"ArrayReduce: both arrays must have the same length.")
	del = flags.ArrayGet(0) == 0
	elm = del ? "" : array.ArrayGetString(0) + (arrlen > 1 ? __ARRAY_DLM : "")
	ret = arrlen > 1 \
		? elm + ArrayReduce(array.ArrayDelete(0), flags.ArrayDelete(0)) \
		: elm
	# if the call to ArrayReduce for the last array element 
	# does delete the element, an excess __ARRAY_DLM will remain
	# at the end of the string; remove it.
	return __right_str(ret, StrLen(__ARRAY_DLM)) == __ARRAY_DLM \
		? __left_str(ret, StrLen(ret) - StrLen(__ARRAY_DLM)) \
		: ret
}

# Returns an array with only distinct elements of 'array' in it. The resulting 
# array is always returned in ascending sort order (ie a[i] < a[i+1] for all i)
# Optional 'cmp_func' must accept two val arguments at the start of its list 
# and return -1,0,1 if arg1<ar2,ar1==arg2,arg1>arg2
# If 'cmp_func' needs extra arguments, these should be provided in 'cmp_args' 
# just like in the array operator functions.
# Optional 'avg_func' must accept two val arguments at the start of its list 
# and return the mean value of them. If 'avg_func' needs extra arguments, 
# these should be provided in 'avg_args' just like in the array operator functions
	
	Function __array_distinct_core(string array, string "cmp_func", string "cmp_args")
	{
		cmp_func = Default(cmp_func, "__array_cmp_default")
		# here we will not construct a string to pass to Eval; 
		# thus if cmp_args are undefined pass them unchanged
		cmp_args = Defined(cmp_args) ? "," + cmp_args : cmp_args
		pred = array.ArrayGetRange(0, -1)	# from [0] to [end-1]
		succ = array.ArrayGetRange(1)		# from [1] to [end]
		# since array is always sorted ascending, 
		# cmp_func will either return -1 or 0 if succ==pred
		# we thus only need to eliminate those indexes 
		# where 0 is returned
		flags = ArrayOpArrayFunc(pred, succ, cmp_func, cmp_args)
		# add an 'exists' flag for the very first element
		flags = flags.ArrayInsert(-1, 0)
		return array.ArrayReduce(flags)
	}
	
Function ArrayDistinct(string array, string "cmp_func", string "cmp_args", \
	string "avg_func", string "avg_args")
{
	# if array length is <= 1 then it only has 
	# distinct elements; return it immediately
	return array.ArrayLen() > 1 \
		? __array_distinct_core(array.ArraySort(true, cmp_func, cmp_args, \
			avg_func, avg_args), cmp_func, cmp_args) \
		: array
}
