/**********************************************************************
 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
***********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

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

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

#include "gotohand.h"


/* Move these into some header */

/* MAXCOST is (uchar_t)(-1) - initializations below depend on this */
#define MAXCOST 255

/* generic move cost function */
typedef int (COSTFN)(void *argstruct, int x0, int y0, int dir);

/* Element of a WARMAP vector */
typedef struct Wartile {
  short next;
  char  dir;
  u_char cost;
} WARTILE;

/* Bucket (header/element) - a bucket list is an array of these
 *   BUCKET[0] is the head, BUCKET[1] the tail index into a vector object
 *   In a list, the 0'th cost bucket contains the current (0) and last (1)
 *   used bucket during list iteration */
typedef short BUCKET[2];

/* TODO: should we collect the pieces together
 * rationale, returning the complete warmap + buckets might be useful
 * for certain kinds of move searches, or partial reset and updates.
 * How would one "fix" a warmap if a single or small number of map
 * postions were updated? Can we store a warmap per city and would
 * there be some sort of low cost update?
*/
typedef struct warmap {
  short     x0, y0;
  short     size;
  u_char    move_type;
  u_char    maxcost;
  BUCKET    *bp;
  WARTILE   *wp;
} WARMAP;


/* Local default working variables */
static WARTILE *default_warmap;

static BUCKET bucket[MAXCOST+1];


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

/* Initialize maxcost buckets */
static BUCKET *init_bucket(BUCKET *bp, int maxcost)
{
  /* use internal defaults? */
  if( NULL == bp )
    bp = bucket;
  if( 0 >= maxcost )
    maxcost = MAXCOST;

  memset(bp, -1, sizeof(BUCKET)*(maxcost+1));
  bp[0][0]= bp[0][1]= 0;

  return bp;
}

/* Add point xy in warmap wp to bucket list bp */
static void add_to_bucket(BUCKET *bp, WARTILE *wp, int xy)
{ int cost, last;

  /* warmap elements are chained into singly linked lists headed by
   * bucket[cost], bucket[cost][0] is the head, bucket[cost][1] the tail.
   * bucket[0] is used during iteration to store the current bucket
   * bucket[0][0], and the last used bucket[0][1].
   *
   * The index values (e.g. last) are the offsets into the warmap wp.
   * 1) set this wp element (i.e. wp[xy]) as a list tail element
   * 2) find the cost bucket, and last element in this list
   * 3) set the new tail element to point to wp[xy]
   * 4) set either the bucket head or the previous tail to point to
   *    wp[xy] depending on whether the bucket is empty or not.
   */
  wp[xy].next = -1;

  cost = wp[xy].cost;
  last = bp[cost][1];

  bp[cost][1] = xy;

  if(-1 == last)
    bp[cost][0] = xy;
  else
    wp[last].next = xy;

  /* Update the index of the last used cost list if necessary */
  if(cost > bp[0][1])
    bp[0][1] = cost;
}

/* Get the next least cost point in warmap wp from the bucket list bp. */
static int get_from_bucket(BUCKET *bp, WARTILE *wp)
{
  int curr;
  short *bcurr = &bp[0][0];
  short *blast = &bp[0][1];

  /* the bucket list is iterated by reading elements from the current
   * cost list (*bcurr) until it is empty, then the next cost list,
   * up to the last used cost list (*blast). */
  do {
    /* get the head/next element from the current bucket */
    if( -1 != (curr= bp[*bcurr][0]) ) {
      if( -1 == (bp[*bcurr][0]= wp[curr].next) )
        bp[*bcurr][1] = -1;  /* housekeeping, mark bucket empty */
      return curr;
    }
  } while ((*bcurr)++ < *blast);
  return -1;
}
/* --- end bucket list iterator methods --- */

/* Generate and return a warmap in wp, using the cost function get_cost
 * with argument structure referenced by args starting at point xy0.
 * If wp is NULL the internal static warmap will be used.  */
WARTILE *get_warmap(WARTILE *wp, COSTFN *get_cost, void *args, int xy0)
{
  int xy, cost;

  /* Use the internal static warmap if none provided */
  if (NULL == wp) {
    if (NULL == default_warmap)
      default_warmap= (WARTILE *)fc_malloc(sizeof(WARTILE)*map.ysize*map.xsize);
    wp= default_warmap;
  }

  /* Initialize everything */
  memset(wp, -1, sizeof(WARTILE)*map.ysize*map.xsize);
  init_bucket(bucket, MAXCOST);

  /* Step outwards from xy0, updating the warmap with the move cost
   * for adjacent tiles and adding them to the bucket list. Then get
   * the least cost tile from the list and repeat until none are left.
   * TODO: add maxcost termination, desttile termination
   */
  xy= xy0, wp[xy].cost= 0;
  do {
    int xy0= xy, x0= xy%map.xsize, y0= xy/map.xsize;
    adjc_dir_iterate(x0, y0, x, y, dir) {
      xy = map_index(x,y);

      /* Only update if this shortens paths */
      if (wp[xy].cost > wp[xy0].cost) {

        /* Evaluate the cost of the move */
        cost= (*get_cost)(args, x0, y0, dir);
        if( cost < 0 ) {

          /* Special case: only update costs, don't allow movement
           *   through the square, e.g. used by ships to attack shore,
           *   or drop off passengers. */
          if ((cost= wp[xy0].cost - cost) < wp[xy].cost) {
            wp[xy].cost= cost;
            wp[xy].dir= DIR_REVERSE(dir);
          }
        } else {

          /* Normal case: update costs, add_to_bucket for more moves. */
          if ((cost+= wp[xy0].cost) < wp[xy].cost) {
            wp[xy].cost= cost;
            wp[xy].dir= DIR_REVERSE(dir);
            add_to_bucket(bucket, wp, xy);
          }
        }
      }
    } adjc_dir_iterate_end;
  } while ((xy= get_from_bucket(bucket, wp)) != -1);
  /* TODO:  && bucket[0][0] < maxcost); ??? */

  /* return the updated warmap */
  return wp;
}


/* SINGLE_MOVE cost function */
int single_move(void *args, int x, int y, int dir)
{
  return SINGLE_MOVE;
}

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

/* TRIREME cost function for SEA_MOVING */
int trireme_seamove(void *args, int x, int y, int dir)
{
  /* -3 means ships can move between */
  if ( map_get_tile(x, y)->move_cost[dir] == -3) {
    if( is_coastline(x,y) )
      return SINGLE_MOVE;
    else
      return SINGLE_MOVE*2;
  }
  else
    return -SINGLE_MOVE;
}

/* Normal LAND_MOVE cost function
 * TODO: If units have the same move_type but different move counts
 *       can we generate a single warmap to handle all.
 *       What are the different move_types?
 *       normal (road and river effects + SINGLE_MOVE)
 *       alpine (ignores roads with triple move, or all road -> SINGLE_MOVE)
 *       fast   (terrain, road and river effects + SINGLE_MOVE)
 *       Is move_cost turns or pseudo-distance (i.e. weighted steps)?
 */
struct NormalLandMove {
  struct player *pplayer;
  struct unit   *punit;
  int           igter;
};

#if EXPERIMENT_WITH_ME
#define SINGLE+MOVE     3  /* 12/1 Note: if change this, bump MAXCOST */
#define MOVE_COST_RIVER 1  /* 12/2   */
#define MOVE_COST_ROAD  1  /* 12/3   */
#define MOVE_COST_RAIL  0  /* 12/INF */
#endif

int normal_move(struct NormalLandMove *args, int x, int y, int dir)
{
  struct player *pplayer = args->pplayer;
  struct unit *punit = args->punit;
  struct tile *ptile = map_get_tile(x, y);
  int x1= x + DIR_DX2[dir], y1= y+DIR_DY2[dir];
  int igter = args->igter;
  int move_cost = 0;
  int t1, tmp;

  if ((t1= map_get_terrain(x1, y1)) == T_OCEAN) {
    if (punit && ground_unit_transporter_capacity(x1, y1, pplayer) > 0)
      move_cost = SINGLE_MOVE;
  }
  else
  if (ptile->terrain == T_OCEAN) {
    int tmp = get_tile_type(t1)->movement_cost * SINGLE_MOVE;
    move_cost = igter ? MOVE_COST_ROAD : MIN(tmp, unit_type(punit)->move_rate);
  }
  else
  /* These next two look like the disembark cost, whereas the previous
   * looks more like this, no??? Is there a != vs == somewhere?
   * Since when do you get road bonus when landing as above???
   * Syela insists on this, Thue has his suspicions. */
  if (igter) {
    move_cost = (ptile->move_cost[dir] ? SINGLE_MOVE : 0);
  }
  else
  if (punit) {
    move_cost = MIN(ptile->move_cost[dir], unit_type(punit)->move_rate);
  }
  else {
    /* we have a city - average tile and city, why? what swamp is this?
     * what happened to the SINGLE_MOVE multipliers? */
    tmp = map_get_tile(x1, y1)->move_cost[DIR_REVERSE(dir)];
    move_cost = (ptile->move_cost[dir] + tmp +
      (ptile->move_cost[dir] > tmp ? 1 : 0))/2;
  }

  return move_cost;
}