#include "DKA.h"


DKA::DKA(int nstates, int nabeceda)
{
    this->nstates = nstates;
    this->nabeceda = nabeceda;
    prechodova_funkcia = new prechod_pre_stav[nstates];
    for (int i=0;i<nstates;i++)
    {
        prechodova_funkcia[i].accept = false;
        prechodova_funkcia[i].pre_pismeno = new int[nabeceda];
    }
}

DKA::~DKA()
{
    for (int i=0;i<nstates;i++)
        delete [] prechodova_funkcia[i].pre_pismeno;
    delete [] prechodova_funkcia;
}

void DKA::add_prechod(int state, int pismeno, int next_state)
{
    prechodova_funkcia[state].pre_pismeno[pismeno] = next_state;
}

void DKA::accept_states(int astates, int * states)
{
    for (int i=0;i<astates;i++)
        prechodova_funkcia[states[i]].accept = true;
}

void DKA::minimize()
{

    std::queue<trieda_pismeno> na_spracovanie;
    int rozklad[nstates]; // triedy do ktorych stavy patria
    doubleint rozdelenie_triedy[nstates];
    zmena_triedy trieda_sa_zmenila[nstates];
    int i,j;
    trieda_pismeno dvojica_na_spracovanie;
    int spolutried = 2;
    int temptried;
    prechod_pre_stav * nova_prechodova_funkcia;

    for (i=0;i<nstates;i++)
    {
        trieda_sa_zmenila[i].rozdelujesa = false;
        trieda_sa_zmenila[i].pismeno_uz_je_vo_fronte = new bool[nabeceda];
        for (j=0;j<nabeceda;j++)
            trieda_sa_zmenila[i].pismeno_uz_je_vo_fronte[j] = false;
        rozdelenie_triedy[i].a = 0;
        rozdelenie_triedy[i].b = 0;
    }

    int akc_stavov=0;
    for (i=0;i<nstates;i++)
    {
        rozklad[i] = prechodova_funkcia[i].accept;
        if (prechodova_funkcia[i].accept)
            akc_stavov++;
    }
    if ((akc_stavov == nstates) || (akc_stavov == 0)) // bud akceptuje vsetko || nic
    {
        spolutried = 1;
        nova_prechodova_funkcia = new prechod_pre_stav[spolutried]; // vytvorenie novej prechodovej funkcie
        for (i=0;i<spolutried;i++)
            nova_prechodova_funkcia[i].pre_pismeno = new int[nabeceda];
        for (i=0;i<spolutried;i++)
        {
            for (j=0;j<nabeceda;j++)
                nova_prechodova_funkcia[i].pre_pismeno[j] = 0;
            nova_prechodova_funkcia[i].accept = (akc_stavov == nstates);
        }

    }
    else
    {
        if (j <= nstates/2)
            dvojica_na_spracovanie.trieda = 1;
        else
            dvojica_na_spracovanie.trieda = 0;
        for (i=0;i<nabeceda;i++)
        {
            dvojica_na_spracovanie.pismeno = i;
            na_spracovanie.push(dvojica_na_spracovanie);
        }
        while (!na_spracovanie.empty()) // vyprazdnujeme triedy na spracovanie
        {
            dvojica_na_spracovanie = na_spracovanie.front(); // trieda C a pismeno
            na_spracovanie.pop();
            for (i=0;i<nstates;i++)
            {
                if (rozklad[prechodova_funkcia[i].pre_pismeno[dvojica_na_spracovanie.pismeno]] == dvojica_na_spracovanie.trieda)
                    rozdelenie_triedy[rozklad[i]].a++; // a++ ak zo stavu i na pismeno prejde do stavu z triedy C
                else rozdelenie_triedy[rozklad[i]].b++; // b++ ak zo stavu i na pismeno prejde do stavu mimo triedy C
            }
            temptried = spolutried;
            for (i=0;i<temptried;i++)
            {
                if ((rozdelenie_triedy[i].a > 0) && (rozdelenie_triedy[i].b > 0)) // teda triedu i, trieda C rozdeluje
                {
                    trieda_sa_zmenila[i].rozdelujesa = true;
                    trieda_sa_zmenila[i].dalsia_trieda = spolutried;
                    spolutried++;
                }
            }
            for (i=0;i<nstates;i++) // zmenime prislusnost do tried
            {
                j = rozklad[i];
                // stavy,ktore prejdu do triedy C - povodna trieda
                // stavy,ktore prejdu mimo triedy C - nova trieda
                if ((trieda_sa_zmenila[rozklad[i]].rozdelujesa) &&
                    (rozklad[prechodova_funkcia[i].pre_pismeno[dvojica_na_spracovanie.pismeno]] != dvojica_na_spracovanie.trieda) &&
                    (!trieda_sa_zmenila[dvojica_na_spracovanie.trieda].rozdelujesa ||
                    (rozklad[prechodova_funkcia[i].pre_pismeno[dvojica_na_spracovanie.pismeno]] != trieda_sa_zmenila[dvojica_na_spracovanie.trieda].dalsia_trieda)))
                    rozklad[i]  = trieda_sa_zmenila[rozklad[i]].dalsia_trieda;
            }
            j = na_spracovanie.size();
            for (i=0;i < j;i++) // pridavame triedy na spracovanie
            {
                dvojica_na_spracovanie = na_spracovanie.front();
                na_spracovanie.pop();
                if (trieda_sa_zmenila[dvojica_na_spracovanie.trieda].rozdelujesa)
                {
                    trieda_sa_zmenila[dvojica_na_spracovanie.trieda].pismeno_uz_je_vo_fronte[dvojica_na_spracovanie.pismeno] = true;
                    na_spracovanie.push(dvojica_na_spracovanie); //stara trieda
                    dvojica_na_spracovanie.trieda = trieda_sa_zmenila[dvojica_na_spracovanie.trieda].dalsia_trieda;
                    na_spracovanie.push(dvojica_na_spracovanie);
                }
                else na_spracovanie.push(dvojica_na_spracovanie);
            }
            for (i=0;i<temptried;i++) // pridavame (trieda,pismeno) ktore este nie su vo fifo
            {
                if (trieda_sa_zmenila[i].rozdelujesa)
                {
                    trieda_sa_zmenila[i].rozdelujesa = false;
                    if (rozdelenie_triedy[i].a < rozdelenie_triedy[i].b)
                        trieda_sa_zmenila[i].dalsia_trieda = i; // minimalnejsia trieda
                    for (j=0;j<nabeceda;j++)
                    {
                        if (!trieda_sa_zmenila[i].pismeno_uz_je_vo_fronte[j])
                        {
                            dvojica_na_spracovanie.pismeno = j;
                            dvojica_na_spracovanie.trieda = trieda_sa_zmenila[i].dalsia_trieda;
                            na_spracovanie.push(dvojica_na_spracovanie);
                        }
                        else trieda_sa_zmenila[i].pismeno_uz_je_vo_fronte[j] = false;
                    }
                }
                rozdelenie_triedy[i].a = 0;
                rozdelenie_triedy[i].b = 0;
            }
        }
        int zac_trieda = rozklad[0]; // ked zac. stav je v triede != 0
        if(zac_trieda != 0)
            for (i=0;i<nstates;i++)
                if(rozklad[i] == zac_trieda) rozklad[i] = 0;
                else if(rozklad[i] == 0) rozklad[i] = zac_trieda;

        nova_prechodova_funkcia = new prechod_pre_stav[spolutried]; // vytvorenie novej prechodovej funkcie
        for (i=0;i<spolutried;i++)
            nova_prechodova_funkcia[i].pre_pismeno = new int[nabeceda];
        for (i=0;i<nstates;i++)
        {
            for (j=0;j<nabeceda;j++)
            {
                nova_prechodova_funkcia[rozklad[i]].pre_pismeno[j] = rozklad[prechodova_funkcia[i].pre_pismeno[j]];
            }
            nova_prechodova_funkcia[rozklad[i]].accept = prechodova_funkcia[i].accept;
        }
    }


    for (i=0;i<nstates;i++)
        delete [] trieda_sa_zmenila[i].pismeno_uz_je_vo_fronte;
    for (int i=0;i<nstates;i++)
        delete [] prechodova_funkcia[i].pre_pismeno;
    delete [] prechodova_funkcia;
    prechodova_funkcia = nova_prechodova_funkcia;
    nstates = spolutried;
}

int DKA::getsize()
{
    return nstates;
}

bool DKA::is_equal(DKA * dka) // dka aj this by mal byt minimalny DKA
{
    if ((this->nstates != dka->nstates) || (this->nabeceda != dka->nabeceda)) return false;
    int izomorfizmus[nstates];
    std::queue<int> stavy_na_spracovanie;
    int i, j,stav;

    for (i = 1;i<nstates;i++) izomorfizmus[i] = -1;
    izomorfizmus[0] = 0;
    stavy_na_spracovanie.push(0);

    while (!stavy_na_spracovanie.empty())
    {
        stav = stavy_na_spracovanie.front();
        stavy_na_spracovanie.pop();
        for (i = 0;i < nabeceda;i++)
            if (izomorfizmus[prechodova_funkcia[stav].pre_pismeno[i]] == -1)
            {
                stavy_na_spracovanie.push(prechodova_funkcia[stav].pre_pismeno[i]);
                izomorfizmus[prechodova_funkcia[stav].pre_pismeno[i]] = dka->prechodova_funkcia[izomorfizmus[stav]].pre_pismeno[i];
            }
    }
    for (i = 0;i<nstates;i++)
    {
        if (prechodova_funkcia[i].accept != dka->prechodova_funkcia[izomorfizmus[i]].accept) return false;
        for (j = 0;j < nabeceda;j++)
            if (izomorfizmus[prechodova_funkcia[i].pre_pismeno[j]] != dka->prechodova_funkcia[izomorfizmus[i]].pre_pismeno[j]) return false;
    }
    return true;
}

void DKA::vypis()
{
    std::cout << std::endl << "  ";
    for (int i = 0;i<nstates;i++)
    {
        if (prechodova_funkcia[i].accept) std::cout << "A";
        std::cout << i << " ";
    }
    for (int j = 0;j<nabeceda;j++)
    {
        std::cout << std::endl << j << " ";
        for (int i = 0;i<nstates;i++)
            std::cout << prechodova_funkcia[i].pre_pismeno[j] << "  ";
    }

}
