#include "length.h"
#include "grid.h"
#include "gradient.h"
#include "machine.h"
#include "slice.h"

#include <algorithm>
#include <vector>

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <unistd.h>

char const* debug_dir = NULL;

char const* debug_file(depth at, char const* name) {
  static char fn[PATH_MAX];
  snprintf(fn, sizeof(fn), "%s/%05d.%s", debug_dir, at, name);
  mkdir(debug_dir, 0777);
  return fn;
}

double test_path(int sx, int sy, int ex, int ey, slice const& s) {
  int total = 0, count = 0;
  for (path bp(s.block, sx, sy, ex, ey), cp(s.cut, sx, sy, ex, ey);
      !bp.done() && !cp.done() && bp.amount() == 0 && cp.amount() > 0;
       bp.next(), cp.next()) {
    total += cp.amount();
    ++count;
  }
  return total > 0 ? double(total) / count : 0;
}

double scan_align(slice const& s,
    int seek, int go, int x, int y,
    int* outx, int* outy, int* dx, int* dy) {
  double best = 0;
  *outx = x; *outy = y;
  int tx = *dx, ty = *dy;
  for (int i = 0; i < 4; ++i) {
    double cut = test_path(x, y, x + tx * go, y + ty * go, s);
    if (cut > best) {
      best = cut;
      *outx = x; *outy = y; *dx = tx; *dy = ty;
    }

    for (path p(s.block, x, y, x + tx * seek, y + ty * seek);
        !p.done() && p.amount() == 0; p.next()) {
      cut = test_path(p.x, p.y, p.x - ty * go, p.y + tx * go, s);
      if (cut > best) {
        best = cut;
        *outx = p.x; *outy = p.y; *dx = -ty; *dy = tx;
      }

      cut = test_path(p.x, p.y, p.x + ty * go, p.y - tx * go, s);
      if (cut > best) {
        best = cut;
        *outx = p.x; *outy = p.y; *dx = ty; *dy = -tx;
      }
    }

    int tmp = tx; tx = -ty; ty = tmp;
  }

  return best;
}

int find_landing(slice const& s, int x, int y, int* outx, int* outy) {
  int dx = 1, dy = 0, len = 1, maxx = 0, maxy = 0;
  for (int i = 0; i < EDGES; ++i) {
    maxx = std::max(maxx, std::max(xsize(s.cut[i]), xsize(s.block[i])));
    maxy = std::max(maxy, std::max(ysize(s.cut[i]), ysize(s.block[i])));
  }

  int bn = 0, cn = 0;
  for (path bp(s.block, -1, -1, x, y), cp(s.cut, -1, -1, x, y);
       !bp.done() && !cp.done(); bp.next(), cp.next()) {
    bn += bp.net(); cn += cp.net();
  }

  while (x >= 0 || y >= 0 || x + len < maxx || y + len < maxy) {
    int ex = x + dx * len, ey = y + dy * len;
    for (path bp(s.block, x, y, ex, ey), cp(s.cut, x, y, ex, ey);
        !bp.done() && !cp.done(); bp.next(), cp.next()) {
      bn += bp.net(); cn += cp.net();
      if (bp.forward == EDGES && (
          bp.x < 0 && dx < 0 || bp.x >= maxx && dx > 0 ||
          bp.y < 0 && dy < 0 || bp.y >= maxy && dy > 0)) {
        break;
      }
      if (bn == 0 && cn > 0) {
        *outx = bp.x; *outy = bp.y;
        return cn;
      }
    }

    x = ex; y = ey;
    if (dx == 0) ++len;  // every other side
    int tmp = dx; dx = -dy; dy = tmp;
  }

  return 0;
}

void cut_slice(
    depth at, grid const& goal, grid const& bit,
    grid* state, machine *mach) {
  slice slice;
  make(at, &goal, &bit, state, &slice);

  grid* map = NULL;
  FILE* log = NULL;
  if (debug_dir) {
    map = new grid;
    debug_map(slice, map);
    write_ppm(*map, debug_file(at, "before.ppm"));
    map->clear();

    log = fopen(debug_file(at, "log.txt"), "w");
    if (log == NULL) perror(debug_file(at, "log.txt"));
  }

  const int go = std::max(xsize(bit), ysize(bit));
  const int seek = go / 2;
  const int run = std::max(xsize(*state), ysize(*state));

  int dx = 1, dy = 0, lx, ly;
  while (int land = find_landing(slice, mach->x, mach->y, &lx, &ly)) {
    if (log) fprintf(log, "land: %d,%d (%d)\n", lx, ly, land);

    int scanx, scany;
    float score = scan_align(slice, seek, go, lx, ly, &scanx, &scany, &dx, &dy);
    do {
      if (mach->at == slice.at && (mach->x != scanx || mach->y != scany)) {
        path xp(slice.block, mach->x, mach->y, scanx, mach->y);
        while (!xp.done() && xp.amount() == 0) xp.next();
        if (xp.done()) {
          path yp(slice.block, scanx, mach->y, scanx, scany);
          while (!yp.done() && yp.amount() == 0) yp.next();
          if (yp.done()) {
            int cut = mill(scanx, mach->y, &slice, mach, map)
                    + mill(scanx, scany, &slice, mach, map);
            if (log)
              fprintf(log, "xy: %d,%d (%d): %.2f\n", scanx, scany, cut, score);
          }
        }
      }

      if (mach->at == slice.at && (mach->x != scanx || mach->y != scany)) {
        path yp(slice.block, mach->x, mach->y, mach->x, scany);
        while (!yp.done() && yp.amount() == 0) yp.next();
        if (yp.done()) {
          path xp(slice.block, mach->x, scany, scanx, scany);
          while (!xp.done() && xp.amount() == 0) xp.next();
          if (xp.done()) {
            int cut = mill(mach->x, scany, &slice, mach, map)
                    + mill(scanx, scany, &slice, mach, map);
            if (log)
              fprintf(log, "yx: %d,%d (%d): %.2f\n", scanx, scany, cut, score);
          }
        }
      }

      if (mach->x != scanx || mach->y != scany || mach->at != slice.at) {
        if (log) fprintf(log, "jump: %d,%d: %.2f\n", scanx, scany, score);
        drill(scanx, scany, &slice, mach, map);
      }

      int last = 1, ex = scanx, ey = scany;
      for (path bp(slice.block, scanx, scany, scanx + dx*run, scany + dy*run),
                cp(slice.cut, scanx, scany, scanx + dx*run, scany + dy*run);
          !bp.done() && !cp.done() && bp.amount() == 0 && cp.amount() >= last;
           bp.next(), cp.next()) {
        ex = cp.x; ey = cp.y;
        last = cp.amount();
      }

      int cut = mill(ex, ey, &slice, mach, map);
      if (log) fprintf(log, "mill: %d,%d (%d)\n", ex, ey, cut);
      score = scan_align(slice, seek, go, ex, ey, &scanx, &scany, &dx, &dy);
    } while (score > 0);
  }

  if (log) {
    fprintf(log, "done: %d,%d", mach->x, mach->y);
    fclose(log);
  }
  if (map) {
    debug_map(slice, map);
    write_ppm(*map, debug_file(at, "after.ppm"));
    delete map;
  }
}

int main(int argc, char** argv) {
  char const* output = NULL;
  depth slice = 0;
  int size = 0;

  int opt;
  while ((opt = getopt(argc, argv, "d:o:s:t:")) != -1) {
    switch (opt) {
      case 'd': debug_dir = optarg; break;
      case 'o': output = optarg; break;
      case 's': slice = parse_length(optarg); break;
      case 't': size = parse_length(optarg); break;
      case '?': exit(2);
    }
  }

  if (argc < optind + 2) {
    fprintf(stderr,
        "usage: %s [flags] start.pgm goal.pgm > out.rml\n",
        argv[0]);
    return 2;
  }

  if (slice == 0) {
    fprintf(stderr,"error: slice size (-s) required\n");
    return 2;
  }

  if (size == 0) {
    fprintf(stderr, "error: tool size (-t) required\n");
    return 2;
  }

  grid state, goal;
  read_pgm(argv[optind], &state);
  read_pgm(argv[optind + 1], &goal);

  grid bit;
  circle(size, &bit);

  // find the uppermost surface of material to cut.
  depth at = BOTTOM;
  for (int x = 0; x < xsize(state); ++x)
    for (int y = 0; y < ysize(state); ++y)
      at = std::min(at, state[x][y]);

  // quantize the cutting level for consistent repeated cuts
  at = (at / slice + 1) * slice;
  machine mach(bit, 10, 5, 15);
  for (;;) {
    cut_slice(at, goal, bit, &state, &mach);

    bool keep_going = false;
    for (int x = 0; !keep_going && x < xsize(state) && x < xsize(goal); ++x)
      for (int y = 0; !keep_going && y < ysize(state) && y < ysize(goal); ++y)
        if (goal[x][y] < BOTTOM && goal[x][y] > at && state[x][y] >= at)
          keep_going = true;

    if (!keep_going) break;
    at += slice;
  }

  mach.stop();
  if (output != NULL) write_pgm(state, output);
  return 0;
}