#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <string.h>
#include <assert.h>
#include <sys/time.h>
#include <unistd.h>

#include "city.h"
#include "packets.h"
#include "log.h"
#include "map.h"
#include "mem.h"
#include "shared.h"		/* for MIN() */
#include "hash.h"
#include "fcintl.h"
#include "unittype.h"

#include "path_finding.h"

#define SPECLIST_TAG cell
#include "speclist.h"
#define SPECLIST_TAG cell
#include "speclist_c.h"

/******* defines, structs, globals, forward declarations  ************/
#define HASH_ACTIONS_LOG_LEVEL			LOG_DEBUG
#define DISCARDED_DIRS_LOG_LEVEL		LOG_DEBUG

#define DEBUG_MAIN_DIJKSTRA			FALSE
#define LIST_CHOICES				FALSE
#define PRINT_RETURNED_PATHS			FALSE

struct cell {
  struct map_position pos;
  int turns[NUM_TURNS], points_left[NUM_TURNS];
  int railroad, steps;

  /* costs */
  int BMC_of_last_step, FC_of_last_step, total_FC, COP;

  struct cell *prev;
  enum direction8 dir_from_prev_to_pos;
  enum {
    IS_NONE, IS_FRONTIER, IS_KNOWN
  } type;

  /* cached values */
  bool is_my_zoc, is_allied_tile;
  int extra_cost1;
  enum known_type known;
};

struct pf_map {
  /*
   * Maps from position to cells.
   */
  struct hash_table *cells;
  struct cell_list flat_frontier;
  struct pf_parameter parameter;

  /* cached values */
  bool zoc_used;
  enum turn_index turn_index;
};

/**** static methods *********************************************/

static unsigned int hash_function(const void *key, unsigned int num_buckets)
{
  const struct map_position *pos = (const struct map_position *) key;
  assert(sizeof(unsigned int) >= 4);
  return ((pos->x << 16) + pos->y) % num_buckets;
}

static int hash_cmp_function(const void *value1, const void *value2)
{
  const struct map_position *pos1, *pos2;

  pos1 = (const struct map_position *) value1;
  pos2 = (const struct map_position *) value2;

  if ((pos1->x == pos2->x) && (pos1->y == pos2->y)) {
    return 0;
  }
  return 1;
}

static int cmp_function(const void *value1, const void *value2)
{
  const struct cell *cell1, *cell2;
  int t;

  cell1 = (const struct cell *) value1;
  cell2 = (const struct cell *) value2;

  t = cell1->COP - cell2->COP;
  if (t != 0) {
    return t;
  }
  t = cell1->railroad - cell2->railroad;
  if (t != 0) {
    return t;
  }
  t = cell1->steps - cell2->steps;
  if (t != 0) {
    return t;
  }
  return 0;
}

static int list_cmp_function(const void *value1, const void *value2)
{
  return cmp_function(*(const void **) value1, *(const void **) value2);
}

static void destroy_cell(struct cell *cell)
{
  free(cell);
}

static void insert_cell_into_hash(struct hash_table *hash, struct cell *cell)
{
  bool inserted;

  freelog(HASH_ACTIONS_LOG_LEVEL, "try to insert cell(%d,%d) into %p",
	  cell->pos.x, cell->pos.y, hash);
  assert(!hash_key_exists(hash, &cell->pos));
  inserted = hash_insert(hash, &cell->pos, cell);
  assert(inserted);
}

static struct cell *get_cell(pf_map_t pf_map,
			     int x, int y, bool create_if_necessary)
{
  struct cell *result;
  struct map_position pos;

  pos.x = x;
  pos.y = y;

  freelog(HASH_ACTIONS_LOG_LEVEL,
	  "try to look up cell(%d,%d) create_if_necessary=%d", x, y,
	  create_if_necessary);
  result = (struct cell *) hash_lookup_data(pf_map->cells, &pos);
  freelog(HASH_ACTIONS_LOG_LEVEL, "%s", result ? "yes" : "no");
  if (create_if_necessary && !result) {
    result = fc_malloc(sizeof(struct cell));

    result->pos.x = x;
    result->pos.y = y;
    result->type = IS_NONE;
    result->known =
	pf_map->parameter.get_known(x, y, pf_map->parameter.owner);

    if (pf_map->zoc_used) {
      result->is_my_zoc = (map_get_city(x, y) || map_get_terrain(x, y) ==
			   T_OCEAN
			   || is_my_zoc(pf_map->parameter.owner, x, y));
      result->is_allied_tile =
	  is_allied_unit_tile(map_get_tile(x, y),
			      pf_map->parameter.owner) != NULL;
    }
    if (pf_map->parameter.extra_cost1) {
      result->extra_cost1 =
	  pf_map->parameter.extra_cost1(x, y, result->known,
					pf_map->parameter.user_data1);
      assert(result->extra_cost1 >= 0);
    } else {
      result->extra_cost1 = 0;
    }
    insert_cell_into_hash(pf_map->cells, result);
  }

  return result;
}

/*
 * Stripped down version of test_unit_move_to_tile
 */
static bool can_unit_type_move_from_to(enum unit_move_type
				       move_type,
				       unsigned int flags,
				       struct player *owner, int src_x,
				       int src_y, int dest_x, int dest_y)
{
  struct tile *pfromtile, *ptotile;
  struct city *pcity;

  pfromtile = map_get_tile(src_x, src_y);
  ptotile = map_get_tile(dest_x, dest_y);

  if (move_type == LAND_MOVING) {
    /* 5) */
    if (ptotile->terrain == T_OCEAN &&
	ground_unit_transporter_capacity(dest_x, dest_y, owner) <= 0) {
      return FALSE;
    }

    /* Moving from ocean */
    if (pfromtile->terrain == T_OCEAN) {
      /* 6) */
      if (!TEST_BIT(flags, F_MARINES)
	  && is_enemy_city_tile(ptotile, owner)) {
	return FALSE;
      }
    }
  } else if (move_type == SEA_MOVING) {
    /* 7) */
    if (ptotile->terrain != T_OCEAN
	&& !is_allied_city_tile(ptotile, owner)) {
      return FALSE;
    }
  }

  /* 8) */
  if (is_non_attack_unit_tile(ptotile, owner)) {
    return MR_NO_WAR;
  }

  /* 9) */
  pcity = ptotile->city;
  if (pcity && pplayers_non_attack(city_owner(pcity), owner)) {
    return FALSE;
  }
  return TRUE;
}

/*
 * Modified version of common/map.c:map_move_cost()
 */
/***************************************************************
  The cost to move punit from where it is to tile x,y.
  It is assumed the move is a valid one, e.g. the tiles are adjacent.
***************************************************************/
static int map_move_cost2(enum unit_move_type move_type, unsigned int flags,
			  int src_x, int src_y, int dest_x, int dest_y)
{
  struct tile *src_tile = map_get_tile(src_x, src_y);
  struct tile *dest_tile = map_get_tile(dest_x, dest_y);

  if (move_type != LAND_MOVING) {
    return SINGLE_MOVE;
  }

  if (tile_has_special(src_tile, S_RAILROAD) &&
      tile_has_special(dest_tile, S_RAILROAD)) {
    return MOVE_COST_RAIL;
  }

  if (TEST_BIT(flags, F_IGTER)) {
    return SINGLE_MOVE / 3;
  }

  if (tile_has_special(src_tile, S_ROAD) &&
      tile_has_special(dest_tile, S_ROAD)) {
    return MOVE_COST_ROAD;
  }

  if (((src_tile->terrain == T_RIVER) && (dest_tile->terrain == T_RIVER)) ||
      (tile_has_special(src_tile, S_RIVER)
       && tile_has_special(dest_tile, S_RIVER))) {
    bool cardinal_move = is_move_cardinal(src_x, src_y, dest_x, dest_y);
    switch (terrain_control.river_move_mode) {
    case RMV_NORMAL:
      break;
    case RMV_FAST_STRICT:
      if (cardinal_move)
	return MOVE_COST_RIVER;
      break;
    case RMV_FAST_RELAXED:
      if (cardinal_move)
	return MOVE_COST_RIVER;
      else
	return 2 * MOVE_COST_RIVER;
    case RMV_FAST_ALWAYS:
      return MOVE_COST_RIVER;
    default:
      break;
    }
  }

  return (get_tile_type(dest_tile->terrain)->movement_cost * SINGLE_MOVE);
}

static void update_min(int cost, int move_rate, int *points_left, int *turns)
{
  assert(cost >= 0);
  assert(*points_left >= 0 && *points_left <= move_rate);

  if (*points_left == 0) {
    (*turns)++;
    *points_left = move_rate;
  }

  if (*points_left >= cost) {
    *points_left -= cost;
  } else {
    *points_left = 0;
  }
}

static void update_max(int cost, int move_rate, int *points_left, int *turns)
{
  assert(cost >= 0);
  assert(*points_left >= 0 && *points_left <= move_rate);

  if (*points_left >= cost) {
    *points_left -= cost;
  } else {
    if (*points_left == move_rate) {
      *points_left = 0;
    } else {
      (*turns)++;
      *points_left = move_rate - cost;
      if (*points_left < 0)
	*points_left = 0;
    }
  }
}

static void update_average(int cost, int move_rate, int min_points_left,
			   int max_points_left,
			   int min_turns,
			   int max_turns, int *points_left, int *turns)
{
  // FIXME
  *turns = (min_turns + max_turns) / 2;
  *points_left = (min_points_left + max_points_left) / 2;
}

static void calculate_costs_for_move(pf_map_t pf_map, struct cell *dest)
{
  struct cell *src = dest->prev;
  struct tile *psrctile = map_get_tile(src->pos.x, src->pos.y);
  struct tile *pdesttile = map_get_tile(dest->pos.x, dest->pos.y);
  int BMC, TC, i, move_rate = pf_map->parameter.move_rate;

  if (pf_map->parameter.restriction == GOTO_MOVE_STRAIGHTEST) {
    BMC = 1;
  } else if (dest->known == TILE_UNKNOWN) {
    BMC = 0;
    assert(dest->extra_cost1 > 0);
  } else {
    if (pf_map->parameter.move_backward) {
      BMC = map_move_cost2(pf_map->parameter.move_type,
			   pf_map->parameter.flags, dest->pos.x, dest->pos.y,
			   src->pos.x, src->pos.y);
    } else {
      BMC = map_move_cost2(pf_map->parameter.move_type,
			   pf_map->parameter.flags, src->pos.x,
			   src->pos.y, dest->pos.x, dest->pos.y);
    }
  }

  freelog(LOG_DEBUG,
	  "move from (%d,%d)[%s] to (%d,%d)[%s] costs %d points, move_rate=%d",
	  src->pos.x, src->pos.y,
	  get_tile_type(map_get_terrain
			(src->pos.x, src->pos.y))->terrain_name, dest->pos.x,
	  dest->pos.y,
	  get_tile_type(map_get_terrain
			(dest->pos.x, dest->pos.y))->terrain_name,
	  BMC, move_rate);

  for (i = 0; i < NUM_TURNS; i++) {
    dest->turns[i] = src->turns[i];
    dest->points_left[i] = src->points_left[i];
  }
  dest->railroad = src->railroad;
  dest->steps = src->steps;
  dest->total_FC = src->total_FC;

  dest->steps++;

  if (tile_has_special(psrctile, S_RAILROAD)
      && tile_has_special(pdesttile, S_RAILROAD)) {
    dest->railroad++;
  }

  dest->BMC_of_last_step = BMC;
  dest->FC_of_last_step =
      dest->BMC_of_last_step * PF_BMC_FACTOR + dest->extra_cost1;
  assert(dest->FC_of_last_step > 0
	 && dest->FC_of_last_step < PF_IGNORE_COST);
  dest->total_FC += dest->FC_of_last_step;
  assert(dest->total_FC > 0 && dest->total_FC < PF_IGNORE_COST);
  
  if (pf_map->parameter.turn_mode == TC_MINIMUM
      || pf_map->parameter.turn_mode == TC_AVERAGE) {
    update_min(BMC, move_rate, &dest->points_left[MINIMAL_TURN],
	       &dest->turns[MINIMAL_TURN]);
  }

  if (pf_map->parameter.turn_mode == TC_MAXIMUM
      || pf_map->parameter.turn_mode == TC_AVERAGE) {
    update_max(BMC, move_rate, &dest->points_left[MAXIMAL_TURN],
	       &dest->turns[MAXIMAL_TURN]);
  }

  if (pf_map->parameter.turn_mode == TC_AVERAGE) {
    update_average(BMC, move_rate,
		   dest->points_left[MINIMAL_TURN],
		   dest->points_left[MAXIMAL_TURN],
		   dest->turns[MINIMAL_TURN], dest->turns[MAXIMAL_TURN],
		   &dest->points_left[AVERAGE_TURN],
		   &dest->turns[AVERAGE_TURN]);
  }

  switch (pf_map->parameter.turn_mode) {
  case TC_NONE:
    TC = 0;
    break;
  case TC_MINIMUM:
  case TC_AVERAGE:
  case TC_MAXIMUM:
    TC =
	pf_map->parameter.turn_cost_factor *
	dest->turns[pf_map->turn_index] +
	pf_map->parameter.move_cost_factor * (move_rate -
					      dest->
					      points_left
					      [pf_map->turn_index]);
    break;
  default:
    assert(0);
  }
  dest->COP = dest->total_FC + TC;
  assert(dest->COP > 0 && dest->COP < PF_IGNORE_COST);
}

static void print_cell(char *msg, struct cell *cell)
{
  char *type = NULL;

  if (cell->type == IS_NONE)
    type = "N";
  else if (cell->type == IS_FRONTIER)
    type = "F";
  else if (cell->type == IS_KNOWN)
    type = "K";

  freelog(LOG_NORMAL,
	  "%s cell [%s] at (%d,%d) (t={%d/%d/%d},p={%d/%d/%d},r=%d,s=%d,F=%d,C=%d) dir=%s",
	  msg, type, cell->pos.x, cell->pos.y, cell->turns[MINIMAL_TURN],
	  cell->turns[AVERAGE_TURN],
	  cell->turns[MAXIMAL_TURN],
	  cell->points_left[MINIMAL_TURN],
	  cell->points_left[AVERAGE_TURN],
	  cell->points_left[MAXIMAL_TURN],
	  cell->railroad, cell->steps,
	  cell->total_FC,
	  cell->COP,
	  dir_get_name(cell->dir_from_prev_to_pos));
}

static void make_frontier(pf_map_t pf_map, struct cell *cell)
{
  assert(cell->type == IS_NONE);
  cell->type = IS_FRONTIER;
  cell_list_insert(&pf_map->flat_frontier, cell);
}

static void copy_cell(struct cell *dest, const struct cell *src)
{
  assert(src->pos.x == dest->pos.x);
  assert(src->pos.y == dest->pos.y);

  memcpy(dest, src, sizeof(*dest));
}

static void change_to_known(pf_map_t pf_map, struct cell *cell)
{
  assert(cell);
  cell_list_unlink(&pf_map->flat_frontier, cell);

  assert(cell->type == IS_FRONTIER);
  cell->type = IS_KNOWN;
}

static void construct_path(pf_map_t pf_map, struct pf_path *path,
			   struct cell *dest_cell)
{
  struct cell *cell = dest_cell;
  int i;

  assert(pf_map);
  assert(cell->type == IS_KNOWN);
  assert(cell->steps < MAX_PATH_LENGTH);

  path->found_a_valid = TRUE;
  path->positions_used = cell->steps + 1;

  for (i = path->positions_used - 1; i >= 0; i--) {
    assert(cell);
    if (i > 0) {
      path->positions[i - 1].direction_for_next_position =
	  cell->dir_from_prev_to_pos;
      path->positions[i-1].BMC_of_next_step = cell->BMC_of_last_step;
    }
    path->positions[i].x = cell->pos.x;
    path->positions[i].y = cell->pos.y;
    cell = cell->prev;
  }

  last_position_on_path(path)->direction_for_next_position = -1;
  last_position_on_path(path)->BMC_of_next_step = -1;
  path->positions[0].total_BMC = 0;

  assert(cell == NULL);
  assert(last_position_on_path(path)->x == dest_cell->pos.x);
  assert(last_position_on_path(path)->y == dest_cell->pos.y);

  for (i = 0; i < NUM_TURNS; i++) {
    path->positions[0].turn[i] = 0;
    path->positions[0].remaining_move_points[i] =
	pf_map->parameter.moves_left_initially;
  }

  for (i = 1; i < path->positions_used; i++) {
    int j,cost = path->positions[i-1].BMC_of_next_step;


    path->positions[i].total_BMC = path->positions[i - 1].total_BMC + cost;

    for (j = 0; j < NUM_TURNS; j++) {
      path->positions[i].remaining_move_points[j] =
	  path->positions[i - 1].remaining_move_points[j];
      path->positions[i].turn[j] = path->positions[i - 1].turn[j];
    }

    update_min(cost,
	       pf_map->parameter.move_rate,
	       &path->positions[i].remaining_move_points[MINIMAL_TURN],
	       &path->positions[i].turn[MINIMAL_TURN]);
    update_max(cost,
	       pf_map->parameter.move_rate,
	       &path->positions[i].remaining_move_points[MAXIMAL_TURN],
	       &path->positions[i].turn[MAXIMAL_TURN]);
    update_average(cost,
	       pf_map->parameter.move_rate,
		   path->positions[i].remaining_move_points[MINIMAL_TURN],
		   path->positions[i].remaining_move_points[MAXIMAL_TURN],
		   path->positions[i].turn[MINIMAL_TURN],
		   path->positions[i].turn[MAXIMAL_TURN],
		   &path->positions[i].remaining_move_points[AVERAGE_TURN],
		   &path->positions[i].turn[AVERAGE_TURN]);

  }

  if (PRINT_RETURNED_PATHS) {
    pf_print_path(path);
  }
}


/************* public functions ********************************************/

pf_map_t pf_get_map(const struct pf_parameter *const parameter)
{
  struct cell *cell;
  pf_map_t pf_map = fc_malloc(sizeof(struct pf_map));

  freelog(LOG_NORMAL, "PF: pf_get_map()");

  pf_map->cells = hash_new(hash_function, hash_cmp_function);
  cell_list_init(&pf_map->flat_frontier);
  memcpy(&pf_map->parameter, parameter, sizeof(pf_map->parameter));

  pf_map->zoc_used = (parameter->move_type == LAND_MOVING
		      && !TEST_BIT(parameter->flags, F_IGZOC));
  /*
   * add start to frontier
   */
  cell = get_cell(pf_map, parameter->start_x, parameter->start_y, TRUE);

  switch (pf_map->parameter.turn_mode) {
  case TC_MINIMUM:
    pf_map->turn_index = MINIMAL_TURN;
    cell->turns[MINIMAL_TURN] = 0;
    cell->points_left[MINIMAL_TURN] = parameter->moves_left_initially;
    break;
  case TC_MAXIMUM:
    pf_map->turn_index = MAXIMAL_TURN;
    cell->turns[MAXIMAL_TURN] = 0;
    cell->points_left[MAXIMAL_TURN] = parameter->moves_left_initially;
    break;
  case TC_AVERAGE:
    pf_map->turn_index = AVERAGE_TURN;
    cell->turns[MINIMAL_TURN] = 0;
    cell->points_left[MINIMAL_TURN] = parameter->moves_left_initially;
    cell->turns[MAXIMAL_TURN] = 0;
    cell->points_left[MAXIMAL_TURN] = parameter->moves_left_initially;
    break;
  case TC_NONE:
    pf_map->turn_index = -1;
    break;
  default:
    assert(0);
    break;
  }

  cell->total_FC = 0;
  cell->COP = 0;
  cell->railroad = 0;
  cell->steps = 0;
  cell->prev = NULL;
  cell->dir_from_prev_to_pos = -1;

  make_frontier(pf_map, cell);

  return pf_map;
}

bool pf_get_next_location(pf_map_t pf_map, pf_location_t * location)
{
  struct cell *current_cell;

  if (cell_list_size(&pf_map->flat_frontier) == 0) {
    freelog(LOG_NORMAL, "pf_get_next_position: no more positions");
    return FALSE;
  }

  cell_list_sort(&pf_map->flat_frontier, list_cmp_function);

  if (LIST_CHOICES) {
    int k, size = cell_list_size(&pf_map->flat_frontier);
    freelog(LOG_NORMAL, "START cells after sorting");
    for (k = 0; k < size; k++) {
      print_cell("  ", cell_list_get(&pf_map->flat_frontier, k));
    }
    freelog(LOG_NORMAL, "FINISH cells after sorting");
  }

  current_cell = cell_list_get(&pf_map->flat_frontier, 0);
  change_to_known(pf_map, current_cell);

  if (DEBUG_MAIN_DIJKSTRA) {
    print_cell("current_cell", current_cell);
  }

  adjc_dir_iterate(current_cell->pos.x, current_cell->pos.y, x1, y1, dir) {
    struct cell tmp, *possible_neighbour = &tmp, *neighbour;

    if (pf_map->parameter.restriction == GOTO_MOVE_CARDINAL_ONLY
	&& DIR_IS_CARDINAL(dir)) {
      freelog(DISCARDED_DIRS_LOG_LEVEL, "  dir=%d, pos=(%d,%d): is card", dir,
	      x1, y1);
      continue;
    }

    neighbour = get_cell(pf_map, x1, y1, TRUE);

    if (pf_map->zoc_used && !(current_cell->is_my_zoc ||
			      neighbour->is_my_zoc
			      || neighbour->is_allied_tile)) {
      freelog(DISCARDED_DIRS_LOG_LEVEL, "  dir=%d, pos=(%d,%d): zoc", dir,
	      x1, y1);
      continue;
    }

    if (neighbour->extra_cost1 >= PF_IGNORE_COST) {
      freelog(DISCARDED_DIRS_LOG_LEVEL,
	      "  dir=%d, pos=(%d,%d): extra_cost1>=ignore", dir, x1, y1);
      continue;
    }

    if (neighbour->known != TILE_UNKNOWN
	&& !can_unit_type_move_from_to(pf_map->parameter.move_type,
				       pf_map->parameter.flags,
				       pf_map->parameter.owner,
				       current_cell->pos.x,
				       current_cell->pos.y, x1, y1)) {
      freelog(DISCARDED_DIRS_LOG_LEVEL,
	      "  dir=%d, pos=(%d,%d): move not possible; terain=%s", dir, x1,
	      y1, get_tile_type(map_get_terrain(x1, y1))->terrain_name);
      continue;
    }

    memcpy(possible_neighbour, neighbour, sizeof(*possible_neighbour));
    possible_neighbour->prev = current_cell;
    possible_neighbour->dir_from_prev_to_pos = dir;

    calculate_costs_for_move(pf_map, possible_neighbour);

    if (neighbour->type == IS_KNOWN) {
      if (DEBUG_MAIN_DIJKSTRA) {
	print_cell("  existing neighbour (fixed)    ", neighbour);
	print_cell("  new possible neighbour (worse)", possible_neighbour);
      }
      assert(cmp_function(neighbour, possible_neighbour) < 0);
    } else if (neighbour->type == IS_NONE) {
      copy_cell(neighbour, possible_neighbour);
      make_frontier(pf_map, neighbour);
    } else {
      assert(neighbour->type == IS_FRONTIER);

      if (DEBUG_MAIN_DIJKSTRA) {
	print_cell("  compare existing ", neighbour);
	print_cell("  with possible new", possible_neighbour);
      }

      if (cmp_function(neighbour, possible_neighbour) > 0) {
	/*
	 * possible_neighbour is better than neighbour
	 */
	copy_cell(neighbour, possible_neighbour);
	if (DEBUG_MAIN_DIJKSTRA) {
	  freelog(LOG_NORMAL, "new wins");
	}
      } else {
	if (DEBUG_MAIN_DIJKSTRA) {
	  freelog(LOG_NORMAL, "old wins");
	}
      }
    }
  }
  adjc_dir_iterate_end;

  *location = current_cell;
  return TRUE;
}

void pf_construct_path(pf_map_t map, struct pf_path *path,
		       const pf_location_t location)
{
  construct_path(map, path, (struct cell *) location);
}

void pf_destroy_map(pf_map_t pf_map)
{
  assert(pf_map);

  freelog(LOG_NORMAL, "destroying a map which has %d cells",
	  hash_num_entries(pf_map->cells));
  for (;;) {
    struct cell *current_cell, *tmp_cell;

    if (hash_num_entries(pf_map->cells) == 0) {
      break;
    }

    current_cell = (struct cell *) hash_value_by_number(pf_map->cells, 0);
    tmp_cell = hash_delete_entry(pf_map->cells, &current_cell->pos);
    assert(tmp_cell && tmp_cell == current_cell);
    destroy_cell(current_cell);
  }

  free(pf_map);
}

struct pf_position *last_position_on_path(struct pf_path *path)
{
  return &path->positions[path->positions_used - 1];
}

int pf_get_location_x(pf_map_t map, const pf_location_t location)
{
  const struct cell *cell = (const struct cell *) location;
  return cell->pos.x;
}

int pf_get_location_y(pf_map_t map, const pf_location_t location)
{
  const struct cell *cell = (const struct cell *) location;
  return cell->pos.y;
}

void pf_init(void)
{
  freelog(LOG_NORMAL, "sizeof(struct cell)=%d", sizeof(struct cell));
}

void pf_print_path(const struct pf_path *path)
{
  int i;

  freelog(LOG_NORMAL, "PF: path (at %p) is %s", path,
	  path->found_a_valid ? "valid" : "invalid");
  if (!path->found_a_valid) {
    return;
  }
  freelog(LOG_NORMAL, "PF:  consists of %d positions:",
	  path->positions_used);
  for (i = 0; i < path->positions_used; i++) {
    freelog(LOG_NORMAL,
	    "PF:    %d/%d: (%d,%d) (t={%d/%d/%d},p={%d/%d/%d}) BMC=%d/%d dir=%s", i,
	    path->positions_used, path->positions[i].x, path->positions[i].y,
	    path->positions[i].turn[MINIMAL_TURN],
	    path->positions[i].turn[AVERAGE_TURN],
	    path->positions[i].turn[MAXIMAL_TURN],
	    path->positions[i].remaining_move_points[MINIMAL_TURN],
	    path->positions[i].remaining_move_points[AVERAGE_TURN],
	    path->positions[i].remaining_move_points[MAXIMAL_TURN],
	    path->positions[i].BMC_of_next_step,
	    path->positions[i].total_BMC,
	    dir_get_name(path->positions[i].direction_for_next_position));
  }
}