Back to index

scribus-ng  1.3.4.dfsg+svn20071115
automata.h
Go to the documentation of this file.
00001 /*
00002  *  automata.h
00003  *  
00004  *
00005  *  Created by Andreas Vox on 02.06.06.
00006  *  Copyright 2006 under GPL2. All rights reserved.
00007  *
00008  */
00009 
00010 
00011 #ifndef AUTOMATA_H
00012 #define AUTOMATA_H
00013 
00014 #include <map>
00015 #include <set>
00016 #include <deque>
00017 
00018 namespace automata {
00019 
00020 template<class STATE, class INPUT, class OUTPUT>
00021 class FA_base {
00022 public:
00023        FA_base(STATE s, OUTPUT d);
00024        FA_base(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt);
00025        virtual ~FA_base();
00026 
00027        typedef std::map<INPUT, OUTPUT> Transitions;
00028 
00029        const std::set<STATE>& states() const;
00030        const std::set<INPUT>& inputs() const;
00031        const Transitions& transitions(STATE s) const;
00032        const STATE start() const;
00033        const OUTPUT deflt() const;
00034        const OUTPUT next(STATE from, INPUT input) const;
00035        
00036        void addState(STATE newState);
00037        void addInput(INPUT newInput);
00038        void setTransition(STATE from, INPUT input, OUTPUT to);
00039 
00040 protected:
00041        std::set<STATE> states_;
00042        std::set<INPUT> inputs_;
00043        std::map<STATE, Transitions> transitions_;
00044        const Transitions noTransitions;
00045        STATE start_;
00046        OUTPUT default_;
00047 };
00048 
00049 template<class STATE, class INPUT, class OUTPUT>
00050 FA_base<STATE, INPUT, OUTPUT>::FA_base(STATE s, OUTPUT d) : states_(), inputs_(), transitions_(), noTransitions(), start_(s), default_(d) 
00051 { 
00052        states_.insert(s); 
00053 }
00054 
00055 template<class STATE, class INPUT, class OUTPUT>
00056 FA_base<STATE, INPUT, OUTPUT>::FA_base(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt) : states_(states), inputs_(inputs), transitions_(), noTransitions(), start_(start), default_(deflt) 
00057 {
00058        if (states_.find(start) == states_.end())
00059               states_.insert(start);      
00060 }
00061 
00062 template<class STATE, class INPUT, class OUTPUT>
00063 const std::set<STATE>& FA_base<STATE, INPUT, OUTPUT>::states() const 
00064 { 
00065        return states_; 
00066 }
00067 
00068 template<class STATE, class INPUT, class OUTPUT>
00069 const std::set<INPUT>& FA_base<STATE, INPUT, OUTPUT>::inputs() const 
00070 { 
00071        return inputs_; 
00072 }
00073 
00074 template<class STATE, class INPUT, class OUTPUT>
00075 const STATE FA_base<STATE, INPUT, OUTPUT>::start() const
00076 { 
00077        return start_; 
00078 }
00079 
00080 template<class STATE, class INPUT, class OUTPUT>
00081 const OUTPUT FA_base<STATE, INPUT, OUTPUT>::deflt() const
00082 { 
00083        return default_; 
00084 }
00085 
00086 template<class STATE, class INPUT>
00087 class DFA : public FA_base<STATE, INPUT, STATE> {
00088 public:
00089        DFA(STATE s, STATE deflt): FA_base<STATE, INPUT, STATE>(s, deflt) {  }
00090        DFA(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt)
00091        : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
00092 };
00093 
00094 
00095 template<class STATE, class INPUT>
00096 class NFA : public FA_base<STATE, INPUT, std::set<STATE> > {
00097 public:
00098        NFA(STATE s, std::set<STATE> d): FA_base<STATE, INPUT, std::set<STATE> >(s, d)  { }
00099        NFA(std::set<STATE>& states, std::set<INPUT>& inputs, STATE start, std::set<STATE> deflt)
00100        : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
00101 
00102        void addTransition(STATE from, INPUT input, STATE to);
00103        
00104        /*
00105          NFA:  S x I -> P(S)
00106          DFA':  P(S) x I -> P(S)
00107          DFA:  N x I -> N
00108         Algo:
00109          todo = { NFA.start }
00110          forall src in todo:
00111             from = create(src)
00112             ntrans: I -> P(S)
00113             for all s in src
00114               for all (i,t) in NFA.trans[s]:
00115                 ntrans[i] += t;
00116             for all (i,nt) in ntrans:
00117               n = create(nt);
00118                  if n is new:
00119                 DFA.addState(n);
00120                       todo += nt;
00121               DFA.addTransition(from, i, n)
00122         */
00123        template<class NSTATE, class XXX>
00124        DFA<NSTATE,INPUT>* constructDFA( XXX createState )
00125 //     DFA<NSTATE,INPUT>* constructDFA(NSTATE (*createState)( std::set<STATE> ))  // wont work
00126        {
00127               std::map<std::set<STATE>, NSTATE> newStates;
00128        
00129               std::set<STATE> startSet;
00130               startSet.insert(FA_base<STATE,INPUT,std::set<STATE> >::start_);
00131               NSTATE nstart = createState(startSet);
00132               newStates[startSet] = nstart;
00133 
00134               NSTATE deflt = createState(FA_base<STATE,INPUT,std::set<STATE> >::default_);
00135               newStates[FA_base<STATE,INPUT,std::set<STATE> >::default_] = deflt;
00136               
00137               DFA<NSTATE,INPUT>* result = new DFA<NSTATE,INPUT>(nstart, deflt);
00138               result->addState(deflt);
00139               
00140               std::deque<std::set<STATE> > todo;
00141               todo.push_back(startSet);
00142               
00143               while (todo.size() > 0)
00144               {
00145                      const std::set<STATE> from = todo.front();
00146                      todo.pop_front();
00147                      std::map<INPUT,std::set<STATE> > ntrans;
00148                      // for all states in from
00149                      typename std::set<STATE>::const_iterator s_it;
00150                      typename std::map<INPUT, std::set<STATE> >::iterator tr_it;
00151                      for (s_it=from.begin(); s_it != from.end(); ++s_it)
00152                      {
00153                             // for all transitions
00154                             typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions& 
00155                                    trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[*s_it]);
00156                             for (tr_it = trans.begin(); tr_it != trans.end(); ++tr_it)
00157                             {
00158                                    ntrans[tr_it->first].insert(tr_it->second.begin(), tr_it->second.end());
00159                             }
00160                      }
00161                      // construct new transitions
00162                      const NSTATE nfrom = newStates[from];
00163                      for (tr_it = ntrans.begin(); tr_it != ntrans.end(); ++tr_it)
00164                      {
00165                             std::set<STATE> & state(tr_it->second);
00166                             // create follow state
00167                             NSTATE nstate;
00168                             if ( newStates.find(state) == newStates.end() ) {
00169                                    nstate = createState(state);
00170                                    result->addState(nstate);
00171                                    newStates[state] = nstate;
00172                                    // remember follow state in todo if new
00173                                    todo.push_back(state);
00174                             }
00175                             else {
00176                                    nstate = newStates[state];
00177                             }
00178                             result->setTransition(nfrom, tr_it->first, nstate);
00179                      }
00180               }
00181               const std::set<INPUT>& inp(FA_base<STATE, INPUT, std::set<STATE> >::inputs());
00182               typename std::set<INPUT>::const_iterator i;
00183               for (i=inp.begin(); i != inp.end(); ++i)
00184                      result->addInput(*i);
00185               return result;
00186        }
00187 };
00188 
00189 
00190 template<class STATE, class INPUT, class OUTPUT>
00191 FA_base<STATE,INPUT,OUTPUT>::~FA_base() 
00192 {
00193        // clean up
00194 }
00195        
00196 template<class STATE, class INPUT, class OUTPUT>
00197 const typename FA_base<STATE,INPUT,OUTPUT>::Transitions& FA_base<STATE,INPUT,OUTPUT>::transitions(STATE s) const
00198 { 
00199        typename std::map<STATE, Transitions>::const_iterator tr = transitions_.find(s);
00200        if (tr != transitions_.end())
00201               return tr->second;
00202        else
00203               return noTransitions; 
00204 }
00205 
00206 template<class STATE, class INPUT, class OUTPUT>
00207 const OUTPUT FA_base<STATE,INPUT,OUTPUT>::next(STATE from, INPUT input) const
00208 {
00209        const Transitions& tr(transitions(from));
00210        typename Transitions::const_iterator it = tr.find(input);
00211        return it==tr.end() ? default_ : it->second;
00212 }
00213 
00214 template<class STATE, class INPUT, class OUTPUT>
00215 void FA_base<STATE,INPUT,OUTPUT>::addState(STATE newState)
00216 {
00217        if (states_.find(newState) == states_.end())
00218               states_.insert(newState);
00219 }
00220 
00221 
00222 template<class STATE, class INPUT, class OUTPUT>
00223 void FA_base<STATE,INPUT,OUTPUT>::addInput(INPUT newInput)
00224 {
00225        if (inputs_.find(newInput) == inputs_.end())
00226               inputs_.insert(newInput);
00227 }
00228 
00229 
00230 template<class STATE, class INPUT, class OUTPUT>
00231 void FA_base<STATE,INPUT,OUTPUT>::setTransition(STATE from, INPUT input, OUTPUT to)
00232 {
00233        Transitions& trans(transitions_[from]);
00234        trans[input] = to;
00235 }
00236        
00237 
00238 template<class STATE, class INPUT>
00239 void NFA<STATE, INPUT>::addTransition(STATE from, INPUT input, STATE to)
00240 {
00241        typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions & 
00242               trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[from]);
00243        trans[input].insert(to);
00244 }
00245 
00246 } // namespace
00247 
00248 #endif