00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #ifndef __CLAW_AUTOMATON_HPP__
00031 #define __CLAW_AUTOMATON_HPP__
00032
00033 #include <map>
00034 #include <vector>
00035 #include <claw/avl.hpp>
00036
00037 namespace claw
00038 {
00039
00040
00055 template<class State, class Edge, class StateComp = std::less<State>,
00056 class EdgeComp = std::less<Edge> >
00057 class automaton
00058 {
00059 public:
00061 typedef State state_type;
00062
00064 typedef Edge edge_type;
00065
00067 typedef StateComp state_compare;
00068
00070 typedef EdgeComp edge_compare;
00071
00073 typedef std::multimap<edge_type, state_type, edge_compare> neighbours_list;
00074
00077 typedef std::map<state_type, neighbours_list, state_compare> adjacent_list;
00078
00080 typedef std::vector<state_type> result_state_list;
00081
00083 typedef std::vector<edge_type> result_edge_list;
00084
00085 public:
00086 void add_edge( const state_type& s1, const state_type& s2,
00087 const edge_type& e );
00088 void remove_edge( const state_type& s1, const state_type& s2,
00089 const edge_type& e );
00090
00091 void add_state( const state_type& s );
00092 void add_initial_state( const state_type& s );
00093 void add_final_state( const state_type& s );
00094
00095 bool state_exists( const state_type& s ) const;
00096 bool state_is_final( const state_type& s ) const;
00097 bool state_is_initial( const state_type& s ) const;
00098
00099 void states( result_state_list& v ) const;
00100 void final_states( result_state_list& v ) const;
00101 void initial_states( result_state_list& v ) const;
00102 void alphabet( result_edge_list& v ) const;
00103
00104 template<class InputIterator>
00105 bool match(InputIterator first, InputIterator last) const;
00106
00107 unsigned int states_count() const;
00108
00109 void reachables( const state_type& s, const edge_type& e,
00110 result_state_list& l ) const;
00111 void reachables( const state_type& s,
00112 result_state_list& l ) const;
00113
00114 void edges( const state_type& s1, const state_type& s2,
00115 result_edge_list& l ) const;
00116 void edges( const state_type& s1, const edge_type& edge,
00117 result_edge_list& l ) const;
00118
00119 private:
00120 template<class InputIterator>
00121 bool match_aux(const state_type& s, InputIterator first,
00122 InputIterator last) const;
00123
00124 private:
00126 static state_compare s_state_compare;
00127
00129 avl<edge_type, edge_compare> m_alphabet;
00130
00132 avl<state_type, state_compare> m_initial_states;
00133
00135 avl<state_type, state_compare> m_final_states;
00136
00138 adjacent_list m_states;
00139 };
00140
00141 }
00142
00143 #include <claw/impl/automaton.tpp>
00144
00145 #endif // __CLAW_AUTOMATON_HPP__