// ====================================================================================================================
// Copyright (c) 2003,2004  Henk Reints, http://henk-reints.nl
// -----------------------------------------------------------
// This script adds some useful methods to the prototype of the Array Object. Adding methods to the prototype of an
// Object makes them available to __ALL__ Instances of that Object type without further action by a programmer. Simply
// include this script at the beginning of your file using "<script language=JavaScript src=hr$arraysort.js></script>"
// and all functionality will be available. The methods are:
//
//	createIndex (userCompareFunction)
//
//		Creates a new Array containing the indices of the original Array in the sorting order of the Array
//		content and adds it to the Array Object Instance as a new property called 'mainIndex'. The content
//		of the original Array is left unchanged. the userCompareFunction is optional. If given then it will
//		be saved within the Array object in order to be used by the 'search' method.
//		See below for more details.
//
//	createIndexNaN (mode)
//
//		Basically the same as createIndex, but intended for sorting Arrays of Numbers that may be NaN
//		(if you're sure that your Array has no NaN values then you'd better use createIndex, it's faster!)
//		the 'createIndexNaN' method has built-in NaN handling, which performs faster than supplying a
//		userCompareFunction to handle NaN values. (Please note that "NaN" means "Not a Number",
//		so mathematically it CANNOT be compared to a Number yielding something like 'greater' or 'less'
//		or 'equal'. The only thing this method does is putting all NaN values before or behind all real
//		Numbers during the sort).
//		The 'mode' argument specifies how to treat NaN values:
//		if mode <= 0 it sorts all NaN values before any real Number (as if NaN < -Infinity),
//		else         it sorts all NaN values behind any real Number (as if NaN > +Infinity).
//		createIndexNaN stores a proper userCompareFunction in the Array for the 'search' method.
//
//	removeDuplicates()
//
//		NOT YET WRITTEN
//		To be used AFTER createIndex. Removes all duplicate elements from the mainIndex.
//		The original content of the Array is left unchanged.
//
//	createKeyIndex (keyName, keyExtractFunction, userCompareFunction)
//
//		NOT YET WRITTEN
//		idea: make a property A.keyIndex.<keyName> (using eval?) which is the Array of key values
//		including its own mainIndex. then it can be addressed easily (only for creation the key
//		name must then be quoted here). !!!also implement functionality for Join etc.
//
//	get (i)
//
//		returns the Array element pointed to by the i-th element of its mainIndex,
//		as created by the 'createIndex' method.
//		if there is no mainIndex, then it simply returns the i-th element of the Array.
//
//	search (searchValue)
//
//		searches for a value with a binary search using the index created by the 'createIndex' method
//		and returns a pointer into the Array's 'mainIndex' property. That index element itself points
//		to the first element that is equal to OR GREATER THAN the searchValue. This enables searching
//		for strings that start with a certain value instead of only searching an exact value. The price
//		is that after invoking the 'search' method another comparison check is needed.
//		if 'createIndex' was called with a userCompareFunction, then it will also be used by 'search',
//		else the native comparison operators are used.
//		Example:
//				A = ["monkey","dollars","money","euros","monetary"]
//				A.createIndex()
//
//				S = "mon"	// the search value
//				i = A.search(S)
//				L = A.mainIndex.length
//				for (; i < L && A.get(i).indexOf(S) == 0; i++)
//				{	WScript.Echo(A.get(i))
//				}
//
//		this will write "monetary", "money", and "monkey" (in that order)
//
//	joinByIndex (separator, index)
//
//		is an equivalent of the built-in 'join' method, but it returns the result in the order given by an
//		index Array, which should be an Array just like the result of the 'createIndex' method.
//
//	Join (separator)
//
//		(mind the initial capital "J" to distinguish it from the built-in 'join' method)
//		checks if the Array has a 'mainIndex' property and if so, it assumes that it is an index as created
//		by the 'createIndex' method. It will then join the Array elements to a String in the order given by
//		that index. If there is no 'mainIndex' property then it reverts to the built-in 'join' method.
//
//	toStringByIndex (index)
//
//		is an equivalent for the 'toString' method. it does a joinByIndex using a comma separator.
//
//	toString ()
//
//		this method REPLACES the built-in 'toString' method.
//		it uses the 'Join' method, so it will implicitly use the mainIndex property if that is defined.
//
// 'toString' and 'toStringByIndex' have an extra functionality: they enclose the result in brackets ("[" and "]").
// Especially for nested Arrays these brackets improve readability (at least to my opinion).
// You can disable this behaviour by defining a 'noStringBrackets' property in the CONSTRUCTOR of the Array Object
// itself and setting that to the boolean value 'true' (e.g. the code 'Array.noStringBrackets = true' will disable
// the brackets for all Arrays). Please not that this is GLOBAL for all Arrays (it's GLOBAL just because of this
// handling of nested Arrays - I assume you want it for ALL Arrays or for none).
//
// Example 1:
//
//	{include this script}
//	A = [3,1,5,2,7,8,6,4]
//	document.write (A)			// this will write: "[3,1,5,2,7,8,6,4]"
//	A.createIndex()
//	document.write (A)			// this will write: "[1,2,3,4,5,6,7,8]"
//	Array.noStringBrackets = true
//	document.write (A)			// this will write: "1,2,3,4,5,6,7,8"
//
// Example 2:
//
//	{DO NOT include THIS script in this example - default behaviour of built-in methods}
//	A = [[1,2],[3,4]]		// define a nested Array (a matrix)
//	document.write (A)		// this will write: "1,2,3,4"
//	
// Example 3:
//
//	{now DO include this script}
//	A = [[1,2],[3,4]]		// define a nested Array (a matrix)
//	document.write (A)		// this will write: "[[1,2],[3,4]]"
//	Array.noStringBrackets = true
//	document.write (A)		// this will write: "1,2,3,4"
//
// ====================================================================================================================
// Extensive description of createIndex:
// -------------------------------------
// The 'createIndex' method is a sorting algorithm that returns a sorted index of the Array.
// See also 'hr$arraysortdemo.js' for an explanation of different sorting algorithms.
// Comparing is done using the native "less than or equal to" comparison operator ("<=") on
// the unmodified and uninterpreted Array elements, so Arrays containing Numbers will automatically
// be sorted numerically and Arrays containing Strings will be sorted alphabetically (the JavaScript
// built-in sort method of the Array Object always sorts alphabetically by the toString() value of
// the elements, yielding incorrect results when sorting Numbers, e.g. 1, 11, 2, 21, 3, 31).
//
// If the Array to be sorted contains elements of different data types then:
//	A) you are a bad programmer!
//	B) YOU ARE A BAD PROGRAMMER!
//	C) you should not make any assumptions about the result.
//
// NOTE:
//	If the Array to be sorted contains Numbers, then none of these should be NaN ('Not a Number').
//	If it contains NaN values then the result will be unpredictable,
//	since NaN is neither [less than or equal to] nor [greater than] a real Number.
//	(e.g. 'NaN <= 1' is 'false', '1 <= NaN' is 'false', and 'NaN <= NaN' is 'false').
//	If you need to sort an Array of Numbers that may be NaN, then you can use the 'createIndexNaN(mode)'
//	method, which is the same algorithm with in-line NaN handling.
//
// THIS sorting algorithm is EXTREMELY EFFICIENT, and MUCH better than the built-in sort method of the Array Object.
// (I've only tested it in the Microsoft Windows Script Host). However, the latter performs faster since it runs
// in native code, whilst THIS algorithm is running in JavaScript, which is an interpreted language.
// A good way of comparing the algorithms is to pass in a userCompare function that counts its own invocations. It
// appears that the built-in sort method does about twice as much compares as THIS algorithm and when sorting more
// than a few thousand records WITH a userCompareFunction then THIS algorithm runs FASTER than the built-in one.
// In fact, the only meaningful use of the built-in sort method is a raw alphabetic left-justified in-place sort
// of an Array that is not too large. For sorting Numbers correctly, you already need to provide the built-in sort
// with a userCompare function, which immediately slows it down so much that THIS one is faster for any reasonable
// amount of data to be sorted. Another test I have performed for sorting Numbers was measuring the time needed for
// numerically sorting a large Array of Numbers. It appeares that the built-in sort has quadratic behaviour, which,
// as explained in the 'hr$arraysortdemo.js' file, is a BAD sorting algorithm.
// And yet another reason why THIS algorithm is better: the built-in sort method is not stable, which means that,
// when sorting with a key that occupies only part of each line sorted, the original order of the lines with equal
// keys is not preserved. THIS algorithm however produces stable results, preserving the original order for equal
// keys.
//
// the userCompareFunction argument is optional,
// if given it should be a function that receives two arguments to be compared.
// Formally it should return a Number with the following meaning:
//   < 0 if the first argument is less    than the second
//   = 0 if the first argument is equal   to   the second
//   > 0 if the first argument is greater than the second
//
// Since the createIndex method checks only for the "less than or equal to" situation, the userCompareFunction
// does not really have to return zero for equal values and the result can be obtained using one single test for
// "less than or equal to", so it could be as simple as:
//
//	function myCompare (a,b) {return a <= b ? -1 : +1}
//
// (but instead of this example you'd better omit it and use native compare, which does just the same but much faster!)
//
// For optimal execution speed, it is usually not a good idea to use a userCompareFunction when sorting large amounts
// of data. It will be called VERY often. Since JavaScript is an interpreted language the userCompare will really
// slow down the sorting process significantly.
// If "smart" or complex comparisons must be done it is better to build another Array of Strings which contain the
// key fields on which to be sorted in such a way that simple alphabetic sorting yields the correct sequence.
// Example:
//	assume:	dataArray = an Array with a number of text lines where the first 2 positions are the sorting key
//
//	then:	for (var i = 0, keysArray = []; i < dataArray.length; keysArray[i] = dataArray[i++].slice(0,2) );
//		keysArray.createIndex()
//
//	will produce the desired index in the keysArray Object. Now you can read dataArray in the order given by
//	this index, e.g. the code:
//
//		function output(x) {do something to output x}
//
//		for (var i = 0; i < keysArray.mainIndex.length; output(dataArray[keysArray.mainIndex[i++]]) );
//
//	would output dataArray sorted by its first 2 positions (stable, i.e. for equal keys the original order
//	has been preserved).
//
// Another example might be a case-insensitive stable sort. It can be done exactly as in the example above,
// with the only difference that ".slice(0,2)" needs to be replaced with ".toUpperCase()" or ".toLowerCase()".
//
// When sorting datatypes for which the "<=" comparison operator does not work, you should also use this method
// of creating a keys Array containing String or Number representations of the data to be sorted.
//
// NOTE: I have plans to implement key handling methods in the (near) future.
// ====================================================================================================================
// Technical note:
// For performance reasons, the availability check for the userCompareFunction is done only once and the actual sorting
// algorithm is coded twice in the if-then-else structure. Both blocks are basically identical, the only difference is
// the native compare versus the invocation of userCompareFunction. Since the algorithm is good it will not need any
// maintenance, but IF it is edited for some reason then both blocks must of course be kept equal.
// Here it is:
// ====================================================================================================================
Array.prototype.createIndex = function createIndex (userCompareFunction)
{	var N = this.length, index = [new Array(N), new Array(N)], iDst = 0
	for (var i = 0; i < N; index[iDst][i] = i++);
	if (arguments.length > 0)
	{	for (var L = 1; L < N; L += L)
		{	for (var iSrc = iDst, iDst = 1 - iSrc, i2 = 0, i3 = 0; i2 < N; )
			{	for (var i1 = i2, L1 = Math.min(i1 + L, N),
					 i2 = L1, L2 = Math.min(i2 + L, N); i1 < L1 && i2 < L2; )
				{	if (userCompareFunction(this[index[iSrc][i1]],this[index[iSrc][i2]]) <= 0)
						index[iDst][i3++] = index[iSrc][i1++]
					else	index[iDst][i3++] = index[iSrc][i2++]
				}
				for (; i1 < L1; index[iDst][i3++] = index[iSrc][i1++] );
				for (; i2 < L2; index[iDst][i3++] = index[iSrc][i2++] );
		}	}
		this.userCompareFunction = userCompareFunction
	} else
	{	for (var L = 1; L < N; L += L)
		{	for (var iSrc = iDst, iDst = 1 - iSrc, i2 = 0, i3 = 0; i2 < N; )
			{	for (var i1 = i2, L1 = Math.min(i1 + L, N),
					 i2 = L1, L2 = Math.min(i2 + L, N); i1 < L1 && i2 < L2; )
				{	if (this[index[iSrc][i1]] <= this[index[iSrc][i2]] )
						index[iDst][i3++] = index[iSrc][i1++]
					else	index[iDst][i3++] = index[iSrc][i2++]
				}
				for (; i1 < L1; index[iDst][i3++] = index[iSrc][i1++] );
				for (; i2 < L2; index[iDst][i3++] = index[iSrc][i2++] );
		}	}
		if (this.userCompareFunction) delete this.userCompareFunction
	}
	this.mainIndex = index[iDst]
}
Array.prototype.createIndexNaN = function createIndexNaN (mode)
{	var N = this.length, index = [new Array(N), new Array(N)], iDst = 0
	for (var i = 0; i < N; index[iDst][i] = i++);
	if (mode <= 0)
	{	for (var L = 1; L < N; L += L)
		{	for (var iSrc = iDst, iDst = 1 - iSrc, i2 = 0, i3 = 0; i2 < N; )
			{	for (var i1 = i2, L1 = Math.min(i1 + L, N),
					 i2 = L1, L2 = Math.min(i2 + L, N); i1 < L1 && i2 < L2; )
				{	var a = this[index[iSrc][i1]], d = a - this[index[iSrc][i2]]
					if ( (!isNaN(d) ? d : isNaN(a) ? -1 : +1) <= 0)
						index[iDst][i3++] = index[iSrc][i1++]
					else	index[iDst][i3++] = index[iSrc][i2++]
				}
				for (; i1 < L1; index[iDst][i3++] = index[iSrc][i1++] );
				for (; i2 < L2; index[iDst][i3++] = index[iSrc][i2++] );
		}	}
		this.userCompareFunction = function (a, b) {var d = a - b; return !isNaN(d) ? d : isNaN(a) ? -1 : +1}
	} else
	{	for (var L = 1; L < N; L += L)
		{	for (var iSrc = iDst, iDst = 1 - iSrc, i2 = 0, i3 = 0; i2 < N; )
			{	for (var i1 = i2, L1 = Math.min(i1 + L, N),
					 i2 = L1, L2 = Math.min(i2 + L, N); i1 < L1 && i2 < L2; )
				{	var b = this[index[iSrc][i2]], d = this[index[iSrc][i1]] - b
					if ( (!isNaN(d) ? d : isNaN(b) ? -1 : +1) <= 0)
						index[iDst][i3++] = index[iSrc][i1++]
					else	index[iDst][i3++] = index[iSrc][i2++]
				}
				for (; i1 < L1; index[iDst][i3++] = index[iSrc][i1++] );
				for (; i2 < L2; index[iDst][i3++] = index[iSrc][i2++] );
		}	}
		this.userCompareFunction = function (a, b) {var d = a - b; return !isNaN(d) ? d : isNaN(b) ? -1 : +1}
	}
	this.mainIndex = index[iDst]
}
// ====================================================================================================================
// How does it work? Please refer to the file "hr$arraysortdemo.js" which explains a lot about sorting.
// This algorithm is a non-recursive variant of the split-sort-merge method described there.
// It starts by interpreting the Array (having length N) as N sets of 1 element.
// A set of 1 element is implicitly in the correct sorting order, so that is a good starting point for merging.
// It takes all pairs of sets and merges each pair into a new sorted subset,
// thus increasing each set size by a factor 2 and decreasing the number of sets by a factor 2.
// This process is repeated until there's only 1 set left.
// It is in the 'for (var L = 1; L < N; L += L)' loop, where 'L += L' doubles the set size at each iteration.
// i1 and i2 are the starting points of each set and L is their size.
// The outer 'for' loop handles the set size, the middle 'for' loop goes through all sets of that size,
// and the inner 'for' loop merges the pairs of sets.
// It uses 2 temporary indexes, one of them (index[iSrc]) to read the elements in the correct order for each subset,
// and the other to store the merged result (index[iDst]).
// For each pass it switches these indexes (iSrc = iDst, iDst = 1 - iSrc).
// ====================================================================================================================
// ====================================================================================================================
// the 'search' method uses the userCompareFunction that was saved in the Array Object by the 'createIndex' method
// (if one was used, otherwise it reverts to native comparison operators).
// the algorithm is a fast binary division method.
// It tests on the "greater than' condition, which is the complement of the 'less than or equal to' used by createIndex,
// so any userCompareFunction will be used correctly, even if it does not explicitly return zero for equality.
// ====================================================================================================================
Array.prototype.search = function search (searchValue)
{	var lo = -1, hi = this.mainIndex.length - 1, mi = Math.floor((lo+hi)/2)
	if (this.userCompareFunction)
	{	while (mi > lo)
		{	if (this.userCompareFunction (searchValue, this[this.mainIndex[mi]]) > 0) {lo = mi} else {hi = mi}
			mi = Math.floor((lo+hi)/2)
		};	lo++
		for (; lo < this.length && this.userCompareFunction(searchValue, this[this.mainIndex[lo]]) > 0; lo++);
	} else
	{	while (mi > lo)
		{	if (searchValue > this[this.mainIndex[mi]]) {lo = mi} else {hi = mi}
			mi = Math.floor((lo+hi)/2)
		};	lo++
		for (; lo < this.length && searchValue > this[this.mainIndex[lo]]; lo++);
	}
	return lo
}
// ====================================================================================================================
Array.prototype.get = function get (i)
{	if (this.mainIndex)	return this[this.mainIndex[i]]
	else			return this[i]
}
// ====================================================================================================================
Array.prototype.joinByIndex = function joinByIndex (separator, index)
{	var N = index.length
	var R = (N > 0 ? "" + this[index[0]] : "")
	for (var i = 1; i < N; R += separator + this[index[i++]]);
	return R
}
// ====================================================================================================================
Array.prototype.Join = function Join (separator)
{	if (this.mainIndex)	return this.joinByIndex	(separator, this.mainIndex)
	else			return this.join	(separator)
}
// ====================================================================================================================
Array.prototype.toStringByIndex = function toStringByIndex (index)
{	return	(Array.noStringBrackets ? "" : "[")	+ this.joinByIndex (",", index)
	+	(Array.noStringBrackets ? "" : "]")
}
// ====================================================================================================================
Array.prototype.toString = function toString()
{	return	(Array.noStringBrackets ? "" : "[")	+ this.Join(",")
	+	(Array.noStringBrackets ? "" : "]")
}
//	#################################################################################################
//	# NOTE												#
//	# if you like this bracketed 'toString' functionality for an Array without the need to sort	#
//	# anything, then you can simply copy the definition of the 'toString' method from above to	#
//	# your own script. You must then however replace "Join" with all-lowercase "join".		#
//	# if you don't need the 'noStringBrackets' functionality but want to force brackets always,	#
//	# then you can simply define the following 'toString' method:					#
//	#												#
//	#	Array.prototype.toString = function toString() {return "[" + this.join(",") + "]"}	#
//	#################################################################################################
//
// ====================================================================================================================
// End of file -- Copyright (c) 2003,2004  Henk Reints, http://henk-reints.nl