package flare.util {

	/**
	 * Utility class for sorting and creating sorting functions. This class
	 * provides a static <code>$()</code> method for creating sorting
	 * comparison functions from sort criteria. Instances of this class can be
	 * used to encapsulate a set of sort criteria and retrieve a corresponding
	 * sorting function.
	 * 
	 * <p>Sort criteria are generally expressed as an array of property names
	 * to sort on. These properties are accessed by sorting functions using the
	 * <code>Property</code> class. Sort criteria are expressed as an
	 * array of property names to sort on. These properties are accessed
	 * by sorting functions using the <code>Property</code> class.
	 * The default is to sort in ascending order. If the field name
	 * includes a "-" (negative sign) prefix, that variable will instead
	 * be sorted in descending order.
	 * </p>
	 */
	public class Sort {

		/** Prefix indicating an ascending sort order. */
		public static const ASC : Number = '+'.charCodeAt(0);
		/** Prefix indicating a descending sort order. */
		public static const DSC : Number = '-'.charCodeAt(0);
		private var _comp : Function;
		private var _crit : Array;

		/** Gets the sorting comparison function for this Sort instance. */
		public function get comparator() : Function { 
			return _comp; 
		}

		/** The sorting criteria. Sort criteria are expressed as an
		 *  array of property names to sort on. These properties are accessed
		 *  by sorting functions using the <code>Property</code> class.
		 *  The default is to sort in ascending order. If the field name
		 *  includes a "-" (negative sign) prefix, that variable will instead
		 *  be sorted in descending order. */
		public function get criteria() : Array { 
			return Arrays.copy(_crit); 
		}

		public function set criteria(crit : *) : void {
			if (crit is String) {
				_crit = [crit];
			} else if (crit is Array) {
				_crit = crit;
			} else if (crit is Vector.<Object>) {
				_crit = Vectors.copyToArray(crit);
			} else {
				throw new ArgumentError("Invalid Sort specification type. " + "Input must be either a String or Array");
			}
			_comp = $(_crit);
		}

		/**
		 * Creates a new Sort instance to encapsulate sorting criteria.
		 * @param crit the sorting criteria. Sort criteria are expressed as an
		 *  array of property names to sort on. These properties are accessed
		 *  by sorting functions using the <code>Property</code> class.
		 *  The default is to sort in ascending order. If the field name
		 *  includes a "-" (negative sign) prefix, that variable will instead
		 *  be sorted in descending order.
		 */
		public function Sort(crit : *) {
			this.criteria = crit;
		}

		/**
		 * Sorts the input array according to the sort criteria.
		 * @param list an array to sort
		 */
		public function sort(list : Vector.<Object>) : void {
			mergeSort(list, comparator, 0, list.length - 1);
		}

		// --------------------------------------------------------------------
		// Static Methods
		
		/**
		 * Default comparator function that compares two values based on blind
		 *  application of the less-than and greater-than operators.
		 * @param a the first value to compare
		 * @param b the second value to compare
		 * @return -1 if a < b, 1 if a > b, 0 otherwise.
		 */
		public static function defaultComparator(a : *, b : *) : int {
			return a > b ? 1 : a < b ? -1 : 0;
		}

		private static function getComparator(cmp : *) : Function {
			var c : Function;
			if (cmp is Function) {
				c = cmp as Function;
			} else if (cmp is Array) {
				c = $(cmp as Array);
			} else if (cmp == null) {
				c = defaultComparator;
			} else {
				throw new ArgumentError("Unknown parameter type: " + cmp);	
			}
			return c;
		}

		/**
		 * Creates a comparator function using the specification given
		 * by the input arguments. The resulting sorting function can be used
		 * to sort objects based on their properties.
		 * @param a A multi-parameter list or a single array containing a set
		 * of data field names to sort on, in priority order. The default is
		 * to sort in ascending order. If the field name includes a "-"
		 * (negative sign) prefix, that variable will instead be sorted in
		 * descending order.
		 * @return a comparison function for use in sorting objects.
		 */
		public static function $(...a) : Function {
			var names : Vector.<Object>;
			if (a && a.length > 0) {
				if(a[0] is Array) names = Vectors.copyFromArray(a[0]);
				else if(a[0] is Vector.<Object>) names = (a[0] as Vector.<Object>);
				else names = Vectors.copyFromArray(a);
			}
			if (names == null || names.length < 1)
				throw new ArgumentError("Bad input.");

			if (names.length == 1) {
				return sortOn(names[0] as String);
			} else {
				var sorts : Vector.<Object> = new Vector.<Object>();
				for each (var field:String in names) {
					sorts.push(sortOn(field));
				}
				return multisort(sorts);
			}
		}

		private static function multisort(f : Vector.<Object>) : Function {
			return function(a : Object, b : Object):int {
				var c : int;
				for (var i : uint = 0;i < f.length; ++i) {
					if ((c = f[i](a, b)) != 0) return c;
				}
				return 0;
			}
		}

		private static function sortOn(field : String) : Function {
			var c : Number = field.charCodeAt(0);
			var asc : Boolean = (c == ASC || c != DSC);
			if (c == ASC || c == DSC) field = field.substring(1);
			var p : Property = Property.$(field);
			return function(a : Object, b : Object):int {
				var da : * = p.getValue(a);
				var db : * = p.getValue(b);
				return (asc ? 1 : -1) * (da > db ? 1 : da < db ? -1 : 0);
			}
		}

		// --------------------------------------------------------------------
		private static const SORT_THRESHOLD : int = 16;

		private static function insertionSort(a : Vector.<Object>, cmp : Function, p : int, r : int) : void {
			var i : int, j : int, key : Object;
			for (j = p + 1;j <= r; ++j) {
				key = a[j];
				i = j - 1;
				while (i >= p && cmp(a[i], key) > 0) {
					a[i + 1] = a[i];
					i--;
				}
				a[i + 1] = key;
			}
		}

		private static function mergeSort(a : Vector.<Object>, cmp : Function, p : int, r : int) : void {
			if (p >= r) {
				return;
			}
			if (r - p + 1 < SORT_THRESHOLD) {
				insertionSort(a, cmp, p, r);
			} else {
				var q : int = (p + r) / 2;
				mergeSort(a, cmp, p, q);
				mergeSort(a, cmp, q + 1, r);
				merge(a, cmp, p, q, r);
			}
		}

		private static function merge(a : Vector.<Object>, cmp : Function, p : int, q : int, r : int) : void {
			var t : Vector.<Object> = new Vector.<Object>(r - p + 1);
			var i : int, p1 : int = p, p2 : int = q + 1;
	    	
			for (i = 0;p1 <= q && p2 <= r; ++i)
	        	t[i] = cmp(a[p2], a[p1]) > 0 ? a[p1++] : a[p2++];
			for (;p1 <= q; ++p1, ++i)
	            t[i] = a[p1];
			for (;p2 <= r; ++p2, ++i)
	            t[i] = a[p2];
			for (i = 0, p1 = p;i < t.length; ++i, ++p1)
	            a[p1] = t[i];
		}
	} // end of class Sort
}