#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

/* global variables */
int log_depth=5;
long current_number=0, skip_until=-1;

/********************** a minimal list implementation **********************/
/* taken from my lists-library */

/* a list is here a double linked list with an empty head-element
   The next-pointer of the last element points to NULL.
   The prev-pointer of the head-element points to the last element. */
typedef struct list_s {
  void *val;
  struct list_s *next, *prev;
} list_t;


/* allocates a new list (i.e. the head-element) and returns a pointer to it */
list_t *new_list ()
{
  list_t *nl=(list_t*)malloc(sizeof(list_t));
  nl->val=NULL;
  nl->next=NULL;
  nl->prev=nl;
  return nl;
}


/* inserts val in to the list head behind the list-element pos. return pos. */
list_t* insert_list_element (list_t* head, list_t* pos, void *v)
{
  list_t *tmp=(list_t*)malloc(sizeof(list_t));
  /* Fehlerabfrage fehlt */
  tmp->val=v;
  tmp->next=pos->next;
  tmp->prev=pos;
  if (pos->next) pos->next->prev=tmp;
  else head->prev=tmp;
  pos->next=tmp;
  return pos;
}


/* frees the memory allocated by the list head. For each value the function
   free_func is called (if !=NULL) */
void clear_list (list_t* head, void (*free_func)(void *))
{
  list_t *tmp;
  while (head) {
    tmp=head->next;
    if (free_func&&head->val) (*free_func)(head->val);
    free(head);
    head=tmp;
  }
}



/***************************** tile-instances *************************/
/* a tile-instance is a tile in a certain position. i.e. e.g.
       #      #
   #####  and ##### belong to the same tile, but are two different
                    tile-instances.

   The two elements xmax and ymax always have to be exact, i.e. the first
   and the last rows and columns always have to contain something.
*/

typedef struct {
  int **a;
  int xmax, ymax;
  int ystart;  /* first occupied position in row 0 */
} tile_instance_t;


/* this function does not return a valid tile-instance, because
   neither the first nor the last neither row nor column contain
   something. But it initializes memory for the real constructors. */
tile_instance_t *empty_tile_instance (int xmax, int ymax)
{
  int i;
  tile_instance_t *res=(tile_instance_t*)malloc(sizeof(tile_instance_t));
  res->a=(int**)malloc(sizeof(int*)*xmax);
  for (i=0; i<xmax; i++)
    res->a[i]=(int*)calloc(ymax, sizeof(int));
  res->xmax = xmax;
  res->ymax = ymax;
  res->ystart=0;
  return res;
}

void refind_ystart (tile_instance_t *ti)
{
  int j;
  for (j=0; j<ti->ymax; j++)
    if (ti->a[0][j]) {
      ti->ystart=j;
      break;
    }
  return;
}

/* makes a tile-instance from a nullterminated array of strings such as
  {"   *",
   "*******",
   "* * *",
   NULL}
*/
tile_instance_t *new_tile_instance (char **map)
{
  int xmin=10000, xmax=0, ymin=10000, ymax=0, i, j;
  tile_instance_t *res=NULL;

  /* first we have to find the dimensions of the tile */
  for (i=0; map[i]; i++) {
    for (j=0; map[i][j]; j++)
      if (map[i][j]!=' ') {
        if (i<xmin) xmin=i;
        if (i>xmax) xmax=i;
        if (j<ymin) ymin=j;
        if (j>ymax) ymax=j;
      }
  }
  /* now we allocate memory und copy */
  res=empty_tile_instance (xmax-xmin+1, ymax-ymin+1);
  for (i=xmin; ((i<=xmax) && (map[i])); i++)
    for (j=ymin; ((j<=ymax) && (map[i][j])); j++)
      res->a[i-xmin][j-ymin]= ((map[i][j]==' ') ? 0 : 1);

  refind_ystart (res);
  return res;
}

/* copies a tile-instance into newly allocated memory */
tile_instance_t *copy_tile_instance (tile_instance_t *ti)
{
  int i,j;
  tile_instance_t *res=empty_tile_instance (ti->xmax, ti->ymax);
  for (i=0; i<ti->xmax; i++)
    for (j=0; j<ti->ymax; j++)
      res->a[i][j] = ti->a[i][j];
  res->ystart=ti->ystart;
  return res;
}

void free_tile_instance (tile_instance_t *ti)
{
  int i;
  for (i=0; i<ti->xmax; i++)
    if (ti->a[i]) free(ti->a[i]);
  free (ti->a);
  free (ti);
  return;
}

/* compares two tile-instances */
int tile_instance_equal (tile_instance_t *ti1, tile_instance_t *ti2)
{
  int i,j;
  if ((ti1->xmax != ti2->xmax) || (ti1->ymax != ti2->ymax)) 
    return 0;
  for (i=0; i<ti1->xmax; i++)
    for (j=0; j<ti1->ymax; j++)
      if (ti1->a[i][j] != ti2->a[i][j]) return 0;
  return 1;
}

/* the following functions turn or mirror a tile-instance */
#define TURN_TILE_INSTANCE 1
#define MIRROR_TILE_INSTANCE 2
void transform_tile_instance (tile_instance_t **ti, int type)
{
  int i,j;
  tile_instance_t *res=empty_tile_instance ((*ti)->ymax, (*ti)->xmax);
  if (res==NULL) return;
  for (i=0; i<(*ti)->xmax; i++)
    for (j=0; j<(*ti)->ymax; j++)
      switch (type) {
      case TURN_TILE_INSTANCE:
        res->a[(*ti)->ymax-j-1][i] = (*ti)->a[i][j];
        break;
      case MIRROR_TILE_INSTANCE:
        res->a[j][i] = (*ti)->a[i][j];
        break;
      }
  free_tile_instance (*ti);
  *ti=res;
  refind_ystart (*ti);
  return;
}

void turn_tile_instance (tile_instance_t **ti)
{
  return (transform_tile_instance (ti, TURN_TILE_INSTANCE));
}
void mirror_tile_instance (tile_instance_t **ti)
{
  return (transform_tile_instance (ti, MIRROR_TILE_INSTANCE));
}

/* prints a tile-intance to file f. Thats for debugging */
void fprintf_tile_instance (FILE *f, tile_instance_t *ti)
{
  int i, j;
  fprintf (f, "----------\n");
  for (i=0; i<ti->xmax; i++) {
    for (j=0; j<ti->ymax; j++)
      fprintf (f, "%s", (ti->a[i][j] ? "*" : " "));
    fprintf (f, "\n");
  }
}


/* this is a very special function. It returns a list of variations of 
   a given tile-instance: Behind the last set field of every row there
   is a further field set. E.g.:

   **       **+    **     **
    **  -->  **     **+    **
    *        *      *      *+

   All new tile-instances are newly allocated. */
list_t *variate_tile_instance (tile_instance_t *ti)
{
  list_t *res=new_list();
  int i, j, k;
  for (i=0; i<ti->xmax; i++) {
    /* find last set field */
    for (j=ti->ymax-1; j>=0; j--)
      if (ti->a[i][j]) break;
    if (j>=0) /* this should alway be the case */
      {
        tile_instance_t *new = copy_tile_instance (ti);
        if (j==ti->ymax-1) { /* we need more place */
          new->ymax++;
          for (k=0; k<new->xmax; k++) {
            new->a[k]=realloc(new->a[k], new->ymax*sizeof(int));
            new->a[k][new->ymax-1]=0;
          }
        } /* now we have enough place */
        new->a[i][j+1] = 1;
        insert_list_element (res, res->prev, new);
      }
  }
  return res;
}

/******************************* tiles *******************************/

/* a tile simply is a nullterminated array of tile-instances.
   and a tile can already be on the board or not. */

typedef struct {
  tile_instance_t *instance[9]; /* a tile contains 8 instances max. + NULL */
  int is_on_board;
} tile_t;


/* tests, whether a tile contains a tile_instance */
int tile_contains_instance (tile_t *t, tile_instance_t *ti)
{
  int i=0;
  while (t->instance[i])
    if (tile_instance_equal(ti, t->instance[i++]))
      return 1;
  return 0;
}

/* generates a tile from an instance. The instance is turned an mirrored */
tile_t *new_tile_from_instance (tile_instance_t **ti)
{
  int count=1, i;
  tile_t *res=(tile_t*)calloc(1, sizeof(tile_t));

  res->instance[0] = copy_tile_instance (*ti);
  for (i=0; i<8; i++) {
    if (i==4) mirror_tile_instance (ti);
    else turn_tile_instance (ti);
    if (!tile_contains_instance(res, *ti))
      res->instance[count++] = copy_tile_instance (*ti);
  }
  return res;
}

void free_tile (tile_t *t)
{
  int i=0;
  while (t->instance[i]) free_tile_instance(t->instance[i++]);
  free (t);
  return;
}

/* output-routines for debugging.
   prints all instances of the tile. */
void fprintf_tile (FILE *f, tile_t *t)
{
  int i=0;

  fprintf (f, "===================\n");
  while (t->instance[i])
    fprintf_tile_instance (f, t->instance[i++]);
  return;
}

/******************************* tile-sets ****************************/

/* a tile-set is simply a collection (here: a list) of tiles */

typedef struct {
  list_t *tiles;
  int no_of_tiles;
} tile_set_t;


/* creates an empty set of tiles */
tile_set_t *empty_tile_set ()
{
  tile_set_t *res=(tile_set_t*)malloc(sizeof(tile_set_t));
  res->tiles = new_list();
  res->no_of_tiles=0;
  return res;
}


void free_tile_set (tile_set_t *ts)
{
  clear_list (ts->tiles, (void(*)(void*))free_tile);
  free (ts);
  return;
}

/* tests, whether the tile-set contains a certain instance of some tile */
int tile_set_contains_instance (tile_set_t *ts, tile_instance_t *ti)
{
  list_t *p=ts->tiles;
  while ((p=p->next))
    if (tile_contains_instance((tile_t*)(p->val), ti))
      return 1;
  return 0;
}

/* adds a new tile to the tileset, if necessary. The tile-instance is
   turned and mirrored. */
void add_instance_to_tile_set (tile_set_t *ts, tile_instance_t **ti)
{
  if (!tile_set_contains_instance (ts, *ti)) {
    insert_list_element (ts->tiles, ts->tiles->prev,
                         new_tile_from_instance (ti));
    ts->no_of_tiles++;
  }
  return;
}


/* generates a tileset with the n-ominos. */
tile_set_t *make_n_ominos (int n)
{
  tile_set_t *res=empty_tile_set();
  if (n==1) { /* create "1-o-minos" */
    char *map[]={"*", NULL};
    tile_instance_t *ti=new_tile_instance (map);
    add_instance_to_tile_set (res, &ti);
    free_tile_instance (ti);
  }
  else { /* create (n-1)-o-minos and variate them */
    tile_set_t *lesser = make_n_ominos (n-1);
    list_t *p=lesser->tiles, *q;
    while ((p=p->next)) {
      list_t *variations;
      int i=0;
      while (((tile_t*)(p->val))->instance[i]) {
        q = variations = 
          variate_tile_instance (((tile_t*)(p->val))->instance[i]);
        while ((q=q->next))
          add_instance_to_tile_set (res, (tile_instance_t**)(&(q->val)));
        clear_list (variations, (void(*)(void*))free_tile_instance);
        i++;
      }
    }
    free_tile_set (lesser);
  } /* else */

  return res;
}

/* outputs the first instance of all tiles in the tile-set. For debugging */
void fprintf_tile_set (FILE *f, tile_set_t *ts)
{
  list_t *p=ts->tiles;
  while ((p=p->next))
    fprintf_tile_instance (f, ((tile_t*)(p->val))->instance[0]);
  fprintf (f, "number of tiles: %d\n", ts->no_of_tiles);
  return;
}


/******************************* boards *******************************/
/* This type is the board, where the tiles-instances are set onto. 
   A field of the array may be empty (0), occupied with some tile
   (1, 2, 3, ...) or not on the board (-1). (The latter is for boards
   not rectangular.) */

typedef struct {
  int **a;
  int xmax, ymax;
  int no_of_set_tiles;
} board_t;


/* this is a safe function for requesting the values of the board */
int board_value (board_t *b, int x, int y)
{
  if ((x<0) || (x>=b->xmax) ||
      (y<0) || (y>=b->ymax)) return -1;
  return (b->a[x][y]);
}

/* makes an empty rectangular board with size (xmax, ymax) */
board_t *empty_board_by_size (int xmax, int ymax)
{
  int i;
  board_t *res=(board_t*)malloc(sizeof(board_t));
  res->xmax = xmax;
  res->ymax = ymax;
  res->no_of_set_tiles=0;
  res->a=(int**)malloc(sizeof(int*)*xmax);
  for (i=0; i<xmax; i++)
    res->a[i]=(int*)calloc(ymax, sizeof(int));
  return res;
}

/* makes a board from a nullterminated array of strings */
board_t *empty_board_by_chars (char **map)
{
  board_t *res=NULL;
  int xmax=0, ymax=0, tmp, i, j;
  /* first we have to find the size */
  while (map[xmax]) {
    if ((tmp=strlen(map[xmax]))>ymax) ymax=tmp;
    xmax++;
  }

  res = empty_board_by_size (xmax, ymax);
  /* set all fields to "not on board" */
  for (i=0; i<xmax; i++)
    for (j=0; j<ymax; j++) 
      res->a[i][j]=-1;

  /* set fields given in map to "free" */
  for (i=0; i<xmax; i++)
    for (j=0; ((map[i][j]) && (j<ymax)); j++)
      if (map[i][j]!=' ') res->a[i][j]=0;

  return res;
}

/* outputs the board in nice ascii-art */
void fprintf_board (FILE *f, board_t *b)
{
  int i, j;

  /* returns the char representing the corner at (x,y) */
  char corner_char (board_t *b, int x, int y)
    {
      if ((board_value(b,x  ,y  ) == board_value(b,x-1,y  )) &&
          (board_value(b,x-1,y  ) == board_value(b,x-1,y-1)) &&
          (board_value(b,x-1,y-1) == board_value(b,x  ,y-1)))   return ' ';
      if ((board_value(b,x  ,y  ) == board_value(b,x-1,y  )) &&
          (board_value(b,x  ,y-1) == board_value(b,x-1,y-1)))   return '|';
      if ((board_value(b,x  ,y  ) == board_value(b,x  ,y-1)) &&
          (board_value(b,x-1,y  ) == board_value(b,x-1,y-1)))   return '-';
      return '+';
    }

  for (i=0; i<=b->xmax; i++) {
    /* edge between rows i and i-1 */
    for (j=0; j<=b->ymax; j++) {
      fprintf (f, "%c", corner_char (b,i,j));
      if (j<b->ymax)
        fprintf (f, "%s", ((board_value(b,i,j) == board_value(b,i-1,j)) ? 
                           "   " : "---"));
    }
    fprintf (f, "\n");
    /* row i */
    if (i<b->xmax)
      for (j=0; j<=b->ymax; j++)
        fprintf (f, "%s", ((board_value(b,i,j) == board_value(b,i,j-1)) ? 
                           "    " : "|   "));
    fprintf (f, "\n");
  }
  fprintf (f, "\n\n");
  fflush (f); /* this is important if the program is interrupted */
  return;
}


/* tests, whether the tile-instance can be set with the left upper corner
   on position x,y of the board */
int tile_instance_fits_to_position (board_t *b, tile_instance_t *ti, 
                                    int x, int y)
{
  int i,j;
  for (i=0; i<ti->xmax; i++)
    for (j=0; j<ti->ymax; j++)
      if ((ti->a[i][j]) && (board_value(b, x+i, y+j)!=0)) return 0;
  return 1;
}


/* tries to set the tile-instance ti onto the board with the upper
   left corner at position x,y. If it was possible, 1 is returned, 0
   otherwise */
int set_tile_instance_to_position (board_t *b, tile_instance_t *ti,
                                   int x, int y)
{
  int i, j;
  if (!tile_instance_fits_to_position(b, ti, x, y)) return 0;
  b->no_of_set_tiles++;
  for (i=0; i<ti->xmax; i++)
    for (j=0; j<ti->ymax; j++)
      if (ti->a[i][j]) b->a[x+i][y+j] = b->no_of_set_tiles;
  return 1;
}  

/* tries to set the instance number instance of tile t onto the board
   at position x,y. return values are as in set_tile_instance_to_position */
int set_tile_to_position (board_t *b, tile_t *t, int instance,
                          int x, int y)
{
  if (set_tile_instance_to_position (b, t->instance[instance], x, y)) {
    t->is_on_board=1;
    return 1;
  }
  return 0;
}

/* removes the tile-instance ti from the board from upper left position
   at x,y without checking, whether it was really there */
void remove_tile_instance_from_position (board_t *b, tile_instance_t *ti,
                                         int x, int y)
{
  int i,j;
  b->no_of_set_tiles--;
  for (i=0; i<ti->xmax; i++)
    for (j=0; j<ti->ymax; j++)
      if (ti->a[i][j]) b->a[x+i][y+j] = 0;
  return;
}

void remove_tile_from_position (board_t *b, tile_t *t, int instance, 
                                int x, int y)
{
  remove_tile_instance_from_position (b, t->instance[instance], x, y);
  t->is_on_board=0;
  return;
}

/************************* trying to fill the board *******************/

/* this function contains the recursion, in which it is tried to 
   tile the board with a given tileset 
   It takes a board b, which is already partially filled. It searches
   the first empty field and tries to place all free tiles onto this
   field. Then is makes the recursion. */

void try_to_fit_part (board_t *b, tile_set_t *ts, int lastx)
{
  int i,j,k,l=0,m;
  list_t *p;

#ifdef DEBUG
  if (b->no_of_set_tiles==4) fprintf (stderr, ".");
#endif

  if (b->no_of_set_tiles == ts->no_of_tiles) fprintf_board (stdout, b);
  else /* search the first free field on board */
    for (i=lastx; i<b->xmax; i++)
      for (j=0; j<b->ymax; j++)
        if (b->a[i][j]==0) { /* try to set all free tiles on it */
          for (p=ts->tiles; (p=p->next); )
            if (!((tile_t*)(p->val))->is_on_board)
              for (k=0; ((tile_t*)(p->val))->instance[k]; k++) { /* test all instances */
                m=((tile_t*)(p->val))->instance[k]->ystart;
                if (((tile_t*)(p->val))->instance[k]->a[l][m])
                  if (set_tile_to_position(b, (tile_t*)(p->val), k, i-l, j-m)) {
                    try_to_fit_part (b, ts, i);
                    remove_tile_from_position (b, (tile_t*)(p->val), k, i-l, j-m);
                  }
              }
          return;
        }
}

/* thats just a wrapper for try_to_fit_part, if that function takes 
   some more variable in the future. */
void try_to_fit (board_t *b, tile_set_t *ts)
{
  try_to_fit_part (b, ts, 0);
  return;
}

/**********************************************************************/

int main (int argc, char *argv[])
{
  tile_set_t *minos = make_n_ominos (5); /* make Pent(5)-ominos */

  /* make a rectangular field with size 12x6. If using rectangular fields,
     it is better to choose the x-size bigger than the y-size. */
  board_t *b=empty_board_by_size (10,6);

  if (argc==3) {
    log_depth  = atoi(argv[1]);
    skip_until = atol(argv[2]);
  }

  fprintf (stderr, "log_depth  is %i\n", log_depth);
  fprintf (stderr, "skip_untio is %li\n", skip_until);

  //  fprintf_tile_set (stdout, minos);

  /* now find the solutions */
  try_to_fit (b, minos);

  return 0;
}