include/AbstractDFAGenerator.hpp

Go to the documentation of this file.
00001 // AbstractDFAAutomaton.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 ABSTRACTDFAGENERATOR
00017 #define ABSTRACTDFAGENERATOR
00018 
00019 #include "CatalanSuit.hpp"
00020 #include "CompletionSuit.hpp"
00021 #include "AbstractAutomaton.hpp"
00022 #include "VerboseOption.hpp"
00023 
00024 #include<queue>
00025 #include<stack>
00026 #include<iterator>
00027 #include<map>
00028 
00029 namespace regal{
00030   
00031   template<typename StateLabel_t,typename Sigma>
00032   class DFA_Generator_transition{
00033   public:
00034     StateLabel_t state;
00035     Sigma word;
00036     DFA_Generator_transition(const StateLabel_t & s,const Sigma & w){
00037       state=s;
00038       word=w;
00039     }
00040     DFA_Generator_transition(){
00041     }
00042   };
00043   
00044   
00045   template<typename StateLabel_t,typename Sigma, class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00046   class AbstractDFAGenerator{
00047     
00048     
00049   protected:
00050     int stateQueueSize;
00051     Automaton_t * result; 
00052     //std::queue<DFA_Generator_transition<StateLabel_t,Sigma> > stateQueue;
00053     DFA_Generator_transition<StateLabel_t,Sigma> * stateQueue;
00054     
00055     
00062     bool isACatalanSuit(int * s,const int & incomplete=0){
00063       int i;
00064       for(i=0;i<(result->getSize()*(result->getAlphabetSize()-1));i++)
00065         if((s[i]-incomplete)<((i/(result->getAlphabetSize()-1))+1))return false;
00066       if((s[i]-incomplete)!=result->getSize())
00067         return false;
00068       return true;
00069     }
00070 
00077     bool isAValidSetPartition(int * s,const int & incomplete=0){
00078       int i,max=-1;
00079       int asize=result->getAlphabetSize();
00080       for(i=incomplete;i<(result->getSize()*asize);i++){
00081         max=(s[i]>max)?s[i]:max;
00082         if(i%asize==0 && (max-incomplete)<(i/asize))
00083           return false;
00084       }
00085       
00086       return true;
00087     }
00088 
00089     
00095     void suitToTrie(int * suit,const int & incomplete=0){
00096       std::stack<DFA_Generator_transition<StateLabel_t,Sigma> > transitionStack;
00097       DFA_Generator_transition<StateLabel_t,Sigma> dfagt;
00098       StateLabel_t tmp=result->getRealValue(0);
00099       std::list<Sigma> listT=result->getAlphabet().getList();
00100       int i,j,counter;
00101       result->setStateAsInitial(tmp,true);
00102           
00103       for(typename std::list<Sigma>::reverse_iterator l=listT.rbegin();l!=listT.rend();l++){
00104         dfagt.word=*l;
00105         dfagt.state=tmp;
00106         transitionStack.push(dfagt);
00107       }
00108       
00109       for(i=0,counter=1,j=1;i<(result->getSize()*(result->getAlphabetSize()-1));i++){
00110         while(j<(suit[i]-incomplete)){
00111           dfagt=transitionStack.top();
00112           transitionStack.pop();
00113           tmp=result->getRealValue(j);
00114           result->addTransition(dfagt.state,tmp,dfagt.word);
00115           
00116           for(typename std::list<Sigma>::reverse_iterator l=listT.rbegin();l!=listT.rend();l++){
00117             dfagt.word=*l;
00118             dfagt.state=tmp;
00119             transitionStack.push(dfagt);
00120           }
00121           counter++;
00122           j++;
00123         }
00124         stateQueue[i]=transitionStack.top();
00125         transitionStack.pop();
00126       }
00127       stateQueue[i]=transitionStack.top();
00128       transitionStack.pop();
00129     }
00130     
00137     void DFAcompletion(int * completion,const int & modifiedPosition,const int & incomplete=0){
00138       DFA_Generator_transition<StateLabel_t,Sigma> dfagt;
00139       int i=modifiedPosition;
00140       while(i<stateQueueSize){
00141         dfagt=stateQueue[i];
00142         result->addTransition(dfagt.state,completion[i]-1-incomplete,dfagt.word);
00143         i++;
00144       }
00145     }
00146      
00153     void setToDFA(int * setPartition,const int & incomplete=0){
00154       std::stack<DFA_Generator_transition<StateLabel_t,Sigma> > transitionStack;
00155       DFA_Generator_transition<StateLabel_t,Sigma> dfagt;
00156       StateLabel_t tmp=result->getRealValue(0);
00157       std::list<Sigma> listT=result->getAlphabet().getList();
00158       int i,counter;
00159       result->setStateAsInitial(tmp,true);
00160           
00161       for(typename std::list<Sigma>::reverse_iterator l=listT.rbegin();l!=listT.rend();l++){
00162         dfagt.word=*l;
00163         dfagt.state=tmp;
00164         transitionStack.push(dfagt);
00165       }
00166       
00167       
00168      
00169       for(i=1,counter=0;i<(result->getSize()*result->getAlphabetSize()+1);i++){
00170         dfagt=transitionStack.top();
00171         transitionStack.pop();
00172         tmp=result->getRealValue(setPartition[i]-incomplete);
00173         result->addTransition(dfagt.state,tmp,dfagt.word);
00174         //std::cout<<dfagt.state<<"."<<dfagt.word<<"="<<tmp<<std::endl;
00175 
00176         
00177         if(tmp==(counter+1)){
00178           for(typename std::list<Sigma>::reverse_iterator l=listT.rbegin();l!=listT.rend();l++){
00179             dfagt.word=*l;
00180             dfagt.state=tmp;
00181             transitionStack.push(dfagt);
00182           }
00183           counter++;
00184         }
00185       }
00186     }
00187     
00194     void suitToDFA(int * catalan,int * completion,const int &incomplete=0){
00195       suitToTrie(catalan,incomplete);
00196       DFAcompletion(completion,0,incomplete);
00197     }
00198     
00199     AbstractDFAGenerator(const int & autSize,const Alphabet<Sigma> & alpha){
00200       result=new Automaton_t(autSize,alpha);
00201       stateQueueSize=(alpha.getSize()-1)*autSize+1;
00202       stateQueue=new DFA_Generator_transition<StateLabel_t,Sigma>[stateQueueSize];
00203       for(int i=0;i<autSize;i++)
00204         result->addState();
00205       verbose("Creation of an AbstractDFAGenerator");
00206     }
00207     
00208     virtual ~AbstractDFAGenerator(){
00209       delete result;
00210       delete [] stateQueue;
00211       verbose("Destruction of an AbstractDFAGenerator");
00212     }
00213     
00214   public:
00219     int getSize(){return result->getSize();}
00220     Automaton_t * getDFA(){return result;}
00221     
00222     
00223     
00224   };
00225   
00226 }
00227   
00228 #endif

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