// Initial ideas from http://www.kryogenix.org/code/browser/sorttable/
// This version at http://www.flester.com/
// Modified by mobileAgent to 
//  1. Show different sort types, including a stable merge sort
//  2. Work with thead/tbody/tfoot type tables
//  3. Work in Safari which doesn't have rowIndex or cellIndex

var ST_USE_IMAGES = false;
var ST_SORT_TYPE = 'merge';
var ST_IGNORE_ROW_CLASS = 'sep';
var ST_IGNORE_COL_CLASS = 'nosort';
var ST_NO_ARROW = '&nbsp;<img src="images/spacer.gif" height="12" width="12"/>';
var ST_UP_ARROW = '&nbsp;<img src="images/up.gif" height="12" width="12"/>';
var ST_DN_ARROW = '&nbsp;<img src="images/down.gif" height="12" width="12"/>';


function setSortType(s) {
  if (s == 'merge' || s == 'default' || s == 'shell') {
    ST_SORT_TYPE = s;
    log('Setting sort type to ' + s);
  } else { 
    log('Invalid sort type being ignored ' + s)
  }
}

function getSortType() {
  return ST_SORT_TYPE;
}

// Find all tables with class sortable and make them sortable
// Tables must have an id to be sortable
function sortables_init() {
    if (!document.getElementsByTagName) return;
    var r = new RegExp('\\bsortable\\b');
    var tbls = document.getElementsByTagName("TABLE");
    var numtbls = tbls.length;
    for (var ti=0;ti<numtbls;ti++) {
        thisTbl = tbls[ti];
        if (r.test(thisTbl.className) && (thisTbl.id)) {
            ts_makeSortable(thisTbl);
	}
    }
}

// Turn the thead->tr[0]->th elements into links to control sorting
function ts_makeSortable(table) {
    
    if (table.tHead == null && table.tFoot == null &&
	table.rows && table.rows.length > 0) {
      var firstRow = table.rows[0];
    } else if (table.tHead != null && table.tHead.rows.length > 0) {
      var firstRow =table.tHead.rows[0];
    }
    if (!firstRow) {
      log('no firstRow in table ' + table.id);
      return;
    }
    
    var r = new RegExp('\\b' + ST_IGNORE_COL_CLASS + '\\b');
    log('makeSortable table ' + table.id);
    
    // We have a first row: assume it's the header,
    // and make its contents clickable links
    for (var i=0;i<firstRow.cells.length;i++) {
        var cell = firstRow.cells[i];
	if (! r.test(cell.className)) {
	  var txt = ts_getInnerText(cell);
	  cell.innerHTML = '<a href="#" class="sortheader" title="Sort this column" onclick="ts_resortTable(this,'+i+');return false;">'+txt+'<span class="sortarrow"></span></a>';
	}
    }
}

// Fix up for gecko browsers that don't have innerText
function ts_getInnerText(el) {
  if (typeof el == "string") return el;
  if (typeof el == "undefined") { return el };
  if (el.innerText) return el.innerText;	//Not needed but it is faster
  var str = "";
  var cs = el.childNodes;
  var l = cs.length;
  for (var i = 0; i < l; i++) {
    switch (cs[i].nodeType) {
    case 1: //ELEMENT_NODE
      str += ts_getInnerText(cs[i]);
      break;
    case 3:	//TEXT_NODE
      str += cs[i].nodeValue;
      break;
    }
  }
  return str;
}

// Called from a click on the header
function ts_resortTable(lnk,clid) {

    // get the span
    var span;
    for (var ci=0;ci<lnk.childNodes.length;ci++) {
        if (lnk.childNodes[ci].tagName && 
	    lnk.childNodes[ci].tagName.toLowerCase() == 'span') {
	  span = lnk.childNodes[ci];
	}
    }
    var td = lnk.parentNode;
    var column = clid || td.cellIndex; // safari hack
    var table = getParent(td,'TABLE');
    var rows = table.tBodies[0].rows;
    var rlen = rows.length;

    var sortdown = (span.getAttribute('sortdir') == 'down' ||
		    span.getAttribute('sortdir') == null ||
		    span.getAttribute('sortdir') == 'none');

    // Quick sort on one row :)
    if (rlen <= 1) return;

    ts_waitcursor();
    
    // Find a suitable row to fool around with
    var idx = 0;
    while (idx < rlen &&
	   (rows[idx].className.indexOf(ST_IGNORE_ROW_CLASS) > -1 ||
	    ts_getInnerText(rows[idx].cells[column]) == '')) {
      idx++;
    }
    
    // Work out a type for the column
    var itm = ts_getInnerText(rows[idx].cells[column]);
    sortfn = ts_sort_caseinsensitive;
    if (itm.match(/^\d\d[\/-]\d\d[\/-]\d\d\d\d$/)) sortfn = ts_sort_date;
    else if (itm.match(/^\d\d[\/-]\d\d[\/-]\d\d$/)) sortfn = ts_sort_date;
    else if (itm.match(/^--\d\d\d\d--$/)) sortfn = ts_sort_date;
    else if (itm.match(/^[-\d]{2}[\/-][-\d]{2}[\/-]\d\d$/)) sortfn = ts_sort_date;
    else if (itm.match(/^[£$]/)) sortfn = ts_sort_currency;
    else if (itm.match(/^[\d\.]+$/)) sortfn = ts_sort_numeric;
    else if (itm.match(/^[\d\.]+.+$/)) sortfn = ts_sort_leading_numeric;

    var cache = new Array(rlen);
    var k=0;
    for (j=0;j<rlen;j++) {
      if (rows[j].className.indexOf(ST_IGNORE_ROW_CLASS) == -1) {
	cache[k++] = {
	  value: ts_getInnerText(rows[j].cells[column]),
	  element: rows[j] 
	};
      } else if (rows[j].className.indexOf('hidden') == -1) {
	// hide our sep rows during sorting.
	rows[j].className += ' hidden';
      }
    }

    switch(ST_SORT_TYPE) {
       case 'default':
         defaultSort(cache,sortfn,sortdown);
         break;
       case 'shell':
         shellSort(cache,sortfn,sortdown);
         break;
       case 'merge':
         doMergeSort(cache,sortfn,sortdown);
         break;
       default:
         log('No such sort type ' + ST_SORT_TYPE);
    }

    span.setAttribute("sortdir",(sortdown?'up':'down'));
    if (ST_USE_IMAGES)
      span.innerHTML = (sortdown ? ST_DN_ARROW : ST_UP_ARROW);
    
    // We appendChild rows that already exist to the tbody,
    // so it moves them rather than creating new ones
    var nrlen = cache.length;
    for (i=0;i<nrlen;i++) {
      cache[i].element.className = (i%2==0 ? 'odd' : 'even');
      table.tBodies[0].appendChild(cache[i].element);
    }
    
    // Delete any other arrows there may be showing
    var allspans = table.getElementsByTagName("span");
    for (var ci=0;ci<allspans.length;ci++) {
        if (allspans[ci].className == 'sortarrow' && allspans[ci] != span) {
	  allspans[ci].setAttribute('sortdir','none');
	  if (ST_USE_IMAGES)
	    allspans[ci].innerHTML = ST_NO_ARROW;
	}
    }

    destroyCache(cache);

    ts_resumecursor();
}

function destroyCache(arr) {
  var l = arr.length;
  for (var i=0; i<l; i++) {
    if (arr[i]) {
      if (arr[i].value) arr[i].value = null;
      if (arr[i].element) arr[i].element = null;
      arr[i] = null;
    }
  }
}

function getParent(el, pTagName) {
  if (el == null) return null;
  else if (el.nodeType == 1 &&
	   // Gecko bug, supposed to be uppercase
	   el.tagName.toLowerCase() == pTagName.toLowerCase())	
    return el;
  else
    return getParent(el.parentNode, pTagName);
}
function ts_sort_date(a,b) {
  // y2k notes: two digit years less than 50 are treated as 20XX, 
  // greater than 50 are treated as 19XX
  aa = a.value;
  bb = b.value;
  var ayr, byr, amo, bmo, aday, bday;

  if (/--\d\d\d\d--/.test(aa)) {
    ayr = aa.substr(2,4);
    amo = 0;
    aday = 0;
  } else if (aa.length == 10) {
    amo = aa.substr(0,2);
    aday = aa.substr(3,2);
    ayr = aa.substr(6,4);
  } else {
    amo = aa.substr(0,2);
    aday = aa.substr(3,2);
    ayr = aa.substr(6,2);
  }
  if (/--\d\d\d\d--/.test(bb)) {
    byr = bb.substr(2,4);
    bmo = 0;
    bday = 0;
  } else if (bb.length == 10) {
    bmo = bb.substr(0,2);
    bday = bb.substr(3,2);
    byr = bb.substr(6,4);
  } else {
    bmo = bb.substr(0,2);
    bday = bb.substr(3,2);
    byr = bb.substr(6,2);
  }

  if (aday == '--') aday = 0; else aday = parseInt(aday);
  if (ayr == '--') ayr = 0; 
  else if (ayr.length == 2 && parseInt(ayr) < 50) ayr = '20'+ayr;
  else if (ayr.length == 2) ayr = '19'+ayr;
  else ayr = parseInt(ayr);
  if (amo == '--') amo = 0; else amo = parseInt(amo);
  if (bday == '--') bday = 0; else bday = parseInt(bday);
  if (bmo == '--') bmo = 0; else bmo = parseInt(bmo);
  if (byr == '--') byr = 0;
  else if (byr.length == 2 && parseInt(byr) < 50) byr = '20'+byr;
  else if (byr.length == 2) byr = '19'+byr;
  else byr = parseInt(byr);

  if (isNaN(ayr)) ayr = 0;
  if (isNaN(amo)) amo = 0;
  if (isNaN(aday)) aday = 0;
  if (isNaN(byr)) byr = 0;
  if (isNaN(bmo)) bmo = 0;
  if (isNaN(bday)) bday = 0;

  if (ayr == byr) {
    if (amo == bmo) {
      if (aday == bday) {
	return 0;
      } else {
	return aday - bday;
      }
    } else {
      return amo - bmo;
    }
  }  else {
    return ayr - byr;
  }
}

function ts_sort_currency(a,b) { 
  aa = a.value.replace(/[^0-9.]/g,'');
  bb = b.value.replace(/[^0-9.]/g,'');
  return parseFloat(aa) - parseFloat(bb);
}

function ts_sort_numeric(a,b) { 
  aa = parseFloat(a.value);
  if (isNaN(aa)) aa = 0;
  bb = parseFloat(b.value);
  if (isNaN(bb)) bb = 0;
  return aa-bb;
}

function ts_sort_caseinsensitive(a,b) {
  aa = a.value.toLowerCase();
  bb = b.value.toLowerCase();
  if (aa==bb) return 0;
  if (aa<bb) return -1;
  return 1;
}

function ts_sort_default(a,b) {
  aa = a.value;
  bb = b.value;
  if (aa==bb) return 0;
  if (aa<bb) return -1;
  return 1;
}

function ts_sort_leading_numeric(a,b) {
  aa = a.value.replace(/[^0-9.]/g,'');
  bb = b.value.replace(/[^0-9.]/g,'');
  aa2 = a.value.replace(/^[0-9.]+ */g,'');
  bb2 = b.value.replace(/^[0-9.]+ */g,'');
  aa = parseFloat(aa);
  bb = parseFloat(bb);
  if (aa == bb) {
    if (aa2==bb2) return 0;
    if (aa2<bb2) return -1;
    return 1;
  }
  return aa-bb;
}
    
  
// addEvent and removeEvent
// cross-browser event handling for IE5+,  NS6 and Mozilla
// By Scott Andrew
function addEvent(elm, evType, fn, useCapture)
{
  if (elm.addEventListener){
    elm.addEventListener(evType, fn, useCapture);
    return true;
  } else if (elm.attachEvent){
    var r = elm.attachEvent("on"+evType, fn);
    return r;
  } else {
    alert("Handler could not be removed");
  }
}

function ts_waitcursor() {
  document.body.style.cursor = 'wait';
}

function ts_resumecursor() {
  document.body.style.cursor = 'default';
}

function defaultSort(arr,fn,dir) {
  log('calling default dir=' + (dir?'down':'up') + ' comparator=' + fn.name);
  arr.sort(fn);
  if (!dir) arr.reverse();
}

function shellSort(arr,fn,dir) {
  log('calling shellSort dir=' + (dir?'down':'up') + ' comparator=' + fn.name);
  var N = arr.length;
  
  if ((k = Math.floor(N/5)) > 7) {
    for (var m=0; m<k; m++) {
      iSort(arr,m,k,N,fn);
    }
  }

  if ((k = Math.floor(N/7)) > 7) {
    for (var m=0; m<k; m++) {
      iSort(arr,m,k,N,fn);
    }
  }

  for (k=7; k>0; k-=2) {
    for (var m=0; m<k; m++) {
      iSort(arr,m,k,N,fn);
    }
  }

  if (!dir) arr.reverse();
}

// used by shell sort
function exchange (arr,i,j) {
  var x = arr[i];
  arr[i] = arr[j];
  arr[j] = x;
}

// Used by shell sort
function iSort(arr,m,k,len,fn) {
  for (var j=m+k; j<len; j+=k) {
    for (var i=j; i>=k && fn(arr[i],arr[i-k]) < 0; i-=k) {
      exchange(arr,i,i-k);
    }
  }
}

function doMergeSort(arr,fn,dir) {
  var workspace = new Array(arr.length);
  log('calling mergeSort dir=' + (dir?'down':'up') + ' comparator=' + fn.name);
  mergeSort(workspace,0,arr.length-1,arr,fn,dir);
}

function mergeSort(workspace, lowerBound, upperBound, arr, fn, dir) {
  if (lowerBound == upperBound) return;
  var mid = Math.floor((lowerBound+upperBound)/2);
  
  // sort lower half
  mergeSort(workspace,lowerBound,mid,arr,fn,dir);

  // sort upper half
  mergeSort(workspace,mid+1,upperBound,arr,fn,dir);

  // merge halves
  merge(workspace,lowerBound, mid+1, upperBound, arr, fn, dir);
}

function merge(workspace, lowPtr, highPtr, upperBound, arr, fn, dir) {
  var j=0,
    lowerBound = lowPtr,
    mid = highPtr-1,
    n = upperBound - lowerBound + 1;
  
  while (lowPtr <= mid && highPtr <= upperBound) {
    var cmp = fn(arr[lowPtr],arr[highPtr]);
    if ((dir && cmp <= 0) || (!dir && cmp >= 0)) {
      workspace[j++] = arr[lowPtr++];
    } else {
      workspace[j++] = arr[highPtr++];
    }
  }

  while (lowPtr <= mid) {
    workspace[j++] = arr[lowPtr++];
  }

  while (highPtr <= upperBound) {
    workspace[j++] = arr[highPtr++];
  }

  for (j=0; j<n; j++) {
    arr[lowerBound+j] = workspace[j];
  }
}

function log(s) {
  var el = document.getElementById('logarea');
  if (el) {
    if (el.value) {
      el.value = el.value + '\n' + s;
    } else {
      el.value = s;
    }
  }
}

addEvent(window, "load", sortables_init);