#include "NKA.h"

NKA::NKA(int nstates, int nabeceda)
{
    this->nstates = nstates;
    this->nabeceda = nabeceda;
    prechodova_funkcia = new prechod_pre_ned_stav[nstates];
    int j,k;
    for (int i=0;i<nstates;i++)
    {
        prechodova_funkcia[i].accept = false;
        prechodova_funkcia[i].pre_pismeno = new bool*[nabeceda];
        for (j=0;j<nabeceda;j++)
        {
            prechodova_funkcia[i].pre_pismeno[j] = new bool[nstates];
            for (k=0;k<nstates;k++) prechodova_funkcia[i].pre_pismeno[j][k] = false;
        }
    }
}

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

}

inline void NKA::add_prechod(int state, int pismeno, bool * next_states)
{
    for (int i=0;i<nstates;i++)
        prechodova_funkcia[state].pre_pismeno[pismeno][i] = next_states[i];
}

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

DKA * NKA::convert2DKA()
{
    int dnstates = 1 << nstates;
    prechod_pre_stav temp_prechodova_funkcia[dnstates];
    int i,j,k,m,stav;

    for (i = 0;i<dnstates;i++)
    {
        temp_prechodova_funkcia[i].pre_pismeno = new int[nabeceda];
        for (j = 0;j<nabeceda;j++)
            temp_prechodova_funkcia[i].pre_pismeno[j] = 0;
        temp_prechodova_funkcia[i].accept = false;
    }
    for (i = 1;i<dnstates;i++)
    {
        stav = 1;
        for (k = 0;k<nstates;k++)
        {
            if ((stav & i) > 0)
                for (j = 0;j<nabeceda;j++)
                {
                    for (m = 0;m<nstates;m++)
                        if (prechodova_funkcia[k].pre_pismeno[j][m] && ((temp_prechodova_funkcia[i].pre_pismeno[j] & (1 << m)) == 0))
                            temp_prechodova_funkcia[i].pre_pismeno[j] += 1 << m;
                }
            stav <<= 1;
        }
    }
// odstranime nedosiahnutelne stavy
    std::queue<int> dosiahnutelne_stavy;
    dosiahnutelne_stavy.push(1);
    temp_prechodova_funkcia[1].accept = true;
    while (!dosiahnutelne_stavy.empty())
    {
        i = dosiahnutelne_stavy.front();
        dosiahnutelne_stavy.pop();
        for (j = 0;j<nabeceda;j++)
                if(!temp_prechodova_funkcia[temp_prechodova_funkcia[i].pre_pismeno[j]].accept)
                {
                    temp_prechodova_funkcia[temp_prechodova_funkcia[i].pre_pismeno[j]].accept = true;
                    dosiahnutelne_stavy.push(temp_prechodova_funkcia[i].pre_pismeno[j]);
                }

    }
// stavy, ktore maju accept==true su dosiahnutelne
    int dosiahnutelnych_dnstates = 0;
    int akceptacnych_stavov = 0;
    int akceptacnestavy = 0;
    int mapovanie[dnstates];
    for (i = 0;i<nstates;i++)
        if (prechodova_funkcia[i].accept)
            akceptacnestavy += (1 << i);
    for (i = 1;i<dnstates;i++)
        if (temp_prechodova_funkcia[i].accept)
        {
            mapovanie[i] = dosiahnutelnych_dnstates;
            dosiahnutelnych_dnstates++;
            if ((i & akceptacnestavy) > 0) akceptacnych_stavov++;
        }
    if (temp_prechodova_funkcia[0].accept)
    {
        mapovanie[0] = dosiahnutelnych_dnstates;
        dosiahnutelnych_dnstates++;
    }
    int zoznamakceptacnychstavov[akceptacnych_stavov];
    akceptacnych_stavov = 0;
    DKA * dka = new DKA(dosiahnutelnych_dnstates,nabeceda);
    for (i = 0;i<dnstates;i++)
        if (temp_prechodova_funkcia[i].accept)
        {
            for (j = 0;j<nabeceda;j++)
                dka->add_prechod(mapovanie[i], j, mapovanie[temp_prechodova_funkcia[i].pre_pismeno[j]]);
            if ((i & akceptacnestavy) > 0)
            {
                zoznamakceptacnychstavov[akceptacnych_stavov] = mapovanie[i];
                akceptacnych_stavov++;
            }
        }
    dka->accept_states(akceptacnych_stavov, zoznamakceptacnychstavov);
    for (i = 0;i<dnstates;i++)
        delete [] temp_prechodova_funkcia[i].pre_pismeno;
    return dka;
}

DKA * NKA::convert2minDKA()
{
    DKA * dka = convert2DKA();
    dka->minimize();
    return dka;
}

int NKA::generateNextNKA() // ak -1 som na zaciatku
{
    int i = nstates - 1;
    bool continues = true;
    while(prechodova_funkcia[i].accept && (i >= 0))
    {
        prechodova_funkcia[i].accept = false;
        i--;
    }
    if(i >= 0) prechodova_funkcia[i].accept = true;
    else {
        for(int i = nstates - 1; (i >= 0) && continues; i--)
            for(int j = nabeceda - 1; (j >= 0) && continues; j--)
                for(int k = nstates - 1; k >= 0; k--)
                {
                    if(prechodova_funkcia[i].pre_pismeno[j][k]) prechodova_funkcia[i].pre_pismeno[j][k] = false;
                    else
                    {
                        continues = false;
                        prechodova_funkcia[i].pre_pismeno[j][k] = true;
                        break;
                    }
                }
        if(continues) return -1;
    }
    return 0;
}

void NKA::generateNextNKA(double prp, double pra)
{
    for(int i = 0; i < nstates; i++)
        for(int j = 0; j < nabeceda; j++)
            for(int k = 0; k < nstates; k++)
                if((rand()/(RAND_MAX + 1.0)) < prp)
                    prechodova_funkcia[i].pre_pismeno[j][k] = true;
                else prechodova_funkcia[i].pre_pismeno[j][k] = false;
    for(int i = 0; i < nstates; i++)
        if((rand()/(RAND_MAX + 1.0)) < pra)
            prechodova_funkcia[i].accept = true;
        else prechodova_funkcia[i].accept = false;
}

void NKA::generateNextNKA(double prp, double prp0, double pra)
{
    for(int i = 0; i < nstates; i++)
    {
        for(int k = 0; k < nstates; k++)
            if((rand()/(RAND_MAX + 1.0)) < prp0)
                prechodova_funkcia[i].pre_pismeno[0][k] = true;
            else prechodova_funkcia[i].pre_pismeno[0][k] = false;
        prechodova_funkcia[i].pre_pismeno[0][(i+1) % nstates] = true;
        for(int j = 1; j < nabeceda; j++)
            for(int k = 0; k < nstates; k++)
                if((rand()/(RAND_MAX + 1.0)) < prp)
                    prechodova_funkcia[i].pre_pismeno[j][k] = true;
                else prechodova_funkcia[i].pre_pismeno[j][k] = false;
    }
    for(int i = 0; i < nstates; i++)
        if((rand()/(RAND_MAX + 1.0)) < pra)
            prechodova_funkcia[i].accept = true;
        else prechodova_funkcia[i].accept = false;
}

void NKA::generateNextNKA(int ohr_d, double pra)
{
    int mdelta, stav;
    for(int i = 0; i < nstates; i++)
        for(int j = 0; j < nabeceda; j++)
        {
            for(int k = 0; k < nstates; k++)
                prechodova_funkcia[i].pre_pismeno[j][k] = false;
            mdelta = (rand() % ohr_d);
            for(int k = 0; k < mdelta; k++)
            {
                stav = rand() % nstates;
                prechodova_funkcia[i].pre_pismeno[j][stav] = true;
            }
        }
    for(int i = 0; i < nstates; i++)
        if((rand()/(RAND_MAX + 1.0)) < pra)
            prechodova_funkcia[i].accept = true;
        else prechodova_funkcia[i].accept = false;
}

bool NKA::is_minimal(DKA * dka) // dka - minimalny DKA k NKA
{
    NKA * nka;
    DKA * dkam;
    for(int i = 1;i < nstates;i++)
    {
        nka = new NKA(i,nabeceda);
        do
        {
            dkam = nka->convert2minDKA();
            if(dkam->is_equal(dka))
            {
                delete dkam;
                delete nka;
                return false;
            }
            delete dkam;
        } while(nka->generateNextNKA() != -1);
        delete nka;
    }
    return true;

}

bool NKA::have_cycle()
{
    std::stack<int> mystack;
    int stav, stav2;
    bool stavy[nstates];
    int i;

    for(i=0;i< nstates;i++) stavy[i] = false;

    for(int j=0;j< nabeceda;j++)
    {
        stavy[0] = true;
        mystack.push(0);
        while ((int) mystack.size() > 0)
        {
            if((int) mystack.size() == nstates)
                if(prechodova_funkcia[mystack.top()].pre_pismeno[j][0])
                    return true;
            stav = mystack.top();
            for(int k=0;k< nstates;k++)
                if(prechodova_funkcia[stav].pre_pismeno[j][k] && !stavy[k])
                {
                    mystack.push(k);
                    stavy[k] = true;
                    break;
                }
            if(mystack.top() == stav)
            {
                stavy[stav] = false;
                mystack.pop();
                if(stav == 0) break;
                stav2 = mystack.top();
                while (mystack.top() == stav2)
                {
                    for(int k=(stav+1);k< nstates;k++)
                        if(prechodova_funkcia[stav2].pre_pismeno[j][k] && !stavy[k])
                        {
                            mystack.push(k);
                            stavy[k] = true;
                            break;
                        }
                    if(stav2 == mystack.top())
                    {
                        stav = stav2;
                        mystack.pop();
                        if(stav2 == 0) break;
                        stavy[stav2] = false;
                        stav2 = mystack.top();
                    }
                }
            }
        }
    }
    return false;
}

void NKA::vypis()
{
    int akc_stavov = 0;
    int pocet_prech = 0;

    std::cout << "digraph NFSA {";
    std::cout << std::endl << "rankdir=LR;";
    std::cout << std::endl << "size=\"8,5\"";
    std::cout << std::endl << "node [shape = doublecircle];";
    for (int i = 0;i<nstates;i++)
    {
        if (prechodova_funkcia[i].accept)
        {
             std::cout << " " << i;
             akc_stavov++;
        }
    }
    std::cout << ";" << std::endl << "node [shape = circle];";

	for (int i = 0;i<nstates;i++)
        for (int j = 0;j<nabeceda;j++)
            for (int k = 0;k<nstates;k++)
                if(prechodova_funkcia[i].pre_pismeno[j][k])
                {
                    std::cout << std::endl << i << " -> " << k << " [ label = \"" << j << "\" ];";
                    pocet_prech++;
                }
    std::cout << std::endl << "label=\"" << akc_stavov << ", " << pocet_prech << "\"" << std::endl;
    std::cout << "}" << std::endl;
/*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++)
        {
            for (int k = 0;k<nstates;k++)
                    std::cout << prechodova_funkcia[i].pre_pismeno[j][k] ;
            std::cout << " " ;
        }
    }*/
}
