// table_sorter.js.
// by Andy (2010-11-15).
// A helper that handles sortable tables through Javascript DOM manipulation.
// Requires Date.fromString() from date.js.

// newTableSorter(...)
// Creates a table sorter, which allows a table's headings to be clicked on to reorder its entries.
// Assumes that the first row is always a heading row (this assumption could changed later).
//
// For styling, 'sortable' indicates the a header can be sorted, and 'sort_ascending'/'sort_descending' can be used to show ordering markers in the style.
//
// Arguments:
//   - table: the table element to register this sorter for.
//   - exclude_last: If true, then the last row is excluded from the sort (useful for things like total bars at the bottom).
//   - column_disable: a list of CSS classes used to disable the option to sort a particular column.
//   - post_process: a post-processing event which is a function(table) { ... } called after the sort completes. This could be used to reapply zebra-striping for example.
//   - options: an object containing key-value mappings of other options. Can contain the following:
//          'aliases': an object containing a mapping from a column id to another column id to sort by instead.
//                     For when disabling a sort isn't allowed, but there is no meaningful sort for the column clicked.
//          'comparators': an object containing a mapping of column id to a comparator function that can be used to sort on that column.
//                         This is for adding special sort types that couldn't be autodetected.
//                         The function is of form function(a, b) { ... }  and returns negative if a < b, positive if a > b, and 0 if a == b.
//          'reverse': an object containing a mapping of column id to its reversal flag.
//                     If a column has a "reverse" setting of true, it will be sorted in descending order on first click.
//                     Otherwise, it will be sorted ascending.
//          'initial_sort': column id of criteria to sort entries by initially.
function newTableSorter(table, exclude_last, column_disable, post_process, options)
{
	exclude_last = !!exclude_last;
	column_disable = column_disable || [];
	post_process = post_process || null;
	options = options || {};
	options.aliases = options.aliases || {};
	options.comparators = options.comparators || {};
	options.reverse = options.reverse || {};
	
	var aliases = options.aliases;
	var user_comparators = options.comparators;
	
	// Create a new sorter object.
	var sorter = {
		// The table to sort with this sorter.
		'table': $(table),
		// Whether or not to exlude the last row.
		'exclude_last': exclude_last,
		// Reversal status is inverted for a column every time it is clicked.
		// Initially empty, but populated as needed.
		'reverse': {},
		// A function to call upon sort completion.
		'post_process': post_process,
		// Heading row reference. This might be modified if it turns out that the first row does not contain any <th> elements.
		'head_row': $(table).down('tr'),
		// Don't optimize the sort unless we have at least this many rows.
		'inefficient_min_rows': 100,
		// Use an optimized sort algorithm?
		'is_really_inefficient': false,
		// The reversal status of the current sort.
		'current_sort_reverse': null,
		// Whether the sorter is actively sorting something currently, preventing multiple sorts occuring at once.
		'busy': false
	};
	
	// Returns the intersection of two arrays a ^ b, which is defined as
	// the array of all elements x that are contained by both a and b.
	// Assumes a and b have unique representation (no duplicate elements)
	var intersect = function(a, b)
	{
		var i, j;
		var result = [];
		for(i = 0; i < a.length; i++)
		{
			for(j = 0; j < b.length; j++)
			{
				if(a[i] == b[j])
				{
					result.push(a[i]);
				}
			}
		}
		return result;
	};
	
	// Instead of having magic numbers in the below function,
	// these constants representing DOM node types are defined.
	var NODE_ELEMENT = 1;
	var NODE_TEXT = 3;
	
	// Gets the innermost text of a particular element.
	// Useful for getting text inside of a <span> or <td>
	var getInnermostText = function(elem)
	{
		// textContent and innerText are non-standard but used in several browsers to get the text of a node without HTML characters.
		return elem.textContent || elem.innerText;

		// Undefined, false, 0, or '' can be returned back as-is.
		if(!elem)
		{
			return elem;
		}
	};
		
	
	var compareNumber = function(a, b)
	{
		return a - b;
	};
	
	var compareString = function(a, b)
	{
		return a.localeCompare(b);
	};
	
	var compareDate = function(a, b)
	{
		return Date.fromString(a, { 'strict': true }).getTime() - Date.fromString(b, { 'strict': true }).getTime();
	}
	
	var compareHeight = function(a, b)
	{
		var piecesA = getHeightValue(a);
		var piecesB = getHeightValue(b);
		
		// If feet are equal, then check the next piece of the height.
		if(piecesA[0] == piecesB[0])
		{
			// Has inches, return difference in inches.
			if(piecesA.length > 1 && piecesB.length > 1)
			{
				return piecesA[1] - piecesB[1];
			}
			// No inches, return equal.
			else
			{
				return 0;
			}
		}
		// Return difference in feet.
		else
		{
			return piecesA[0] - piecesB[0];
		}
	}
	
	var getHeightValue = function(s)
	{
		var result = s.match(/^(\d+)'(\d*)"?$/);
		if(result)
		{
			//alert(result);
			// Remove the full text match (we only want the captures).
			result.splice(0, 1);
			return result;
		}
		else
		{
			return false;
		}
	}
	
	var isBlank = function(s)
	{
		return s == '' || s == '-';
	};
	
	var getComparator = function(s, t)
	{
		// If both strings are numeric, or one string is numeric
		// and the other is a blank, then use numeric comparison.
		if(!isNaN(s) && !isNaN(t)
			|| !isNaN(s) && isBlank(t)
			|| isBlank(s) && !isNaN(t)
		)
		{
			return compareNumber;
		}
		// Non-numeric compare
		else
		{
			var dateA = Date.fromString(s, { 'strict': true });
			var dateB = Date.fromString(t, { 'strict': true });
			
			// Both strings are valid dates. Use date comparison.
			if(!isNaN(dateA) && !isNaN(dateB))
			{
				return compareDate;
			}
			// Both strings are valid heights.
			else if(getHeightValue(s) && getHeightValue(t))
			{
				return compareHeight;
			}
			else
			{
				return compareString;
			}
		}		
	};
	
	// Get rows out of the table's tbody.
	var getRows = function(table)
	{
		return $(table).down('tbody').getElementsBySelector('tr');
	};
	
	var sortRows = function(sorter, column_index)
	{
		if(sorter.busy)
		{
			return;
		}
		sorter.busy = true;
		document.body.style.cursor = 'wait';
		
		var tbody = $(sorter.table).down('tbody');
		
		// Remove the sort_ascending/descending class of every column.
		var head = sorter.head_row.down('th');
		do
		{
			head.removeClassName('sort_ascending');
			head.removeClassName('sort_descending');
		} while(head = head.next('th'));
		
		// Now add the ascending/descending as appropriate to the newly selected column.
		head = sorter.head_row.down('th', column_index);
		head.addClassName('sort_' + (sorter.reverse[column_index] ? 'ascending' : 'descending'));
		
		// Get the comparator for this column if one exists.
		var comparator = user_comparators[head.identify()] || null;
		
		var rows = getRows(sorter.table);
		
		// Look for the heading row in the list of table rows.
		// Remove it row from this list, because it can't be sorted.
		rows = rows.without( sorter.head_row );
		
		var last_row = null;
		if(sorter.exclude_last)
		{
			last_row = rows.pop();
		}

		if(!comparator)
		{
			var s = getInnermostText(rows.first().down('td', column_index)) || '';
			var t = getInnermostText(rows.last().down('td', column_index)) || '';
			comparator = getComparator(t, s);
		}
		
		sorter.current_sort_reverse = sorter.reverse[column_index];
		
		var column_data = {};
		var compare = function(a, b)
		{
			//var s = getInnermostText(a.down('td', column_index)).strip() || '';
			//var t = getInnermostText(b.down('td', column_index)).strip() || '';
			var s = column_data[a.identify()];
			var t = column_data[b.identify()];

			if( s.empty() || s == '-' ) {
				return 1;
			}

			if( t.empty() || t == '-' ) {
				return -1;
			}

			// First, use straight-forward data comparison.
			var result = comparator(s, t);

			// If reversed, then swap the comparison.
			if(sorter.reverse[column_index])
				result = -result;

			return result;
		};
		
		var row_index = 0;
		var extract_data = function()
		{
			var timestamp = (new Date()).getTime();
			while((new Date()).getTime() - timestamp <= 1000 && row_index < rows.length)
			{
				var row = rows[row_index++];
				var c = getInnermostText(row.down('td', column_index)) || '';
				column_data[row.identify()] = c.strip();
			}
			// Not done extracting columns out of the table yet. Use a timeout to fool IE into giving us more time.
			if(row_index < rows.length)
			{
				setTimeout(extract_data, 1);
			}
			// Otherwise, start the sort.
			else
			{
				setTimeout(function() {
						// Copy the old list so we know where to move everything.
						rows = rows.sort( compare );

						// Alternate the reversal flag for this column for the next time it is clicked.
						sorter.reverse[column_index] = !sorter.reverse[column_index];
						
						// Rearrange all rows, by reinserting them before the last row of the table.
						for(i = 0; i < rows.length; i++)
						{
							tbody.insertBefore(rows[i], last_row);
						}
						
						// Post-process the table, if a hook exists.
						if(sorter.post_process)
						{
							sorter.post_process(sorter.table);
						}
						
						setTimeout(function() {
								sorter.busy = false;
								document.body.style.cursor = 'auto';
							}
						, 1);
							
					}, 1);
			}
		};
		
		extract_data();
	};
	
	var createSortCallback = function(sorter, i)
	{
		return function()
		{
			sortRows(sorter, i);
		};
	}
	
	var registerClickEvent = function(col, sorter, i)
	{
		col.addClassName('sortable');
		col.onclick = createSortCallback(sorter, i);
	};

	// See: http://blog.vjeux.com/2009/javascript/speed-up-javascript-sort.html	
	var check_sort_tostring = function () {
		// Fill the array with 3 values
		var array = new Array(3);
		for (var i = 0; i < 3; ++i) {
			array[i] = new Object();
		  array[i].value = i-3;
		}
	 
		// Override the toString method that counts how many times it is being called
		var count = 0;
		var save = Object.prototype.toString;
		Object.prototype.toString = function () { count += 1; return String(this.value); };
	 
		// Sort
		array.sort();
		Object.prototype.toString = save;
	 
		// 3 times is good, more is bad!
		return (count == 3);
	};
	
	var check_sort_compare = function () {
		// Fill the array with 5 values
		var array = new Array(5);
		for (var i = 0; i < 5; ++i) {
			array[i] = new Object();
		  array[i].value = i-5;
		}
	 
		// Count how many times our compare function is called.
		var count = 0;
		array.sort( function( a, b ) {
			count += 1;
			return b.value - a.value;
		} );
	 
		// 8 times is good, more is bad!
		// And less than 8 indicates a fundamentally broken sort algorithm.
		return (count == 8);
	};
			
	// Use the heading columns of the first row as possible sorting criteria
	var initSorter = function()
	{
		var col = null;
		var column_data = {};

		// Clear out any whitespace.		
		var tbody = $(sorter.table).down('tbody');
		tbody.cleanWhitespace();
		// Find the first row with a heading.
		while(sorter.head_row && !(col = sorter.head_row.down('th')))
		{
			sorter.head_row = sorter.head_row.next('tr');
		}
		
		// No row found with a heading, can't initialize the sorter.
		if(!sorter.head_row)
		{
			return;
		}
	
		// Get list of rows under the table's tbody.
		var rows = getRows(table);

		// See if we need to optimize the sort.
		if( 
				(rows.length > sorter.inefficient_min_rows)
				&& (!check_sort_compare())
				&& (check_sort_tostring())
			) {
			sorter.is_really_inefficient = true;

			// We really don't have a good alternative as yet,
			// So die out rather than struggling on.
			//return false;
		}

		// Look for the heading row in the list of table rows.
		// Remove it row from this list, because it can't be sorted.
		for(i = 0; i < rows.length; i++)
		{
			if(rows[i][0] == sorter.head_row)
			{
				rows.splice(i, 1);
				break;
			}
		}
		
		if(exclude_last)
		{
			rows.pop();
		}

		var i = 0;
		do
		{
			// Record this column's index. id -> index, element.
			column_data[col.identify()] = [i, col];
			
			// Reverse for this column if its id matches one in options.reverse and is true.
			sorter.reverse[i] = options.reverse[col.identify()];
			
			// Only allow sorting if there is nothing in common between this column's class names and the column_disable list.
			if(intersect($w(col.className), column_disable).length == 0)
			{
				registerClickEvent(col, sorter, i);
			}
			i++;
		} while(col = col.next('th'));
		
		// For any column in the table with an id in aliases, (re)map its click event according to the alias found.
		for(var column_id in column_data)
		{
			if(aliases[column_id])
			{
				var from_col = column_data[column_id][1];
				var to_index = column_data[aliases[column_id]][0];
				registerClickEvent(from_col, sorter, to_index);
			}
		}
		
		if(options.initial_sort)
		{
			createSortCallback(sorter, column_data[options.initial_sort][0])();
		}
	};

	initSorter();
	return sorter;
}