include/ReverseDFAAlgorithm.hpp

Go to the documentation of this file.
00001 // ReverseDFAAlgorithm.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 REVERSEDFAALGORITHM
00017 #define REVERSEDFAALGORITHM
00018 
00019 #include "Alphabet.hpp"
00020 #include "AbstractAutomaton.hpp"
00021 #include "toolbox/GenericFunction.hpp"
00022 
00023 #include <list>
00024 #include <iostream>
00025 
00026 using namespace std;
00027 
00028 namespace regal{
00029   
00030   template<typename StateLabel_t,typename Sigma,class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00031   class ReverseDFAAlgorithm{
00032   private:
00033     list<int> ** data;
00034     int automatonSize;
00035     int alphabetSize;
00036     
00037     void initMemory(Automaton_t * a){
00038       freeMemory();
00039       automatonSize=a->getSize();
00040       alphabetSize=a->getAlphabet().getSize();
00041       data=new list<int> *[automatonSize];
00042       for(int i=0;i<automatonSize;i++)
00043         data[i]=new list<int>[alphabetSize];
00044     }
00045     
00046     
00047     void freeMemory(){
00048       if(automatonSize!=0){
00049         for(int i=0;i<automatonSize;i++)
00050           delete [] data[i];
00051         delete [] data;
00052       }
00053     }
00054     
00055   public:
00056     
00057     list<int> ** reverseDFA(Automaton_t * a){
00058       int i,arrival;
00059       initMemory(a);
00060       Alphabet<Sigma> alphabet=a->getAlphabet();
00061       typename std::list<Sigma> alphabetL=alphabet.getList();
00062       for(i=0;i<automatonSize;i++){
00063         for(typename std::list<Sigma>::iterator l=alphabetL.begin();l!=alphabetL.end();l++){
00064           arrival=a->getArrivalNumericalState(i,*l);
00065           if(arrival!=-1)
00066             data[arrival][alphabet.getNumericalValue(*l)].push_back(i);
00067         }
00068       }
00069       return data;
00070     }
00071     
00072     
00073     
00074     ReverseDFAAlgorithm(){
00075       automatonSize=0;
00076       alphabetSize=0;
00077       data=NULL;
00078     }
00079     
00080     ~ReverseDFAAlgorithm(){
00081       freeMemory();
00082     }
00083     
00084     
00085   };
00086   
00087 }
00088 
00089 
00090 #endif

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