#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#include "combat.h"
#include "game.h"
#include "log.h"
#include "map.h"
#include "mem.h"
#include "rand.h"

#include "maphand.h"
#include "settlers.h"
#include "unithand.h"
#include "unittools.h"

#include "path_finding10.h"

/* For speed set to powers of 2 */
#define MAX_XSIZE 100
#define MAX_YSIZE 100

/*======================================================================*/
/*===================== Hidden structures ==============================*/
/*======================================================================*/
typedef short xy_t;

struct pf_node {
  xy_t next;
  xy_t prev;
  u_char cost;
  u_char extra_cost;
  enum direction8 came_from;
};
typedef struct pf_node *pf_node_t;

typedef xy_t bucket_t[2];
typedef unsigned int t_uint;

/* 
 * warmap elements are chained into doubly linked lists headed by
 * bucket[cost], bucket[cost][0] is the head, bucket[cost][1] the tail.
 *
 * The values stored in buckets (e.g. last) are the offsets into the 
 * lattice.
 */
struct pf_queue {
  bucket_t *bucket_list;
  t_uint first_bucket;
  t_uint last_bucket;
};

/*
 * Anything else goes here?
 */
struct pf_map {
  short x0, y0;                        /* the origin */
  short x, y, xy;                      /* the current position */
  COSTFN *get_cost;
  EXTRAFN *get_extra;
  enum known_type (*get_known)(int, int, struct player *);
  enum known_type dest_known_type;
  struct pf_queue *queue;
  struct pf_node *lattice;
  struct player *pplayer;
  enum turn_mode turn_mode;
  int move_rate;
};

/* --- The conversion methods (x,y) <--> xy --- */

/*******************************************************************
 * (x,y) --> xy
 *******************************************************************/
static xy_t get_xy_from_x_and_y(int x, int y)
{
  return y * MAX_XSIZE + x;
}

/*******************************************************************
 * xy --> x
 *******************************************************************/
static int get_x_from_xy(xy_t xy)
{
  return xy % MAX_XSIZE;
}

/*******************************************************************
 * xy --> y
 *******************************************************************/
static int get_y_from_xy(xy_t xy)
{
  return xy / MAX_XSIZE;
}

/*******************************************************************
 * x of the current node
 *******************************************************************/
int pf_get_current_x(const pf_map_t the_map)
{
  return the_map->x;
}

/*******************************************************************
 * y of the current node
 *******************************************************************/
int pf_get_current_y(const pf_map_t the_map)
{
  return the_map->y;
}

/*******************************************************************
 * cost of the shortest path to the current node
 *******************************************************************/
int pf_get_current_cost(const pf_map_t the_map)
{
  return the_map->lattice[the_map->xy].cost;
}

/*******************************************************************
 * extra cost of the shortest path to the current node
 *******************************************************************/
int pf_get_current_extra_cost(const pf_map_t the_map)
{
  return the_map->lattice[the_map->xy].extra_cost;
}

/* --- The next 3 functions are methods for a bucket list iterator. --- */

/*********************************************************************** 
 * Initialize the queue
 ***********************************************************************/
static void pf_init_queue(struct pf_queue *queue, int maxcost)
{
  assert(queue);

  /* use internal defaults? */
  if( 0 >= maxcost ) {
    maxcost = (PF_MAXCOST + 1) * (PF_AMC_FACTOR + 1) - 1;
  }
  
  queue->bucket_list = fc_malloc(sizeof(bucket_t)*(maxcost+1));
  memset(queue->bucket_list, -1, sizeof(bucket_t)*(maxcost+1));

  queue->first_bucket = 0;
  queue->last_bucket = 0;
}

/*****************************************************************
 * Add node xy to the queue, new is FALSE if the node is already 
 * in the queue (yes it can happen, we might find a shorter route 
 * to an already known destination)
 *****************************************************************/
static void pf_add_to_queue(struct pf_queue *queue, 
                            struct pf_node *node_list, 
                            int xy, bool new)
{ 
  int cost, last;

  /* First remove this element from the list (if it's in there) */

  if (!new) {
    xy_t prev = node_list[xy].prev;
    xy_t next = node_list[xy].next;
    if (prev != -1) {
      node_list[prev].next = next;
    }
    if (next != -1) {
      node_list[next].prev = prev;
    }
  }

  /* Add the new element to the list */

  /* find the cost bucket */
  cost = node_list[xy].cost * (PF_AMC_FACTOR + 1) + node_list[xy].extra_cost;

  /* get the current last element in the cost bucket */
  last = queue->bucket_list[cost][1];
  if (-1 == last) {
    /* the bucket was empty */
    queue->bucket_list[cost][0] = xy;
  } else {
  /* point it old last element to the new last element */
    node_list[last].next = xy;  
  }
  /* set the new last element's tail */
  node_list[xy].next = -1;
  /* set the new last element's head */
  node_list[xy].prev = last;
  /* set the bucket to point to the new last element */
  queue->bucket_list[cost][1] = xy;

  /* Update the index of the last used cost list if necessary */
  if(cost > queue->last_bucket) {
    queue->last_bucket = cost;
  }

}

/********************************************************************* 
 * Get the next least cost point in warmap wp from the bucket list bp. 
 *********************************************************************/
static xy_t pf_get_from_queue(struct pf_queue *queue, 
                              struct pf_node *node_list)
{
  /* the bucket list is iterated by reading elements from the current
   * cost list until it is empty, then the next cost list,
   * up to the last used cost list. */
  while (queue->first_bucket <= queue->last_bucket) {
    /* the current cost */
    int cost = queue->first_bucket;
    /* get the head/next element from the current bucket */
    xy_t curr = queue->bucket_list[cost][0];

    if( -1 != curr ) {
      /* current cost list is not empty */
      /* remove the node from the list */
      queue->bucket_list[cost][0] = node_list[curr].next; 
      if( -1 == queue->bucket_list[cost][0]) {
        /* the list is empty now! */
        /* mark bucket empty */
        queue->bucket_list[cost][1] = -1;
        /* NB: we do not shift first_bucket as yet */ 
      }
      return curr;
    }

    queue->first_bucket++;
  }

  return -1;
}

/***********************************************************************
 * Tidy up after use.  The bucket_list is _long_, so it's imperative 
 * to use this function.
 ***********************************************************************/
static void pf_destroy_queue(struct pf_queue *queue)
{
  free(queue->bucket_list);
}

/* --------------- end bucket list iterator methods --------------- */


/*-------------------- Possible cost functions -------------------*/
/* SINGLE_MOVE cost function */
int single_move(pf_map_t the_map, int x, int y, int dir)
{
  return SINGLE_MOVE;
}

/* SINGLE_MOVE cost function for SEA_MOVING */
int single_seamove(pf_map_t the_map, int x, int y, int dir)
{
  /* -3 means ships can move between */
  if ( map_get_tile(the_map->x, the_map->y)->move_cost[dir] == -3)
    return SINGLE_MOVE;
  else
    return PF_MAXCOST;
}

/* LAND_MOVE cost function for a unit */
int normal_move_unit(pf_map_t the_map, int x1, int y1, int dir)
{
  struct tile *ptile = map_get_tile(the_map->x, the_map->y);
  int t1 = map_get_terrain(x1, y1);
  int move_cost = PF_MAXCOST;

  // Testing
  if (the_map->dest_known_type == TILE_UNKNOWN) {
    return the_map->move_rate;
  }

  if (t1 == T_OCEAN) {
    if (ground_unit_transporter_capacity(x1, y1, the_map->pplayer) > 0)
      move_cost = SINGLE_MOVE;
    else
      move_cost = PF_MAXCOST;
    move_cost = PF_MAXCOST;
  } else if (ptile->terrain == T_OCEAN) {
    move_cost = get_tile_type(t1)->movement_cost * SINGLE_MOVE;
  } else {
    move_cost = ptile->move_cost[dir];
  }
  return move_cost;
}

/* NOT TESTED */
/* IGTER_MOVE cost function for a unit */
int igter_move_unit(pf_map_t the_map, int x1, int y1, int dir)
{
  struct tile *ptile = map_get_tile(the_map->x, the_map->y);
  int move_cost;

  if (map_get_terrain(x1, y1) == T_OCEAN) {
    if (ground_unit_transporter_capacity(x1, y1, the_map->pplayer) > 0)
      move_cost = SINGLE_MOVE;
    else
      move_cost = PF_MAXCOST;
  } else if (ptile->terrain == T_OCEAN) {
    move_cost = MOVE_COST_ROAD;
  } else {
    /* Why is it SINGLE_MOVE below? */
    /* Or why is it MOVE_COST_ROAD above? */
    move_cost = (ptile->move_cost[dir] ? SINGLE_MOVE : 0);
  }
  return move_cost;
}

/* NOT TESTED */
/* LAND_MOVE cost function for a city ?? */
int normal_move_city(pf_map_t the_map, int x1, int y1, int dir)
{
  /* have no idea what code below is for */

  if (map_get_terrain(x1, y1) == T_OCEAN)
    return PF_MAXCOST;
  else {
    struct tile *ptile = map_get_tile(the_map->x, the_map->y);
    int tmp = map_get_tile(x1, y1)->move_cost[DIR_REVERSE(dir)];
    return (ptile->move_cost[dir] + tmp +
	    (ptile->move_cost[dir] > tmp ? 1 : 0))/2;
  }
}

/* --------------------- extra cost functions --------------------- */

/*********************************************************************
 * An example of extra cost fn: will avoid hills if possible 
 *********************************************************************/
int avoid_hills(pf_map_t the_map, int x, int y)
{
  enum tile_terrain_type ter = map_get_terrain(x, y);

  switch (ter){
  case T_HILLS:
    return 1;
  case T_MOUNTAINS:
    return 3;
  default:
    return 0;
  }
}

/*********************************************************************
 * Strict trireme function: will never go into the unknown and 
 * away from shore.
 *********************************************************************/
int strict_trireme(pf_map_t the_map, int x, int y)
{
  if (the_map->dest_known_type != TILE_UNKNOWN && is_coastline(x,y)) {
    return 0;
  }
  return PF_MAX_EXTRA;
}

/* -------------------- manipulating the cost --------------------- */
/********************************************************************
 * Adjust BMC to reflect the turn mode and the move_rate.
 * THe result is AMC.
 ********************************************************************/
static int adjust_cost(pf_map_t the_map, int cost)
{
  if (the_map->turn_mode == TM_NONE) {
    return cost;
  }
  
  cost = MIN(cost, the_map->move_rate);

  if (the_map->turn_mode == TM_AVERAGE) {
    return cost;
  } else {
    int moves_left = the_map->move_rate 
      - (the_map->lattice[the_map->xy].cost % the_map->move_rate);

    switch (the_map->turn_mode) {
    case TM_MAXIMUM:
      return  (cost > moves_left ? moves_left + cost
               : cost);
    case TM_MINIMUM:
      return (cost > moves_left ? moves_left
              : cost);
    default:
      freelog(LOG_ERROR, "Unknown turn mode in path finding");
    }
  }
  
  return PF_MAXCOST;
}


/* -------------------- get_known function(s) ------------ */
/********************************************************************
 * Server-side get_known function 
 ********************************************************************/
enum known_type server_get_known(int x, int y, struct player *pplayer)
{
  if (!map_get_known(x, y, pplayer)) {
    return TILE_UNKNOWN;
  } else if (map_get_known_and_seen(x, y, pplayer)) { 
    return TILE_KNOWN;
  } else {
    return TILE_KNOWN_FOGGED;
  }
}


/* -------------------- generating the map ------------------------ */

/*****************************************************************
 * Primary method for iterative path-finding.
 * Plan: 1. Process previous position
 *       2. Get new nearest position and return it
 *****************************************************************/
bool pf_iterate_map(pf_map_t the_map)
{
  int cost;
  xy_t xy;
  pf_node_t node_xy = &the_map->lattice[the_map->xy];
  int extra = 0;

  /* Default known type, to avoid stupid mistakes */
  the_map->dest_known_type = TILE_KNOWN;


  /* Processing Stage */
  /* The previous position is contained in {x,y} fields of the_map */
  
  adjc_dir_iterate(the_map->x, the_map->y, x1, y1, dir) {
    xy_t xy1 = get_xy_from_x_and_y(x1, y1);
    pf_node_t node_xy1 = &the_map->lattice[xy1];
    
    /* Only update if this might shorten the paths */
    if (node_xy1->cost > node_xy->cost) {

      /* Establish the "known" status of the destination */
      if (the_map->get_known) {
        the_map->dest_known_type 
          = (*(the_map->get_known))(x1, y1, the_map->pplayer);
      }

      /* Evaluate the cost of the move */
      cost = (*(the_map->get_cost))(the_map, x1, y1, dir);
      if (cost < PF_MAXCOST) {
        cost = adjust_cost(the_map, cost);
      }

      assert( cost > 0 ); /* No special cases yet */

      /* Evaluate the extra cost of the destination */
      if (the_map->get_extra) {
        extra = (*(the_map->get_extra))(the_map, x1, y1);
      }

      /* Total costs at xy1 */
      cost += node_xy->cost;
      extra += node_xy->extra_cost;
      /* Are they reasonable? */
      if (cost >= PF_MAXCOST || extra >= PF_MAX_EXTRA) {
        continue;
      }

      /* Update costs and add_to_queue, if we found a better route to xy1. */
      if (cost < node_xy1->cost && extra < node_xy1->extra_cost) {
        bool new = (node_xy1->cost == PF_MAXCOST);
        node_xy1->cost = cost;
        node_xy1->extra_cost = extra;
        pf_add_to_queue(the_map->queue, the_map->lattice, xy1, new);
      }
    }
  } adjc_dir_iterate_end;

  /* Get the next nearest node */
  xy = pf_get_from_queue(the_map->queue, the_map->lattice);
  if (xy == -1) {
    return FALSE;
  }
  the_map->xy = xy;
  the_map->x = get_x_from_xy(xy);
  the_map->y = get_y_from_xy(xy);

  return TRUE;
}

/******************************************************************
 * Allocates the memory for the map.  No initialization.
 ******************************************************************/
pf_map_t pf_create_map()
{
  pf_map_t the_map = fc_malloc(sizeof(struct pf_map));

  the_map->lattice = 
    fc_malloc(sizeof(struct pf_node) * MAX_XSIZE * MAX_YSIZE);
  memset(the_map->lattice, -1, 
         sizeof(struct pf_node) * MAX_XSIZE * MAX_YSIZE);
  the_map->queue = 
    fc_malloc(sizeof(struct pf_queue));
  pf_init_queue(the_map->queue, 0);

  return the_map;
}

/*****************************************************************
 * Creates the map and does minimal initializations.  
 * For debugging period only.  
 * To mature into pf_get_map eventually.
 *****************************************************************/
pf_map_t pf_init_map(struct unit *punit)
{
  pf_map_t the_map = pf_create_map();

  the_map->move_rate = unit_type(punit)->move_rate;
  the_map->x0 = punit->x;
  the_map->y0 = punit->y;
  the_map->x = punit->x;
  the_map->y = punit->y;
  the_map->xy = get_xy_from_x_and_y(punit->x, punit->y);
  the_map->lattice[the_map->xy].cost = the_map->move_rate 
    - punit->moves_left;
  the_map->lattice[the_map->xy].extra_cost = 0;
  /* Default */
  the_map->get_extra = NULL;
  if (is_ground_unit(punit)) {
    the_map->get_cost = normal_move_unit;
  } else if (is_sailing_unit(punit)) {
    the_map->get_cost = single_seamove;
    if (unit_flag(punit, F_TRIREME)) {
      the_map->get_extra = strict_trireme;
    }
  } else {
    /* Yet unsupported */
    assert(0);
  }
  the_map->pplayer = unit_owner(punit);
  the_map->turn_mode = TM_MAXIMUM;

  the_map->get_known = server_get_known;

  /*  (the_map->queue).bucket_list = NULL;
      pf_init_queue(&(the_map->queue), 0); */

  return the_map;
}

/*********************************************************************
 * After usage the map must be destroyed.
 *********************************************************************/
void pf_destroy_map(pf_map_t the_map)
{
  free(the_map->lattice);
  pf_destroy_queue(the_map->queue);
}