00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef ASTL_DETERMINIZE_H
00023 #define ASTL_DETERMINIZE_H
00024
00025 #include <astl.h>
00026 #include <closure.h>
00027 #include <set>
00028 #include <iterator>
00029
00030 using namespace std;
00031
00032 namespace astl {
00033
00034
00035 template <typename NFA>
00036 struct default_tag_mapper
00037 {
00038 typedef empty result_type;
00039
00040
00041
00042 template <typename InputIterator>
00043 result_type operator()(const NFA&, InputIterator,
00044 InputIterator) const {
00045 return empty();
00046 }
00047 };
00048
00055 template <typename NFA, typename TagMapper = default_tag_mapper<NFA> >
00056 class dcursor : public cursor_concept
00057 {
00058 public:
00059 typedef dcursor self;
00060 typedef set<typename NFA::state_type> state_type;
00061 typedef typename TagMapper::result_type tag_type;
00062 typedef typename NFA::char_traits char_traits;
00063 typedef typename NFA::char_type char_type;
00064
00065 protected:
00066 const NFA *nfa;
00067 state_type q;
00068
00069 public:
00070 dcursor()
00071 { }
00072
00073 dcursor(const NFA &a)
00074 : nfa(&a)
00075 { }
00076
00077 dcursor(const NFA &a, typename NFA::state_type p)
00078 : nfa(&a) {
00079 if (p != a.null_state) q.insert(p);
00080 }
00081
00082 dcursor(const NFA &a, const state_type& p)
00083 : nfa(&a), q(p)
00084 { }
00085
00086 state_type src() const { return q; }
00087
00088 self& operator=(const typename NFA::state_type& p) {
00089 q.clear();
00090 q.insert(p);
00091 return *this;
00092 }
00093
00094 self& operator=(const state_type& p) {
00095 q = p;
00096 return *this;
00097 }
00098
00099 self& operator=(const self &x) {
00100 nfa = x.nfa;
00101 q = x.q;
00102 return *this;
00103 }
00104
00105 bool operator==(const self &x) const { return q == x.q && nfa == x.nfa; }
00106
00107 bool sink() const { return q.empty(); }
00108
00109 state_type sink_state() const { return state_type(); }
00110
00111 bool forward(const char_type& a) {
00112 state_type p;
00113 insert_iterator<state_type> j(p, p.begin());
00114 for(typename state_type::const_iterator i = q.begin(); i != q.end(); ++i)
00115 nfa->delta1(*i, a, j);
00116 q.swap(p);
00117 return !sink();
00118 }
00119
00120 bool src_final() const {
00121 for(typename state_type::const_iterator i = q.begin(); i != q.end(); ++i)
00122 if (nfa->final(*i)) return true;
00123 return false;
00124 }
00125
00126 tag_type src_tag() const { return TagMapper()(*nfa, q.begin(), q.end()); }
00127
00128 bool exists(const char_type& a) const {
00129 state_type p;
00130 insert_iterator<state_type> j(p, p.begin());
00131 for(typename state_type::const_iterator i = q.begin(); i != q.end(); ++i) {
00132 nfa->delta1(*i, a, j);
00133 if (!p.empty()) return true;
00134 }
00135 return false;
00136 }
00137 };
00138
00145 template <typename NFA, typename TagMapper = default_tag_mapper<NFA> >
00146 class forward_dcursor
00147 : public dcursor<NFA, TagMapper>, public forward_cursor_concept
00148 {
00149 public:
00150 typedef forward_dcursor self;
00151 typedef dcursor<NFA, TagMapper> super;
00152 typedef typename super::char_traits char_traits;
00153 typedef typename super::tag_type tag_type;
00154 typedef typename super::char_type char_type;
00155 typedef typename super::state_type state_type;
00156 typedef forward_cursor_concept concept;
00157
00158
00159 protected:
00160 char_type a;
00161 state_type p;
00162
00163 public:
00164 forward_dcursor()
00165 { }
00166
00167 forward_dcursor(const NFA &n)
00168 : super(n)
00169 { }
00170
00171 forward_dcursor(const NFA &n, typename NFA::state_type p)
00172 : super(n, p)
00173 { }
00174
00175 forward_dcursor(const NFA &n, const state_type& s)
00176 : super(n, s)
00177 { }
00178
00179 self& operator=(const self &x) {
00180 super::operator=(x);
00181 a = x.a;
00182 p = x.p;
00183 return *this;
00184 }
00185
00186 self& operator=(const state_type &x) {
00187 super::operator=(x);
00188 return *this;
00189 }
00190
00191 self& operator=(typename NFA::state_type x) {
00192 super::operator=(x);
00193 return *this;
00194 }
00195
00196 bool operator==(const self &x) const {
00197 return super::operator==(x) && super::char_traits::eq(a, x.a)
00198 && p == x.p;
00199 }
00200
00201 char_type letter() const { return a;}
00202
00203 bool first() {
00204 p.clear();
00205 insert_iterator<state_type> j(p, p.begin());
00206
00207 typename state_type::const_iterator i;
00208 typename NFA::edges_type::const_iterator first
00209 = nfa->delta2(*q.begin()).end();
00210 typename NFA::edges_type::const_iterator last = first, k;
00211 for(i = q.begin(); i != q.end(); ++i) {
00212 k = nfa->delta2(*i).begin();
00213 if (k != nfa->delta2(*i).end())
00214 if (first == last || super::char_traits::lt((*k).first, (*first).first))
00215 first = k;
00216 }
00217
00218 if (first == last) return false;
00219 a = (*first).first;
00220 for(i = q.begin(); i != q.end(); ++i)
00221 nfa->delta1(*i, a, j);
00222
00223 return !p.empty();
00224 }
00225
00226 bool next() {
00227 p.clear();
00228 insert_iterator<state_type> j(p, p.begin());
00229 char_type tmp = a;
00230
00231 typename state_type::const_iterator i;
00232 typename NFA::edges_type::const_iterator k;
00233 for(i = q.begin(); i != q.end(); ++i) {
00234 k = nfa->delta2(*i).upper_bound(tmp);
00235 if (k != nfa->delta2(*i).end())
00236 if (tmp == a || super::char_traits::lt((*k).first, a))
00237 a = (*k).first;
00238 }
00239
00240 if (a == tmp) return false;
00241 for(i = q.begin(); i != q.end(); ++i)
00242 nfa->delta1(*i, a, j);
00243
00244 return !p.empty();
00245 }
00246
00247 void forward() { q.swap(p); }
00248
00249 bool forward(const char_type& c) { return super::forward(c); }
00250
00251 bool find(const char_type& c) {
00252 p.clear();
00253 insert_iterator<state_type> j(p, p.begin());
00254 a = c;
00255
00256 for(typename state_type::const_iterator i = q.begin();
00257 i != q.end(); ++i)
00258 nfa->delta1(*i, c, j);
00259
00260 return !p.empty();
00261 }
00262
00263 state_type aim() const { return p; }
00264
00265 bool aim_final() const {
00266 for(typename state_type::const_iterator i = p.begin(); i != p.end(); ++i)
00267 if (nfa->final(*i)) return true;
00268 return false;
00269 }
00270
00271 tag_type aim_tag() const {
00272 return TagMapper()(*nfa, p.begin(), p.end());
00273 }
00274
00275 protected:
00276 using super::nfa;
00277 using super::q;
00278 };
00279
00280 template <typename NFA, typename TagMapper = default_tag_mapper<NFA> >
00281 class async_forward_dcursor : public forward_dcursor<NFA, TagMapper>
00282 {
00283 public:
00284 typedef async_forward_dcursor self;
00285 typedef forward_dcursor<NFA, TagMapper> super;
00286 typedef typename super::char_type char_type;
00287 typedef typename super::state_type state_type;
00288
00289 protected:
00290 char_type x;
00291
00292 public:
00293 async_forward_dcursor()
00294 : super()
00295 { }
00296
00297 async_forward_dcursor(const NFA& n, const char_type &a)
00298 : super(n), x(a)
00299 { }
00300
00301 async_forward_dcursor(const NFA &n, const char_type &a,
00302 typename NFA::state_type p)
00303 : super(n, p), x(a) {
00304 epsilon_closure(q);
00305 }
00306
00307 async_forward_dcursor(const NFA &n, const char_type &a, const state_type& s)
00308 : super(n, s), x(a) {
00309 epsilon_closure(q);
00310 }
00311
00312 self& operator=(const self &y) {
00313 super::operator=(y);
00314 x = y.x;
00315 return *this;
00316 }
00317
00318 self& operator=(const state_type &y) {
00319 super::operator=(y);
00320 epsilon_closure(q);
00321 return *this;
00322 }
00323
00324 self& operator=(typename NFA::state_type y) {
00325 super::operator=(y);
00326 epsilon_closure(q);
00327 return *this;
00328 }
00329
00330 void forward() { super::forward(); }
00331
00332 bool forward(const char_type& a) {
00333 if (super::forward(a)) {
00334 epsilon_closure(q);
00335 return true;
00336 }
00337 return false;
00338 }
00339
00340 bool find(const char_type& a) {
00341 if (super::find(a)) {
00342 epsilon_closure(p);
00343 return true;
00344 }
00345 return false;
00346 }
00347
00348 bool first() {
00349 if (super::first()) {
00350 if (super::letter() == x)
00351 return next();
00352 else {
00353 epsilon_closure(p);
00354 return true;
00355 }
00356 }
00357 return false;
00358 }
00359
00360 bool next() {
00361 if (super::next()) {
00362 if (super::letter() == x)
00363 return next();
00364 else {
00365 epsilon_closure(p);
00366 return true;
00367 }
00368 }
00369 return false;
00370 }
00371
00372 protected:
00373 using super::q;
00374 using super::nfa;
00375 using super::p;
00376
00377 void epsilon_closure(state_type &s) {
00378 state_type tmp = s;
00379 insert_iterator<state_type> c(s, s.begin());
00380 closure_cursor<transition_cursor<NFA> > t(transitionc(*nfa, NFA::null_state), x);
00381 for(typename state_type::const_iterator i = tmp.begin(); i != tmp.end(); ++i) {
00382 t = *i;
00383 crop(c, dfirst_markc(t));
00384 }
00385 }
00386 };
00387
00391 template <typename NFA>
00392 inline
00393 dcursor<NFA> plaindc(const NFA &a) {
00394 return dcursor<NFA>(a, a.initial());
00395 }
00396
00400 template <typename NFA>
00401 inline
00402 dcursor<NFA> plaindc(const NFA &a, typename NFA::state_type q) {
00403 return dcursor<NFA>(a, q);
00404 }
00405
00409 template <typename NFA>
00410 inline
00411 forward_dcursor<NFA> forwarddc(const NFA &a) {
00412 return forward_dcursor<NFA>(a, a.initial());
00413 }
00414
00418 template <typename NFA>
00419 inline
00420 forward_dcursor<NFA> forwarddc(const NFA &a, typename NFA::state_type q) {
00421 return forward_dcursor<NFA>(a, q);
00422 }
00423
00424 template <typename NFA>
00425 inline
00426 async_forward_dcursor<NFA>
00427 async_forwarddc(const NFA &a, const typename NFA::char_type &c) {
00428 return async_forward_dcursor<NFA>(a, c, a.initial());
00429 }
00430
00431 template <typename NFA>
00432 inline
00433 async_forward_dcursor<NFA>
00434 async_forwarddc(const NFA &a, const typename NFA::char_type &c,
00435 typename NFA::state_type q) {
00436 return async_forward_dcursor<NFA>(a, c, q);
00437 }
00438
00439 #ifdef NEWSCHOOL
00440 template <typename TransitionCursor, typename TagMapper = default_tag_mapper<NFA> >
00441 class forward_dcursor
00442 : public public forward_cursor_concept
00443 {
00444 public:
00445 struct transitionc_order : public binary_function<TransitionCursor, TransitionCursor, bool>
00446 {
00447 bool operator()(const TransitionCursor &x, const TransitionCursor &y) const {
00448 return x.src() < y.src();
00449 }
00450 };
00451 typedef forward_dcursor self;
00452 typedef typename TransitionCursor::char_traits char_traits;
00453 typedef typename TagMapper::result_type tag_type;
00454 typedef typename TransitionCursor::char_type char_type;
00455 typedef typename set<TransitionCursor, transitionc_order> state_type;
00456 typedef forward_cursor_concept concept;
00457
00458
00459 protected:
00460
00461 };
00462
00463 #endif
00464
00465 }
00466
00467 #endif // ASTL_DETERMINIZE_H
00468
00469
00470
00471