var Rect = Base.extend({
    constructor: function(x, y, width, height) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.ar = width / height;
    },
    name: "Rect",
    // Updates the height based on the aspect ratio and the width
    update_height: function() {
        this.height = this.width / this.ar;
    },
    // Updates the width based on the aspect ratio and the height
    update_width: function() {
        this.width = this.height / this.ar;
    }
});

var BoundRect = Rect.extend({
    constructor: function(rect) {
        this.base(0, 0, rect.width, rect.height);
        this.rect = rect;
    },
    name: "BoundRect",
    // Apply changes to your bound rectangle object
    flush: function(x_off, y_off, scale) {
        this.rect.x = x_off + this.x * scale;
        this.rect.y = y_off + this.y * scale;
        this.rect.width = this.width * scale;
        this.rect.height = this.height * scale;
    }
});

var CompositeRect = Rect.extend({
    constructor: function(rects, x, y, width, height) {
        this.base(x, y, width, height);
        this.rects = rects;
    },
    name: "CompositeRect",
    // Tell all your children to flush themselves. Pass geometric context down the line
    flush: function(x_off, y_off, scale) {
        for(var i = 0; i < this.rects.length; i++) {
            this.rects[i].flush(x_off + this.x * scale, y_off + this.y * scale, this.width * scale);
        }
    }
});

function find_ar(rects, ar) {
    var min_i = 0;
    var max_i = rects.length - 1;
    while(max_i - min_i > 1) {
        var mid_i = Math.floor((max_i + min_i) / 2);
        var mid_ar = rects[mid_i].ar;
        if(mid_ar == ar)
            return mid_i;
        else if(ar > mid_ar)
            min_i = mid_i;
        else
            max_i = mid_i;
    }
    var log_ar = Math.log(ar);
    if(Math.abs(Math.log(rects[max_i].ar) - log_ar) < Math.abs(Math.log(rects[min_i].ar) - log_ar))
        return max_i
    return min_i
}
function sort_ar(rect_a, rect_b) {
    return ((rect_a.width/rect_a.height < rect_b.width/rect_b.height) ? -1 : ((rect_a.width/rect_a.height > rect_b.width/rect_b.height) ? 1 : 0));
}

function tile(input_rects, target_width, target_height) {
    /*
        Tiles a given set of images into a rectangle of approximately the same dimensions as those given.
        The rectangles are given as a list of rectangle objects containing, at the very least, a
        'width' and a 'height' parameter. After tiling, the rectangles in that list will have been modified
        to now contain an 'x' and a 'y' parameter, as well as a new 'width' and 'height'.
        It returns a (width, height) tuple of the actual size of the final tiled rectangle.
    */
    var rects = [];
    $.each(input_rects, function(key, value) {
        var rect = new BoundRect(value);
        rects.push(rect);
    });
    rects.sort(sort_ar);
    var composite = tile_r(rects, rects.length, target_width / target_height);
    composite.flush(0, 0, target_width);
    return target_width, target_width / composite.ar;
}

// Recursive function to tile a series of rectangle objects. returns a _CompositeRect normalized to a width of 1.
function tile_r(rectpool, rects, target_ar) {
    if(rects == 1) {
        var rect = rectpool.splice(find_ar(rectpool, target_ar), 1)
        return rect[0];
    }

    if(rectpool.length == 2) {
        /* Try tiling in these two different ways:

             (1)      (2)
          ___ _____   ___
         |   |     | |   |
         |___|_____| |___|
                     |   |
                     |   |
                     |___|

        and see which one is closer to the target aspect ratio.
        */
        var r0 = rectpool.pop();
        var r1 = rectpool.pop();

        // Aspect ratio if they're tiled horizontally
        var h_ar = r0.ar + r1.ar

        // Aspect ratio if they're tiled vertically
        var v_ar = 1 / (1 / r0.ar + 1 / r1.ar);

        // Which of the two tilings was closer?
        var log_ar = Math.log(target_ar);

        if(Math.abs(Math.log(h_ar) - log_ar) < Math.abs(Math.log(v_ar) - log_ar)) {
            // Horizontal tiling was closer
            r0.width = r0.ar / (r0.ar + r1.ar);
            r1.width = r1.ar / (r0.ar + r1.ar);
            r0.update_height();
            r1.update_height();

            r0.x = 0;
            r0.y = 0;
            r1.x = r0.width;
            r1.y = 0;
            return new CompositeRect([r0, r1], 0, 0, 1, r0.height);
        } else {
            // Vertical tiling was closer
            r0.width = 1;
            r1.width = 1;
            r0.update_height();
            r1.update_height();
            r0.x = 0;
            r0.y = 0;
            r1.x = 0;
            r1.y = r0.height;
            return new CompositeRect([r0, r1], 0, 0, 1, r0.height + r1.height);
        }

    }

    var rects_a = Math.floor(rects / 2);
    var rects_b = rects - rects_a;

    var new_ar = 0;
    if(target_ar > 1)
        new_ar = target_ar / 2;
    else
        new_ar = target_ar * 2;

    var rect_a = tile_r(rectpool, rects_a, new_ar);

    var new_ar =2.5;
    if(target_ar > rect_a.ar)
        // You want to be wider, append to the side
        new_ar = target_ar - rect_a.ar
    else if(target_ar < rect_a.ar)
        // You want to be taller, append to the bottom
        new_ar = 1 / (1 / target_ar - 1 / rect_a.ar);
    else {
        // TODO: What happens if you happen to full the rectangle perfectly without the second
        // half? Right now, target_ar is arbitrarily set to 2.5
        console.log("FYI: There was an aspect ratio collision!");
    }

    var rect_b = tile_r(rectpool, rects_b, new_ar);

    var new_pair = [rect_a, rect_b];
    new_pair.sort(sort_ar);

    return tile_r(new_pair, 2, target_ar);
}