ArrayUtils

 

/*
 Copyright aswing.org, see the LICENCE.txt.
*/
 
package com.xxxx.utils{
	
	/**
	 * Utils functions about Array.
	 * @author iiley
	 */
	public class ArrayUtils{
		
		/**
		 * Call the operation by pass each element of the array once.
		 * <p>
		 * for example:
		 * <pre>
		 * //hide all component in vector components
		 * ArrayUtils.each( 
		 *     components,
		 *     function(c:Component){
		 *         c.setVisible(false);
		 *     });
		 * <pre>
		 * @param arr the array for each element will be operated.
		 * @param the operation function for each element
		 * @see Vector#each
		 */
		public static function each(arr:Array, operation:Function):void{
			for(var i:int=0; i<arr.length; i++){
				operation(arr[i]);
			}
		}
		
		/**
		 * Sets the size of the array. If the new size is greater than the current size, 
		 * new undefined items are added to the end of the array. If the new size is less than 
		 * the current size, all components at index newSize and greater are removed.
		 * @param arr the array to resize
		 * @param size the new size of this vector 
		 */
		public static function setSize(arr:Array, size:int):void{
			//TODO test this method
			if(size < 0) size = 0;
			if(size == arr.length){
				return;
			}
			if(size > arr.length){
				arr[size - 1] = undefined;
			}else{
				arr.splice(size);
			}
		}
		
		/**
		 * Removes the object from the array and return the index.
		 * @return the index of the object, -1 if the object is not in the array
		 */
		public static function removeFromArray(arr:Array, obj:Object):int{
			var i:int = arr.indexOf(obj);
			if (i != -1)
				arr.splice(i, 1);
			return i;
		}
		
		public static function removeAllFromArray(arr:Array, obj:Object):void{
			for(var i:int=0; i<arr.length; i++){
				if(arr[i] == obj){
					arr.splice(i, 1);
					i--;
				}
			}
		}
		
		public static function removeAllBehindSomeIndex(array:Array , index:int):void{
			if(index <= 0){
				array.splice(0);
			}
			else {
				array.splice(index + 1);
			}
		}
		
		public static function cloneArray(arr:Array):Array{
			return arr.concat();
		}
		
		public static function deepClone(a:Array):Array {
			var r:Array = new Array();
			for each (var obj:Object in a) {
				if (obj.hasOwnProperty("clone")) {
					obj = obj.clone();
				}
				r.push(obj);
			}
			return r;
		}
		
		/**
		 * 
		 * 全闭区间 [start, end] 
		 * 
		 */	
		public static function copyArrayByRange(dst:Array, src:Array, start:int, end:int):Boolean {
			if (dst == null || src == null)
				return false;
			
			var l:int = src.length;
			if (l == 0 || l <= end)
				return false;
			
			dst.splice(0);
			for (var i:int = start; i <= end; ++i) {
				dst.push(src[i]);
			}
			return true;
		}
		
		/**
		 *mix the array 
		 * @param array
		 */	
		public static function mixArray(array:Array):void{
			array.sort(function(n1:*, n2:*):Number{
				var r:Number = Math.random()*1;
				return r>0.5?1:-1;
			});
		}
		
		public static function swap(array:Array, i:int, j:int):void {
			var t:Object = array[i];
			array[i] = array[j];
			array[j] = t;
		}
		
		public static function bubbleSort(array:Array, fnCompare:Function):void {
			var c:int = array.length - 1;
			for (var i:int = 0; i < c; ++i) {
				var bSwapped:Boolean = false;
				for (var j:int = 0; j < c - i; ++j) {
					if (fnCompare(array[j + 1], array[j])) {
						swap(array, j, j + 1);
						bSwapped = true;
					}
				}
				if (!bSwapped) {
					break;
				}
			}
		}
		
		public static function quickSort(array:Array, fnCompare:Function):void {
			doQuickSort(array, fnCompare, 0, array.length - 1);
		}
		
		private static function doQuickSort(array:Array, fnCompare:Function, bottom:int, top:int):void {
			if (top > bottom) {
				var piv:int = bottom;
				var k:int = bottom + 1;
				var r:int = top;
				var pivObj:Object = array[piv];
				while (k != r /*k < r*/) {
					if (fnCompare(array[k], pivObj)) {
						++k;
					}
					else {
						swap(array, k, r--);
					}
				}
				if (fnCompare(array[k], pivObj)) {
					swap(array, k, bottom);
					doQuickSort(array, fnCompare, bottom, k - 1);
					doQuickSort(array, fnCompare, r + 1, top);
				}
				else {
					if (top - bottom > 1) {
						--k;
						swap(array, k, bottom);
						doQuickSort(array, fnCompare, bottom, k - 1);
						doQuickSort(array, fnCompare, k + 1, top);
					}
				}
			}
		}
		
		public static function selectSort(array:Array, fnCompare:Function):void {
			var l:int = array.length;
			for (var i:int = 1; i < l; ++i) {
				var iMin:int = i - 1;
				var minCh:Object = array[iMin];
				for (var j:int = i; j < l; ++j) {
					var ch:Object = array[j];
					if (fnCompare(ch, minCh)) {
						iMin = j;
						minCh = ch;
					}
				}
				if (iMin != (i - 1)) {
					swap(array, iMin, i - 1);
				}
			}
		}
		
		public static function heapSort(array:Array, fnCompare:Function):void {
			for (var i:int = array.length - 1; i > 0; --i) {
				heapTree(array, fnCompare, i, i);
			}
		}
		
		private static function heapTree(array:Array, fnCompare:Function, iRootIndex:int, iTopIndex:int):void {
			if (iRootIndex > iTopIndex) {
				return;
			}
			
			var iLeftIndex:int = 0;
			var iRightIndex:int = 1;
			if (iRootIndex < iTopIndex) {
				iLeftIndex = (iRootIndex + 1) * 2;
				iRightIndex = iLeftIndex + 1;
			}
			
			if (iLeftIndex < iTopIndex) {
				var chRoot:Object = array[iRootIndex];
				var chLeft:Object = array[iLeftIndex];
				if (iRightIndex < iTopIndex) {
					var chRight:Object = array[iRightIndex];
					if (fnCompare(chRight, chLeft)) {
						if (fnCompare(chRoot, chLeft)) {
							swap(array, iLeftIndex, iRootIndex);
						}
					}
					else {
						if (fnCompare(chRoot, chRight)) {
							swap(array, iRightIndex, iRootIndex);
						}
					}
					
					heapTree(array, fnCompare, iLeftIndex, iTopIndex);
					heapTree(array, fnCompare, iRightIndex, iTopIndex);
					
					chRoot = array[iRootIndex];
					chLeft = array[iLeftIndex];
					chRight = array[iRightIndex];
					if (fnCompare(chRight, chLeft)) {
						if (fnCompare(chRoot, chLeft)) {
							swap(array, iLeftIndex, iRootIndex);
						}
					}
					else {
						if (fnCompare(chRoot, chRight)) {
							swap(array, iRightIndex, iRootIndex);
						}
					}
				}
				else {
					if (fnCompare(chRoot, chLeft)) {
						swap(array, iLeftIndex, iRootIndex);
					}
				}
			}
			else {
				
			}
		}
	}
}