Scribus Developer Documentation - API
logo-pen

Scribus Developer Documentation - API

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
Created with personalized Doxygen. This is documentation for GPL software Scribus - Open Source Desktop Publishing.