/* 
 * Implements a case-insensitive binary search algorithm documented here:
 * http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
 * This could be improved to extract a range, see:
 * http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary
 */
function binarySearch(strArray, str) {
	var key = str.toLowerCase();
	var low = 0;
	var high = strArray.length - 1;

	while (low <= high) {
		var mid = parseInt((low + high) / 2);
		var midVal = strArray[mid].toLowerCase();

		if (midVal < key)
			low = mid + 1;
		else if (midVal > key)
			high = mid - 1;
		else
			return mid; // key found
	}
	return -(low + 1);  // key not found.
}

/*
 * Returns a sub array of strArray
 * whose entries start with the given prefix and are wrapped as arrays.
 */
function matchPrefix(strArray, prefix, namesToCrsCodes) {
	var first = binarySearch(strArray, prefix);
	if (first < 0)
		first = -(first + 1);
	var last = binarySearch(strArray, prefix + "~");
	var matches = new Array();
	for (var i = first; i < -(last + 1); i++) {
		var crsCode = namesToCrsCodes[strArray[i]];
		//Remove * char if present. This char is used for aliases
		var indexOfAliasChar = crsCode.indexOf("*");
		var displayedCrsCode = crsCode;
		if(indexOfAliasChar != -1){
			displayedCrsCode = crsCode.substring(0,indexOfAliasChar);
		}
		matches.push(new Array(strArray[i], displayedCrsCode));
	}
	return matches;
}

/*
 * Returns an array of arrays
 * whose entries start with the given (URI-encoded) prefix.
 */
function search(prefix, names, crsCodesToNames, namesToCrsCodes) {
	if (prefix.length == 0 ){
		return new Array();
	}
    var decodedPrefix = decodeURI(prefix);
    var matches = matchPrefix(names, decodedPrefix, namesToCrsCodes);
    if (decodedPrefix.length == 3) {
    	var crs = decodedPrefix.toUpperCase();
    	var station = crsCodesToNames[crs];
    	// Don't duplicate top entry
    	if (undefined != station && (matches.length == 0 || (matches[0][1] != crs))) {
    		var crsMatch = new Array(station, crs);
    		removeItem(matches, crsMatch);
	    	matches.unshift(crsMatch);
		}
    }
	return matches;	
}


/*
 * Removes the specified item (if present) from the array
 */
 function removeItem(array, item) {
 	var itemIndex = -1;
 	for (var i = 0; i < array.length; i++){
 		if(item[0] == array[i][0] && item[1] == array[i][1]){
 			itemIndex = i;
 			break;
 		}
 	}
 	
 	if(itemIndex != -1){
 		array.splice(itemIndex,1);
 	}
 }