/*
 * Copyright (C) 2009 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

// GridSort
//
// This test is designed to test the performance of sorting a grid of nodes
// such as what you might use in a spreadsheet application.

// returns an array of integers from 0 to totalCells
function generateValuesArray(totalCells) {
    var values = [];
    for (var i = 0; i < totalCells; i++)
        values[i] = i;
    return values;
}

// creates value text nodes in a table using DOM methods
function populateTableUsingDom(tableId, width, height) {
    var table = document.getElementById(tableId);
    var values = generateValuesArray(width * height);

    for (var i = 0; i < height; i++) {
        var row = table.insertRow(i);
        for (var j = 0; j < width; j++) {
            var cell = row.insertCell(j);
            var valueIndex = Math.floor(Math.random() * values.length);
            var value = values.splice(valueIndex, 1);
            cell.appendChild(document.createTextNode(value));
        }
    }
}

// returns HTML string for rows/columns of table data
function getTableContentHTML(width, height) {
    var values = generateValuesArray(width * height);

    var html = []; // fragments we will join together at the end
    var htmlIndex  = 0;

    for (var i = 0; i < height; i++) {
        html.push("<tr>");
        for (var j = 0; j < width; j++) {
            html.push("<td>");
            var valueIndex = Math.floor(Math.random() * values.length);
            var value = values.splice(valueIndex, 1);
            html.push(value);
            html.push("</td>");
        }
        html.push("</tr>");
    }
    return html.join("");
}

// When sorting a table by a column, we create one of these for each
// cell in the column, and it keeps pointers to all the nodes in that
// row. This way we can sort an array of SortHelper objects, and then
// use the sibling node pointers to move all values in a row to their
// proper place according to the new sort order.
function SortHelper(row, index) {
    this.nodes = [];
    var numCells = row.cells.length;
    for (var i = 0; i < numCells; i++)
        this.nodes[i] = row.cells[i].firstChild;
    this.originalIndex = index;
}

function compare(a, b) {
    return a - b;
}

// sorts all rows of the table on a given column
function sortTableOnColumn(table, columnIndex) {
    var numRows = table.rows.length;
    var sortHelpers = [];
    for (var i = 0; i < numRows; i++)
        sortHelpers.push(new SortHelper(table.rows[i], i));

    // sort by nodeValue with original position breaking ties
    sortHelpers.sort(function(a, b) {
        var cmp = compare(Number(a.nodes[columnIndex].nodeValue), Number(b.nodes[columnIndex].nodeValue));
        if (cmp === 0)
            return compare(a.originalIndex, b.originalIndex);
        return cmp;
    });

    // now place all cells in their new position
    var numSortHelpers = sortHelpers.length;
    for (var i = 0; i < numSortHelpers; i++) {
        var helper = sortHelpers[i];
        if (i == helper.originalIndex)
            continue; // no need to move this row
        var columnCount = table.rows[i].cells.length;
        for (var j = 0; j < columnCount; j++) {
            var cell = table.rows[i].cells[j];
            if (cell.firstChild) {
                // a SortHelper will still have a reference to this node, so it
                // won't get orphaned/garbage collected
                cell.removeChild(cell.firstChild);
            }
            cell.appendChild(helper.nodes[j]);
        }
    }
}

function clearExistingTable() {
    var table = document.getElementById("gridsort_table");
    if (table) {
        // clear out existing table
        table.parentNode.removeChild(table);
    }
}

function createTableUsingDom() {
    clearExistingTable();
    var table = document.createElement("table");
    table.id = "gridsort_table";
    table.border = 1;
    document.getElementById("benchmark_content").appendChild(table);
    populateTableUsingDom("gridsort_table", 60, 60);
}

function createTableUsingInnerHtml() {
    clearExistingTable();
    var tableContent = getTableContentHTML(60, 60);
    var html = "<table id='gridsort_table' border='1'>" + tableContent + "</table>";
    document.getElementById("benchmark_content").innerHTML = html;
}

function sortTable() {
    var table = document.getElementById("gridsort_table");
    // TODO - it might be interesting to sort several (or all)
    // columns in succession, but for now that's fairly slow
    sortTableOnColumn(table, 0);
}

var GridSortTest = new BenchmarkSuite('GridSort', [
    new Benchmark("SortDomTable (60x60)", sortTable, createTableUsingDom, null, false),
    new Benchmark("SortInnerHtmlTable (60x60)", sortTable, createTableUsingInnerHtml, null, false)
]);