// midpoint(end1, end2) => number
// Pick a random number between two end values.
function midpoint (end1, end2) {
  return Math.floor(Math.random() * (end2 - end1) + end1 + 0.5);
}


// fillrow(grid, row, endleft, endright)
// Recursively fill one row.
// Used to bootstrap the recursive area fill.
// Also used to fudge our way out of ?x2 rectangles.
function fillrow (grid, row, endleft, endright) {
  if (endleft + 1 == endright) return;
  // Set the dot in the middle.
  var middleX = Math.floor((endright - endleft) / 2 + endleft);
  grid[row][middleX] = midpoint(grid[row][endleft], grid[row][endright]);
  // Go fill the two new sub-rows
  fillrow(grid, row, endleft, middleX);
  fillrow(grid, row, middleX, endright);
}


// fillcol(grid, col, endtop, endbottom)
// Recursively fill one column.
// Used to bootstrap the recursive area fill.
// Also used to fudge our way out of ?x2 rectangles.
function fillcol(grid, col, endtop, endbottom) {
  if (endtop + 1 == endbottom) return;
  // Set the dot in the middle.
  var middleY = Math.floor((endbottom - endtop) / 2 + endtop);
  grid[middleY][col] = midpoint(grid[endtop][col], grid[endbottom][col]);
  // Go fill the two new sub-columns
  fillcol(grid, col, endtop, middleY);
  fillcol(grid, col, middleY, endbottom);
}


// fillarea(grid, endtop, endbottom, endleft, endright)
// Recursively fill the area.
function fillarea(grid, endtop, endbottom, endleft, endright) {
  if ((endleft + 1 == endright) && (endtop + 1 == endbottom)) {
    // This is just a 2x2 square.  Nothing to do.
  } else if (endleft + 1 == endright) {
    // This is just a 2x? rectangle.  Fill in some vertical space.
    fillcol(grid, endright, endtop, endbottom);
  } else if (endtop + 1 == endbottom) {
    // This is just a ?x2 rectangle.  Fill in some horizontal space.
    fillrow(grid, endbottom, endleft, endright);
  } else {
    // Wide open space; something to sink our recursive teeth into...
    // Set the dot half way along the bottom row.
    var middleX = Math.floor((endright - endleft) / 2 + endleft);
    grid[endbottom][middleX] = midpoint(grid[endbottom][endleft], grid[endbottom][endright]);

    // Set the dot half way along the right column.
    var middleY = Math.floor((endbottom - endtop) / 2 + endtop);
    grid[middleY][endright] = midpoint(grid[endtop][endright], grid[endbottom][endright]);

    // Set the dot in the middle (midpoint of two midpoints).
    var centre1 = midpoint(grid[endtop][middleX], grid[endbottom][middleX]);
    var centre2 = midpoint(grid[middleY][endright], grid[middleY][endleft]);
    grid[middleY][middleX] = midpoint(centre1, centre2);

    // Go fill the four new quadrants.
    fillarea(grid, endtop, middleY, endleft, middleX);
    fillarea(grid, middleY, endbottom, endleft, middleX);
    fillarea(grid, endtop, middleY, middleX, endright);
    fillarea(grid, middleY, endbottom, middleX, endright);
  }
}

function generate_grid(cols, rows) {
  // Loop variables
  var row, col;

  // The grid of points that make up the image.
  var grid = Array(rows);
  for (row = 0; row < rows; row++) {
    grid[row] = Array(cols);
  }

  // Flip a coin to determine which diagonally opposite corners get the master colours.
  if (Math.random() >= .5) {
    grid[0][0] = 0;
    grid[rows - 1][cols - 1] = 255;
    grid[rows - 1][0] = Math.floor(Math.random() * 255);
    grid[0][cols - 1] = Math.floor(Math.random() * 255);
  } else {
    grid[0][cols - 1] = 0;
    grid[rows - 1][0] = 255;
    grid[0][0] = Math.floor(Math.random() * 255);
    grid[rows - 1][cols - 1] = Math.floor(Math.random() * 255);
  }

  // Draw the top row and left column.
  fillrow(grid, 0, 0, cols - 1);
  fillcol(grid, 0, 0, rows - 1);

  // Now we have the top edge, the left edge, and the bottom/right dot.
  // We are all setup to fill the remaining area.
  fillarea(grid, 0, rows - 1, 0, cols - 1);

  return grid;
}

function generate_palette() {
  // RGB colour declarations for the master colours
  var c1r, c1g, c1b;
  var c2r, c2g, c2b;

  do {
    c1r = Math.floor(Math.random() * 256);
    c1g = Math.floor(Math.random() * 256);
    c1b = Math.floor(Math.random() * 256);
    c2r = Math.floor(Math.random() * 256);
    c2g = Math.floor(Math.random() * 256);
    c2b = Math.floor(Math.random() * 256);
    // Keep looping until you get dissimilar colours.
  } while ((Math.abs(c1r - c2r) + Math.abs(c1g - c2g) + Math.abs(c1b - c2b)) < 256);

  // Compute all 256 colours.
  var palette = [];
  for (var x = 0; x <= 255; x++) {
    var r = Math.floor(c1r * x / 255 + c2r * (1 - x / 255));
    var g = Math.floor(c1g * x / 255 + c2g * (1 - x / 255));
    var b = Math.floor(c1b * x / 255 + c2b * (1 - x / 255));
    palette[x] = [r, g, b];
  }
  return palette;
}