home *** CD-ROM | disk | FTP | other *** search
/ Clickx 115 / Clickx 115.iso / software / tools / windows / tails-i386-0.16.iso / live / filesystem.squashfs / usr / include / scribus-ng / desaxe / automata.h < prev    next >
Encoding:
C/C++ Source or Header  |  2007-02-17  |  6.9 KB  |  249 lines

  1. /*
  2.  *  automata.h
  3.  *  
  4.  *
  5.  *  Created by Andreas Vox on 02.06.06.
  6.  *  Copyright 2006 under GPL2. All rights reserved.
  7.  *
  8.  */
  9.  
  10.  
  11. #ifndef AUTOMATA_H
  12. #define AUTOMATA_H
  13.  
  14. #include <map>
  15. #include <set>
  16. #include <deque>
  17.  
  18. namespace automata {
  19.  
  20. template<class STATE, class INPUT, class OUTPUT>
  21. class FA_base {
  22. public:
  23.     FA_base(STATE s, OUTPUT d);
  24.     FA_base(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt);
  25.     virtual ~FA_base();
  26.  
  27.     typedef std::map<INPUT, OUTPUT> Transitions;
  28.  
  29.     const std::set<STATE>& states() const;
  30.     const std::set<INPUT>& inputs() const;
  31.     const Transitions& transitions(STATE s) const;
  32.     const STATE start() const;
  33.     const OUTPUT deflt() const;
  34.     const OUTPUT next(STATE from, INPUT input) const;
  35.     
  36.     void addState(STATE newState);
  37.     void addInput(INPUT newInput);
  38.     void setTransition(STATE from, INPUT input, OUTPUT to);
  39.  
  40. protected:
  41.     std::set<STATE> states_;
  42.     std::set<INPUT> inputs_;
  43.     std::map<STATE, Transitions> transitions_;
  44.     const Transitions noTransitions;
  45.     STATE start_;
  46.     OUTPUT default_;
  47. };
  48.  
  49. template<class STATE, class INPUT, class OUTPUT>
  50. FA_base<STATE, INPUT, OUTPUT>::FA_base(STATE s, OUTPUT d) : states_(), inputs_(), transitions_(), noTransitions(), start_(s), default_(d) 
  51.     states_.insert(s); 
  52. }
  53.  
  54. template<class STATE, class INPUT, class OUTPUT>
  55. 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) 
  56. {
  57.     if (states_.find(start) == states_.end())
  58.         states_.insert(start);    
  59. }
  60.  
  61. template<class STATE, class INPUT, class OUTPUT>
  62. const std::set<STATE>& FA_base<STATE, INPUT, OUTPUT>::states() const 
  63.     return states_; 
  64. }
  65.  
  66. template<class STATE, class INPUT, class OUTPUT>
  67. const std::set<INPUT>& FA_base<STATE, INPUT, OUTPUT>::inputs() const 
  68.     return inputs_; 
  69. }
  70.  
  71. template<class STATE, class INPUT, class OUTPUT>
  72. const STATE FA_base<STATE, INPUT, OUTPUT>::start() const
  73.     return start_; 
  74. }
  75.  
  76. template<class STATE, class INPUT, class OUTPUT>
  77. const OUTPUT FA_base<STATE, INPUT, OUTPUT>::deflt() const
  78.     return default_; 
  79. }
  80.  
  81. template<class STATE, class INPUT>
  82. class DFA : public FA_base<STATE, INPUT, STATE> {
  83. public:
  84.     DFA(STATE s, STATE deflt): FA_base<STATE, INPUT, STATE>(s, deflt) {  }
  85.     DFA(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt)
  86.     : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
  87. };
  88.  
  89.  
  90. template<class STATE, class INPUT>
  91. class NFA : public FA_base<STATE, INPUT, std::set<STATE> > {
  92. public:
  93.     NFA(STATE s, std::set<STATE> d): FA_base<STATE, INPUT, std::set<STATE> >(s, d)  { }
  94.     NFA(std::set<STATE>& states, std::set<INPUT>& inputs, STATE start, std::set<STATE> deflt)
  95.     : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
  96.  
  97.     void addTransition(STATE from, INPUT input, STATE to);
  98.     
  99.     /*
  100.       NFA:  S x I -> P(S)
  101.       DFA':  P(S) x I -> P(S)
  102.       DFA:  N x I -> N
  103.      Algo:
  104.       todo = { NFA.start }
  105.       forall src in todo:
  106.          from = create(src)
  107.          ntrans: I -> P(S)
  108.          for all s in src
  109.            for all (i,t) in NFA.trans[s]:
  110.              ntrans[i] += t;
  111.          for all (i,nt) in ntrans:
  112.            n = create(nt);
  113.            if n is new:
  114.              DFA.addState(n);
  115.              todo += nt;
  116.            DFA.addTransition(from, i, n)
  117.      */
  118.     template<class NSTATE, class XXX>
  119.     DFA<NSTATE,INPUT>* constructDFA( XXX createState )
  120. //    DFA<NSTATE,INPUT>* constructDFA(NSTATE (*createState)( std::set<STATE> ))  // wont work
  121.     {
  122.         std::map<std::set<STATE>, NSTATE> newStates;
  123.     
  124.         std::set<STATE> startSet;
  125.         startSet.insert(FA_base<STATE,INPUT,std::set<STATE> >::start_);
  126.         NSTATE nstart = createState(startSet);
  127.         newStates[startSet] = nstart;
  128.  
  129.         NSTATE deflt = createState(FA_base<STATE,INPUT,std::set<STATE> >::default_);
  130.         newStates[FA_base<STATE,INPUT,std::set<STATE> >::default_] = deflt;
  131.         
  132.         DFA<NSTATE,INPUT>* result = new DFA<NSTATE,INPUT>(nstart, deflt);
  133.         result->addState(deflt);
  134.         
  135.         std::deque<std::set<STATE> > todo;
  136.         todo.push_back(startSet);
  137.         
  138.         while (todo.size() > 0)
  139.         {
  140.             const std::set<STATE> from = todo.front();
  141.             todo.pop_front();
  142.             std::map<INPUT,std::set<STATE> > ntrans;
  143.             // for all states in from
  144.             typename std::set<STATE>::const_iterator s_it;
  145.             typename std::map<INPUT, std::set<STATE> >::iterator tr_it;
  146.             for (s_it=from.begin(); s_it != from.end(); ++s_it)
  147.             {
  148.                 // for all transitions
  149.                 typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions& 
  150.                     trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[*s_it]);
  151.                 for (tr_it = trans.begin(); tr_it != trans.end(); ++tr_it)
  152.                 {
  153.                     ntrans[tr_it->first].insert(tr_it->second.begin(), tr_it->second.end());
  154.                 }
  155.             }
  156.             // construct new transitions
  157.             const NSTATE nfrom = newStates[from];
  158.             for (tr_it = ntrans.begin(); tr_it != ntrans.end(); ++tr_it)
  159.             {
  160.                 std::set<STATE> & state(tr_it->second);
  161.                 // create follow state
  162.                 NSTATE nstate;
  163.                 if ( newStates.find(state) == newStates.end() ) {
  164.                     nstate = createState(state);
  165.                     result->addState(nstate);
  166.                     newStates[state] = nstate;
  167.                     // remember follow state in todo if new
  168.                     todo.push_back(state);
  169.                 }
  170.                 else {
  171.                     nstate = newStates[state];
  172.                 }
  173.                 result->setTransition(nfrom, tr_it->first, nstate);
  174.             }
  175.         }
  176.         const std::set<INPUT>& inp(FA_base<STATE, INPUT, std::set<STATE> >::inputs());
  177.         typename std::set<INPUT>::const_iterator i;
  178.         for (i=inp.begin(); i != inp.end(); ++i)
  179.             result->addInput(*i);
  180.         return result;
  181.     }
  182. };
  183.  
  184.  
  185. template<class STATE, class INPUT, class OUTPUT>
  186. FA_base<STATE,INPUT,OUTPUT>::~FA_base() 
  187. {
  188.     // clean up
  189. }
  190.     
  191. template<class STATE, class INPUT, class OUTPUT>
  192. const typename FA_base<STATE,INPUT,OUTPUT>::Transitions& FA_base<STATE,INPUT,OUTPUT>::transitions(STATE s) const
  193.     typename std::map<STATE, Transitions>::const_iterator tr = transitions_.find(s);
  194.     if (tr != transitions_.end())
  195.         return tr->second;
  196.     else
  197.         return noTransitions; 
  198. }
  199.  
  200. template<class STATE, class INPUT, class OUTPUT>
  201. const OUTPUT FA_base<STATE,INPUT,OUTPUT>::next(STATE from, INPUT input) const
  202. {
  203.     const Transitions& tr(transitions(from));
  204.     typename Transitions::const_iterator it = tr.find(input);
  205.     return it==tr.end() ? default_ : it->second;
  206. }
  207.  
  208. template<class STATE, class INPUT, class OUTPUT>
  209. void FA_base<STATE,INPUT,OUTPUT>::addState(STATE newState)
  210. {
  211.     if (states_.find(newState) == states_.end())
  212.         states_.insert(newState);
  213. }
  214.  
  215.  
  216. template<class STATE, class INPUT, class OUTPUT>
  217. void FA_base<STATE,INPUT,OUTPUT>::addInput(INPUT newInput)
  218. {
  219.     if (inputs_.find(newInput) == inputs_.end())
  220.         inputs_.insert(newInput);
  221. }
  222.  
  223.  
  224. template<class STATE, class INPUT, class OUTPUT>
  225. void FA_base<STATE,INPUT,OUTPUT>::setTransition(STATE from, INPUT input, OUTPUT to)
  226. {
  227.     Transitions& trans(transitions_[from]);
  228.     trans[input] = to;
  229. }
  230.     
  231.  
  232. template<class STATE, class INPUT>
  233. void NFA<STATE, INPUT>::addTransition(STATE from, INPUT input, STATE to)
  234. {
  235.     typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions & 
  236.         trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[from]);
  237.     trans[input].insert(to);
  238. }
  239.  
  240. } // namespace
  241.  
  242. #endif
  243.