#include <cassert>
#include "processing.h"

using namespace std;

// REQUIRES: img points to a valid Image
// MODIFIES: *img
// EFFECTS:  The image is rotated 90 degrees to the left (counterclockwise).
void rotate_left(Image* img) {

  // for convenience
  int width = Image_width(img);
  int height = Image_height(img);

  // auxiliary image to temporarily store rotated image
  Image *aux = new Image;
  Image_init(aux, height, width); // width and height switched

  // iterate through pixels and place each where it goes in temp
  for (int r = 0; r < height; ++r) {
    for (int c = 0; c < width; ++c) {
      Image_set_pixel(aux, width - 1 - c, r, Image_get_pixel(img, r, c));
    }
  }

  // Copy data back into original
  *img = *aux;
  delete aux;
}

// REQUIRES: img points to a valid Image.
// MODIFIES: *img
// EFFECTS:  The image is rotated 90 degrees to the right (clockwise).
void rotate_right(Image* img){

  // for convenience
  int width = Image_width(img);
  int height = Image_height(img);

  // auxiliary image to temporarily store rotated image
  Image *aux = new Image;
  Image_init(aux, height, width); // width and height switched

  // iterate through pixels and place each where it goes in temp
  for (int r = 0; r < height; ++r) {
    for (int c = 0; c < width; ++c) {
      Image_set_pixel(aux, c, height - 1 - r, Image_get_pixel(img, r, c));
    }
  }

  // Copy data back into original
  *img = *aux;
  delete aux;
}

static int squared_difference(Pixel p1, Pixel p2) {
  int dr = p2.r - p1.r;
  int dg = p2.g - p1.g;
  int db = p2.b - p1.b;
  // Divide by 100 is to avoid possible overflows
  // later on in the algorithm.
  return (dr*dr + dg*dg + db*db) / 100;
}

// REQUIRES: img points to a valid Image.
//           energy points to a Matrix.
// MODIFIES: *energy
// EFFECTS:  energy serves as an "output parameter".
//           The Matrix pointed to by energy is initialized to be the same
//           size as the given Image, and then the energy matrix for that
//           image is computed and written into it.

void compute_energy_matrix(const Image* img, Matrix* energy) {
    Matrix_init(energy, Image_width(img), Image_height(img));
    Matrix_fill(energy, 0);
    for (int r = 1; r < Matrix_height(energy) - 1; r++) {
        for (int c = 1; c < Matrix_width(energy) - 1; c++)  {
            Pixel pn = Image_get_pixel(img, r - 1, c);
            Pixel ps = Image_get_pixel(img, r + 1, c);
            Pixel pw = Image_get_pixel(img, r, c - 1);
            Pixel pe = Image_get_pixel(img, r, c + 1);
            *Matrix_at(energy, r, c) = 
              squared_difference(pn, ps) + squared_difference(pw, pe);
        }
    }
    Matrix_fill_border(energy, Matrix_max(energy));
}


// REQUIRES: energy points to a valid Matrix.
//           cost points to a Matrix.
//           energy and cost aren't pointing to the same Matrix
// MODIFIES: *cost
// EFFECTS:  cost serves as an "output parameter".
//           The Matrix pointed to by cost is initialized to be the same
//           size as the given energy Matrix, and then the cost matrix is
//           computed and written into it.

void compute_vertical_cost_matrix(const Matrix* energy, Matrix *cost) {
    Matrix_init(cost, Matrix_width(energy), Matrix_height(energy));
    for (int c = 0; c < Matrix_width(cost); c++)   {
        *Matrix_at(cost, 0, c) = *Matrix_at(energy, 0, c);
    }
    for (int r = 1; r < Matrix_height(cost); r++)  {
        for (int c = 0; c < Matrix_width(cost); c++)   {
            if (c == 0) {
                *Matrix_at(cost, r, c) = *Matrix_at(energy, r, c) 
                  + Matrix_min_value_in_row(cost, r - 1, c, c + 2);
            }
            else if (c == Matrix_width(cost) - 1)   {
                *Matrix_at(cost, r, c) = *Matrix_at(energy, r, c) 
                  + Matrix_min_value_in_row(cost, r - 1, c - 1, c + 1);
            }
            else    {
                *Matrix_at(cost, r, c) = *Matrix_at(energy, r, c) 
                  + Matrix_min_value_in_row(cost, r - 1, c - 1, c + 2);
            }
        }
    }
}


// REQUIRES: cost points to a valid Matrix
//           seam points to an array
//           the size of seam is >= Matrix_height(cost)
// MODIFIES: seam[0]...seam[Matrix_height(cost)-1]
// EFFECTS:  seam serves as an "output parameter".
//           The vertical seam with the minimal cost according to the given
//           cost matrix is found and the seam array is filled with the column
//           numbers for each pixel along the seam, with the pixel for each
//           row r placed at seam[r]. While determining the seam, if any pixels
//           tie for lowest cost, the leftmost one (i.e. with the lowest
//           column number) is used.

void find_minimal_vertical_seam(const Matrix* cost, int seam[]) {
    int i = Matrix_height(cost) - 1;
    seam[i] = Matrix_column_of_min_value_in_row
      (cost, Matrix_height(cost) - 1, 0, Matrix_width(cost) - 1);
    i -= 1; 
    for (int r = Matrix_height(cost) - 2; r >= 0; r--)  {
        int c = seam[i + 1];
        if (c == 0)  {
            seam[i] = Matrix_column_of_min_value_in_row(cost, r, c, c + 2);
            i -= 1;
        }
        else if (c == Matrix_width(cost) - 1) {
            seam[i] = Matrix_column_of_min_value_in_row(cost, r, c - 1, c + 1);
            i -= 1;
        }
        else    {
            seam[i] = Matrix_column_of_min_value_in_row(cost, r, c - 1, c + 2);
            i -= 1;
        }
    }
}


// REQUIRES: img points to a valid Image with width >= 2
//           seam points to an array
//           the size of seam is == Image_height(img)
//           each element x in seam satisfies 0 <= x < Image_width(img)
// MODIFIES: *img
// EFFECTS:  Removes the given vertical seam from the Image. That is, one
//           pixel will be removed from every row in the image. The pixel
//           removed from row r will be the one with column equal to seam[r].
//           The width of the image will be one less than before.
/
void remove_vertical_seam(Image *img, const int seam[]) {
    Image *aux_img = new Image;
    Image_init(aux_img, Image_width(img) - 1, Image_height(img));
    for (int r = 0; r < Image_height(aux_img); r++) {
        for (int c = 0; c < Image_width(aux_img); c++)  {
            if (c < seam[r])    {
              Image_set_pixel(aux_img, r, c, Image_get_pixel(img, r, c));
            }
            if (c >= seam[r])   {
              Image_set_pixel(aux_img, r, c, Image_get_pixel(img, r, c + 1));
            }
        }
    }
    *img = *aux_img;
    delete aux_img;
}


// REQUIRES: img points to a valid Image
//           0 < newWidth && newWidth <= Image_width(img)
// MODIFIES: *img
// EFFECTS:  Reduces the width of the given Image to be newWidth by using
//           the seam carving algorithm. 

void seam_carve_width(Image *img, int newWidth) {
  assert(0 < newWidth && newWidth <= Image_width(img));

  Matrix *energy = new Matrix;
  Matrix *cost = new Matrix;
  int *seam = new int[Image_height(img)];

  while (Image_width(img) > newWidth) {
    compute_energy_matrix(img, energy);
    compute_vertical_cost_matrix(energy, cost);
    find_minimal_vertical_seam(cost, seam);
    remove_vertical_seam(img, seam);
  }

  delete energy;
  delete cost;
  delete[] seam;
}

// REQUIRES: img points to a valid Image
//           0 < newHeight && newHeight <= Image_height(img)
// MODIFIES: *img
// EFFECTS:  Reduces the height of the given Image to be newHeight.

void seam_carve_height(Image *img, int newHeight) {
  assert(0 < newHeight && newHeight <= Image_height(img));

  rotate_left(img);
  seam_carve_width(img, newHeight);
  rotate_right(img);
}

// REQUIRES: img points to a valid Image
//           0 < newWidth && newWidth <= Image_width(img)
//           0 < newHeight && newHeight <= Image_height(img)
// MODIFIES: *img
// EFFECTS:  Reduces the width and height of the given Image to be newWidth
//           and newHeight, respectively.

void seam_carve(Image *img, int newWidth, int newHeight) {
  assert(0 < newWidth && newWidth <= Image_width(img));
  assert(0 < newHeight && newHeight <= Image_height(img));

  seam_carve_width(img, newWidth);
  seam_carve_height(img, newHeight);
}