// Copyright (c) 2008 Tony Garnock-Jones <tonyg@lshift.net>
// Copyright (c) 2008 LShift Ltd. <query@lshift.net>
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation files
// (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

DrawDvcs = {
    renderRepository: function (repo) {
        var childCount = {};
        var ordering = [];
        var i, j, item, parent, column, row;

        var worklist = repo.childlessRevisions();
        while (worklist.length) {
            item = worklist.shift();
            ordering.push(item);

            var parents = repo.lookupParents(item);
            for (i = 0; i < parents.length; i++) {
                parent = parents[i];
                if (childCount[parent] == undefined) {
                    childCount[parent] = repo.lookupChildren(parent).length;
                }
                childCount[parent] = childCount[parent] - 1;
                if (childCount[parent] === 0) {
                    worklist.push(parent);
                }
            }
        }

        var slots = [];
        var assignments = {};

        function allocateSlot(item) {
            var column = assignments[item];
            if (typeof(column) != 'number') {
                column = null;
                for (var j = 0; j < slots.length; j++) {
                    if (slots[j] === null) {
                        column = j;
                        break;
                    }
                }
                if (column === null) {
                    slots.push(item);
                    column = slots.length - 1;
                }
            }
            return column;
        }

        var finalAssignments = [];
        var cells = [];
        var oldrow = [];

        for (i = 0; i < ordering.length; i++) {
            item = ordering[i];
            var hasKid = typeof(assignments[item]) == 'number';
            column = allocateSlot(item);
            var parentIds = repo.lookupParents(item);
            var parentColumns = [];
            slots[column] = null;

            for (j = 0; j < parentIds.length; j++) {
                parent = parentIds[j];
                var c2 = (j === 0)
                    ? (typeof(assignments[parent]) == 'number'
                       ? allocateSlot(parent)
                       : column)
                    : allocateSlot(parent);
                parentColumns.push(c2);
                slots[c2] = parent;
                assignments[parent] = c2;
            }

            finalAssignments.push(column);

            row = [];
            for (j = 0; j < slots.length; j++) {
                var oldCell = (oldrow.length >= j ? oldrow[j] : 0);
                if (oldCell & 16) {
                    row[j] = (oldCell & 4) ? 1 : 0;
                } else {
                    row[j] = (oldCell & (1 | 4 | 8)) ? 1 : 0;
                }
            }
            row[column] = 16 | (hasKid ? 1 : 0);
            for (j = 0; j < parentColumns.length; j++) {
                var parentColumn = parentColumns[j];
                var n1 = Math.min(parentColumn, column) + 1;
                var n2 = Math.max(parentColumn, column);
                for (var k = n1; k < n2; k++) {
                    row[k] = row[k] | 2;
                }
                if (parentColumn == column) {
                    row[parentColumn] = row[parentColumn] | 4;
                } else {
                    row[parentColumn] = row[parentColumn] | (column > parentColumn ? 8 : 4);
                    row[column] = row[column] | (column > parentColumn ? 2 : 8);
                }
            }
            cells.push(row);
            oldrow = row;
        }

        var results = [];
        for (i = 0; i < ordering.length; i++) {
            item = ordering[i];
            column = finalAssignments[i];

            row = cells[i];

            var result = {revId: item, pictures: []};
            for (j = 0; j < row.length; j++) {
                var v = row[j];
                result.pictures.push((v & 16 ? "blob_" : "stick_") + (v & 15) + ".png");
            }
            results.push(result);
        }

        return results;
    },

    simpleRenderRepository: function (repo) {
        var ordering = DrawDvcs.renderRepository(repo);
        var html = "";
        for (var i = 0; i < ordering.length; i++) {
            var item = ordering[i];
            var rev = repo.lookupRev(item.revId);
            var pictures = item.pictures;
            for (var j = 0; j < pictures.length; j++) {
                html = html + "<img src='img/" + pictures[j] + "' />";
            }
            html = html+" "+item.revId+" ("+rev.branch+") "+(rev.metadata||{}).summary+"<br />\n";
        }
        return "<p style='line-height: 0px; white-space: nowrap;'>" + html + "</p>";
    }
};