Claw 1.7.0
automaton.hpp
Go to the documentation of this file.
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__