include/DFAAutomaton.hpp

Go to the documentation of this file.
00001 // DFAAutomaton.hpp: this file is part of the REGAL project.
00002 //
00003 // REGAL : Random and Exhaustive Generators for Automata - Library
00004 //
00005 // Copyright (C) 2007 Julien DAVID.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 //
00016 #ifndef DFAAUTOMATON
00017 #define DFAAUTOMATON
00018 
00019 #include <list>
00020 #include <iterator>
00021 #include "AbstractAutomaton.hpp"
00022 #include "VerboseOption.hpp"
00023 #include "Pair.hpp"
00024 
00025 using namespace std;
00026 
00027 namespace regal{
00028 
00029   struct AutomatonLimitSizeExcedeedException : public std::exception {};
00030   
00031   template<typename StateLabel_t,typename Sigma>
00032   class DFAAutomaton: public AbstractAutomaton<StateLabel_t, Sigma> {
00033   private:
00034     int maxSize; 
00035     //int number; /*!< actual number of states in the automaton */
00036     int languageSize; 
00037     int ** data; 
00038     bool * finalStates; 
00039     bool * initialStates; 
00046     void exportFormat(Converter * cc){
00047       char * name=(char*)calloc(sizeof(char),32);
00048       char * name2=(char*)calloc(sizeof(char),32);
00049       char * word=(char*)calloc(sizeof(char),32);
00050       int c,w,c2;
00051       std::list<Sigma> listT=this->alphabet.getList();
00052       typename std::list<Sigma>::iterator l;
00053       cc->beginAutomaton(165,(maxSize/5)*33);
00054       
00055       for(c=0;c<getSize();c++){
00056         sprintf(name,"%d",c);
00057         cc->draw_node(name,(c%5)*20,-(c/5)*33,isInitial(c),isFinal(c));
00058       }
00059     
00060       for(c=0;c<getSize();c++){
00061         //for(w=0;w<languageSize;w++){
00062         for(l=listT.begin();l!=listT.end();l++){  
00063           w=this->alphabet.getNumericalValue(*l);
00064           c2=data[c][w];
00065           if(c2!=undefinedTransition()){
00066             sprintf(name,"%d",c);
00067             sprintf(name2,"%d",c2);
00068             sprintf(word,"%c",*l);
00069             cc->draw_edge(name,name2,word);
00070           }
00071         }
00072       }
00073       free(name);
00074       free(name2);
00075       free(word);
00076       cc->endAutomaton();
00077     }
00078     
00079   public:
00086     int createState(const int & value=0){
00087       if(this->stateNumber<=maxSize)
00088         return this->stateNumber++;
00089       
00090       cout<<"This Automaton has a fixed number of states"<<endl;
00091       throw new AutomatonLimitSizeExcedeedException();
00092     }  
00093 
00099     void deleteLastState(){
00100       this->undefineLastState();
00101     }
00102     
00103 
00104     
00105     Pair<int,int> createState(const Pair<int,int> & value){
00106       if(this->stateNumber<maxSize){
00107         this->stateNumber++;
00108         return value;
00109       }
00110       cout<<"This Automaton has a fixed number of states"<<endl;
00111       throw new AutomatonLimitSizeExcedeedException();
00112     }
00113 
00114     
00115 
00116 
00122     StateLabel_t undefinedTransition() const{
00123       return -1;
00124     }    
00125 
00126         
00131     int getSize(){return this->stateNumber;}
00132     
00139     StateLabel_t getArrivalState(const StateLabel_t & start,const Sigma & word){
00140       return getRealValue(data[this->getIntegerValue(start)][this->alphabet.getNumericalValue(word)]);
00141     }
00142     
00149     int getArrivalNumericalState(const int & start,const Sigma & word){
00150       return data[start][this->alphabet.getNumericalValue(word)];
00151     }
00152     
00159     void addTransition(const StateLabel_t& start,const StateLabel_t& end,
00160                        const Sigma & value){
00161       if(this->getIntegerValue(start)<this->stateNumber&&this->getIntegerValue(end)<this->stateNumber
00162          &&this->alphabet.getNumericalValue(value)<languageSize)
00163         data[this->getIntegerValue(start)][this->alphabet.getNumericalValue(value)]=this->getIntegerValue(end);
00164       else{
00165         cout<<"Automaton Max Size : "<<maxSize<<" Size : "<<this->stateNumber<<", tried values : "<<this->getIntegerValue(start)<<" "<<this->getIntegerValue(end)<<" ";
00166         cout<<this->alphabet.getNumericalValue(value)<<endl;
00167         throw new InvalidStateException();
00168       }
00169     }
00170 
00171    
00172     
00173     
00179     bool isFinal(const StateLabel_t & sl){
00180       if(this->getIntegerValue(sl)<this->stateNumber&&finalStates[this->getIntegerValue(sl)]==true)
00181         return true;
00182       return false;
00183     }
00184 
00190     bool isInitial(const StateLabel_t & sl){
00191       if(this->getIntegerValue(sl)<this->stateNumber&&initialStates[this->getIntegerValue(sl)]==true)
00192         return true;
00193       return false;
00194     }
00195     
00200     void setStateAsFinal(const StateLabel_t & sl,const bool & value){
00201       if(this->getIntegerValue(sl)<this->stateNumber)
00202         finalStates[this->getIntegerValue(sl)]=value;
00203       else
00204         throw new InvalidStateException();
00205     }
00206     
00211     void setStateAsInitial(const StateLabel_t & sl,const bool & value){
00212       if(this->getIntegerValue(sl)<this->stateNumber){
00213         initialStates[this->getIntegerValue(sl)]=value;
00214       }
00215       else
00216         throw new InvalidStateException();
00217     }
00218     
00219     
00225     void toGasteX(GasteXConverter * gc){
00226       exportFormat(gc);
00227     }
00228     
00229     
00234     void toDOT(DotConverter * dc){
00235       exportFormat(dc);
00236     }
00237     
00238     
00239     friend ostream& operator<<(ostream& o,const DFAAutomaton<int,char> & a);
00240     friend ostream& operator<<(ostream& o,const DFAAutomaton<Pair<int,int> ,char> & a);
00241     
00248     DFAAutomaton(const int& sSize,const Alphabet<Sigma> & a):AbstractAutomaton<StateLabel_t,Sigma>::AbstractAutomaton(a){
00249       int i,j;
00250       maxSize=sSize;
00251       languageSize=a.getSize();
00252             
00253       data= new int*[maxSize+1];
00254       finalStates= new bool[maxSize+1];
00255       initialStates= new bool[maxSize+1];
00256       
00257       for(i=0;i<(maxSize+1);i++){
00258         data[i]=new int[languageSize];
00259         for(j=0;j<languageSize;j++)
00260           data[i][j]=undefinedTransition();
00261         finalStates[i]=false;
00262         initialStates[i]=false;
00263       }
00264       verbose("Creation of an DFAAutomaton");
00265       
00266     }
00270     virtual ~DFAAutomaton(){
00271       int i;
00272       for(i=0;i<(maxSize+1);i++)
00273         delete [] data[i];
00274       delete [] data;
00275       delete [] finalStates;
00276       delete [] initialStates;
00277       verbose("Destruction of an DFAAutomaton");
00278     }
00279   };
00280   
00281 
00282 
00289   ostream& operator<<(ostream& o,const DFAAutomaton<int,char> & a){
00290     int i,j;
00291     o<<endl<<"----------"<<endl;
00292     o<<"Automaton"<<endl;
00293     o<<"MaxSize = "<<a.maxSize<<endl;
00294     o<<"Language Size = "<<a.languageSize<<endl<<endl;
00295     o<<"   ";
00296     std::list<char> listT=a.getAlphabet().getList();
00297     for(std::list<char>::iterator l=listT.begin();l!=listT.end();l++)
00298       o<<"  "<<*l;
00299     o<<"    Initial    Final";
00300     o<<endl<<endl;
00301     for(i=0;i<a.stateNumber;i++){
00302       o<<i<<"  ";
00303       for(j=0;j<a.languageSize;j++)
00304         if(a.data[i][j]==a.undefinedTransition())
00305           o<<"  "<<"?";
00306         else
00307           o<<"  "<<a.data[i][j];
00308       o<<"    "<<a.initialStates[i]<<"          "<<a.finalStates[i];
00309       o<<endl;
00310     }
00311     o<<endl<<"----------"<<endl;
00312     return o;
00313   }
00314   
00321   ostream& operator<<(ostream& o,const DFAAutomaton<Pair<int,int> ,char> & a){
00322     int i,j;
00323     Pair<int,int> p;
00324     o<<endl<<"----------"<<endl;
00325     o<<"Automaton"<<endl;
00326     o<<"MaxSize = "<<a.maxSize<<endl;
00327     o<<"Language Size = "<<a.languageSize<<endl<<endl;
00328     o<<"   ";
00329     std::list<char> listT=a.getAlphabet().getList();
00330     for(std::list<char>::iterator l=listT.begin();l!=listT.end();l++)
00331       o<<"  "<<*l;
00332     o<<"    Initial    Final";
00333     o<<endl<<endl;
00334     for(i=0;i<a.stateNumber;i++){
00335       o<<i<<"  ";
00336       for(j=0;j<a.languageSize;j++){
00337         p=a.data[i][j];
00338         if(p.first==a.undefinedTransition())
00339           cout<<"        "<<a.undefinedTransition();
00340         else
00341           o<<"  "<<p;
00342       }
00343       o<<"    "<<a.initialStates[i]<<"          "<<a.finalStates[i];
00344       o<<endl;
00345     }
00346     o<<endl<<"----------"<<endl;
00347     return o;
00348   }
00349 
00350 }
00351 
00352 #endif

Generated on Mon Sep 29 16:33:58 2008 for REGAL by  doxygen 1.5.1