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
00027
00028
00029
00030
00031
00032
00033
00034 #include <gecode/int.hh>
00035
00036 namespace Gecode { namespace Int { namespace Extensional {
00037
00041 class TransByI_State {
00042 public:
00043 forceinline bool
00044 operator ()(const DFA::Transition& x, const DFA::Transition& y) {
00045 return x.i_state < y.i_state;
00046 }
00047 forceinline static void
00048 sort(DFA::Transition t[], int n) {
00049 TransByI_State tbis;
00050 Support::quicksort<DFA::Transition,TransByI_State>(t,n,tbis);
00051 }
00052 };
00053
00057 class TransBySymbol {
00058 public:
00059 forceinline bool
00060 operator ()(const DFA::Transition& x, const DFA::Transition& y) {
00061 return x.symbol < y.symbol;
00062 }
00063 forceinline static void
00064 sort(DFA::Transition t[], int n) {
00065 TransBySymbol tbs;
00066 Support::quicksort<DFA::Transition,TransBySymbol>(t,n,tbs);
00067 }
00068 };
00069
00073 class TransBySymbolI_State {
00074 public:
00075 forceinline bool
00076 operator ()(const DFA::Transition& x, const DFA::Transition& y) {
00077 return ((x.symbol < y.symbol) ||
00078 ((x.symbol == y.symbol) && (x.i_state < y.i_state)));
00079 }
00080 forceinline static void
00081 sort(DFA::Transition t[], int n) {
00082 TransBySymbolI_State tbsi;
00083 Support::quicksort<DFA::Transition,TransBySymbolI_State>(t,n,tbsi);
00084 }
00085 };
00086
00090 class TransByO_State {
00091 public:
00092 forceinline bool
00093 operator ()(const DFA::Transition& x, const DFA::Transition& y) {
00094 return x.o_state < y.o_state;
00095 }
00096 forceinline static void
00097 sort(DFA::Transition t[], int n) {
00098 TransByO_State tbos;
00099 Support::quicksort<DFA::Transition,TransByO_State>(t,n,tbos);
00100 }
00101 };
00102
00103
00107 class StateGroup {
00108 public:
00109 int state;
00110 int group;
00111 };
00112
00116 class StateGroupByGroup {
00117 public:
00118 forceinline bool
00119 operator ()(const StateGroup& x, const StateGroup& y) {
00120 return ((x.group < y.group) ||
00121 ((x.group == y.group) && (x.state < y.state)));
00122 }
00123 static void
00124 sort(StateGroup sg[], int n) {
00125 StateGroupByGroup o;
00126 Support::quicksort<StateGroup,StateGroupByGroup>(sg,n,o);
00127 }
00128 };
00129
00133 class GroupStates {
00134 public:
00135 StateGroup* fst;
00136 StateGroup* lst;
00137 };
00138
00140 enum StateInfo {
00141 SI_NONE = 0,
00142 SI_FROM_START = 1,
00143 SI_TO_FINAL = 2,
00144 SI_FINAL = 4
00145 };
00146
00147 }}}
00148
00149 namespace Gecode {
00150
00151 DFA::DFA(int start, Transition t_spec[], int f_spec[], bool minimize) {
00152 using namespace Int;
00153 using namespace Extensional;
00154
00155 int n_states = start;
00156 int n_trans = 0;
00157 for (Transition* t = &t_spec[0]; t->i_state >= 0; t++) {
00158 n_states = std::max(n_states,t->i_state);
00159 n_states = std::max(n_states,t->o_state);
00160 n_trans++;
00161 }
00162 for (int* f = &f_spec[0]; *f >= 0; f++)
00163 n_states = std::max(n_states,*f);
00164 n_states++;
00165
00166
00167 Transition* trans = heap.alloc<Transition>(n_trans);
00168 for (int i = n_trans; i--; )
00169 trans[i] = t_spec[i];
00170
00171 int* final = heap.alloc<int>(n_states+1);
00172 bool* is_final = heap.alloc<bool>(n_states+1);
00173 int n_finals = 0;
00174 for (int i = n_states+1; i--; )
00175 is_final[i] = false;
00176 for (int* f = &f_spec[0]; *f != -1; f++) {
00177 is_final[*f] = true;
00178 final[n_finals++] = *f;
00179 }
00180
00181 if (minimize) {
00182
00183 TransBySymbolI_State::sort(trans, n_trans);
00184 Transition** idx = heap.alloc<Transition*>(n_trans+1);
00185
00186 int n_symbols = 0;
00187 {
00188 int j = 0;
00189 while (j < n_trans) {
00190 idx[n_symbols++] = &trans[j];
00191 int s = trans[j].symbol;
00192 while ((j < n_trans) && (s == trans[j].symbol))
00193 j++;
00194 }
00195 idx[n_symbols] = &trans[j];
00196 assert(j == n_trans);
00197 }
00198
00199 int* s2g = heap.alloc<int>(n_states+1);
00200 StateGroup* part = heap.alloc<StateGroup>(n_states+1);
00201 GroupStates* g2s = heap.alloc<GroupStates>(n_states+1);
00202
00203 for (int i = n_states+1; i--; ) {
00204 part[i].state = i;
00205 part[i].group = is_final[i] ? 1 : 0;
00206 s2g[i] = part[i].group;
00207 }
00208
00209
00210
00211
00212
00213 StateGroupByGroup::sort(part,n_states+1);
00214 int n_groups;
00215 if (part[0].group == part[n_states].group) {
00216
00217 g2s[0].fst = &part[0]; g2s[0].lst = &part[n_states+1];
00218 n_groups = 1;
00219 } else {
00220 int i = 0;
00221 assert(part[0].group == 0);
00222 do i++; while (part[i].group == 0);
00223 g2s[0].fst = &part[0]; g2s[0].lst = &part[i];
00224 g2s[1].fst = &part[i]; g2s[1].lst = &part[n_states+1];
00225 n_groups = 2;
00226 }
00227
00228
00229 {
00230 int m_groups;
00231 do {
00232 m_groups = n_groups;
00233
00234 for (int sidx = n_symbols; sidx--; ) {
00235
00236 for (int g = n_groups; g--; ) {
00237
00238 if (g2s[g].lst-g2s[g].fst > 1) {
00239
00240
00241
00242 Transition* t = idx[sidx];
00243 Transition* t_lst = idx[sidx+1];
00244 for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
00245 while ((t < t_lst) && (t->i_state < sg->state))
00246 t++;
00247
00248 if ((t < t_lst) && (t->i_state == sg->state))
00249 sg->group = s2g[t->o_state];
00250 else
00251 sg->group = s2g[n_states];
00252 }
00253
00254 StateGroupByGroup::sort(g2s[g].fst,
00255 static_cast<int>(g2s[g].lst-g2s[g].fst));
00256
00257 if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
00258
00259 StateGroup* sg = g2s[g].fst+1;
00260 while ((sg-1)->group == sg->group)
00261 sg++;
00262
00263 StateGroup* lst = g2s[g].lst;
00264 g2s[g].lst = sg;
00265 while (sg < lst) {
00266 s2g[sg->state] = n_groups;
00267 g2s[n_groups].fst = sg++;
00268 while ((sg < lst) && ((sg-1)->group == sg->group)) {
00269 s2g[sg->state] = n_groups; sg++;
00270 }
00271 g2s[n_groups++].lst = sg;
00272 }
00273 }
00274 }
00275 }
00276 }
00277 } while (n_groups != m_groups);
00278
00279 start = s2g[start];
00280
00281 n_finals = 0;
00282 for (int g = n_groups; g--; )
00283 for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
00284 if (is_final[sg->state]) {
00285 final[n_finals++] = g;
00286 break;
00287 }
00288
00289 int* s2r = heap.alloc<int>(n_states+1);
00290 for (int i = n_states+1; i--; )
00291 s2r[i] = -1;
00292 for (int g = n_groups; g--; )
00293 s2r[g2s[g].fst->state] = g;
00294
00295 int j = 0;
00296 for (int i = 0; i<n_trans; i++)
00297 if (s2r[trans[i].i_state] != -1) {
00298 trans[j].i_state = s2g[trans[i].i_state];
00299 trans[j].symbol = trans[i].symbol;
00300 trans[j].o_state = s2g[trans[i].o_state];
00301 j++;
00302 }
00303 n_trans = j;
00304 n_states = n_groups;
00305 heap.free<int>(s2r,n_states+1);
00306 }
00307 heap.free<GroupStates>(g2s,n_states+1);
00308 heap.free<StateGroup>(part,n_states+1);
00309 heap.free<int>(s2g,n_states+1);
00310 heap.free<Transition*>(idx,n_trans+1);
00311 }
00312
00313
00314 Gecode::Support::StaticStack<int,Heap> visit(heap,n_states);
00315 int* state = heap.alloc<int>(n_states);
00316 for (int i=n_states; i--; )
00317 state[i] = SI_NONE;
00318
00319 Transition** idx = heap.alloc<Transition*>(n_states+1);
00320 {
00321
00322
00323 TransByI_State::sort(trans, n_trans);
00324 {
00325 int j = 0;
00326 for (int i=0; i<n_states; i++) {
00327 idx[i] = &trans[j];
00328 while ((j < n_trans) && (i == trans[j].i_state))
00329 j++;
00330 }
00331 idx[n_states] = &trans[j];
00332 assert(j == n_trans);
00333 }
00334
00335 state[start] = SI_FROM_START;
00336 visit.push(start);
00337 while (!visit.empty()) {
00338 int s = visit.pop();
00339 for (Transition* t = idx[s]; t < idx[s+1]; t++)
00340 if (!(state[t->o_state] & SI_FROM_START)) {
00341 state[t->o_state] |= SI_FROM_START;
00342 visit.push(t->o_state);
00343 }
00344 }
00345 }
00346
00347
00348 {
00349
00350
00351 TransByO_State::sort(trans, n_trans);
00352 {
00353 int j = 0;
00354 for (int i=0; i<n_states; i++) {
00355 idx[i] = &trans[j];
00356 while ((j < n_trans) && (i == trans[j].o_state))
00357 j++;
00358 }
00359 idx[n_states] = &trans[j];
00360 assert(j == n_trans);
00361 }
00362
00363 for (int i = n_finals; i--; ) {
00364 state[final[i]] |= (SI_TO_FINAL | SI_FINAL);
00365 visit.push(final[i]);
00366 }
00367 while (!visit.empty()) {
00368 int s = visit.pop();
00369 for (Transition* t = idx[s]; t < idx[s+1]; t++)
00370 if (!(state[t->i_state] & SI_TO_FINAL)) {
00371 state[t->i_state] |= SI_TO_FINAL;
00372 visit.push(t->i_state);
00373 }
00374 }
00375 }
00376 heap.free<Transition*>(idx,n_states+1);
00377 heap.free<int>(final,n_states+1);
00378 heap.free<bool>(is_final,n_states+1);
00379
00380
00381 int* re = heap.alloc<int>(n_states);
00382 for (int i = n_states; i--; )
00383 re[i] = -1;
00384
00385
00386 int m_states = 0;
00387
00388 re[start] = m_states++;
00389
00390
00391 for (int i = n_states; i--; )
00392 if ((state[i] == (SI_FINAL | SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
00393 re[i] = m_states++;
00394
00395 int final_fst = (state[start] & SI_FINAL) ? 0 : 1;
00396 int final_lst = m_states;
00397
00398
00399
00400 for (int i = n_states; i--; )
00401 if ((state[i] == (SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
00402 re[i] = m_states++;
00403
00404
00405 int m_trans = 0;
00406 for (int i = n_trans; i--; )
00407 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0))
00408 m_trans++;
00409
00410
00411 DFAI* d = new DFAI(m_trans);
00412 d->n_states = m_states;
00413 d->n_trans = m_trans;
00414 d->final_fst = final_fst;
00415 d->final_lst = final_lst;
00416 {
00417 int j = 0;
00418 Transition* r = &d->trans[0];
00419 for (int i = 0; i<n_trans; i++)
00420 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0)) {
00421 r[j].symbol = trans[i].symbol;
00422 r[j].i_state = re[trans[i].i_state];
00423 r[j].o_state = re[trans[i].o_state];
00424 j++;
00425 }
00426 TransBySymbol::sort(r,m_trans);
00427 }
00428 {
00429
00430 unsigned int n_symbols = 0;
00431 for (int i = 0; i<m_trans; ) {
00432 int s = d->trans[i++].symbol;
00433 n_symbols++;
00434 while ((i<m_trans) && (d->trans[i].symbol == s))
00435 i++;
00436 }
00437 d->n_symbols = n_symbols;
00438 }
00439 {
00440
00441 unsigned int max_degree = 0;
00442 unsigned int* deg = heap.alloc<unsigned int>(m_states);
00443
00444
00445 for (int i = m_states; i--; )
00446 deg[i] = 0;
00447 for (int i = m_trans; i--; )
00448 deg[d->trans[i].o_state]++;
00449 for (int i = m_states; i--; )
00450 max_degree = std::max(max_degree,deg[i]);
00451
00452
00453 for (int i = m_states; i--; )
00454 deg[i] = 0;
00455 for (int i = m_trans; i--; )
00456 deg[d->trans[i].i_state]++;
00457 for (int i = m_states; i--; )
00458 max_degree = std::max(max_degree,deg[i]);
00459
00460 heap.free<unsigned int>(deg,m_states);
00461
00462
00463 {
00464 int i=0;
00465 while (i < m_trans) {
00466 int j=i++;
00467 while ((i < m_trans) &&
00468 (d->trans[j].symbol == d->trans[i].symbol))
00469 i++;
00470 max_degree = std::max(max_degree,static_cast<unsigned int>(i-j));
00471 }
00472 }
00473
00474 d->max_degree = max_degree;
00475 }
00476
00477 d->fill();
00478 object(d);
00479 heap.free<int>(re,n_states);
00480 heap.free<int>(state,n_states);
00481 heap.free<Transition>(trans,n_trans);
00482 }
00483
00484 bool
00485 DFA::equal(const DFA& d) const {
00486 assert(n_states() == d.n_states());
00487 assert(n_transitions() == d.n_transitions());
00488 assert(n_symbols() == d.n_symbols());
00489 assert(final_fst() == d.final_fst());
00490 assert(final_lst() == d.final_lst());
00491 DFA::Transitions me(*this);
00492 DFA::Transitions they(d);
00493 while (me()) {
00494 if (me.i_state() != they.i_state())
00495 return false;
00496 if (me.symbol() != they.symbol())
00497 return false;
00498 if (me.o_state() != they.o_state())
00499 return false;
00500 ++me;
00501 ++they;
00502 }
00503 return true;
00504 }
00505
00506 }
00507
00508
00509