Claw 1.7.3
automaton.hpp
Go to the documentation of this file.
1/*
2 CLAW - a C++ Library Absolutely Wonderful
3
4 CLAW is a free library without any particular aim but being useful to
5 anyone.
6
7 Copyright (C) 2005-2011 Julien Jorge
8
9 This library is free software; you can redistribute it and/or
10 modify it under the terms of the GNU Lesser General Public
11 License as published by the Free Software Foundation; either
12 version 2.1 of the License, or (at your option) any later version.
13
14 This library is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
18
19 You should have received a copy of the GNU Lesser General Public
20 License along with this library; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22
23 contact: julien.jorge@gamned.org
24*/
30#ifndef __CLAW_AUTOMATON_HPP__
31#define __CLAW_AUTOMATON_HPP__
32
33#include <map>
34#include <vector>
35#include <claw/avl.hpp>
36
37namespace claw
38{
39 //***************************** automate ************************************
40
55 template<class State, class Edge, class StateComp = std::less<State>,
56 class EdgeComp = std::less<Edge> >
58 {
59 public:
61 typedef State state_type;
62
64 typedef Edge edge_type;
65
67 typedef StateComp state_compare;
68
70 typedef EdgeComp edge_compare;
71
73 typedef std::multimap<edge_type, state_type, edge_compare> neighbours_list;
74
77 typedef std::map<state_type, neighbours_list, state_compare> adjacent_list;
78
80 typedef std::vector<state_type> result_state_list;
81
83 typedef std::vector<edge_type> result_edge_list;
84
85 public:
86 void add_edge( const state_type& s1, const state_type& s2,
87 const edge_type& e );
88 void remove_edge( const state_type& s1, const state_type& s2,
89 const edge_type& e );
90
91 void add_state( const state_type& s );
92 void add_initial_state( const state_type& s );
93 void add_final_state( const state_type& s );
94
95 bool state_exists( const state_type& s ) const;
96 bool state_is_final( const state_type& s ) const;
97 bool state_is_initial( const state_type& s ) const;
98
99 void states( result_state_list& v ) const;
100 void final_states( result_state_list& v ) const;
101 void initial_states( result_state_list& v ) const;
102 void alphabet( result_edge_list& v ) const;
103
104 template<class InputIterator>
105 bool match(InputIterator first, InputIterator last) const;
106
107 unsigned int states_count() const;
108
109 void reachables( const state_type& s, const edge_type& e,
110 result_state_list& l ) const;
111 void reachables( const state_type& s,
112 result_state_list& l ) const;
113
114 void edges( const state_type& s1, const state_type& s2,
115 result_edge_list& l ) const;
116 void edges( const state_type& s1, const edge_type& edge,
117 result_edge_list& l ) const;
118
119 private:
120 template<class InputIterator>
121 bool match_aux(const state_type& s, InputIterator first,
122 InputIterator last) const;
123
124 private:
126 static state_compare s_state_compare;
127
130
132 avl<state_type, state_compare> m_initial_states;
133
135 avl<state_type, state_compare> m_final_states;
136
138 adjacent_list m_states;
139 }; // automaton
140
141} // namespace claw
142
143#include <claw/impl/automaton.tpp>
144
145#endif // __CLAW_AUTOMATON_HPP__
AVL Binary search tree.
Basic automaton structure.
Definition automaton.hpp:58
std::vector< state_type > result_state_list
The return type of the methods returning states.
Definition automaton.hpp:80
std::vector< edge_type > result_edge_list
The return type of the methods returning edges.
Definition automaton.hpp:83
std::map< state_type, neighbours_list, state_compare > adjacent_list
Each state is given a set of reachable states with a neighbours list.
Definition automaton.hpp:77
std::multimap< edge_type, state_type, edge_compare > neighbours_list
The neighbours list associates states to edge symbols.
Definition automaton.hpp:73
Edge edge_type
The type of the symbols on the edges.
Definition automaton.hpp:64
State state_type
The type of the states.
Definition automaton.hpp:61
StateComp state_compare
The type of the operator used to compare states.
Definition automaton.hpp:67
EdgeComp edge_compare
The type of the operator used to compare edge symbols.
Definition automaton.hpp:70
Binary search tree AVL implementation.
Definition avl.hpp:44
Fuction object to get the first element of a std::pair.
This is the main namespace.
Definition algorithm.hpp:34