//// ********************************************************************
////
////  BrainJar Table Sorting
////
////	Sorts a TBODY section of any table on any column value, forward or
////  backwards, and provides CSS 'striping/grouping' updates and dynamic
////  rankings.
////
////	Adapted from www.BrainJar.com
////
////	NS updates 12/07 -
////		o Now supports secondary column sorting
////    o Much faster mergesort algorithm plus efficient value cacheing
////    o Supports multi-row CSS grouping - fixed size, or group-by-value
////


//-----------------------------------------------------------------------------
// sortTable(id, col, rev)
//
//  id     - ID of the TABLE, TBODY, THEAD or TFOOT element to be sorted.
//  col    - Index of the column to sort, 0 = first column, 1 = second column,
//           etc.
//  secCol - Secondary sort column (null = preserve existing order)
//  rev    - If true, the column is sorted in reverse (descending) order
//           initially.
//  stripe - alternate row striping.  >0 = group by this size, 0 or null =
//           no striping, -1 = stripe by equal values in sort column
// rankCol - re-rank results in this column (null or <0 = omit)
//-----------------------------------------------------------------------------

function sortTable(id, col, secCol, rev, stripe, rankCol) {

  // Get the table or table section to sort.
  var tblEl = document.getElementById(id);

	// change the cursor since this can take a while for big tables
	if (document.documentElement) {
		tblEl.cursorSave = document.documentElement.style.cursor;
		document.documentElement.style.cursor = "wait";
	} else {
		tblEl.cursorSave = document.body.style.cursor;
		document.body.style.cursor = "wait";
	}

	// dispatch to sortTable1() for the heavy lifting
	setTimeout("sortTable1('" + id + "', " + col + ", " + secCol + ", "
	                          + rev + ", " + stripe + ", " + rankCol + ");", 0);
	return false;
}


// Picks up where sortTable() left off....
// Do not call this function directly if you want the screen to update
//
function sortTable1(id, col, secCol, rev, stripe, rankCol) {

  // Get the table or table section to sort.
  var tblEl = document.getElementById(id);

  // The first time this function is called for a given table, set up an
  // array of reverse sort flags, and mark each row with an initial
  // sequence # (for tertiary tiebreaking)
  //
  if (tblEl.reverseSort == null) {
    tblEl.reverseSort = new Array();
    for (var i = 0; i < tblEl.rows.length; i++) {
    	tblEl.rows[i].initOrdinal = i;
    }
    tblEl.lastColumn = -1;
  }

  // If this column has not been sorted before, set the initial sort direction.
  if (tblEl.reverseSort[col] == null)
    tblEl.reverseSort[col] = rev;

  // If this column was the last one sorted, reverse its sort direction.
  if (col == tblEl.lastColumn)
    tblEl.reverseSort[col] = !tblEl.reverseSort[col];

  // Remember this column as the last one sorted.
  var prevCol = tblEl.lastColumn;
  tblEl.lastColumn = col;

  // Set the table display style to "none".  This is a requirement for NN6 and
  // below.
  //
  var oldDsply = tblEl.style.display;
  tblEl.style.display = "none";

	// do the sort
	mergesort(tblEl, 0, tblEl.rows.length-1, col, secCol);
//	selectionsort(tblEl, 0, tblEl.rows.length-1, col, secCol);

  // Make it look pretty.
  if (stripe && stripe != 0) {
  	makePretty(tblEl, col, prevCol, stripe);
  }

  // Set rankings.
  if (rankCol >= 0) {
	  setRanks(tblEl, col, rev, rankCol);
	}

  // Restore the table's display style.
  tblEl.style.display = oldDsply;
	if (document.documentElement) {
		document.documentElement.style.cursor = tblEl.cursorSave;
	} else {
		document.body.style.cursor = tblEl.cursorSave;
	}


  return false;
}


//-----------------------------------------------------------------------------
// In-Place Stable MergeSort
//-----------------------------------------------------------------------------

function mergesort(tblEl, fromIx, toIx, col, secCol) {
	var pivotIx;
	var lHead, rHead;
	var lVal, rVal, cmp, tmpElt, nextr;

	if (fromIx < 0 || toIx < 0  || fromIx >= toIx) {		// terminus
		return;
	} else {
		// partition the array and sort each side
		pivotIx = Math.floor((fromIx + toIx)/2);
		mergesort(tblEl, fromIx, pivotIx, col, secCol);
		mergesort(tblEl, pivotIx+1, toIx, col, secCol);

		// combine the sorted subarrays inline.  At every iteration we are
		// placing the element at lHead (which starts at fromIx).  The
		// left list runs from lHead to (rHead-1), inclusive; the right list
		// from rHead to toIx, inclusive.  At each comparison step, -1 means
		// choose left, 1 means choose right.
		//
		lHead = fromIx;
		rHead = pivotIx+1;

    var lRow = tblEl.rows[lHead];
    var rRow = tblEl.rows[rHead];
		while (lHead < toIx) {
			// which list are we choosing the value from?
			if (lHead >= rHead) {			// left list is empty
				return;
			} else if (rHead > toIx) {		// right list is empty
				return;
			} else {
	      cmp = compareRows(lRow, rRow, col, secCol, tblEl.reverseSort[col]);
      }

      // rValue selection : move it to head of list, increment rHead & lHead
      // lValue selection : already in the correct spot, just increment lHead
      if (cmp > 0) {
//     		nextr = rRow.nextSibling; bad in Firefox
				nextr = tblEl.rows[rHead+1];
				tmpElt = tblEl.removeChild(rRow);
				tblEl.insertBefore(tmpElt, lRow);
				rRow = nextr;
				rHead++;
				lHead++;
			} else {
//				lRow = lRow.nextSibling; bad in Firefox
				lRow = tblEl.rows[lHead+1];
				lHead++;
			}
		}	// end while

	} // if non-terminus
}



//-----------------------------------------------------------------------------
// In-Place Selection Sort
//-----------------------------------------------------------------------------

function selectionsort(tblEl, fromIx, toIx, col, secCol) {
  var i, j, lRow, rRow, minIx;
  var minVal, testVal;

	// nothing to do?

	if (fromIx < 0 || toIx < 0  || fromIx >= toIx) {
		return;
	}

	for (i=fromIx; i < toIx; i++) {
		// assume to start that the first element is indeed the lowest
		minIx = i;
		lRow = tblEl.rows[i];
		minVal = getTextValue(lRow.cells[col]);

    // Search the rows that follow the current one for a smaller value.
    for (j = i + 1; j <= toIx; j++) {
    	rRow = tblEl.rows[j];
      testVal = getTextValue(rRow.cells[col]);
			cmp = compareValues(getTextValue(lRow.cells[col]),
													getTextValue(rRow.cells[col]));
			// in the event of a tie: if a secondary column is supplied, use
			// that followed by the original ordering.  Otherwise, stable sort.
			if (cmp == 0) {
				if (secCol != null && secCol >= 0) {		// go secondary & tertiary
					if (col != secCol) {	// go right to tertiary in this case
						cmp = compareValues(getTextValue(lRow.cells[secCol]),
																getTextValue(rRow.cells[secCol]));
					}
					if (cmp == 0) {	// tertiary step is original order; guarantees uniqueness
						cmp = lRow.initOrdinal - rRow.initOrdinal;
					}
				} else {	// no secondary column, choose the left value (stable sort)
					cmp = -1;
				}
			}
			// flip-flop the value if we're doing a reverse sort
			if (tblEl.reverseSort[col]) {
				cmp = -cmp;
			}

      // If this row has a smaller value than the current minimum, remember its
      // position and update the current minimum value.
      if (cmp > 0) {
        minIdx = j;
        minVal = testVal;
      }
    }

		// By now, we have the row with the smallest value. Remove it from the
		// table and insert it before the current row.
		if (minIdx > i) {
			tmpEl = tblEl.removeChild(tblEl.rows[minIdx]);
			tblEl.insertBefore(tmpEl, tblEl.rows[i]);
		}
	}

}



//-----------------------------------------------------------------------------
// Functions to get and compare values during a sort.
//-----------------------------------------------------------------------------

// This code is necessary for browsers that don't reflect the DOM constants
// (like IE).
if (document.ELEMENT_NODE == null) {
  document.ELEMENT_NODE = 1;
  document.TEXT_NODE = 3;
}


function getTextValue(el) {
  var i;
  var s;

	if (el.CACHED_TEXT != null) {		// have we calculated this node's TV yet?
		return el.CACHED_TEXT;
	}

  // Find and concatenate the values of all text nodes contained within the
  // element.
  s = "";
  for (i = 0; i < el.childNodes.length; i++) {
    if (el.childNodes[i].nodeType == document.TEXT_NODE)
      s += el.childNodes[i].nodeValue;
    else if (el.childNodes[i].nodeType == document.ELEMENT_NODE &&
             el.childNodes[i].tagName == "BR")
      s += " ";
    else
      // Use recursion to get text within sub-elements.
      s += getTextValue(el.childNodes[i]);
  }

	el.CACHED_TEXT = normalizeString(s);
	return el.CACHED_TEXT;

}


function compareRows(lRow, rRow, col, secCol, rev) {
		var cmp;

		// primary sort
		cmp = compareValues(getTextValue(lRow.cells[col]),
												getTextValue(rRow.cells[col]));

		// in the event of a tie: if a secondary column is supplied, use
		// that followed by the original ordering.  Otherwise, stable sort.
		if (cmp == 0) {
			if (secCol != null && secCol >= 0) {		// go secondary & tertiary
				if (col != secCol) {	// go right to tertiary in this case
					cmp = compareValues(getTextValue(lRow.cells[secCol]),
															getTextValue(rRow.cells[secCol]));
				}
				if (cmp == 0) {	// tertiary step is original order; guarantees uniqueness
					cmp = lRow.initOrdinal - rRow.initOrdinal;
				}
			} else {	// no secondary column, choose the left value (stable sort)
				cmp = -1;
			}
		}
		// flip-flop the value if we're doing a reverse sort
		if (rev) {
			cmp = -cmp;
		}

		return cmp;
}



function compareValues(v1, v2) {
  var f1, f2;

  // If the values are numeric, convert them to floats.
  // NS - Numbers always sort before non-numbers.
  f1 = parseFloat(v1);
  f2 = parseFloat(v2);
  if (isNaN(f1) && !isNaN(f2)) {
  	return -1;
  } else if (!isNaN(f1) && isNaN(f2)) {
  	return 1;
  } else if (!isNaN(f1) && !isNaN(f2)) {
  	return f1 - f2;
  }

  // Both are nonnumeric.  Return 1 if v1 is 'greater', -1 if v2.
  if (v1 == v2)
    return 0;
  if (v1 > v2)
    return 1
  return -1;
}


// Regular expressions for normalizing white space.
var whtSpEnds = new RegExp("^\\s*|\\s*$", "g");
var whtSpMult = new RegExp("\\s\\s+", "g");


function normalizeString(s) {
  s = s.replace(whtSpMult, " ");  // Collapse any multiple whites space.
  s = s.replace(whtSpEnds, "");   // Remove leading or trailing white space.
  return s;
}



//-----------------------------------------------------------------------------
// Functions to update the table appearance after a sort.
//-----------------------------------------------------------------------------

// Style class names.
var rowClsNm = "alternateRow";
var colClsNm = "sortedColumn";

// Regular expressions for setting class names.
var rowTest = new RegExp(rowClsNm, "gi");
var colTest = new RegExp(colClsNm + "\w*", "gi");


/* striping: >0=fixed-size groups, 0=none, <0=group by value */
function makePretty(tblEl, col, prevCol, striping) {
  var i, j;
  var rowEl, cellEl;
  var rowClass, cellClass, rowCells;
  var grpSize;
  var curVal, lastVal, lastStriped;

	if (!striping || striping == 0)
		return;

  // Set style classes on each row to alternate their appearance.
  // NS - added striping options
  lastVal = null;
  lastStriped = true;
  for (rowEl = tblEl.firstChild, i=-1;
       rowEl != null;
       rowEl = rowEl.nextSibling) {
    if (typeof rowEl.className != "undefined") {
			i++;
			rowClass = rowEl.className.replace(rowTest, "");

			// fixed-size grouping
			if (striping > 0) {
				grpSize = (i - (i % striping)) / striping;  // add a div operator to JS already!
				if (grpSize % 2 != 0) {
					rowClass += " " + rowClsNm;
				}
			}
			// value-dependent grouping
			else {
				curVal = getTextValue(rowEl.cells[col]);
				if (lastVal == null || compareValues(curVal, lastVal) != 0) {
					lastStriped = !lastStriped;
				}
				if (lastStriped) {
					rowClass += " " + rowClsNm;
				}
				lastVal = curVal;
			}

			rowClass = normalizeString(rowClass);
			if (rowEl.className != rowClass) {
				rowEl.className = rowClass;
			}

			// Set style classes on each column to
			// highlight the one that was sorted.
			rowCells = rowEl.cells;
			for (j = col; j >= 0; j = ((j==prevCol) ? -1 : prevCol) ) {
				cellEl = rowCells[j];
				cellClass = cellEl.className.replace(colTest, "");
				if (j == col)
					cellClass += " " + colClsNm;
				cellClass = normalizeString(cellClass)
				if (cellEl.className != cellClass) {
						cellEl.className = cellClass;
				}
			}
		}
  }

  // Find the table header and highlight the column that was sorted.
  var el = tblEl.parentNode.tHead;
  rowEl = el.rows[el.rows.length - 1];
  // Set style classes for each column as above.
  for (i = 0; i < rowEl.cells.length; i++) {
    cellEl = rowEl.cells[i];
    cellEl.className = cellEl.className.replace(colTest, "");
    // Highlight the header of the sorted column.
    if (i == col) {
      cellEl.className += " " + colClsNm + " "
                       +  colClsNm + (tblEl.reverseSort[col] ? "Down" : "Up");
		}
    cellEl.className = normalizeString(cellEl.className);
  }
}


function setRanks(tblEl, col, rev, rankCol) {

  // Determine whether to start at the top row of the table and go down or
  // at the bottom row and work up. This is based on the current sort
  // direction of the column and its reversed flag.

  var i    = 0;
  var incr = 1;

  if (col == rankCol) {
  	return;
  }
  if (tblEl.reverseSort[col])
    rev = !rev;
  if (rev) {
    incr = -1;
    i = tblEl.rows.length - 1;
  }

  // Now go through each row in that direction and assign it a rank by
  // counting 1, 2, 3...

  var count   = 1;
  var rank    = count;
  var curVal;
  var lastVal = null;

  while (i >= 0 && i < tblEl.rows.length) {

    // Get the value of the sort column in this row.
    curVal = getTextValue(tblEl.rows[i].cells[col]);

    // On rows after the first, compare the sort value of this row to the
    // previous one. If they differ, update the rank to match the current row
    // count. (If they are the same, this row will get the same rank as the
    // previous one.)
    if (lastVal != null && compareValues(curVal, lastVal) != 0)
        rank = count;
    // Set the rank for this row.
    tblEl.rows[i].rank = rank;

    // Save the sort value of the current row for the next time around and bump
    // the row counter and index.
    lastVal = curVal;
    count++;
    i += incr;
  }

  // Now go through each row (from top to bottom) and display its rank. Note
  // that when two or more rows are tied, the rank is shown on the first of
  // those rows only.

  var rowEl, cellEl;
  var lastRank = 0;

  // Go through the rows from top to bottom.
  for (i = 0; i < tblEl.rows.length; i++) {
    rowEl = tblEl.rows[i];
    cellEl = rowEl.cells[rankCol];
    // Delete anything currently in the rank column.
    while (cellEl.lastChild != null)
      cellEl.removeChild(cellEl.lastChild);
    // If this row's rank is different from the previous one, Insert a new text
    // node with that rank.
    if (rowEl.rank != lastRank) {
      cellEl.appendChild(document.createTextNode(rowEl.rank));
      lastRank = rowEl.rank;
    }
  }
}