// -*- mode: js2; indent-tabs-mode: nil; -*-

// Adapted from
//
// https://github.com/RiverTrail/RiverTrail/blob/master/examples/liquid-resize/resize-compute-dp.js
//
// which in turn is based on an algorithm from the paper below (which
// also appeared in ACM SIGGRAPH 2007):
// Shai Avidan and Ariel Shamir. 2007. Seam carving for content-aware image resizing.
// ACM Trans. Graph. 26, 3, Article 10 (July 2007).
// DOI=10.1145/1276377.1276390 http://doi.acm.org/10.1145/1276377.1276390

///////////////////////////////////////////////////////////////////////////
// Inputs

function buildArray(width, height, func) {
  var length = width * height;
  var array = new Array(length);
  var index = 0;
  for (var y = 0; y < height; y++) {
    for (var x = 0; x < width; x++) {
      array[index++] = func(y, x);
    }
  }
  return array;
}

function parImage(seqImage, width, height) {
  return new ParallelArray([height, width], function (y, x) {
    return seqImage[y*width + x];
  });
}

var tinyImage =
  buildArray(20, 5, function(y, x) {
    var ret;
    if (6 <= x && x < 8 && 0 <= y && y < 4)
      ret = ".";
    else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
      ret = "^";
    else if ((x-20)*(x-20)+(y-3)*(y-3) < 2)
      ret = "%";
    else if ((x-1)*(x-1)+(y-3)*(y-3) < 2)
      ret = "@";
    else
      ret = " ";
    return ret.charCodeAt(0) - 32;
  });

var SmallImageWidth = 60;
var SmallImageHeight = 15;
var SmallImage =
  buildArray(SmallImageWidth, SmallImageHeight, function(y, x) {
    var ret;
    if (6 <= x && x < 8 && 0 <= y && y < 7)
      ret = ".";
    else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
      ret = "^";
    else if ((x-40)*(x-40)+(y-6)*(y-6) < 6)
      ret = "%";
    else if ((x-1)*(x-1)+(y-12)*(y-12) < 2)
      ret = "@";
    else
      ret = " ";
    return ret.charCodeAt(0) - 32;
  });

var SmallImagePar = parImage(SmallImage,
                             SmallImageWidth,
                             SmallImageHeight);

var bigImage =
  buildArray(200, 70, function(y, x) {
    var ret;
    if (4 <= x && x < 7 && 10 <= y && y < 40)
      ret = ".";
    else if ((x-150)*(x-150)+(y-13)*(y-13) < 70)
      ret = "^";
    else if ((x-201)*(x-201)+(y-33)*(y-33) < 200)
      ret = "%";
    else if ((x-15)*(x-15)+(y-3)*(y-3) < 7)
      ret = "@";
    else
      ret = " ";
    return ret.charCodeAt(0) - 32;
  });

// randomImage: Nat Nat Nat Nat -> RectArray
function randomImage(w, h, sparsity, variety) {
  return buildArray(w, h, function (x,y) {
    if (Math.random() > 1/sparsity)
      return 0;
    else
      return 1+Math.random()*variety|0;
  });
}

// stripedImage: Nat Nat -> RectArray
function stripedImage(w, h) {
  return buildArray(w, h, function (y, x) {
    return (Math.abs(x%100-y%100) < 10) ? 32 : 0;
  });
}

var massiveImage =
  buildArray(70, 10000, function(y, x) (Math.abs(x%100-y%100) < 10) ? 32 : 0);

function printImage(array, width, height) {
  print("Width", width, "Height", height);
  for (var y = 0; y < height; y++) {
    var line = "";
    for (var x = 0; x < width; x++) {
      var c = array[y*width + x];
      line += String.fromCharCode(c + 32);
    }
    print(line);
  }
}

///////////////////////////////////////////////////////////////////////////
// Common

var SobelX = [[-1.0,  0.0,  1.0],
              [-2.0,  0.0,  2.0],
              [-1.0,  0.0,  1.0]];
var SobelY = [[ 1.0,  2.0,  1.0],
              [ 0.0,  0.0,  0.0],
              [-1.0, -2.0, -1.0]];

// computeEnergy: Array -> RectArray
//
// (The return type is forced upon us, for now at least, until we add
// appropriate API to ParallelArray; there's a dependency from each
// row upon its predecessor, but the contents of each row could be
// computed in parallel.)
function computeEnergy(source, width, height) {
  var energy = new Array(width * height);
  energy[0] = 0;
  for (var y = 0; y < height; y++) {
    for (var x = 0; x < width; x++) {
      var e = source[y*width + x];
      if (y >= 1) {
        var p = energy[(y-1)*width + x];
        if (x > 0) {
          p = Math.min(p, energy[(y-1)*width + x-1]);
        }
        if (x < (width - 1)) {
          p = Math.min(p, energy[(y-1)*width + x+1]);
        }
        e += p;
      }
      energy[y*width + x] = e;
    }
  }
  return energy;
}

// findPath: RectArray -> Array
// (This is inherently sequential.)
function findPath(energy, width, height)
{
  var path = new Array(height);
  var y = height - 1;
  var minPos = 0;
  var minEnergy = energy[y*width + minPos];

  for (var x = 1; x < width; x++) {
    if (energy[y+width + x] < minEnergy) {
      minEnergy = energy[y*width + x];
      minPos = x;
    }
  }

  path[y] = minPos;
  for (y = height - 2; y >= 0; y--) {
    minEnergy = energy[y*width + minPos];
    // var line = energy[y]
    var p = minPos;
    if (p >= 1 && energy[y*width + p-1] < minEnergy) {
      minPos = p-1; minEnergy = energy[y*width + p-1];
    }
    if (p < width - 1 && energy[y*width + p+1] < minEnergy) {
      minPos = p+1; minEnergy = energy[y*width + p+1];
    }
    path[y] = minPos;
  }
  return path;
}

///////////////////////////////////////////////////////////////////////////
// Sequential

function transposeSeq(array, width, height) {
  return buildArray(height, width, function(y, x) {
    return array[x*width + y];
  });
}

// detectEdgesSeq: Array Nat Nat -> Array
function detectEdgesSeq(data, width, height) {
  var data1 = new Array(width * height);
  for (var y = 0; y < height; y++) {
    for (var x = 0; x < width; x++) {
      var total = compute(y, x);
      data1[y*width + x] = total | 0;
    }
  }
  return data1;

  function compute(y, x) {
    var totalX = 0;
    var totalY = 0;

    var offYMin = (y == 0 ? 0 : -1);
    var offYMax = (y == height - 1 ? 0 : 1);
    var offXMin = (x == 0 ? 0 : -1);
    var offXMax = (x == width - 1 ? 0 : 1);

    for (var offY = offYMin; offY <= offYMax; offY++) {
      for (var offX = offXMin; offX <= offXMax; offX++) {
        var e = data[(y + offY) * width + x + offX];
        totalX += e * SobelX[offY + 1][offX + 1];
        totalY += e * SobelY[offY + 1][offX + 1];
      }
    }

    return (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
  }
}

function cutPathHorizontallyBWSeq(array, width, height, path) {
  return buildArray(width-1, height, function (y, x) {
    if (x < path[y]-1)
      return array[y*width + x];
    if (x == path[y]-1)
      return (array[y*width + x] + array[y*width + x+1]) / 2 | 0;
    else
      return array[y*width + x+1];
  });
}

function cutPathVerticallyBWSeq(array, width, height, path) {
  return buildArray(width, height-1, function (y, x) {
    if (y < path[x]-1)
      return array[y*width + x];
    if (y == path[x]-1)
      return (array[y*width + x] + array[(y+1)*width + x]) / 2 | 0;
    else
      return array[(y+1)*width + x];
  });
}

function cutHorizontalSeamBWSeq(array, width, height)
{
  var edges = detectEdgesSeq(array, width, height);
  var energy = computeEnergy(edges, width, height);
  var path = findPath(energy, width, height);
  edges = null; // no longer live
  return cutPathHorizontallyBWSeq(array, width, height, path);
}

function cutVerticalSeamBWSeq(array, width, height)
{
  var arrayT = transposeSeq(array, width, height);
  var edges = detectEdgesSeq(arrayT, height, width);
  var energy = computeEnergy(edges, height, width);
  var path = findPath(energy, height, width);
  edges = null; // no longer live
  return cutPathVerticallyBWSeq(array, width, height, path);
}

function reduceImageBWSeq(image,
                          width, height,
                          newWidth, newHeight,
                          intermediateFunc,
                          finalFunc) {
  while (width > newWidth || height > newHeight) {
    intermediateFunc(image, width, height);

    if (width > newWidth) {
      image = cutHorizontalSeamBWSeq(image, width, height);
      width -= 1;
    }

    if (height > newHeight) {
      image = cutVerticalSeamBWSeq(image, width, height);
      height -= 1;
    }
  }

  finalFunc(image, width, height);
  return image;
}

///////////////////////////////////////////////////////////////////////////
// Parallel

function transposePar(image) {
  var height = image.shape[0];
  var width = image.shape[1];
  return new ParallelArray([width, height], function (y, x) {
    return image.get(x, y);
  });
}

// detectEdgesSeq: Array Nat Nat -> Array
function detectEdgesPar(image) {
  var height = image.shape[0];
  var width = image.shape[1];
  return new ParallelArray([height, width], function (y, x) {
    var totalX = 0;
    var totalY = 0;

    var offYMin = (y == 0 ? 0 : -1);
    var offYMax = (y == height - 1 ? 0 : 1);
    var offXMin = (x == 0 ? 0 : -1);
    var offXMax = (x == width - 1 ? 0 : 1);

    for (var offY = offYMin; offY <= offYMax; offY++) {
      for (var offX = offXMin; offX <= offXMax; offX++) {
        var e = image.get(y + offY, x + offX);
        totalX += e * SobelX[offY + 1][offX + 1];
        totalY += e * SobelY[offY + 1][offX + 1];
      }
    }

    var result = (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
    return result;
  });
}

function cutPathHorizontallyBWPar(image, path) {
  var height = image.shape[0];
  var width = image.shape[1];
  return new ParallelArray([height, width-1], function (y, x) {
    if (x < path[y]-1)
      return image.get(y, x);
    if (x == path[y]-1)
      return (image.get(y, x) + image.get(y, x+1)) / 2 | 0;
    else
      return image.get(y, x+1);
  });
}

function cutPathVerticallyBWPar(image, path) {
  var height = image.shape[0];
  var width = image.shape[1];
  return new ParallelArray([height-1, width], function (y, x) {
    if (y < path[x]-1)
      return image.get(y, x);
    if (y == path[x]-1)
      return (image.get(y, x) + image.get(y+1, x)) / 2 | 0;
    else
      return image.get(y+1, x);
  });
}

function cutHorizontalSeamBWPar(image)
{
  var height = image.shape[0];
  var width = image.shape[1];
  var edges = detectEdgesPar(image);
  var energy = computeEnergy(edges.buffer, width, height);
  var path = findPath(energy, width, height);
  edges = null; // no longer live
  return cutPathHorizontallyBWPar(image, path);
}

function cutVerticalSeamBWPar(image) {
  var height = image.shape[0];
  var width = image.shape[1];
  var imageT = transposePar(image);
  var edges = detectEdgesPar(imageT);
  var energy = computeEnergy(edges.buffer, height, width);
  var path = findPath(energy, height, width);
  edges = null; // no longer live
  return cutPathVerticallyBWPar(image, path);
}

function reduceImageBWPar(image,
                          newWidth, newHeight,
                          intermediateFunc,
                          finalFunc) {
  var height = image.shape[0];
  var width = image.shape[1];
  while (width > newWidth || height > newHeight) {
    intermediateFunc(image.buffer, width, height);

    if (width > newWidth) {
      image = cutHorizontalSeamBWPar(image);
      width -= 1;
    }

    if (height > newHeight) {
      image = cutVerticalSeamBWPar(image);
      height -= 1;
    }
  }

  finalFunc(image.buffer, width, height);
  return image.buffer;
}

///////////////////////////////////////////////////////////////////////////
// Benchmarking via run.sh

var BenchmarkImageWidth = 512;
var BenchmarkImageHeight = 256;
var BenchmarkImage = stripedImage(BenchmarkImageWidth,
                                  BenchmarkImageHeight);
var BenchmarkImagePar = parImage(BenchmarkImage,
                                 BenchmarkImageWidth,
                                 BenchmarkImageHeight);

var benchmarking = (typeof(MODE) != "undefined");
if (benchmarking) {
  load(libdir + "util.js");
  benchmark("LIQUID-RESIZE", 1, DEFAULT_MEASURE,
            function() {
              return reduceImageBWSeq(
                BenchmarkImage,
                BenchmarkImageWidth, BenchmarkImageHeight,
                BenchmarkImageWidth/2, BenchmarkImageHeight/2,
                function() {},
                function() {});
            },

            function() {
              return reduceImageBWPar(
                BenchmarkImagePar,
                BenchmarkImageWidth/2, BenchmarkImageHeight/2,
                function() {},
                function() {});
            });
}

///////////////////////////////////////////////////////////////////////////
// Running (sanity check)

if (!benchmarking) {
  var seqData =
    reduceImageBWSeq(SmallImage, SmallImageWidth, SmallImageHeight,
                     SmallImageWidth - 15, SmallImageHeight - 10,
                     function() {},
                     printImage);

  var parData =
    reduceImageBWPar(SmallImagePar,
                     SmallImageWidth - 15, SmallImageHeight - 10,
                     function() {},
                     printImage);

  assertEq(seqData, parData);
}