#include<stdio.h>
#include<stdarg.h>
#include<stdlib.h>
#include<ctype.h>
#include<ncurses.h>
#include<assert.h>

/*
Kompilace: gcc slova.c -o slova -lncurses
Spusteni: ./slova
Ovladani:
  Sipky -- pohyb v "bludisti"
  Klavesa q -- ukonceni programu
Prvky:
  Kurzor uprostred -- aktualni poloha "panacka v bludisti"
  Krizky -- sloupy neboli zdi
  Blikajici body -- stejna mista jako aktualni (svet je "periodicky")
  Prazdna mista -- misto, kde prechazi jedna oblast v jinou
  Ruzna pismena -- ruzne konstanty
  Ruzne barvy -- ruzne promenne
  Velka pismena -- po odstraneni vsech malych pismen by to bylo opet reseni

Tento programek resi dve veci.

Jednak to je nastroj pro upravu spojovych seznamu znaku (tedy slov).
Tomuto tematu se venuje vetsina funkci.

A pak umoznuje vizualizaci sveta reseni 2D rovnice
  funkce generate_sol_world svet vyrobi na zaklade 2-rovnice a reseni
  funkce show_sol_world jej barevne zobrazi
 */

// struktury pro upravy slov
typedef struct word word; // slovo
typedef struct list list;

// struktury pro 2D rovnici
typedef struct square square;
typedef struct sq_fifo sq_fifo;

struct list{
  char ch;
  list *next;
};

struct word{
  list *first;
  list *last;
};

struct square{
  square *up;
  square *down;
  square *left;
  square *right;
  unsigned char C;
  short v;
};

char additional = 0;

void print_word(word *w)
{
  list *l;

  for(l = w->first; l; l=l->next) printf("%c ", l->ch);
  printf("\n");
}

void print_words(word *w1, ...)
{
  va_list vl;
  word *w;
  list *l;

  va_start(vl, w1);
  for(w=w1; w; w = va_arg(vl, word *))
    for(l = w->first; l; l=l->next){
      if(l != w->first) printf(" ");
      else if(w != w1) printf("|");
      printf("%c", l->ch);
    }
  va_end(vl);

  printf("\n");
}

word *new_word(char *str)
{
  word *result;
  list *l;

  result = malloc(sizeof(word));
  if(!(*str)){
    result->first = result->last = NULL;
    return result;
  }

  result->first = result->last = malloc(sizeof(list));
  result->first->ch = *str;
  while(*(++str)){
    result->last->next = malloc(sizeof(list));
    result->last = result->last->next;
    result->last->ch = *str;
  }
  result->last->next = NULL;

  return result;
}

void add_char_to_end(word *w, char ch)
{
  if(additional) ch = tolower(ch);

  if(!w->first)
    w->first = w->last = malloc(sizeof(list));
  else{
    w->last->next = malloc(sizeof(list));
    w->last = w->last->next;
  }
  w->last->ch = ch;
  w->last->next = NULL;
}

void add_char_to_start(char ch, word *w)
{
  list *l;

  if(additional) ch = tolower(ch);

  l = malloc(sizeof(list));
  l->ch = ch;
  l->next = w->first;
  if(!w->last) w->last = l;
}

void add_to_end(word *firstw, ...)
{
  va_list vl;
  word *w;
  list *l;

  va_start(vl, firstw);
  for(;;){
    w = va_arg(vl, word *);
    if(!w) break;
    for(l=w->first; l; l=l->next)
      add_char_to_end(firstw, l->ch);
  }
  va_end(vl);
}

void add_to_start(word *w1, ...)
{
  va_list vl;
  word *w, *wstart, *lastw;
  list *l;

  wstart = new_word("");
  lastw = NULL;

  va_start(vl, w1);
  for(w=w1; w; w = va_arg(vl, word *)){
    if(lastw) add_to_end(wstart, lastw, NULL);
    lastw = w;
  }
  va_end(vl);

  if(wstart->last){
    wstart->last->next = lastw->first;
    lastw->first = wstart->first;
    if(!lastw->last) lastw->last = wstart->last;
  }

  free(wstart);
}

void free_word(word *w)
{
  list *l, *m;

  for(l=w->first; l; l=m){
    m = l->next;
    free(l);
  }

  free(w);
}

int word_len(word *w)
{
  int result = 0;
  list *l;

  for(l=w->first; l; l=l->next) result++;
  return result;
}

square *cur_square = NULL;

/*
Funkce dostane jako prvni parametr string -- 2-rovnici tvaru
"xAyBuCz = zCyBuAx"
mala pismena jsou promenne, velka konstanty.

Dalsi parametry jsou slova (pointer na strukturu word), ktera
tvori obrazy promennych v reseni. Tato slova jsou serazena
podle toho, jak jdou po sobe v leve strane rovnice.

Funkce nijak nekontroluje, jestli to skutecne tvori reseni,
tedy zda se leva strana shoduje s pravou

Funkce vrati nektere jedno policko sveta reseni 2D rovnice.
 */
square *generate_sol_world(char *eq_str, ...)
{
  int i, j, k, len;
  int var_index[256];
  int var_len[256];
  int v_counter;
  square *lside;
  word *w;
  list *l;
  va_list vl;
  square *result = NULL;

  for(i=0; i<256; i++) var_index[i] = -1;

  va_start(vl, eq_str);
  len = 0;
  for(i=0; eq_str[i] && eq_str[i] != '='; i++){ // namerim delku a spoctu indexy
    if(!isalpha(eq_str[i])) continue;
    if(isupper(eq_str[i])) len++;
    else{
      if(var_index[eq_str[i]] >= 0){
	fprintf(stderr, "Double variable '%c'\n", eq_str[i]);
	return NULL;
      }
      var_index[eq_str[i]] = len;

      w = va_arg(vl, word *);
      len += var_len[eq_str[i]] = word_len(w);
    }
  }
  va_end(vl);

  if(eq_str[i] != '='){
    fprintf(stderr, "Symbol '=' missing\n");
    return NULL;
  }

  lside = (square *)malloc(sizeof(square)*len);

  va_start(vl, eq_str);

  v_counter = j = 0;
  for(i=0; eq_str[i] != '='; i++){ // vyplnim pole lside a propojim levoprave
    if(!isalpha(eq_str[i])) continue;
    if(isupper(eq_str[i])){
      lside[j].C = 0;
      lside[j].v = 0;
      j++;
    }
    else{
      v_counter++;
      w = va_arg(vl, word *);
      for(l = w->first; l; l = l->next){
	if(!result) result = &lside[j];
	lside[j].v = v_counter;
	lside[j].C = l->ch;
	if(l == w->first) lside[j].left = NULL;
	else lside[j].left = &lside[j-1];
	if(l == w->last) lside[j].right = NULL;
	else lside[j].right = &lside[j+1];
	j++;
      }
    }
  }
  va_end(vl);
  assert(j == len);

  j = 0;
  for(; eq_str[i]; i++){
    if(!isalpha(eq_str[i])) continue;
    if(isupper(eq_str[i])) lside[j++].down = NULL;
    else{
      if(var_index[eq_str[i]] < 0){
	fprintf(stderr, "Unknown variable '%c'\n", eq_str[i]);
	return NULL;
      }
      for(k=0; k < var_len[eq_str[i]]; k++){
	lside[j+k].down = &lside[var_index[eq_str[i]]+k];
	if(!lside[j+k].v) lside[var_index[eq_str[i]]+k].up = NULL;
	else lside[var_index[eq_str[i]]+k].up = &lside[j+k];
      }
      j += k;
      var_index[eq_str[i]] = -1;
    }
  }

  if(j != len){
    printf("|left side| = %d != %d = |right side|\n", len, j);
    return NULL;
  }

  if(!result){
    fprintf(stderr, "Absence of free square\n");
    return NULL;
  }

  initscr();
  start_color();
  init_pair(1, COLOR_CYAN, COLOR_BLACK);
  init_pair(2, COLOR_RED, COLOR_BLACK);
  init_pair(3, COLOR_YELLOW, COLOR_BLACK);
  init_pair(4, COLOR_GREEN, COLOR_BLACK);
  init_pair(5, COLOR_MAGENTA, COLOR_BLACK);
  init_pair(6, COLOR_BLUE, COLOR_WHITE);
  init_pair(7, COLOR_BLACK, COLOR_WHITE);
  init_pair(8, COLOR_WHITE, COLOR_BLACK);
  keypad(stdscr,TRUE);
  noecho();

  return result;
}

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

 nasledujici funkce, promenne a struktury jsou pomocne pro funkci show_sol_world()

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

int lastkey;
int center_x, center_y;

void print_square(int x, int y, square *s)
{
  move(y+center_y, 2*x+center_x);
  if(s){
    if(s == cur_square) attron(A_BLINK);
    attron(COLOR_PAIR(s->v));
    printw("%c", s->C);
    attroff(COLOR_PAIR(s->v));
    if(s == cur_square) attroff(A_BLINK);;
  }
  else printw("#");
}

void erase_square(int x, int y)
{
  move(y+center_y, 2*x+center_x);
  printw(" ");
}

struct sq_fifo{
  square *s;
  int x, y;
} *fifo_field;

int fifo_end;

int x_min, x_max, y_min, y_max;

sq_fifo **used_square_field;
sq_fifo **used_square(int x, int y)
{
  if(x < x_min || x > x_max || y < y_min || y > y_max) return NULL;
  return &used_square_field[(x-x_min)+(y-y_min)*(x_max+1-x_min)];
}

void fifo_put(int x, int y, square *s)
{
  sq_fifo **used;

  used = used_square(x, y);
  if(used == NULL) return;
  if(*used){
    if((*used)->s != s){
      if(s && (*used)->s) erase_square(x, y);
      else print_square(x, y, NULL);
      (*used)->x = x_min-1;
    }
    return;
  }
  *used = &fifo_field[fifo_end];

  fifo_field[fifo_end].x = x;
  fifo_field[fifo_end].y = y;
  fifo_field[fifo_end].s = s;
  fifo_end++;
}

void show_sol_world()
{
  int width, height;
  int upwall, downwall, upwall_ori, downwall_ori;
  int x, y, i;
  square *s;

  clear();

  //printw("%d\n", lastkey);

  width = getmaxx(stdscr);
  height = getmaxy(stdscr);
  center_x = width/2;
  center_y = height/2;
  x_min = -(center_x/2);
  x_max = (width-center_x-1)/2;
  y_min = -center_y;
  y_max = height-center_y-1;

  used_square_field = (sq_fifo **)malloc(sizeof(sq_fifo *)*(x_max+1-x_min)*(y_max+1-y_min));
  fifo_field = (sq_fifo *)malloc(sizeof(sq_fifo)*(x_max+1-x_min)*(y_max+1-y_min));

  for(i=0; i<(x_max+1-x_min)*(y_max+1-y_min); i++) used_square_field[i] = NULL;
  fifo_end = 0;

  fifo_put(0, 0, cur_square);

  for(i=0; i<fifo_end; i++){
    x = fifo_field[i].x;
    y = fifo_field[i].y;
    s = fifo_field[i].s;
    if(x < x_min) continue;
    print_square(x, y, s);
    if(fifo_field[i].s){
      fifo_put(x+1, y, s->right);
      fifo_put(x-1, y, s->left);
      fifo_put(x, y-1, s->up);
      fifo_put(x, y+1, s->down);
    }
  }

  free(used_square_field);
  free(fifo_field);

  move(center_y, center_x);
}

int main()
{
  word *x, *y0, *y1, *z, *A, *B, *C;

  x = new_word("BCB");
  z = new_word("B");
  y0 = new_word("");
  y1 = new_word("");
  A = new_word("A");
  B = new_word("B");
  C = new_word("C");

  /*
    v tuto chvili mame reseni rovnice x A y0 B y1 C z = z C y0 B y1 A x
    tuto rovnici budeme upravovat "inverznimi makro-operacemi"
  */

  /* ladici tick, pri nezapnuti vizualizace
  print_words(x, A, y0, B, y1, C, z, NULL);
  print_words(z, C, y0, B, y1, A, x, NULL);
  */

  additional = 1; // vsechna nove pridana pismenka uz budou mala

  add_to_end(z,  C, y0,       NULL); // x A y0 B y1 C z = z B y1 A x C y0
  add_to_end(y0, B, y1,       NULL); // x A y0 C z B y1 = z B y1 A x C y0

  add_to_end(y1, A, x,        NULL); // x A y0 C z B y1 = z B y1 C y0 A x
  add_to_end(x,  A, y0, C, z, NULL); // x B y1 A y0 C z = z B y1 C y0 A x
  add_to_end(z,  B, y1,       NULL); // x B y1 A y0 C z = z C y0 A x B y1
  add_to_end(y1, A, y0,       NULL); // x B y1 C z A y0 = z C y0 A x B y1
  add_to_end(y0, A, x,        NULL); // x B y1 C z A y0 = z C y0 B y1 A x
  add_to_end(x,  B, y1, C, z, NULL); // x A y0 B y1 C z = z C y0 B y1 A x (jako na zacatku)

  /* ladici tick, pri nezapnuti vizualizace
  printf("\n");
  printf("x = "); print_word(x);
  printf("y0 = "); print_word(y0);
  printf("y1 = "); print_word(y0);
  printf("z = "); print_word(z);
  printf("\n");
  print_words(x, A, y0, B, y1, C, z, NULL);
  print_words(z, C, y0, B, y1, A, x, NULL);
  */

  cur_square = generate_sol_world("xAyBuCz = zCyBuAx", x, y0, y1, z);

  /* zas jiny priklad 2-soustavy a reseni
  x = new_word("AB");
  y0 = new_word("CD");
  z = new_word("EF");
  y1 = new_word("ABCDEFABCDEF");

  cur_square = generate_sol_world("uXAByEFxCDz = xCDzAByEFXu", y1, y0, x, z);
  */

  if(!cur_square) return 1;

  for(;;){
    show_sol_world();
    lastkey = getch();
    if(lastkey == 'q') break;
    switch(lastkey){
    case 260: // left
      if(cur_square->left) cur_square = cur_square->left;
      break;
    case 261: // right
      if(cur_square->right) cur_square = cur_square->right;
      break;
    case 259: // up
      if(cur_square->up) cur_square = cur_square->up;
      break;
    case 258:
      if(cur_square->down) cur_square = cur_square->down;
      break;
    }
  }
  endwin();

  return 0;
}