#include <stdio.h>
#include "util.h"
#include "gmap.h"

typedef struct index_map {
  int internal_index;
  int mapped_index;
  int range;
  int * entries;
} * IM;

IM IM_alloc(internal_index, range, length) int internal_index, range, length;
{
  int * entries = (int *) malloc ((1 + length) * sizeof(int));
  IM x = (IM) malloc (sizeof(*x));
  x -> internal_index = internal_index;
  x -> mapped_index = 0;
  x -> range = range;
  x -> entries = entries;
  bzero(x -> entries, (1 + length) * sizeof(int));
  return x;
}

skip_to_eol(fd) FILE * fd;
{
  while(fgetc(fd) != '\n') ;
}

skip_prologue(fd) FILE * fd;
{
  while(fgetc(fd) != ' ') skip_to_eol(fd);
}

readn(fd) FILE * fd;
{
  int i,x;
  x = fscanf(fd,"%d",&i);
  if (x != 1) {
    fprintf(stderr,"READN failed to read an integer\n"); abort(1);
  }
  return i;
}

int global_count;
IM * global_maps;

column_cost(k1,k2,count,maps)
     int k1,k2,count;
     IM * maps;
{
  int t = 0, i;
  for (i = 0; i < count; i++)
    if (maps[i] -> entries[k1] != maps[i] -> entries[k2]) t++;
  return t;
}

compare_columns(j1,j2) int j1,j2;
{
  return column_cost(j1,j2,global_count, global_maps) == 0;
}

hash_column(j) int j;
{
  int i;
  int x = 1;
  int base = 0;
  for (i = 0; i < global_count; i++)
    {
    x = x * (base + global_maps[i] -> entries[j]);
    base = base + global_maps[i] -> range + 1;
    }
  return x;
}

copy_column(j) int j; {return j; }

GMAP colmap;

read_i_maps(fd) FILE * fd;
{
  int count, size, internal_index, range;
  int i,j,k;
  IM * maps;

  skip_prologue(fd);
  count = readn(fd);
  size = readn(fd);

  maps = (IM *) malloc (sizeof(IM) * count);
  
  global_maps = maps;
  global_count = count;
  
  for (i = 0; i < count; i++)
    {
      internal_index = readn(fd);
      range = readn(fd);
      maps[i] = IM_alloc(internal_index, range, size);
      for (j = 1; j <= size; j++)
	{
	  maps[i] -> entries[j] = readn(fd);
	}
    }
  printf("Read in matrix of %d rows, %d columns\n", count, size);

  {
    int cost = 0;
    for (j = 2; j <= size; j++)
      {
	cost = cost + column_cost(j - 1, j, count,maps);
      }
    printf("Raw cost is %d (total internal transition count)\n", cost);
  }

    colmap = g_new_map(hash_column, copy_column, copy_column, compare_columns, size, size);

    for (j = 1; j <= size; j++)
      g_map(colmap,j);

  k = g_map_size(colmap);
  printf("%d columns before removing duplicates, %d after\n", size, k);
      
  {
    int cost = 0;
    for (j = 2; j <= k; j++)
      {
	cost = cost + column_cost(g_unmap(colmap,j - 1),
				  g_unmap(colmap,j),
				  count,
				  maps);
      }
    printf("Reduced cost is %d (total internal transition count)\n", cost);
  }
}

stream(in,out) FILE * in, *out;
{
  int c = fgetc(in);
  while (c != EOF)
    {
      fputc(c,out);
      c = fgetc(in);
    }
}

main()
{
  read_i_maps(stdin);

#ifdef CHECK_INPUT
  printf("Remainder of input is:\n----\n");
  stream(stdin,stdout);
  printf("----\n");
#endif
}