include/ExhaustiveDFAGenerator.hpp

Go to the documentation of this file.
00001 // ExhaustiveDFAGenerator.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 EXHAUSTIVEDFAGENERATOR
00017 #define EXHAUSTIVEDFAGENERATOR
00018 
00019 #include "AbstractExhaustiveGenerator.hpp"
00020 #include "AbstractDFAGenerator.hpp"
00021 #include "VerboseOption.hpp"
00022 #include "StronglyConnected.hpp"
00023 #include "CoAccessible.hpp"
00024 #include "MooreAlgorithm.hpp"
00025 
00026 namespace regal{
00027   
00028   template<typename StateLabel_t,typename Sigma, class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00029   class ExhaustiveDFAGenerator : 
00030     public AbstractExhaustiveGenerator<Automaton_t>, AbstractDFAGenerator<StateLabel_t,Sigma,Automaton_t>{
00031   private:
00032     CatalanSuit * catS; 
00033     CompletionSuit *comS; 
00034     int lastFinal; 
00035     int finalCounter; 
00040     bool firstFinalise(){
00041       for(lastFinal=0;lastFinal<this->result->getSize();lastFinal++)
00042         this->result->setStateAsFinal(this->result->getRealValue(lastFinal),false);
00043       lastFinal--;
00044       finalCounter=0;
00045       return true;
00046     }
00047     
00051     bool nextFinalize(){
00052       while(this->result->isFinal(this->result->getRealValue(lastFinal))){
00053         lastFinal--;
00054         if(lastFinal<0)return false;
00055       }
00056       this->result->setStateAsFinal(this->result->getRealValue(lastFinal),true);
00057       finalCounter++;
00058       for(lastFinal++;lastFinal<this->result->getSize();lastFinal++){
00059         this->result->setStateAsFinal(this->result->getRealValue(lastFinal),false);
00060         finalCounter--;
00061       }
00062       lastFinal--;
00063       return true;
00064     }
00065     
00066     
00067 
00068   public: 
00069  
00074     Automaton_t * first(){
00075       catS->first();
00076       comS->first();
00077       //cout<<*catS<<" - "<<*comS<<endl;
00078       this->suitToDFA(catS->getSuit(),comS->getSuit());
00079       firstFinalise();
00080       return this->result;
00081     }
00082     
00087     Automaton_t * next(){
00088       if(!nextFinalize()){
00089         if(comS->next()==NULL){
00090           if(catS->next()==NULL)
00091             return NULL;
00092           comS->first();
00093           this->suitToDFA(catS->getSuit(),comS->getSuit());
00094         }
00095         else
00096           this->DFAcompletion(comS->getSuit(),comS->getModifiedPosition());
00097         firstFinalise();
00098         //cout<<*catS<<" - "<<*comS<<endl;
00099       }
00100       return this->result;
00101     }
00102 
00103 
00104     int getFinalCounter(){return finalCounter;}
00105 
00112     Automaton_t * nextComplementary(){
00113       bool finalTest;
00114       int p=this->result->getSize()/2;
00115       do{
00116         finalTest=nextFinalize();
00117       }while(finalTest==true&&finalCounter>p);
00118       if(!finalTest){
00119         if(comS->next()==NULL){
00120           if(catS->next()==NULL)
00121             return NULL;
00122           comS->first();
00123           this->suitToDFA(catS->getSuit(),comS->getSuit());
00124         }
00125         else
00126           this->DFAcompletion(comS->getSuit(),comS->getModifiedPosition());
00127         firstFinalise();
00128         //cout<<*catS<<" - "<<*comS<<endl;
00129       }
00130       return this->result;
00131     }
00132 
00133 
00134 
00135     Automaton_t * end(){return NULL;}
00136     
00142     ExhaustiveDFAGenerator(const int & autSize,const Alphabet<Sigma> & alpha):
00143       AbstractDFAGenerator<StateLabel_t,Sigma,Automaton_t>::AbstractDFAGenerator(autSize,alpha){
00144       
00145       catS=new CatalanSuit(this->result->getSize(),alpha.getSize());
00146       comS=new CompletionSuit(catS);
00147       verbose("Creation of the ExhaustiveDFAGenerator");
00148     }
00149     
00150     
00154     virtual ~ExhaustiveDFAGenerator(){ 
00155       delete catS;
00156       delete comS;
00157       verbose("Destruction of the ExhaustiveDFAGenerator");
00158       
00159     }
00160     
00161   };
00162   
00163 }
00164 
00165 #endif

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