00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef ASTL_LAZY_H
00023 #define ASTL_LAZY_H
00024
00025 #include <astl.h>
00026 #include <map>
00027 #include <utility>
00028
00029 #define CLASSICAL_LAZY
00030
00031 using namespace std;
00032
00033 namespace astl {
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046 template <typename Cursor,
00047 template <typename Sigma, typename Tag> class DFA = DFA_matrix>
00048 class lazy_cursor : public cursor_concept
00049 {
00050 public:
00051 #ifdef CLASSICAL_LAZY
00052 typedef DFA<typename Cursor::char_traits, typename Cursor::state_type> DFA_type;
00053 #else
00054 typedef DFA<typename Cursor::char_traits, const typename Cursor::state_type*> DFA_type;
00055 #endif
00056
00057 protected:
00058 typedef map<typename Cursor::state_type,
00059 safe<typename DFA_type::state_type, DFA_type::null_state> > mapper;
00060 typename DFA_type::state_type my_sink;
00061 Cursor c;
00062 smart_ptr<DFA_type> dfa;
00063 smart_ptr<mapper> mapping;
00064 safe<typename DFA_type::state_type> q;
00065
00066 public:
00067 typedef lazy_cursor self;
00068 typedef typename DFA_type::state_type state_type;
00069 typedef empty_tag tag_type;
00070 typedef typename Cursor::char_type char_type;
00071 typedef typename Cursor::char_traits char_traits;
00072
00073 lazy_cursor(const Cursor &x)
00074 : c(x)
00075 {
00076 if (!x.sink())
00077 {
00078 q = dfa->new_state();
00079 #ifdef CLASSICAL_LAZY
00080 dfa->tag(q) = c.src();
00081 (*mapping)[c.src()] = q;
00082 #else
00083 pair<typename mapper::iterator, bool> p = mapping->insert(make_pair(c.src(), q));
00084 dfa->tag(q) = &(p.first->first);
00085 #endif
00086 dfa->final(q) = c.src_final();
00087 dfa->initial(q);
00088 my_sink = dfa->new_state();
00089 }
00090 }
00091
00092
00093 const Cursor& cursor() {
00094 c = dfa->tag(q);
00095 return c;
00096 }
00097
00098 const Cursor& adaptee() {
00099 #ifdef CLASSICAL_LAZY
00100 c = dfa->tag(q);
00101 #else
00102 c = *dfa->tag(q);
00103 #endif
00104 return c;
00105 }
00106
00107 const DFA_type& cache() const {
00108 return *dfa;
00109 }
00110
00111 state_type src() const {
00112 return q;
00113 }
00114
00115 self& operator=(state_type p) {
00116 q = p;
00117 return *this;
00118 }
00119
00120 bool src_final() const {
00121 return dfa->final(q);
00122 }
00123
00124 empty_tag src_tag() const {
00125 return empty_tag();
00126 }
00127
00128 bool sink() const {
00129 return q == DFA_type::null_state;
00130 }
00131
00132 state_type sink_state() const {
00133 return DFA_type::null_state;
00134 }
00135
00136 bool exists(const char_type &a) const {
00137 state_type aim = dfa->delta1(q, a);
00138 switch (aim) {
00139 case my_sink :
00140 return false;
00141
00142 case DFA_type::null_state :
00143 Cursor tmp = c;
00144 tmp = dfa->tag(q);
00145 return tmp.exists(a);
00146
00147 default :
00148 return true;
00149 }
00150 }
00151
00152 bool forward(const char_type &a) {
00153 state_type tmp = dfa->delta1(q, a);
00154 if (tmp == my_sink) {
00155 q = DFA_type::null_state;
00156 return false;
00157 }
00158 if (tmp == DFA_type::null_state)
00159 {
00160 #ifdef CLASSICAL_LAZY
00161 c = dfa->tag(q);
00162 #else
00163 c = *dfa->tag(q);
00164 #endif
00165 if (c.forward(a))
00166 {
00167 #ifndef CLASSICAL_LAZY
00168 pair<typename mapper::iterator, bool> p = mapping->insert(make_pair(c.src(), DFA_type::null_state));
00169 if (p.second == true) {
00170 state_type tmp2 = dfa->new_state();
00171 p.first->second = tmp2;
00172 dfa->final(tmp2) = c.src_final();
00173 dfa->tag(tmp2) = &(p.first->first);
00174 }
00175 tmp = p.first->second;
00176 #else
00177 safe<state_type, DFA_type::null_state> &tmp2 = (*mapping)[c.src()];
00178 if (tmp2 == DFA_type::null_state) {
00179 tmp2 = dfa->new_state();
00180 dfa->final(tmp2) = c.src_final();
00181 dfa->tag(tmp2) = c.src();
00182 (*mapping)[c.src()] = tmp2;
00183 }
00184 tmp = tmp2;
00185 #endif
00186 dfa->set_trans(q, a, tmp);
00187 }
00188 else {
00189 dfa->set_trans(q, a, my_sink);
00190 q = DFA_type::null_state;
00191 return false;
00192 }
00193 }
00194 q = tmp;
00195 return true;
00196 }
00197 };
00198
00199 template <class Cursor>
00200 inline
00201 lazy_cursor<Cursor> lazyc(const Cursor &c) {
00202 return lazy_cursor<Cursor>(c);
00203 }
00204
00205
00206
00207 template <class Cursor,
00208 template <class Sigma, class Tag> class DFA = DFA_matrix>
00209 class lazy_cursor_tag : public cursor_concept
00210 {
00211 public:
00212 typedef DFA<typename Cursor::char_traits,
00213 pair<typename Cursor::tag_type, typename Cursor::state_type> > DFA_type;
00214
00215 protected:
00216 typedef map<typename Cursor::state_type,
00217 safe<typename DFA_type::state_type, DFA_type::null_state> > mapper;
00218 typename DFA_type::state_type my_sink;
00219 Cursor c;
00220 smart_ptr<DFA_type> dfa;
00221 smart_ptr<mapper> mapping;
00222 safe<typename DFA_type::state_type, DFA_type::null_state> q;
00223
00224 public:
00225 typedef lazy_cursor_tag self;
00226 typedef typename DFA_type::state_type state_type;
00227 typedef typename Cursor::tag_type tag_type;
00228 typedef typename Cursor::char_type char_type;
00229 typedef typename Cursor::char_traits char_traits;
00230
00231 lazy_cursor_tag(const Cursor &x)
00232 : c(x)
00233 {
00234 if (!x.sink())
00235 {
00236 q = dfa->new_state();
00237 dfa->tag(q).second = c.src();
00238 dfa->tag(q).first = c.src_tag();
00239 (*mapping)[c.src()] = q;
00240 dfa->final(q) = c.src_final();
00241 dfa->initial(q);
00242 my_sink = dfa->new_state();
00243 }
00244 }
00245
00246 const DFA_type& cache() const {
00247 return *dfa;
00248 }
00249
00250 state_type src() const {
00251 return q;
00252 }
00253
00254 self& operator=(state_type p) {
00255 q = p;
00256 return *this;
00257 }
00258
00259 bool src_final() const {
00260 return dfa->final(q);
00261 }
00262
00263 tag_type src_tag() const {
00264 return dfa->tag(q).first;
00265 }
00266
00267 bool sink() const {
00268 return q == DFA_type::null_state;
00269 }
00270
00271 state_type sink_state() const {
00272 return DFA_type::null_state;
00273 }
00274
00275 bool forward(const char_type &a) {
00276 state_type tmp = dfa->delta1(q, a);
00277 if (tmp == my_sink) {
00278 q = DFA_type::null_state;
00279 return false;
00280 }
00281 if (tmp == DFA_type::null_state)
00282 {
00283 c = dfa->tag(q).second;
00284 if (c.forward(a))
00285 {
00286 safe<state_type, DFA_type::null_state> &tmp2 = (*mapping)[c.src()];
00287 if (tmp2 == DFA_type::null_state) {
00288 tmp2 = dfa->new_state();
00289 dfa->final(tmp2) = c.src_final();
00290 dfa->tag(tmp2).second = c.src();
00291 dfa->tag(tmp2).first = c.src_tag();
00292 (*mapping)[c.src()] = tmp2;
00293 }
00294 tmp = tmp2;
00295 dfa->set_trans(q, a, tmp);
00296 }
00297 else {
00298 dfa->set_trans(q, a, my_sink);
00299 q = DFA_type::null_state;
00300 return false;
00301 }
00302 }
00303 q = tmp;
00304 return true;
00305 }
00306 };
00307
00308 template <class Cursor>
00309 inline
00310 lazy_cursor_tag<Cursor> lazyc_tag(const Cursor &c) {
00311 return lazy_cursor_tag<Cursor>(c);
00312 }
00313
00314 }
00315
00316 #endif // ASTL_LAZY_H
00317
00318
00319
00320
00321
00322