/*******************************************************************
* Kainaw'd Data Table
* Copyright (c)2005 CS Wagner.
* This script is free for any use.
********************************************************************
* This is a script to dynamically sort the rows of a table without
* sending a request to the server.
********************************************************************
* INSTALLATION
* Place this file in your website directory.
* Include it: <script language='javascript' src='kdt.js'></script>
********************************************************************
* USAGE
* Create a table in your webpage.
* This table MUST have <thead> and <tbody> sections, ie:
*  <table>
*    <thead><tr><th>ID</th><th>NAME</th></tr></thead>
*    <tbody>
*      <tr><td>1</td><td>Homer</td></tr>
*      <tr><td>2</td><td>Marge</td></tr>
*      <tr><td>3</td><td>Bart</td></tr>
*      <tr><td>4</td><td>Lisa</td></tr>
*      <tr><td>5</td><td>Maggie</td></tr>
*    </tbody>
*  </table>
* In the TH tags, add an onclick function:
*  <th onclick='kdt_resort(this);'>
* Every header that has this onclick will sort the table when a
* user clicks on it.  You can use that to keep the user from
* sorting by certain columns.
********************************************************************
* COMPATIBILITY
* This has been checked on:
*  Firefox 1.0
*  IE 6
*  Konqueror 3.4
* If it doesn't work on a browser, the user will still see the data,
* but will not be able to sort it.
********************************************************************
* TO DO
* I would also like to add up/down arrows to the column that has
* been sorted so you know which column is being used for the sort.
********************************************************************/

function kdt_resort(column)
{
	if(!column.sortorder)
		column.sortorder = 1;
	else
		column.sortorder*= -1;
	table = column.parentNode.parentNode.parentNode;

	kdt_quicksort(table.tBodies[0], column.cellIndex, column.sortorder, 0, table.tBodies[0].rows.length-1);
}

function kdt_quicksort(tBody, cellIndex, sortOrder, left, right)
{
	if(right > left)
	{
		var pivotIndex = left;
		var pivotNewIndex = kdt_partition(tBody, cellIndex, sortOrder, left, right, pivotIndex);
		kdt_quicksort(tBody, cellIndex, sortOrder, left, pivotNewIndex-1);
		kdt_quicksort(tBody, cellIndex, sortOrder, pivotNewIndex+1, right);
	}
}

function kdt_partition(tBody, cellIndex, sortOrder, left, right, pivotIndex)
{
	if(right <= left) return left;
	var pivotValue = tBody.rows[pivotIndex].cells[cellIndex].innerHTML;
	kdt_swap(tBody, pivotIndex, right); // Move pivot to end
	var storeIndex = left;
	for(var i=left; i<right; i++)
	{
		if(sortOrder == 1)
		{
			if(tBody.rows[i].cells[cellIndex].innerHTML < pivotValue)
			{
				kdt_swap(tBody, storeIndex, i);
				storeIndex = storeIndex + 1;
			}
		}
		else
		{
			if(tBody.rows[i].cells[cellIndex].innerHTML > pivotValue)
			{
				kdt_swap(tBody, storeIndex, i);
				storeIndex = storeIndex + 1;
			}
		}
	}
	kdt_swap(tBody, right, storeIndex); // Move pivot to its final place
	return storeIndex;
}

function kdt_swap(tBody, r1, r2)
{
	if(tBody.moveRow)
	{
		tBody.moveRow(r1, r2);
	}
	else if(tBody.replaceChild)
	{
		if(r2 == r1)
		{
			// Do Nothing.
		}
		else if(r2 > r1)
		{
			tBody.insertBefore(tBody.rows[r1], tBody.rows[r2]);
			tBody.insertBefore(tBody.rows[r2], tBody.rows[r1]);
		}
		else
		{
			tBody.insertBefore(tBody.rows[r2], tBody.rows[r1]);
			tBody.insertBefore(tBody.rows[r1], tBody.rows[r2]);
		}
	}
	else
	{
		var tmp = tBody.rows[r1];
		tBody.rows[r1] = tBody.rows[r2];
		tBody.rows[r2] = tmp;
	}
}