/*
 * ArrayEx JavaScript 数组功能扩展函数库, 包含排列组合功能
 *
 * Copyright (c) 2007 Zhiwei Ou (ouzhiwei@gmail.com)
 * licensed under the GPL licenses.
 *
 * Reference：
 *  zArray by Nicholas C. Zakas, http://www.nczonline.net/
 *
 * $Date: 2007-12-14 $
 * $Rev: $
 */

/**
 * 数组克隆（复制）
 * @return 数组的拷贝
 */
Array.prototype.clone = function () {
    return this.concat();
};

/**
 * 判断数组是否包含指定的元素(值)
 * @param vItem 元素(值)
 * @return True/False
 */
Array.prototype.contains = function (vItem) {
    return this.indexOf(vItem)>-1;
};

/**
 * 在数组末尾追加元素，可一次追加多个
 */
Array.prototype.append = function () {
    for (var i=0; i < arguments.length; i++) {
        this[this.length] = arguments[i];
    }
};

/**
 * 删除指定位置的数组元素
 * @param iIndex 元素位置(索引)
 * @return 删除元素后的数组
 */
Array.prototype.removeAt = function (iIndex) {
    if (iIndex == 0) {
        var aNew = this.slice(1);
 	   	return aNew;
    } else if (iIndex > 0 && iIndex < this.length) {
        this.splice(iIndex, 1);
 	   	return this;
    }
};

/**
 * 删除指定值的数组元素
 * @param vItem 欲删除的元素(值)
 * @return 被删除的元素(值)
 */
Array.prototype.remove = function (vItem) {
    return this.removeAt(this.indexOf(vItem));    
};

/**
 * 插入数组元素(值)到指定位置
 * @param iIndex 指定位置(索引)
 * @param vItem 欲插入的元素(值)
 */
Array.prototype.insertAt = function (iIndex, vItem) {
    this.splice(iIndex, 0, vItem);
    return this;
};

/**
 * 插入数组元素(值)到指定元素之前
 * @param vItem 欲插入的元素(值)
 * @param vBeforeItem 指定元素(值)
 */
Array.prototype.insertBefore = function (vBeforeItem, vItem) {
    this.insertAt(this.indexOf(vBeforeItem), vItem);
};


/**
 * 交换指定位置的数组元素
 * @param iIndex1 元素位置(索引)1
 * @param iIndex2 元素位置(索引)2
 * @return 交换元素后的数组
 */
Array.prototype.swap = function (iIndex1, iIndex2) {
    var vItem1 = this[iIndex1];
    var vItem2 = this[iIndex2];
	this[iIndex1]=vItem2;
    this[iIndex2]=vItem1;
    return this;
};

/**
 * 按指定的顺序数组重新排列
 */
Array.prototype.reOrder = function (aOrder) {
	var aClone = this.clone();
    for (var i=0; i < aOrder.length; i++) {
        this[aOrder[i]] = aClone[i];
    }
    return this;
};

/**
 * 按索引数组取得其中一部分
 */
Array.prototype.getPart = function ( aIndex ) {
	var aPart = [];
    for (var i=0; i < aIndex.length; i++) {
        aPart.push(this[aIndex[i]]);
    }
    return aPart;
};

/**
 * 取得 0 到 iLen 的所有排列顺序
 */
function getOrders( iLen ) {
	var aResult = [];
	var aNum = [];
	var aNumFlag = [];
	var i, j;
 	for(i = 0; i < iLen; i++) {
 		aNum[i] = i,
 		aNumFlag[i] = 1;
 	}
	
	for(;;){
		aResult.push(aNum.clone());
		aNumFlag[aNum[iLen-1]] = 0;
		for(i = iLen - 2; i>=0; i--){
			aNumFlag[aNum[i]] = 0;
			if(aNum[i] < aNum[i+1]) {
				break;
			}
		}
  		if( i < 0) {
  			break;
  		}

		for(j = aNum[i] + 1; j < iLen; j++){
			if(!aNumFlag[j]) {
				break;
			}
		}

		aNumFlag[j] = 1;
		aNum[i] = j;
		for(j=0, i++; i < iLen; j++) {
			if(!aNumFlag[j]) {
				aNum[i++] = j;
				aNumFlag[j] = 1;
			}
		}
	}
	return aResult;
}

/**
 * 生成数组的全排列
 * 方法: 先生成数组长度以下的所有顺序, 然后根据顺序数组重排原数组
 */
function arrayInAllOrder( aData ) { 
    var aResult = []; 
    var aOrders = getOrders(aData.length);
	var aOrder = aOrders.shift();
	while(aOrder) {
		aResult.push(aData.clone().reOrder(aOrder));
		aOrder = aOrders.shift();
	}
    return aResult;
}

/**
 * 插入递归排序法
 */
function getAllOrderByInsert(aData, aOrder) {
	if(!aOrder) {
		aOrder = [[aData[0]]];
	}
	var iLen = aOrder[0].length;
	if(iLen == aData.length) {
		return aOrder;
	}
	var aNewOrder = [];
	var vInsert = aData[iLen];
	for(var i = 0; i < aOrder.length; i++) {
		var aOld = aOrder[i];
		for(var j = 0; j <= aOrder[i].length; j++) {
			var aNew = aOld.clone().insertAt(j, vInsert);
			aNewOrder.push(aNew);
		}
	}
	return getAllOrderByInsert(aData, aNewOrder);
}

/**
 * 得到从 m 元素中取 n 元素的所有组合
 * 结果为[0,1...]形式的数组, 1表示选中，0表示不选
 */
function getCombFlags(m, n) {
    if(n == null || n < 1) {
        return [];
    }

    var aResult = [];
    var aFlag = [];
    for (i=0; i<m; i++) {
        aFlag[i] = (i < n) ? 1 : 0;
    }

	aResult.push(aFlag.clone());
	var bNext = true;
    while (bNext) {
    	var iCnt1 = 0;
	    for (var i = 0; i < m - 1; i++) {
			if (aFlag[i] == 1) {
				if(aFlag[i+1] == 0) {
					for(j = 0; j < i; j++) {
						aFlag[j] =  (j < iCnt1) ? 1 : 0;
					}
					aFlag[i] = 0;
					aFlag[i+1] = 1;
					var aTmp = aFlag.clone();
					aResult.push(aTmp);
					if(aTmp.slice(-n).join("").indexOf('0') == -1) {
						bNext = false;
					}
					break;
				}
				iCnt1++;
			}
		}
	}
    return aResult;
} 

/**
 * 从数组中生成指定长度的组合
 * 方法: 先生成[0,1...]形式的数组, 然后根据0,1从原数组取元素，得到组合数组
 */
function combInArray( aData, n) {
	if(n > aData.length) {
		return [];
	}
	
	var aResult = [];
	var aaFlags = getCombFlags(aData.length, n);
	var aFlag = aaFlags.shift();
	while(aFlag) {
		var aComb = [];
		for(var i = 0; i < aData.length; i++) {
			if(aFlag[i] == 1) {
				aComb.push(aData[i]);
			}
		}
		aResult.push(aComb);
		aFlag = aaFlags.shift();
	}
	
	return aResult;
}

/**
 * 取得可重复组合的下一个顺序数组(n进制算法)
 */
function getNextIndexArray(aIndex, max) {
	for(var i = 0; i < aIndex.length; i++) {
		if(aIndex[i] < max) {
			aIndex[i] += 1;
			return aIndex;
		} else {
			for(var j = i+1; j < aIndex.length; j++) {
				if(aIndex[j] < max) {
					aIndex[j] += 1; 
					for(var k=j-1; k>=0; k--) {
						aIndex[k] = 0; 
					}
					return aIndex;
				}
			}
		}
	}
	return null;
}

/**
 * 从数组中生成指定长度的可重复组合(aaa,bbb,aab ...)
 */
function combInArrayDup(aData, n) {
	var aResult = [];

	var aIndex = [];
	for(var i = 0; i < n; i++) {
		aIndex[i] = 0;
	}
	var iMax = aData.length - 1;
	for(;;) {
		if(aIndex == null) {
			break;
		}
		aResult.push(aData.getPart(aIndex));
		aIndex = getNextIndexArray(aIndex, iMax);
	}
	return aResult;
}


///**
// * 十进制数字转二进制字符串
// */
//function dec2bin(x, len) {
//	if (x < 1) {
//		bin = "";
//	} else {
//		bin = dec2bin((x - (x % 2)) / 2) + x % 2;
//	}
//	left0 = '';
//	for(var i=0; i<(len -bin.length); i++) {
//		left0 += '0';
//	}
//	return left0 + bin;
//}
//
///**
// * 二进制字符串转十进制数字
// */
//function bin2dec(bin) {
//	var j = 1;
//	var dec = 0;
//	for (var i = bin.length - 1; i >= 0; i--) {
//		dec += (bin.charAt(i) == "1" ? 1 : 0) * j;
//		j *= 2;
//	}
//	return dec;
//}
//
///**
// * 生成指定区间的所有二进制数
// */
//function getBinStrArray(strMin, strMax) {
//	var aBinStr = [];
//	var len = strMax.length;
//	for(var x = bin2dec(strMin); x <= bin2dec(strMax); x++) {
//		aBinStr.push(dec2bin(x, len));
//	}
//	return aBinStr;
//};
///**
// * n进制数组转十进制（用于调试）
// */
//function toDec(arr, n) {
//	var iRet = 0;
//	for(var i = 0; i < arr.length; i++) {
//		iRet += arr[i] * Math.pow(n,i);
//	}
//	return iRet;
//}