ThomasTest.js

function Grid(M, N, mapFunction){
  this.grid = [];
  this.M = M;
  this.N = N;

  if (M < 1 || N <1) throw new Error('Grid dimensions must be greater than 0');

  if (typeof mapFunction == 'function'){
    this.init(mapFunction);
  }
  else {
    this.init(function(){ return 0; });
  }
}

Grid.prototype = {
  init: function(mapFunction){
    for (var x = 0; x < this.M; x++)
      for (var y = 0; y < this.N; y++)
        this.grid[this.index(x, y)] = mapFunction(x, y);
  },
  index: function (x, y){
    if (x < 0 || y < 0 || x > this.M || y > this.N) throw new Error('Out of bounds!');
    return (y*this.M) + x;
  },
  get: function(x, y){
    return this.grid[this.index(x,y)];
  },
  sumSquareSlow: function (x1, x2, y1, y2){
    var xx1 = Math.min(x1, x2),
        xx2 = Math.max(x1, x2),
        yy1 = Math.min(y1, y2),
        yy2 = Math.max(y1, y2),
        sum = 0;

    for (var xd = xx1; xd <= xx2; xd++)
      for (var yd = yy1; yd <= yy2; yd++)
        sum += this.get(xd, yd);

    return sum;
  },
  print: function(){
    var out = "";
    for (var y = 0; y < this.N; y++) {
      for (var x = 0; x < this.M; x++){
        var n = this.get(x, y);
        out += (n < 10 ? " " : "") + n + " ";
      }
      out += "\n";
    }
    console.log(out);
  },
  sumSquareConstant: function(x1, x2, y1, y2){
    var self = this;
    if (!this.cumulativeSumGrid){
      this.cumulativeSumGrid = new Grid(this.M, this.N, function(x, y){
        return self.sumSquareSlow(0, x, 0, y);
      });
    }

    var xx1 = Math.min(x1, x2),
        xx2 = Math.max(x1, x2),
        yy1 = Math.min(y1, y2),
        yy2 = Math.max(y1, y2),
        topx = xx2, topy = yy1 - 1,
        leftx = xx1 - 1, lefty = yy2,
        topLeftx = xx1 - 1, topLefty = yy1 - 1;

    var topSum = 0, leftSum = 0, topLeftSum = 0;
    if (topy >= 0) topSum = this.cumulativeSumGrid.get(topx, topy);
    if (leftx >= 0) leftSum = this.cumulativeSumGrid.get(leftx, lefty);
    if (topLeftx >= 0 && topLefty >= 0) topLeftSum = this.cumulativeSumGrid.get(topLeftx, topLefty);
    return this.cumulativeSumGrid.get(xx2, yy2) - leftSum - topSum + topLeftSum;
  }
};


function test(){
  var randomGrid = new Grid(5, 4, function(){ return Math.floor(Math.random()*5); });
  for (var i = 0; i < 10; i++) {
    var x1 = Math.floor(Math.random() * 5);
    var x2 = Math.floor(Math.random() * 5);
    var y1 = Math.floor(Math.random() * 4);
    var y2 = Math.floor(Math.random() * 4);
    if (randomGrid.sumSquareSlow(x1, x2, y1, y2) == randomGrid.sumSquareConstant(x1, x2, y1, y2)){
      console.log("PASS: (" + x1 + ", " + y1 + ") (" + x2 + ", " + y2 + ")");
    }
    else {
      console.log("FAIL: " + x1 + ", " + y1 + ") (" + x2 + ", " + y2 + ")");
    }
  }
}