00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef ASTL_DFA_TR_H
00027 #define ASTL_DFA_TR_H
00028
00029
00030 #include <dfa_base.h>
00031 #include <vector>
00032 #include <algorithm>
00033 #include <functional>
00034
00035 #if (__GNUG__ && __GNUG__ > 2)
00036 using namespace __gnu_cxx;
00037 #endif
00038
00039 namespace astl {
00040
00041 template <class Sigma_ = plain,
00042 class Tag_ = empty_tag>
00043 class DFA_tr
00044 : public DFA_base<Sigma_, Tag_,
00045 vector<pair<typename Sigma_::char_type, unsigned int> > >
00046 {
00047 protected:
00048 typedef vector<pair<typename Sigma_::char_type, unsigned int> >
00049 transition_container;
00050
00051 public:
00052 typedef DFA_base<Sigma_, Tag_, vector<pair<typename Sigma_::char_type,
00053 unsigned int> > > super;
00054 typedef typename super::char_traits char_traits;
00055 typedef Tag_ tag_type;
00056 typedef typename char_traits::char_type char_type;
00057 typedef unsigned int state_type;
00058 using super::null_state;
00059
00060
00061 typedef char_traits Sigma;
00062 typedef char_type Alphabet;
00063 typedef tag_type Tag;
00064 typedef state_type State;
00065
00066 class edges_type
00067 {
00068 protected:
00069 const transition_container *container;
00070 typedef typename transition_container::iterator iterator;
00071
00072
00073 public:
00074 typedef char_type key_type;
00075 typedef state_type data_type;
00076 typedef pair<key_type, state_type> value_type;
00077 typedef value_type* pointer;
00078 typedef const value_type* const_pointer;
00079 typedef value_type& reference;
00080 typedef const value_type& const_reference;
00081 typedef unsigned long size_type;
00082 typedef long difference_type;
00083
00084 struct key_compare : public binary_function<key_type, key_type, bool>
00085 {
00086 bool operator () (const key_type &x, const key_type &y) const {
00087 return char_traits::eq(x, y);
00088 }
00089 };
00090
00091 struct value_compare : public binary_function<value_type, value_type, bool>
00092 {
00093 bool operator () (const value_type& x, const value_type& y) const {
00094 return key_compare()(x.first, y.first);
00095 }
00096 };
00097
00098 typedef typename transition_container::const_iterator
00099 const_iterator;
00100 typedef typename transition_container::const_reverse_iterator
00101 const_reverse_iterator;
00102
00103
00104
00105 edges_type(const transition_container *c = NULL)
00106 : container(c) { }
00107
00108 edges_type(const edges_type& x)
00109 : container(x.container) { }
00110
00111 key_compare key_comp() const {
00112 return key_compare();
00113 }
00114
00115 value_compare value_comp() const {
00116 return value_compare();
00117 }
00118
00119 const_iterator begin() const {
00120 return container->begin();
00121 }
00122
00123 const_iterator end() const {
00124 return container->end();
00125 }
00126
00127 const_reverse_iterator rbegin() const {
00128 return container->rbegin();
00129 }
00130 const_reverse_iterator rend() const {
00131 return container->rend();
00132 }
00133
00134 bool empty() const {
00135 return container->empty();
00136 }
00137 size_type size() const {
00138 return container->size();
00139 }
00140 size_type max_size() const {
00141 return container->max_size();
00142 }
00143
00144
00145 const_iterator find(const key_type& x) const {
00146 return find_if(container->begin(), container->end(),
00147 compose1(bind2nd(key_compare(), x),
00148 select1st<value_type>()));
00149 }
00150
00151 size_type count(const key_type& x) const {
00152 return find(x) == end() ? 0 : 1;
00153 }
00154
00155 const_iterator lower_bound(const key_type& x) const {
00156 return find(x);
00157 }
00158
00159 const_iterator upper_bound(const key_type& x) const {
00160 const_iterator i = find(x);
00161 return i == end() ? i : ++i;
00162 }
00163
00164 pair<const_iterator, const_iterator> equal_range(const key_type& x) const {
00165 const_iterator i = find(x);
00166 return i == end() ? make_pair(i, i) : make_pair(i, ++i);
00167 }
00168
00169 friend bool operator==(const edges_type& x, const edges_type& y) {
00170 return x.container == y.container || *x.container == *y.container;
00171 }
00172 };
00173
00174 void set_trans(state_type s, const char_type &a, state_type aim)
00175 {
00176 Q[s]->edges().push_back(make_pair(a, aim));
00177 ++trans_count_;
00178 }
00179
00180 void del_trans(state_type s, const char_type &a)
00181 {
00182 Q[s]->edges().erase(find_if(Q[s]->edges().begin(), Q[s]->edges().end(),
00183 compose1(bind2nd(typename DFA_tr<Sigma_,Tag_>::edges_type::key_compare(), a),
00184 select1st<pair<char_type, state_type> >())));
00185 --trans_count_;
00186 }
00187
00188 void change_trans(state_type s, const char_type &a, state_type new_aim) {
00189 (*find_if(Q[s]->edges().begin(), Q[s]->edges().end(),
00190 compose1(bind2nd(typename DFA_tr<Sigma_,Tag_>::edges_type::key_compare(), a),
00191 select1st<pair<char_type, state_type> >()))).second = new_aim;
00192 }
00193
00194 state_type delta1(state_type s, const char_type &a) const
00195 {
00196 transition_container &edges = Q[s]->edges();
00197 typename transition_container::iterator i =
00198 find_if(edges.begin(), edges.end(),
00199 compose1(bind2nd(typename DFA_tr<Sigma_,Tag_>::edges_type::key_compare(), a),
00200 select1st<pair<char_type, state_type> >()));
00201 if (i == edges.end()) return null_state;
00202 else {
00203 if (i != edges.begin()) {
00204 iter_swap(i, i - 1);
00205 return (*(i - 1)).second;
00206 }
00207 return (*i).second;
00208 }
00209 }
00210
00211 edges_type delta2(state_type s) const {
00212 return edges_type(&Q[s]->edges());
00213 }
00214
00215 DFA_tr(unsigned long n = 0)
00216 : super(n)
00217 { }
00218
00219 protected:
00220 using super::Q;
00221 using super::trans_count_;
00222 };
00223
00224 }
00225
00226 #endif // ASTL_DFA_TR_H
00227
00228
00229
00230
00231
00232