// Return the concatenation of text nodes below 'node' in prefix order.
function text_content(node) {
    if (node.nodeType == node.TEXT_NODE) {
        return node.data;
    } else {
        var content = '';
        var i;
        for (i = 0; i < node.childNodes.length; ++i) {
            content += text_content(node.childNodes[i]);
        }
        return content;
    }
}

// Starting at NODE, walk the DOM in prefix order until an element node
// is found with class="KEY".  Then return the text contents of that
// node.  If no such element is found, return null.
function find_string_key(node, key) {
    if (node.nodeType == node.ELEMENT_NODE
        && node.getAttribute('class') == key)
    {
        return text_content(node);
    } else {
        var i;
        for (i = 0; i < node.childNodes.length; ++i) {
            var k = find_string_key(node.childNodes[i], key);
            if (k) {
                return k;
            }
        }
    }
    return null;
}

// Return the text content of the 'key'th <TD> element in 'row'.
function find_number_key(row, key) {
    var tds = row.getElementsByTagName('TD');
    if (0 <= key && key < tds.length) {
        return text_content(tds[key])
    }
}

// Return the key data for 'row'. 'key' is a number or string, as
// described below for 'sort_table'.
function find_key(row, key) {
    if (typeof key == 'string') {
        return find_string_key(row, key);
    } else if (typeof key == 'number') {
        return find_number_key(row, key);
    } else {
        throw "Don't know how to find " + typeof key + " key.";
    }
}

// Comparison function for any two values.
function compare_any(a, b) {
    if (a < b) {
        return -1;
    } else if (b < a) {
        return 1;
    } else {
        return 0;
    }
}

// Comparison function for strings to be treated as integers.
function compare_int(a, b) {
    return compare_any(parseInt(a), parseInt(b));
}

// Comparison function for strings to be treated as floating-point numbers.
function compare_float(a, b) {
    return compare_any(parseFloat(a), parseFloat(b));
}

// Return the element with 'tag' containing 'node', if any, or null
// if no such element is found.
function containing_node(node, tag) {
    while (node && (node.nodeType != node.ELEMENT_NODE
                    || node.tagName != tag)) 
    {
        node = node.parentNode;
    }
    return node;
}

// Remember by what key we most recently sorted each table, and whether
// the most recent sort was reversed.  This is a map from table node to
// objects {'key': STRING, 'reverse': BOOL, 'anchor' = NODE}.
var current_sort = new Object();

// Sort the rows of the first <TBODY> element in a table (or the whole
// table if it has no <TBODY> element).
//
// 'anchor' is the element to which the sort indicator will be attached
// (typically it's the anchor which is clicked to perform the sort).
//
// 'id' determines the table to sort:
// If string: it's the one with id='id'.
// If null: it's the one containing the 'anchor' element.
//
// 'key' determines the sort key for each row:
// If string: the text of the first element in the row with class='key'.
// If number: the text of the 'key'th <TD> cell in the row.
// If null: the text of the 'n'th <TD> cell in the row (where 'anchor'
// is contained in the 'n'th <TH> cell its header row).
//
// If 'rev' is true, the first sort on this key is reversed (normally
// the first sort is in normal order, and the second is reversed).
//
// 'compare' is the comparison function to be applied to the keys to
// determine the order of rows.  If not supplied, it defaults to
// 'compare_any'.
function sort_table(anchor, id, key, rev, compare) {
    var table;
    if (id) {
        // Determine table from 'id' if supplied.
        table = document.getElementById(id);
    } else {
        // Table defaults to the TABLE containing 'anchor'.
        table = containing_node(anchor, 'TABLE');
    }
    if (!table || !table.tagName || table.tagName != 'TABLE') {
        throw "No such table: " + what
    }
    var tbody = table.getElementsByTagName('tbody')[0]
    if (!tbody) {
        // No TBODY: sort whole table.
        tbody = table;
    }

    if (key == null || typeof key == 'undefined') {
        // Key defaults to the column number of the TH containing 'anchor'.
        var th = containing_node(anchor, 'TH');
        if (!th) {
            throw "Unable to determine a key: anchor not containing in TH";
        }
        var tr = containing_node(th, 'TR');
        if (!tr) {
            throw "Unable to determine a key: anchor not containing in TR";
        }
        var ths = tr.getElementsByTagName('TH');
        for (i = 0; i < ths.length; ++i) {
            if (th == ths[i]) {
                key = i;
                break;
            }
        }
        if (key == null || typeof key == 'undefined') {
            throw "Unable to determine a key: inconsistent DOM."
        }
    }

    if (!compare) {
        // 'compare' argument defaults to 'compare_any'.
        compare = compare_any;
    }

    // Find the keys for all the rows in the table, remove them from the
    // table, and sort them by their keys (a Schwartzian Transform).
    // Note that process the rows in reverse order so that we can remove
    // them safely from their container without breaking anything.
    var table_rows = tbody.getElementsByTagName('tr');
    var rows = new Array();
    var i;
    for (i = table_rows.length - 1; 0 <= i; --i) {
        var o = new Object();
        o.row = table_rows[i];
        o.key = find_key(o.row, key);
        rows.push(o);
        tbody.removeChild(o.row);
    }
    rows.sort(function (a, b) {return compare(a.key, b.key);});

    // Work out which order to sort the table rows.
    var s = current_sort[table];
    if (!s) {
        // First ever sort on this table.
        s = new Object();
        s.key = key;
        s.reverse = rev ? true : false;
        current_sort[table] = s;
    } else if (s.key == key) {
        // Subsequent sorts on the same key reverse the sort order.
        s.reverse = !s.reverse;
    } else {
        s.key = key;
        s.reverse = rev ? true : false;
    }
    if (s.reverse) {
        rows.reverse();
    }

    // Is there an existing sort indicator for this table? If so, remove it.
    if (s.anchor) {
        var children = s.anchor.childNodes;
        for (i = children.length - 1; 0 <= i; --i) {
            var n = children[i];
            if (n.nodeType == n.ELEMENT_NODE
                && n.tagName == 'SPAN'
                && n.getAttribute('class') == 'sort_indicator')
            {
                s.anchor.removeChild(n);
                break;
            }
        }
    }

    // Put the rows back in sorted order.
    for (i = 0; i < rows.length; ++i) {
        tbody.appendChild(rows[i].row);
    }

    // Add a sort indicator.
    span = document.createElement('span');
    span.setAttribute('class', 'sort_indicator');
    if (s.reverse) {
        span.innerHTML = '&nbsp;&#x25BE;';
    } else {
        span.innerHTML = '&nbsp;&#x25B4;';
    }
    anchor.appendChild(span);
    s.anchor = anchor;

    // Suppress the link.
    return false;
}