/*
  Dinko Korunic, 36355514, kreator@fly.srk.fer.hr
  Mon Oct  2 23:02:57 CEST 2000

  1. Konstruirati NKA (nedeterministicki konacni automat) koji
  odred/uje ispravnost zapisa cijelih i realnih brojeva. Izgrad/eni konacni
  automat programski realizirati. Izgrad/eni program iz datoteke cita
  pojedine zapise koji mogu biti odvojeni prazninama, tabulatorima te
  znakovima za novi red. Za svaki zapis program provjeriava pripadnost
  pojedinoj klasi brojeva i ispisuje ih u posebnu datoteku.

*/

#define ULAZNA_DATOTEKA "ulaz.txt"
#define IZLAZNA_DATOTEKA "izlaz.txt"
#define DATOTEKA_STANJA "stanja.txt"

#include <iostream.h>
#include <fstream.h>
#include <stl.h> // Standard template library

#ifdef DEBUG
#define GC_DEBUG
#include <gc.h> // Conservative garbage collector (Boehm's GC)
#endif

void fatal(char *);
char *transliterator(char *);

#ifndef __USE_BSD
char *strsep(char **, char *, char *);
#endif

struct Stanje
{
  vector<int> VektorStanja; // vektor stanja koja vode iz tog stanja
};

class NKA
{
private:
  int *Prihvatljivost, // polje prihvatljivosti
    BrojRedova, // broj redova u tablici stanja
    BrojStupaca; // broj stupaca u tablici stanja
  Stanje **Tablica; // tablica stanja
public:
  NKA();
  Simuliraj(int, char *);
  char *UlazniZnakovi; // polje ulaznih znakova
};

NKA::NKA()
{
  // otvaranje datoteke i citanje osnovnih podataka
  ifstream ifs;
  ifs.open(DATOTEKA_STANJA);
  if (!ifs)
    fatal("Nije moguce otvoriti "+DATOTEKA_STANJA);
  // primjer datoteke:
  // 2 2                --> dva retka i dva stupca podataka
  // +-                 --> moguci znakovi
  // 0,1; x; 0;         --> prijelaz u 0,1; kraj; neprihvatljivo
  //   1; x; 1;         --> prijelaz u 1; prijelaz u 1; prihvatljivo
  ifs >> BrojRedova >> BrojStupaca;
  
  // alociramo prostor za dvodimenzionalnu tablicu stanja
  Tablica=new (Stanje *)[BrojRedova];
  int i, j;
  for (i=0; i<BrojRedova; ++i)
    Tablica[i]=new Stanje[BrojStupaca]; // moglo se napraviti VectorOfVector
  // napravimo tablicu prihvatljivosti stanja
  Prihvatljivost=new int[BrojRedova];
  // a isto tako napravimo i tablicu ulaznih znakova
  UlazniZnakovi=new [BrojRedova];
  ifs.getline(UlazniZnakovi, BrojStupaca+1);

  // petlja u kojoj cemo napuniti tablicu stanja
  char ch;
  int tmpI;
  i=0;
  j=0;
  while(ifs.get(ch)) // C++ f/(i/o)stream je bufferiran, pa "nije" sporo
    {
      switch(ch)
	{
	case 'x': // posljednje stanje
	  Tablica[i][j].VektorStanja.push_back(-1);
	  break;
	case ';': // kraj doticnog stanja
	  if (i==BrojStupaca)
	    ++j;
	  else ++i;
	  break;
	case ',': // izmedju dva stanja, zbog ';' nam nije tako vazan
	case ' ': // razni delimiteri ...
	case '\n':
	case '\t':
	  break; // ... se ignoriraju!
	default: // opa, ovo nije delimiter!
	  ifs.putback(ch);
	  ifs >> tmpI;
	  if (i>BrojStupaca)
	    {
	      Prihvatljivost[j]=tmpI; // dakle, ucitaj prihvatljivost
	      i=0;
	      ++j;
	    }
	  else
	    Tablica[i][j].VektorStanja.push_back(tmpI);
	}
    }
  
  ifs.close();
}

// vraca prihvatljivost 0/1, ulazno su tekuce stanje + ulazni znak
int NKA::Simuliraj(int stanje, char *znak)
{
  // dosli smo do kraja niza, vrati prihvatljivost
  if (!(*znak))
    return Prihvatljivost[stanje];
  
  // saznaj poziciju unutar tablice stanja
  char *location=find(UlazniZnakovi, UlazniZnakovi+BrojStupaca, *znak);
  // ovo gore se moglo izvesti i sa index()
  if (location==NULL) // dakle nije nadjen ulazni znak
    return 0;
  int pos=location-UlazniZnakovi;

  // iteriraj listu stanja
  vector<int>::iterator iterStanja;
  for (iterStanja=Tablica[stanje][pos].VektorStanja.begin();
       iterStanja!=Tablica[stanje][pos].VektorStanja.end();
       ++iterStanja)
      // dakle ako je _iti jedno_ stanje prihvatljivo, vrati 1
      if (Simuliraj(Tablica[stanje][pos].VektorStanja[iterStanja], ++znak))
	return 1;
  // niti jedno stanje nije bilo prihvatljivo!
  return 0;
}

int main(void)
{
  istream ifs;
  ifs.open(ULAZNA_DATOTEKA);
  if (!ifs)
    fatal("Nije moguce otvoriti "+ULAZNA_DATOTEKA);
  ostream ofs;
  ofs.open(IZLAZNA_DATOTEKA);
}

void fatal(char *msg)
{
  cerr << msg << endl;
  exit(EXIT_FAILURE);
}

// ovaj dio je iz moje starije verzije ovog labosa pisane kompletno u C-u
char *transliterator(char *oldstring, char *znakovi)
{
  char *posp, *charp, *pos, *stringp, *tmp=strdup(znakovi);

  /* Polako scanniraj ulazni niz i transliteriraj, s time sto se ide po
   * razlicitim klasama za transliteriranje i zamjenjuje svaki znak koji
   * se pojavljuje */
  for (stringp=strsep(&posp, tmp, ";"); stringp!=NULL;
       stringp=strsep(&posp, NULL, ";"))
    for (charp=stringp+1; *charp; ++charp)
      for (pos=oldstring; (pos=index(pos, *charp))!=NULL;
	   *(pos++)=*stringp);
  free(tmp);
}

// ako na sistemu ne postoji BSD-ish strsep(), opet cisti C
char *strsep(char **save, char *str, char *fs)
{
  char *pos=*save, /* Zadnja pozicija (kod zadnjeg poziva) */
    *tmp;
  if (str!=NULL) pos=str; /* Uu.. scanniramo novi string */
  for (;pos && *pos &&
	 index(fs, *pos)!=NULL; ++pos); /* Izbjegni vodece sep. */
  if (!pos || !*pos)
    return (pos=*save=NULL); /* Baah. String ima samo separatore */
  tmp=pos; /* OK. Zadrzi poziciju tokena */
  for (;*pos && index(fs, *pos)==NULL;
       ++pos); /* Izbjegni sadrzaj tokena */
  if (*pos) *pos++=0; /* Makni prvi separator poslije tokena */
  else pos=NULL; /* Gle! Kraj stringa :-) */
  *save=pos;
  return(tmp);
}