00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "gecode/int.hh"
00023 #include "gecode/support/sort.hh"
00024 #include "gecode/support/static-stack.hh"
00025
00026
00027 namespace Gecode { namespace Int { namespace Regular {
00028
00032 class TransByI_State {
00033 public:
00034 forceinline bool
00035 operator()(const DFA::Transition& x, const DFA::Transition& y) {
00036 return x.i_state < y.i_state;
00037 }
00038 forceinline static void
00039 sort(DFA::Transition t[], int n) {
00040 TransByI_State tbis;
00041 Support::quicksort<DFA::Transition,TransByI_State>(t,n,tbis);
00042 }
00043 };
00044
00048 class TransBySymbol {
00049 public:
00050 forceinline bool
00051 operator()(const DFA::Transition& x, const DFA::Transition& y) {
00052 return x.symbol < y.symbol;
00053 }
00054 forceinline static void
00055 sort(DFA::Transition t[], int n) {
00056 TransBySymbol tbs;
00057 Support::quicksort<DFA::Transition,TransBySymbol>(t,n,tbs);
00058 }
00059 };
00060
00064 class TransBySymbolI_State {
00065 public:
00066 forceinline bool
00067 operator()(const DFA::Transition& x, const DFA::Transition& y) {
00068 return ((x.symbol < y.symbol) ||
00069 (x.symbol == y.symbol) && (x.i_state < y.i_state));
00070 }
00071 forceinline static void
00072 sort(DFA::Transition t[], int n) {
00073 TransBySymbolI_State tbsi;
00074 Support::quicksort<DFA::Transition,TransBySymbolI_State>(t,n,tbsi);
00075 }
00076 };
00077
00081 class TransByO_State {
00082 public:
00083 forceinline bool
00084 operator()(const DFA::Transition& x, const DFA::Transition& y) {
00085 return x.o_state < y.o_state;
00086 }
00087 forceinline static void
00088 sort(DFA::Transition t[], int n) {
00089 TransByO_State tbos;
00090 Support::quicksort<DFA::Transition,TransByO_State>(t,n,tbos);
00091 }
00092 };
00093
00094
00098 class StateGroup {
00099 public:
00100 int state;
00101 int group;
00102 };
00103
00107 class StateGroupByGroup {
00108 public:
00109 forceinline bool
00110 operator()(const StateGroup& x, const StateGroup& y) {
00111 return ((x.group < y.group) ||
00112 (x.group == y.group) && (x.state < y.state));
00113 }
00114 static void
00115 sort(StateGroup sg[], int n) {
00116 StateGroupByGroup o;
00117 Support::quicksort<StateGroup,StateGroupByGroup>(sg,n,o);
00118 }
00119 };
00120
00124 class GroupStates {
00125 public:
00126 StateGroup* fst;
00127 StateGroup* lst;
00128 };
00129
00131 #define S_NONE 0
00133 #define S_FROM_START 1
00135 #define S_TO_FINAL 2
00137 #define S_FINAL 4
00138
00139 }}}
00140
00141 namespace Gecode {
00142
00143 void
00144 DFA::init(int start, Transition t_spec[], int f_spec[], bool minimize) {
00145 using namespace Int;
00146 using namespace Regular;
00147
00148 int n_states = start;
00149 int n_trans = 0;
00150 for (Transition* t = &t_spec[0]; t->i_state >= 0; t++) {
00151 n_states = std::max(n_states,t->i_state);
00152 n_states = std::max(n_states,t->o_state);
00153 n_trans++;
00154 }
00155 for (int* f = &f_spec[0]; *f >= 0; f++)
00156 n_states = std::max(n_states,*f);
00157 n_states++;
00158
00159
00160 GECODE_AUTOARRAY(Transition, trans, n_trans);
00161 for (int i = n_trans; i--; )
00162 trans[i] = t_spec[i];
00163
00164 GECODE_AUTOARRAY(int, final, n_states+1);
00165 GECODE_AUTOARRAY(bool, is_final, n_states+1);
00166 int n_finals = 0;
00167 for (int i = n_states+1; i--; )
00168 is_final[i] = false;
00169 for (int* f = &f_spec[0]; *f != -1; f++) {
00170 is_final[*f] = true;
00171 final[n_finals++] = *f;
00172 }
00173
00174 if (minimize) {
00175
00176 TransBySymbolI_State::sort(trans, n_trans);
00177 GECODE_AUTOARRAY(Transition*, idx, n_trans+1);
00178
00179 int n_symbols = 0;
00180 {
00181 int j = 0;
00182 while (j < n_trans) {
00183 idx[n_symbols++] = &trans[j];
00184 int s = trans[j].symbol;
00185 while ((j < n_trans) && (s == trans[j].symbol))
00186 j++;
00187 }
00188 idx[n_symbols] = &trans[j];
00189 assert(j == n_trans);
00190 }
00191
00192 GECODE_AUTOARRAY(int, s2g, n_states+1);
00193 GECODE_AUTOARRAY(StateGroup, part, n_states+1);
00194 GECODE_AUTOARRAY(GroupStates, g2s, n_states+1);
00195
00196 for (int i = n_states+1; i--; ) {
00197 part[i].state = i;
00198 part[i].group = is_final[i] ? 1 : 0;
00199 s2g[i] = part[i].group;
00200 }
00201
00202
00203
00204
00205
00206 StateGroupByGroup::sort(part,n_states+1);
00207 int n_groups;
00208 if (part[0].group == part[n_states].group) {
00209
00210 g2s[0].fst = &part[0]; g2s[0].lst = &part[n_states+1];
00211 n_groups = 1;
00212 } else {
00213 int i = 0;
00214 assert(part[0].group == 0);
00215 do i++; while (part[i].group == 0);
00216 g2s[0].fst = &part[0]; g2s[0].lst = &part[i];
00217 g2s[1].fst = &part[i]; g2s[1].lst = &part[n_states+1];
00218 n_groups = 2;
00219 }
00220
00221
00222 {
00223 int m_groups;
00224 do {
00225 m_groups = n_groups;
00226
00227 for (int sidx = n_symbols; sidx--; ) {
00228
00229 for (int g = n_groups; g--; ) {
00230
00231 if (g2s[g].lst-g2s[g].fst > 1) {
00232
00233
00234
00235 Transition* t = idx[sidx];
00236 Transition* t_lst = idx[sidx+1];
00237 for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
00238 while ((t < t_lst) && (t->i_state < sg->state))
00239 t++;
00240
00241 if ((t < t_lst) && (t->i_state == sg->state))
00242 sg->group = s2g[t->o_state];
00243 else
00244 sg->group = s2g[n_states];
00245 }
00246
00247 StateGroupByGroup::sort(g2s[g].fst,
00248 static_cast<int>(g2s[g].lst-g2s[g].fst));
00249
00250 if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
00251
00252 StateGroup* sg = g2s[g].fst+1;
00253 while ((sg-1)->group == sg->group)
00254 sg++;
00255
00256 StateGroup* lst = g2s[g].lst;
00257 g2s[g].lst = sg;
00258 while (sg < lst) {
00259 s2g[sg->state] = n_groups;
00260 g2s[n_groups].fst = sg++;
00261 while ((sg < lst) && ((sg-1)->group == sg->group)) {
00262 s2g[sg->state] = n_groups; sg++;
00263 }
00264 g2s[n_groups++].lst = sg;
00265 }
00266 }
00267 }
00268 }
00269 }
00270 } while (n_groups != m_groups);
00271
00272 start = s2g[start];
00273
00274 n_finals = 0;
00275 for (int g = n_groups; g--; )
00276 for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
00277 if (is_final[sg->state]) {
00278 final[n_finals++] = g;
00279 break;
00280 }
00281
00282 GECODE_AUTOARRAY(int, s2r, n_states+1);
00283 for (int i = n_states+1; i--; )
00284 s2r[i] = -1;
00285 for (int g = n_groups; g--; )
00286 s2r[g2s[g].fst->state] = g;
00287
00288 int j = 0;
00289 for (int i = 0; i<n_trans; i++)
00290 if (s2r[trans[i].i_state] != -1) {
00291 trans[j].i_state = s2g[trans[i].i_state];
00292 trans[j].symbol = trans[i].symbol;
00293 trans[j].o_state = s2g[trans[i].o_state];
00294 j++;
00295 }
00296 n_trans = j;
00297 n_states = n_groups;
00298 }
00299 }
00300
00301
00302 Support::StaticStack<int> visit(n_states);
00303 GECODE_AUTOARRAY(int, state, n_states);
00304 for (int i=n_states; i--; )
00305 state[i] = S_NONE;
00306
00307 {
00308
00309
00310 TransByI_State::sort(trans, n_trans);
00311 GECODE_AUTOARRAY(Transition*, idx, n_states+1);
00312 {
00313 int j = 0;
00314 for (int i=0; i<n_states; i++) {
00315 idx[i] = &trans[j];
00316 while ((j < n_trans) && (i == trans[j].i_state))
00317 j++;
00318 }
00319 idx[n_states] = &trans[j];
00320 assert(j == n_trans);
00321 }
00322
00323 state[start] = S_FROM_START;
00324 visit.push(start);
00325 while (!visit.empty()) {
00326 int s = visit.pop();
00327 for (Transition* t = idx[s]; t < idx[s+1]; t++)
00328 if (!(state[t->o_state] & S_FROM_START)) {
00329 state[t->o_state] |= S_FROM_START;
00330 visit.push(t->o_state);
00331 }
00332 }
00333 }
00334
00335
00336 {
00337
00338
00339 TransByO_State::sort(trans, n_trans);
00340 GECODE_AUTOARRAY(Transition*, idx, n_states+1);
00341 {
00342 int j = 0;
00343 for (int i=0; i<n_states; i++) {
00344 idx[i] = &trans[j];
00345 while ((j < n_trans) && (i == trans[j].o_state))
00346 j++;
00347 }
00348 idx[n_states] = &trans[j];
00349 assert(j == n_trans);
00350 }
00351
00352 for (int i = n_finals; i--; ) {
00353 state[final[i]] |= (S_TO_FINAL | S_FINAL);
00354 visit.push(final[i]);
00355 }
00356 while (!visit.empty()) {
00357 int s = visit.pop();
00358 for (Transition* t = idx[s]; t < idx[s+1]; t++)
00359 if (!(state[t->i_state] & S_TO_FINAL)) {
00360 state[t->i_state] |= S_TO_FINAL;
00361 visit.push(t->i_state);
00362 }
00363 }
00364 }
00365
00366
00367 GECODE_AUTOARRAY(int, re, n_states);
00368 for (int i = n_states; i--; )
00369 re[i] = -1;
00370
00371
00372 int m_states = 0;
00373
00374 re[start] = m_states++;
00375
00376
00377 for (int i = n_states; i--; )
00378 if ((state[i] == (S_FINAL | S_FROM_START | S_TO_FINAL)) && (re[i] < 0))
00379 re[i] = m_states++;
00380
00381 int final_fst = (state[start] & S_FINAL) ? 0 : 1;
00382 int final_lst = m_states;
00383
00384
00385
00386 for (int i = n_states; i--; )
00387 if ((state[i] == (S_FROM_START | S_TO_FINAL)) && (re[i] < 0))
00388 re[i] = m_states++;
00389
00390
00391 int m_trans = 0;
00392 for (int i = n_trans; i--; )
00393 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0))
00394 m_trans++;
00395
00396
00397 DFAI* d = reinterpret_cast<DFAI*>
00398 (Memory::malloc(sizeof(DFAI) + sizeof(Transition)*(m_trans-1)));
00399 d->use_cnt = 1;
00400 d->n_states = m_states;
00401 d->n_trans = m_trans;
00402 d->final_fst = final_fst;
00403 d->final_lst = final_lst;
00404 {
00405 int j = 0;
00406 Transition* r = &d->trans[0];
00407 for (int i = 0; i<n_trans; i++)
00408 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0)) {
00409 r[j].symbol = trans[i].symbol;
00410 r[j].i_state = re[trans[i].i_state];
00411 r[j].o_state = re[trans[i].o_state];
00412 j++;
00413 }
00414 TransBySymbol::sort(r,m_trans);
00415 }
00416 dfai = d;
00417 }
00418
00419 }
00420
00421 std::ostream&
00422 operator<<(std::ostream& os, const Gecode::DFA& dfa) {
00423 os << "Start state: 0" << std::endl
00424 << "States: 0..." << dfa.n_states()-1 << std::endl
00425 << "Transitions:";
00426 for (int s = 0; s < static_cast<int>(dfa.n_states()); s++) {
00427 Gecode::DFA::Transitions t(dfa);
00428 int n = 0;
00429 while (t()) {
00430 if (t.transition()->i_state == s) {
00431 if ((n % 4) == 0)
00432 os << std::endl << "\t";
00433 os << "[" << t.transition()->i_state << "]"
00434 << "- " << t.transition()->symbol << " >"
00435 << "[" << t.transition()->o_state << "] ";
00436 ++n;
00437 }
00438 ++t;
00439 }
00440 }
00441 os << std::endl << "Final states: "
00442 << std::endl
00443 << "\t[" << dfa.final_fst() << "] ... ["
00444 << dfa.final_lst()-1 << "]"
00445 << std::endl;
00446 return os;
00447 }
00448
00449 namespace Gecode {
00450
00451 DFA::DFAI*
00452 DFA::DFAI::copy(void) {
00453 DFAI* d = reinterpret_cast<DFAI*>
00454 (Memory::malloc(sizeof(DFAI) + sizeof(Transition)*(n_trans-1)));
00455 d->use_cnt = 1;
00456 d->n_states = n_states;
00457 d->n_trans = n_trans;
00458 d->final_fst = final_fst;
00459 d->final_lst = final_lst;
00460 memcpy(&d->trans[0], &trans[0], sizeof(Transition)*n_trans);
00461 return d;
00462 }
00463
00464 }
00465
00466
00467