sort.as

用于flash/flex的 as3的 2D图形图像图表的动态生成

package flare.util
{
	import flash.display.DisplayObjectContainer;
		
	/**
	 * 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 = Arrays.copy(crit as Array);
			} 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:Array):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
		{
			if (a && a.length > 0 && a[0] is Array) a = a[0];
			if (a==null || a.length < 1)
				throw new ArgumentError("Bad input.");

			if (a.length == 1) {
				return sortOn(a[0]);
			} else {
				var sorts:Array = [];
				for each (var field:String in a) {
					sorts.push(sortOn(field));
				}
				return multisort(sorts);
			}
		}
		
		private static function multisort(f:Array):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:Array, 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:Array, 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:Array, cmp:Function, p:int, q:int, r:int):void
	    {
	    	var t:Array = new Array(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
}