#include "automaton.h"

#include <iostream>

// Default constructor die automaton initialiseert
Automaton::Automaton() {
    correctAutomaton = false;
} // Automaton::Automaton

// Setter voor de boolean die aangeeft of het object een correct automaat is
void Automaton::setCorrectAutomaton(bool const correctAutomaton) {
    this->correctAutomaton = correctAutomaton;
} // Automaton::setCorrectAutomaton

// Maakt de vector automaton leeg
void Automaton::clear() {
    automaton.clear();
} // Automaton::clear

// Geeft de size van de automaton vector
int Automaton::getSize() const {
    return automaton.size();
} // Automaton::GetSize

// Creeërt de DOT-notatie van deze automaton en stuurt deze naar std::cout
void Automaton::dotAutomaton() const {
    if(correctAutomaton) {
        // De toestanden de juiste vorm geven. S wordt gemaakt om een pijl naar de begintoestand te laten wijzen
        std::cout << "digraph {" << std::endl << "  rankdir=LR;" << std::endl << "  node [shape = point] S" << std::endl
                  << "  node [shape = doublecircle] " << automaton.size()-1 << std::endl << "  node [shape = circle]"
                  << std::endl << "  S -> 0" << std::endl;

        int const automatonSize = getSize();
        for(int i = 0; i < automatonSize; i++) {
            if(automaton.at(i).secondType != Transition::final) {
                std::cout << "  " << i << " -> " << automaton.at(i).first;
                if(automaton.at(i).secondType == Transition::state) {
                    std::cout << std::endl << "  " << i << " -> " << automaton.at(i).second.state << std::endl;
                } // Als de toestand i 2 uitgaande pijlen heeft
                else if(automaton.at(i).secondType == Transition::letter) {
                    std::cout << " [xlabel=\"" << automaton.at(i).second.letter << "\"]" << std::endl;
                } // Als de toestand i 1 uitgaande pijl heeft met een label
                else {
                    std::cout << std::endl;
                } // Als het type lambda is dan is er maar 1 transitie en moet je gewoon naar de volgende regel
            }
        }
        std::cout << "}";
        return;
    } // DOT wordt alleen uitgevoerd als een geldige automaat is ingelezen
    std::cerr << "Er is geen geldige automaat ingelezen dus deze functie wordt niet uitgevoerd" << std::endl;
} // Automaton::dotAutomaton

// Voegt een eerste transitie toe
void Automaton::firstTransition(char const letter) {
    if(!((letter >= 'a' && letter <= 'z') || letter == '$')) {
        std::cerr << "\nMeegegeven karakter is geen letter" << std::endl;
        return;
    } // geen letter
    if(getSize() > 0) {
        std::cerr << "\nKan geen eerste eerste transitie toevoegen bij een automaat groter dan 1" << std::endl;
    } // de automaat is niet leeg, dus geen eerste transitie

    if(letter != '$') {
        Transition transition1; // begin- en eindtoestand
        transition1.first = 1;
        transition1.secondType = Transition::letter; // letter type
        transition1.second.letter = letter;
        automaton.push_back(transition1);
    } // bij $ hebben we niet te maken met een letter

    Transition transition2;
    transition2.secondType = Transition::final; // final state
    automaton.push_back(transition2);
} // Automaton::firstTransition

// Geeft de transition op de meegegeven idnex in de automaton
Transition Automaton::getTransition(int const index) const {
    int const size = getSize(); // size of vector
    Transition transition = Transition(); // transitie
    if(index < 0 || index >= size) {
        std::cerr << "\nIndex zit buiten de vector size" << std::endl;
    }
    else {
        transition = automaton.at(index);
    }
    return transition;
} // Automaton::GetTransition

// Voert conacetantie uit met auto1
void Automaton::concat(Automaton auto1) {
    int const auto1Size = auto1.getSize(); // aantal elementen in auto1
    int addIndex = getSize() - 1; // getal dat moet worden toegevoegd aan de indexen van auto1
    if(addIndex == -1) {
        addIndex = 0;
    }
    automaton.pop_back(); // verwijdert laatste element, zodat deze gereplaced kan worden met eerste element auto1

    for(int i = 0; i < auto1Size; i++) {
        Transition transition = auto1.getTransition(i);
        Transition copyTransition;
        copyTransition.first = transition.first + addIndex;
        copyTransition.secondType = transition.secondType;

        switch(copyTransition.secondType) {
            case Transition::state:
                copyTransition.second.state = transition.second.state + addIndex;
                break;
            case Transition::letter:
                copyTransition.second.letter = transition.second.letter;
                break;
            default:
                break;
        } // Zal het tweede type juist kopiëren
        automaton.push_back(copyTransition);
    } // kopiëert de transitie-elementen van auto1 en voegt deze toe aan automaton
} // Automaton::concat

// Voert de plus operatie uit met als opties auto1 of auto2
void Automaton::plus(Automaton auto1, Automaton auto2) {
    if(getSize() > 0) {
        std::cerr << "\nKan geen plus operatie doen op een automaat die al gevuld is" << std::endl;
    }
    Transition transition1;
    transition1.secondType = Transition::state;
    transition1.first = 1; // gaat wijzen naar copy van eerste element auto1
    automaton.push_back(transition1);
    automaton.push_back(Transition());
    concat(auto1);
    automaton.at(0).second.state = getSize(); // gaat wijzen naar copy van eerste element auto2
    automaton.push_back(Transition());
    concat(auto2);
    automaton.at(auto1.getSize()).secondType = Transition::lambda;
    automaton.at(auto1.getSize()).first = getSize(); // einde auto1 gaat wijzen naar eindtoestand
    automaton.at(getSize() - 1).secondType = Transition::lambda;
    automaton.at(getSize() - 1).first = getSize(); // einde auto2 gaat wijzen naar eindtoestand
    Transition endState;
    endState.secondType = Transition::final;
    automaton.push_back(endState);
} // Automaton::plus

// Voert de ster operatie uit op huidige automaton
void Automaton::star() {
    int const size = getSize();
    if(size == 0) {
        std::cerr << "\nKan geen star operatie doen op een automaat die niet gevuld is" << std::endl;
    }
    automaton.at(size - 1).first = size; // wijst naar komende nieuwe laatste transitie-element
    automaton.at(size - 1).secondType = Transition::state;
    automaton.at(size - 1).second.state = 0; // wijst naar huidige eerste transitie-element
    
    for(int i = 0; i < size; i++) {
        automaton.at(i).first++;
        if(automaton.at(i).secondType == Transition::state) {
            automaton.at(i).second.state++;
        }
    } // verhoogt alle transitie waarden, zodat er aan het begin een element kan worden toegevoegd

    Transition newLast;
    newLast.secondType = Transition::final;
    automaton.push_back(newLast); // nieuwe laatste transitie-element
    Transition newFirst;
    newFirst.first = 1; 
    newFirst.secondType = Transition::state;
    newFirst.second.state = size + 1; // wijst naar het nieuwe laatste transitie-element
    automaton.insert(automaton.begin(), newFirst); // voegt lambdaTransition toe aan het begin
} // Automaton::star

// Functie die alle waarden initialiseert en dan een andere functie aanroept om de
// e-afsluiting te berekenen
std::vector<int> Automaton::getEClosure(int state) const {
    std::vector<int> result; // Vector met de e-afsluiting van states
    std::vector<bool> visited; // Vector die bijhoudt welke states al bezocht zijn
    for(int i = 0; i < int(automaton.size()); i++) {
        visited.push_back(false);
    } // Alle states op false zetten want ze zijn nog niet bezocht
    getEClosureRec(state, result, visited);
    return result;
} // Automaton::getEClosure

// Berekent recursief de e-afsluiting van een knoop waarbij in de gaten wordt gehouden
// of knopen niet al bezocht zijn en er daardoor geen oneindinge loop ontstaat
void Automaton::getEClosureRec(int const state, std::vector<int> &eClosure, std::vector<bool> &visited) const {
    visited.erase(visited.begin() + state);           // Aangeven dat de
    visited.insert((visited.begin() + state), true);  // knoop is bezocht
    eClosure.push_back(state);

    if(automaton.at(state).secondType == Transition::state || automaton.at(state).secondType == Transition::lambda) {
        if(!visited.at(automaton.at(state).first)) {
            getEClosureRec(automaton.at(state).first, eClosure, visited);
        } // Als de knoop nog niet bezocht is dan wordt de e-afsluiting van die knoop berekent 
        if(automaton.at(state).secondType == Transition::state && !visited.at(automaton.at(state).second.state)) {
            getEClosureRec(automaton.at(state).second.state, eClosure, visited);
        } // Alleen als de knoop twee e-transities heeft en de tweede knoop is nog niet bezocht
    } // Als de knoop twee uitgaande e-transities heeft
} // Automaton::getEClosure

// Functie die controleert of je vanuit een van de toestanden van vector states
// in de accepterende toestand terecht komt
bool Automaton::checkFinal(std::vector<int> const states) const {
    std::vector<int> eClosure; // Vector die de e-afsluitng van een toestand bevat

    for(int i = 0; i < int(states.size()); i++) {
        eClosure = getEClosure(states.at(i));
        for(int j = 0; j < int(eClosure.size()); j++) {
            if(automaton.at(eClosure.at(j)).secondType == Transition::final) {
                return true;
            }
        } // Alle toestanden in de e-afsluiting van de desbetreffende toestand afgaan
    } // Alle toestanden in states afgaan

    return false;
} // Automaton::checkFinal

// Controleert eerst of state al in de vector states zit en als dat niet zo is dan wordt die toegevoegd.
// Als die er wel in zit dan gebeurd er niks
void Automaton::addState(std::vector<int> &states, int const state) const {
    for(int i = 0; i < int(states.size()); i++) {
        if(states.at(i) == state) {
            return;
        }
    }
    states.push_back(state);
} // Automaton::addState

// Roept de private functie match aan met de juiste parameters en retourneert een string
// die aangeeft of de expressie wordt geaccepteerd door de automaat
std::string Automaton::match(std::string const expressie) const {
    if(correctAutomaton) {
        std::vector<int> states;
        states.push_back(0); // Alleen 0 zit in states omdat dat de begintoestand is

        if(match(expressie, 0, states)) {
            return "match";
        } // Als de expressie door de automaat geaccepteerd wordt
        return "geen match";
    } // Alleen match uitvoeren bij een geldige automaat

    return "Er is geen geldige automaat ingelezen dus deze functie wordt niet uitgevoerd";
} // Automaton::match

// Bekijkt of de string expressie wordt geaccepteerd door de automaat door er recursief met een pointer
// position langs te gaan en in states bij te houden waar je zou kunnen zijn
bool Automaton::match(std::string const expressie, int const position, std::vector<int> &states) const {
    if(position == int(expressie.size())) {
        return checkFinal(states);
    }
    std::vector<int> eClosure; // Vector die de e-afsluiting bijhoudt
    std::vector<int> oldStates(states); // Kopieer de oude states naar de nieuwe states
    states.clear();

    for(int i = 0; i < int(oldStates.size()); i++) {
        eClosure = getEClosure(oldStates.at(i));

        for(int j = 0; j < int(eClosure.size()); j++) {
            if(automaton.at(eClosure.at(j)).secondType == Transition::letter &&
              automaton.at(eClosure.at(j)).second.letter == expressie.at(position)) {
                addState(states, automaton.at(eClosure.at(j)).first);
            } // Als de letter van de transitie overeenkomt met de letter op plek position in expressie
            else if(expressie.at(position) == '$') {
                addState(states, eClosure.at(j));
            } // Als de lege string de expressie is of erin voorkomt
        } // Elke knoop in de e-afsluiting van de state afgaan

    } // Alle meegegeven states afgaan
    return match(expressie, position+1, states);
} // Automaton::match