/*
  4. Minimizirati DKA iz prethodne vjezbe. Ispisati zadani DKA i dobiveni
     minimalni DKA. Za zadanu ulaznu datoteku provjeriti ekvivalentnost rada
     automata.

     Dinko Korunic, Tue Nov 21 01:20:46 CET 2000
*/

// 	$Id: afjjp1-2b.cpp,v 1.7 2000/12/11 08:35:50 kreator Exp $	

#include <stl.h>
#include <iostream.h>
#include <string.h>
#include <strings.h>

// prirucni makroi radi razumijevanja
#define SkipBlankNL(ifs) SkipChar(ifs, " \n")
#define SkipDelimBlank(ifs) SkipChar(ifs, "; ")

typedef vector<int> Vector; // 1d
typedef vector<Vector> Vector2; // 2d

// preskacemo zeljene znakove, ma koliko ih god bilo
void SkipChar(istream &ifs, char *igme)
{
  for (; index(igme, ifs.peek())!=NULL; ifs.ignore());
} // SkipChar()

class Table
{
  Vector2 DFTable; // tablica stanja
 public:
  int OcistiNedohvatljiva(void);
  int Minimiziraj(void);
  int IsteGrupe(Vector2 *, int *, int *);
  friend ostream& operator<< (ostream &, Table &);
  friend istream& operator>> (istream &, Table &);
}; // class Table

// overload operatora >> i <<
ostream& operator<< (ostream &, Table &);
istream& operator>> (istream &, Table &);

// za ciscenje nedohvatljivih stanja
int Table::OcistiNedohvatljiva(void)
{
  Vector tmpDohvatljiva; // vektor koji sadrzi sva dohvatljiva stanja
  tmpDohvatljiva.push_back(0); // prema definiciji, pocinjem od 0-og stanja

  // pretrazi stanja koja su dohvatljiva
  for (Vector::iterator it1=tmpDohvatljiva.begin();
       it1!=tmpDohvatljiva.end(); it1++)
    for (Vector::iterator it2=DFTable[*it1].begin();
	 it2!=DFTable[*it1].end(); it2++)
      {
	// ako je vec u listi dohvatljivih, nemoj dodati
	if (*find(tmpDohvatljiva.begin(), tmpDohvatljiva.end(),
		  *it2)!=*it2)
	  {
	    // dodaj u listu dohvatljivih
	    tmpDohvatljiva.push_back(*it2);
	    // popravi iteratore
	    it1=tmpDohvatljiva.begin();
	    break;
	  }
      }

  // sortiraj listu dohvatljivih
  sort(tmpDohvatljiva.begin(), tmpDohvatljiva.end());

  // izbacuj, ali unazad
  for (int i=DFTable.size()-1; i>=0; --i)
    if (*find(tmpDohvatljiva.begin(), tmpDohvatljiva.end(), i)!=i)
      DFTable.erase(&DFTable[i]);

  // vrati broj dohvatljivih
  return tmpDohvatljiva.size();
} // Table::OcistiNedohvatljiva()

// provjeravanje za odredjeno stanje unutar DFTable da li za sve ulazne
// znakove vode u iste grupe..
int Table::IsteGrupe(Vector2 *Podjela, int *a, int *b)
{
  // sanity check
  if (DFTable[*a].size()!=DFTable[*b].size())
    return 0;

  // za sve ulazne znakove
  for (unsigned i=0; i<DFTable[*a].size(); ++i)
    // za svaku grupu u podjeli grupa
    for (unsigned gi=0; gi<Podjela->size(); ++gi)
      {
	Vector::iterator
	  ita=find((*Podjela)[gi].begin(), (*Podjela)[gi].end(),
		   DFTable[*a][i]),
	  itb=find((*Podjela)[gi].begin(), (*Podjela)[gi].end(),
		   DFTable[*b][i]);

	// ako je nadjen prijelaz za znak a, a znak b nije nadjen, onda
	// vrati 0
	if (ita!=(*Podjela)[gi].end() && *ita==DFTable[*a][i] &&
	    itb==(*Podjela)[gi].end())
	  return 0; // inace vrati 0
      }
  return 1; // u istim grupama
} // Table::IsteGrupe()

// minimizacija
int Table::Minimiziraj(void)
{

  Vector2 *twoI=new Vector2[2]; // prethodna iteracija i trenutna iteracija

  // pocetni uvjeti
  Vector tmp1, tmp2;
  for (unsigned i=0; i<DFTable.size(); ++i)
    if (*(DFTable[i].end()-1)) // ako je prihvatljiv
      tmp1.push_back(i);
    else
      tmp2.push_back(i);
  // dvije grupe podijeljene prema prihvatljivostima
  twoI[0].push_back(tmp1);
  twoI[0].push_back(tmp2);

  // radi dok mozes podijeliti
  int iter=1, newdeal=1;
  for (; newdeal; iter^=1)
    {
      newdeal=0;
      twoI[iter]=twoI[iter^1]; // novi vektor radimo modifikacijom postojeceg
      // za svaki vektor-grupu unutar trenutno promatranog
      for (unsigned i=0; i<twoI[iter^1].size(); ++i)
	{
	  Vector tmp; // dodatna grupa za izbacene elemente
	  for (unsigned j=1; j<twoI[iter][i].size(); )
	    // ako ne vode u iste grupe dodaj u tmp vektor, i obrisi iz ovog
	    // vektora
	    if (!IsteGrupe(&twoI[iter^1], &twoI[iter][i][0],
			   &twoI[iter][i][j]))
	      {
		newdeal=1;
		tmp.push_back(twoI[iter][i][j]);
		twoI[iter][i].erase(&twoI[iter][i][j]);
	      }
	    else
	      ++j;
	  if (newdeal)
	    twoI[iter].push_back(tmp);
	}
    }

  // vektor koji ce sadrzavati retke za izbaciti
  Vector tmpIzbaci;
  
  // za sve grupe unutar zadnje podjele
  for (Vector2::iterator it=twoI[iter].begin();
       it!=twoI[iter].end(); ++it)
    // ako ima vise od jednog elementa u listi ekvivalentnih
    if (it->size()>1)
      // za svaki element u listi ekvivalentnih osim za prvog
      for (Vector::iterator it1=it->begin()+1;
	   it1!=it->end(); tmpIzbaci.push_back(*it1), ++it1)
	for (Vector2::iterator itV=DFTable.begin();
	     itV!=DFTable.end(); ++itV)
	  // zamijeni sve reference u stanjima na [0] element
	  for (Vector::iterator itVV=itV->begin();
	       itVV!=itV->end()-1; ++itVV)
	    // veci je od retka koji treba izbaciti, dakle nakon
	    // izbacivanja ce pokazivati za jedan previse
	    if (*itVV==*it1)
	      *itVV=*(it->begin());
  
  // reverse jer tako treba izbacivati
  reverse(tmpIzbaci.begin(), tmpIzbaci.end());

  // osim toga treba pronaci sve elemente ispod redaka koje treba izbaciti i
  // popraviti pokazivace - ako je polje > od onog koji cemo izbaciti,
  // smanji ga za 1, i to pocevsi od najviseg do najnizeg!
  for (Vector::iterator it1=tmpIzbaci.begin();
       it1!=tmpIzbaci.end(); ++it1)
    for (Vector2::iterator itV=DFTable.begin();
	 itV!=DFTable.end(); ++itV)
      for (Vector::iterator itVV=itV->begin();
	   itVV!=itV->end()-1; ++itVV)
	if (*itVV>*it1)
	  (*itVV)--;

  // samo izbacivanje elemenata
  for (Vector::iterator it=tmpIzbaci.begin();
       it!=tmpIzbaci.end(); ++it)
    DFTable.erase(&DFTable[*it]);
    
  return tmpIzbaci.size();
} // Table::Minimiziraj()

// Overload operatora `>>' da napravimo transparentno ucitavanje tablice u
// mememoriju koja se naravno dinamicki alocira. Vraca se broj ucitanih
// stanja
istream& operator>> (istream &ifs, Table &TableOb)
{
  int tmpRead; // trenutni procitani _integer_
  while (ifs.peek()!=EOF) // dok mozes citaj
    {
      Vector tmpRow; // privremeni vektor za cijeli redak
      while (ifs && ifs.peek()!='\n')
	{
	  ifs >> tmpRead;
	  tmpRow.push_back(tmpRead); // ucitani vektor za 1 stanje
	  SkipDelimBlank(ifs);
	}
      TableOb.DFTable.push_back(tmpRow); // redak u kompletnu tablicu
      SkipBlankNL(ifs);
    }
  return ifs;
} // operator>>

// Isto za ispis.
ostream& operator<< (ostream &ofs, Table &TableOb)
{
  for (Vector2::iterator it1=TableOb.DFTable.begin();
       it1!=TableOb.DFTable.end(); ++it1)
    {
      ostream_iterator<int> out(ofs, "; ");
      copy(it1->begin(), it1->end(), out);
      ofs << endl;
    }
  
  return ofs;
} // operator<<

int main(void)
{
  Table burek;

  cin >> burek;
  cout << "Originalna tablica\n" << burek << endl;
  burek.OcistiNedohvatljiva();
  cout << "Tablica bez nedohvatljivih stanja\n" << burek << endl;
  burek.Minimiziraj();
  cout << "Minimizirana tablica\n" << burek << endl;
} // main