/* metrics.cc -- compute metrics about an 8-puzzle state.
   Copyright (C) 2007  Casey Marshall <csm@soe.ucsc.edu> */


#include "puzzle_state.h"

#define XVAL(n) ((n % 3) + 1)
#define YVAL(n) ((n / 3) + 1)

inline int abs(int x) { if (x >= 0) return x; return -x; }
inline int md(int x1, int x2, int y1, int y2) { return abs(x1 - x2) + abs(y1 - y2); }

typedef std::pair<int, int> point;

point
location_of(int x, puzzle_state& state)
{
  int i;
  for (i = 0; i < 9; i++)
    {
      if (x == (int) state.state[i])
        break;
    }
  return std::make_pair<int, int>(XVAL(i), YVAL(i));
}

int
edge_distance(puzzle_state& state)
{
  int distance = 0;
  for (int i = 0; i < 9; i++)
    {
      switch ((int) state.state[i])
        {
        case 1:
        case 2:
          distance += YVAL(i) - 1;
          break;

        case 3:
        case 4:
          distance += 3 - XVAL(i);
          break;

        case 5:
        case 6:
          distance += 3 - YVAL(i);
          break;

        case 7:
        case 8:
          distance += XVAL(i) - 1;
          break;
        }
    }
  return distance;
}

int
neighbor_distance(puzzle_state& state, bool withBlank)
{
  int distance = 0;
  for (int i = 0; i < 9; i++)
    {
      point p = std::make_pair<int, int>(XVAL(i), YVAL(i));
      switch ((int) state.state[i])
        {
        case 1:
          {
            point p2 = location_of(2, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(8, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
          }
          break;

        case 2:
          {
            point p2 = location_of(1, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(3, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            if (withBlank)
              {
                p2 = location_of(BLANK, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
              }
          }
          break;

        case 3:
          {
            point p2 = location_of(2, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(4, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
          }
          break;

        case 4:
          {
            point p2 = location_of(3, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(5, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            if (withBlank)
              {
                p2 = location_of(BLANK, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
              }
          }
          break;

        case 5:
          {
            point p2 = location_of(4, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(6, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
          }
          break;

        case 6:
          {
            point p2 = location_of(5, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(7, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            if (withBlank)
              {
                p2 = location_of(BLANK, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
              }
          }
          break;

        case 7:
          {
            point p2 = location_of(8, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(6, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
          }
          break;

        case 8:
          {
            point p2 = location_of(1, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            p2 = location_of(7, state);
            distance += md(p.first, p2.first, p.second, p2.second) - 1;
            if (withBlank)
              {
                p2 = location_of(BLANK, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
              }
          }
          break;

        case BLANK:
          {
            if (withBlank)
              {
                point p2 = location_of(2, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
                p2 = location_of(4, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
                p2 = location_of(6, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
                p2 = location_of(8, state);
                distance += md(p.first, p2.first, p.second, p2.second) - 1;
              }
          }
          break;

        default:
          std::cerr << "error! invalid tile number "
                    << ((int) state.state[i]) << std::endl;
          abort();
        }
    }

  return distance;
}

int
manhattan_distance (puzzle_state& state, bool withBlank)
{
  int distance = 0;
  for (int i = 0; i < 9; i++)
    {
      int s = state.state[i] & 0xFF;
      switch (s)
        {
        case 1:
          distance += md(XVAL(i),1,YVAL(i),1);
          break;

        case 2:
          distance += md(XVAL(i),2,YVAL(i),1);
          break;

        case 3:
          distance += md(XVAL(i),3,YVAL(i),1);
          break;

        case 4:
          distance += md(XVAL(i),3,YVAL(i),2);
          break;

        case 5:
          distance += md(XVAL(i),3,YVAL(i),3);
          break;

        case 6:
          distance += md(XVAL(i),2,YVAL(i),3);
          break;

        case 7:
          distance += md(XVAL(i),1,YVAL(i),3);
          break;

        case 8:
          distance += md(XVAL(i),1,YVAL(i),2);
          break;

        case BLANK:
          if (withBlank)
            distance += md(XVAL(i),2,YVAL(i),2);
          break;
        }
    }
  return distance;
}