/** 
 *  Custom index based on string prefix.
 * 
 *  Each key contains the a prefix of the values it contains 
 *  While entry contains the rest of the value, and a pointer to its location
 *  in the whole array. It is good for dispersing results, thus making searches faster.
 *  It's performance depends on the spread of actual items, but should suffice for
 *  a few thousand items. Performance depends on the system, too.
 *
 *  Note: Expects an 'associative array', Grouped by a key.
 *  If its value is an array, the first [0] field is used for the index key.
 *  Examples:
 *  {81273:['moshe',data,data],813214:['tzachi',data,data]} Will work
 *  {81273:'moshe',813214:'tzachi'} Will also work
 *   
 * @author Erick S <esatire at gmail dot com>
 * @version 1.2
 * 16/02/2008 - Memory use reduction, optimisations. Settled on prefix = 1
 * 13/02/2008 - Made shin1 version
 */

/** Regex for eliminating junk and numbers */ 
PrefixIndex.REGEX = /[^a-zאבגדהוזחטיכלמנסעפצקרשתןםךץ]/g

/**
 * Constructor 
 * 
 * @param items {Object};
 */
function PrefixIndex(items)
{
	// create the alphabetical index to search in the list
	this.index = this.insertMany(items);
}
/** 
 * Performs a search for multiple items with the same prefix
 * @param needle {string}
 * @param limit {int}
 * @return {array} of keys from the original associative array
 */
PrefixIndex.prototype.search = function(value,limit)
{
	var results = new Array();
	var count = 0;
	if (!value || value.length == 0) return results;
	// Format needle to be just alphabet
	var needle = value.toLowerCase().replace(PrefixIndex.REGEX,'');
	// Yes, we need quite a vew variables for this search
	var key,subKey,i,haystack,value;
	// For needles of size 1 - we return the values of all subkeys
	if (needle.length == 1)
	{
		key = needle.charCodeAt(0);
		// There is, of course, a chance that this key is empty
		if (this.index[key] === undefined) return results;
		// Include all items of this key
		haystack = this.index[key]
		for (subKey in haystack)
		{
			if (typeof(haystack[subKey]) != 'object')
			{
				results[count++] = haystack[subKey]; // The key of the original array
				if (count >= limit) return results; // Stop at LIMIT
			}
			else
			{
				for (i=0;i<haystack[subKey].length;++i)
				{
					results[count++] = haystack[subKey][i]; 
					if (count >= limit) return results;
				}
			}
		}
		return results;
	}
	// Regular search - check key and then look in subkeys
	// If needle did not contain any alphabet - try the 'other' key
	if (needle.length == 0)
	{
		needle = value; // Check full value, before taking out symbols and numbers
		key = 'other';
	}
	else // Regular search - use the first char as a key, and the rest for values
	{
		key = needle.charCodeAt(0);
	}
	// If there are no items starting with this prefix, return
	if (this.index[key] === undefined)	return results;
	haystack = this.index[key];
	var curVal=null,len = needle.length;
	for (subKey in haystack)
	{
		curVal = subKey.substr(0,len);
		// They're not sorted internally, due to the non-alphabet replacing
		if (curVal != needle) continue;
		// Right on track - return all values contained in this subkey
		if (typeof(haystack[subKey]) != 'object')
		{
			results[count++] = haystack[subKey]; // The key of the original array
			if (count >= limit) return results; // Stop at LIMIT
		}
		else
		{
			for (i=0;i<haystack[subKey].length;++i)
			{
				value = haystack[subKey][i];
				results[count++] = value;
				if (count >= limit) return results;
			}
		}
	}
	return results;
}

/**
 * New version - indexes only alphabet characters
 * 
 * The result will be a three dimensional array pointing to the original position/key.
 * The last dimension can also be an array, if there are duplicates
 * Example:
 * [a][AbRaham Molech] => 312,[d][Dharma Roland] => [192,68],[a][a] => [1,15,28,81], ...
 * 
 * @param {Object} Associative array containing keys and values ONLY (0=>'shmulik',1=>'bobby', ...)
 */
PrefixIndex.prototype.insertMany = function(items)
{
	var index = new Object(); //{length:0};
	// Regex that checks for non-alphanumeric characters
	var indexKey; // Will contain just the 2 first letters
	var value; // Will contain the value after processing 
	for (var key in items)
	{
		if (items[key] instanceof Array)
		{
			value = items[key][0].toLowerCase().replace(PrefixIndex.REGEX,'');
		}
		else
		{
			value = items[key].toLowerCase().replace(PrefixIndex.REGEX,'');
		}
		// All values that are too full of junk to be parsed will go to the 'other' index key
		if (value.length == 0)
		{
			value = (items[key] instanceof Array) ? items[key][0] : items[key];
			indexKey = 'other';
		}
		else indexKey = value.charCodeAt(0);
			
		if (index[indexKey] === undefined) { index[indexKey] = new Object; }
		if (index[indexKey][value] === undefined) index[indexKey][value] = key; 
		else // Duplicates - should be rare
		{
			// If not array - create
			if (typeof(index[indexKey][value]) != 'object') index[indexKey][value] = [index[indexKey][value]]
			// Add key to array
			index[indexKey][value].push(key);
		}
	}
	return index;
}