// JavaScript Document
/**
 * Tetris-like population of a grid with various-sized
 * items, filling in as much empty space as possible
 *
 * Usage:
 *   g = new Grid(5); // instantiate a new 5-column grid
 *   pos = g.addItem({'width': 2, 'height': 1});
 *   // pos = {'row': 0, 'col': 0}
 *   pos = g.addItem({'width': 1, 'height': 2});
 *   // pos = {'row': 0, 'col': 2}
 *
 */

Grid = function(cols) {
    this.cols = cols;
    this.grid = [];
    this.lastFilled = {'row':0, 'col':0};
};

Grid.prototype = {
    
    // find the next opening, starting at a given row/col position
    'nextOpening': function(start) {
        
        // if we weren't passed a starting position, use the last filled position
        start = start || this.lastFilled;
        
        // try to find an opening in existing rows
        for (var r = start.row; r < this.grid.length; r++) {
            for (var c = 0; c < this.cols; c++) {
                if(this.grid[r][c] == undefined && !(r <= start.row && c <= start.col)) {
                    return {'row': r, 'col': c};
                }
            }
        }
        
        // if we didn't find an opening, add a new row
        this.grid.push([]);
        return {'row': this.grid.length - 1, 'col': 0};
    },
    
    // given a row/col position and width/height, determine if
    // there is room for an item at the position
    'testFit': function(row, col, width, height) {
        
        // sanity check: we can't have an item in the starting position
        if (this.grid[row][col] != undefined) return false;
        
        // if this is a 1x1, we're good to go
        if (width == 1 && height == 1) return true;
        
        // iterate over width/height to check for cells already taken
        for (var r = row; r < row + height; r++) {
            for (var c = col; c < col + width; c++) {
                if (c >= this.cols) return false;
                if(this.grid[r] && this.grid[r][c] != undefined) {
                    return false;
                }
            }
        }
        
        // if we didn't hit any filled cells, we're good to go
        return true;
    },
    
    // add an item to the grid
    'addItem': function(item) {
        
        // figure out where to place the item
        var position = this.nextOpening();
        var firstOpening = true;
        while (!this.testFit(position.row, position.col, item.width, item.height)) {
            firstOpening = false;
            position = this.nextOpening(position);
        }
        
        // if we placed the item in the first available opening, update the lastFilled
        // position so we don't search for any openings ahead of it
        if (firstOpening) this.lastFilled = position;
        
        // add the item to the primary position where it lives
        item.overflow = false;
        this.grid[position.row][position.col] = item;
        
        // add overflow markers for any positions it hangs over into
        for (var r = position.row; r < position.row + item.height; r++) {
            for (var c = position.col; c < position.col + item.width; c++) {
                if (!(r == position.row && c == position.col)) {
                    if (this.grid[r] == undefined) this.grid[r] = [];
                    this.grid[r][c] = {'width': item.width, 'height': item.height, 'overflow': true};
                }
            }
        }
        
        // return the place item
        return {'row': position.row, 'col': position.col};
    }
};