Claw 1.7.0
|
00001 /* 00002 CLAW - a C++ Library Absolutely Wonderful 00003 00004 CLAW is a free library without any particular aim but being useful to 00005 anyone. 00006 00007 Copyright (C) 2005-2011 Julien Jorge 00008 00009 This library is free software; you can redistribute it and/or 00010 modify it under the terms of the GNU Lesser General Public 00011 License as published by the Free Software Foundation; either 00012 version 2.1 of the License, or (at your option) any later version. 00013 00014 This library is distributed in the hope that it will be useful, 00015 but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00017 Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public 00020 License along with this library; if not, write to the Free Software 00021 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00022 00023 contact: julien.jorge@gamned.org 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 //***************************** automate ************************************ 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 }; // automaton 00140 00141 } // namespace claw 00142 00143 #include <claw/impl/automaton.tpp> 00144 00145 #endif // __CLAW_AUTOMATON_HPP__