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
00035
00036
00037
00038 #include <climits>
00039 #include <algorithm>
00040
00041 namespace Gecode { namespace Int { namespace Extensional {
00042
00049 template<class Var>
00050 class VarTraits {};
00051
00057 template<>
00058 class VarTraits<IntVar> {
00059 public:
00061 typedef Int::IntView View;
00062 };
00063
00069 template<>
00070 class VarTraits<BoolVar> {
00071 public:
00073 typedef Int::BoolView View;
00074 };
00075
00076
00077
00078
00079
00080 template<class View, class Val, class Degree, class StateIdx>
00081 forceinline void
00082 LayeredGraph<View,Val,Degree,StateIdx>::State::init(void) {
00083 i_deg=o_deg=0;
00084 }
00085
00086
00087 template<class View, class Val, class Degree, class StateIdx>
00088 forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
00089 LayeredGraph<View,Val,Degree,StateIdx>::i_state(int i, StateIdx is) {
00090 return layers[i].states[is];
00091 }
00092 template<class View, class Val, class Degree, class StateIdx>
00093 forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
00094 LayeredGraph<View,Val,Degree,StateIdx>::i_state
00095 (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00096 return i_state(i,e.i_state);
00097 }
00098 template<class View, class Val, class Degree, class StateIdx>
00099 forceinline bool
00100 LayeredGraph<View,Val,Degree,StateIdx>::i_dec
00101 (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00102 return --i_state(i,e).o_deg == 0;
00103 }
00104 template<class View, class Val, class Degree, class StateIdx>
00105 forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
00106 LayeredGraph<View,Val,Degree,StateIdx>::o_state(int i, StateIdx os) {
00107 return layers[i+1].states[os];
00108 }
00109 template<class View, class Val, class Degree, class StateIdx>
00110 forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
00111 LayeredGraph<View,Val,Degree,StateIdx>::o_state
00112 (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00113 return o_state(i,e.o_state);
00114 }
00115 template<class View, class Val, class Degree, class StateIdx>
00116 forceinline bool
00117 LayeredGraph<View,Val,Degree,StateIdx>::o_dec
00118 (int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
00119 return --o_state(i,e).i_deg == 0;
00120 }
00121
00122
00123
00124
00125
00126 template<class View, class Val, class Degree, class StateIdx>
00127 forceinline
00128 LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::LayerValues(void) {}
00129 template<class View, class Val, class Degree, class StateIdx>
00130 forceinline
00131 LayeredGraph<View,Val,Degree,StateIdx>::LayerValues
00132 ::LayerValues(const Layer& l)
00133 : s1(l.support), s2(l.support+l.size) {}
00134 template<class View, class Val, class Degree, class StateIdx>
00135 forceinline void
00136 LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::init(const Layer& l) {
00137 s1=l.support; s2=l.support+l.size;
00138 }
00139 template<class View, class Val, class Degree, class StateIdx>
00140 forceinline bool
00141 LayeredGraph<View,Val,Degree,StateIdx>::LayerValues
00142 ::operator ()(void) const {
00143 return s1<s2;
00144 }
00145 template<class View, class Val, class Degree, class StateIdx>
00146 forceinline void
00147 LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::operator ++(void) {
00148 s1++;
00149 }
00150 template<class View, class Val, class Degree, class StateIdx>
00151 forceinline int
00152 LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::val(void) const {
00153 return s1->val;
00154 }
00155
00156
00157
00158
00159
00160
00161 template<class View, class Val, class Degree, class StateIdx>
00162 forceinline
00163 LayeredGraph<View,Val,Degree,StateIdx>::Index::Index(Space& home, Propagator& p,
00164 Council<Index>& c,
00165 int i0)
00166 : Advisor(home,p,c), i(i0) {}
00167
00168 template<class View, class Val, class Degree, class StateIdx>
00169 forceinline
00170 LayeredGraph<View,Val,Degree,StateIdx>::Index::Index(Space& home, bool share,
00171 Index& a)
00172 : Advisor(home,share,a), i(a.i) {}
00173
00174
00175
00176
00177
00178
00179 template<class View, class Val, class Degree, class StateIdx>
00180 forceinline
00181 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::IndexRange(void)
00182 : _fst(INT_MAX), _lst(INT_MIN) {}
00183 template<class View, class Val, class Degree, class StateIdx>
00184 forceinline void
00185 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::reset(void) {
00186 _fst=INT_MAX; _lst=INT_MIN;
00187 }
00188 template<class View, class Val, class Degree, class StateIdx>
00189 forceinline void
00190 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::add(int i) {
00191 _fst=std::min(_fst,i); _lst=std::max(_lst,i);
00192 }
00193 template<class View, class Val, class Degree, class StateIdx>
00194 forceinline void
00195 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::add
00196 (const typename LayeredGraph<View,Val,Degree,StateIdx>::IndexRange& ir) {
00197 _fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
00198 }
00199 template<class View, class Val, class Degree, class StateIdx>
00200 forceinline bool
00201 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::empty(void) const {
00202 return _fst>_lst;
00203 }
00204 template<class View, class Val, class Degree, class StateIdx>
00205 forceinline void
00206 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::lshift(int n) {
00207 if (empty())
00208 return;
00209 if (n > _lst) {
00210 reset();
00211 } else {
00212 _fst = std::max(0,_fst-n);
00213 _lst -= n;
00214 }
00215 }
00216 template<class View, class Val, class Degree, class StateIdx>
00217 forceinline int
00218 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::fst(void) const {
00219 return _fst;
00220 }
00221 template<class View, class Val, class Degree, class StateIdx>
00222 forceinline int
00223 LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::lst(void) const {
00224 return _lst;
00225 }
00226
00227
00228
00229
00230
00231
00232
00233
00234 template<class View, class Val, class Degree, class StateIdx>
00235 template<class Var>
00236 forceinline
00237 LayeredGraph<View,Val,Degree,StateIdx>::LayeredGraph(Home home,
00238 const VarArgArray<Var>& x,
00239 const DFA& dfa)
00240 : Propagator(home), c(home), n(x.size()),
00241 max_states(static_cast<StateIdx>(dfa.n_states())) {
00242 assert(n > 0);
00243 }
00244
00245 template<class View, class Val, class Degree, class StateIdx>
00246 forceinline void
00247 LayeredGraph<View,Val,Degree,StateIdx>::audit(void) {
00248 #ifdef GECODE_AUDIT
00249
00250 unsigned int n_e = 0;
00251 unsigned int n_s = 0;
00252 StateIdx m_s = 0;
00253 for (int i=n; i--; ) {
00254 n_s += layers[i].n_states;
00255 m_s = std::max(m_s,layers[i].n_states);
00256 for (ValSize j=layers[i].size; j--; )
00257 n_e += layers[i].support[j].n_edges;
00258 }
00259 n_s += layers[n].n_states;
00260 m_s = std::max(m_s,layers[n].n_states);
00261 assert(n_e == n_edges);
00262 assert(n_s <= n_states);
00263 assert(m_s <= max_states);
00264 #endif
00265 }
00266
00267 template<class View, class Val, class Degree, class StateIdx>
00268 template<class Var>
00269 forceinline ExecStatus
00270 LayeredGraph<View,Val,Degree,StateIdx>::initialize(Space& home,
00271 const VarArgArray<Var>& x,
00272 const DFA& dfa) {
00273
00274 Region r(home);
00275
00276
00277 layers = home.alloc<Layer>(n+1);
00278
00279
00280 State* states = r.alloc<State>(max_states*(n+1));
00281 for (int i=static_cast<int>(max_states)*(n+1); i--; )
00282 states[i].init();
00283 for (int i=n+1; i--; )
00284 layers[i].states = states + i*max_states;
00285
00286
00287 Edge* edges = r.alloc<Edge>(dfa.max_degree());
00288
00289
00290 i_state(0,0).i_deg = 1;
00291
00292
00293 for (int i=0; i<n; i++) {
00294 layers[i].x = x[i];
00295 layers[i].support = home.alloc<Support>(layers[i].x.size());
00296 ValSize j=0;
00297
00298 for (ViewValues<View> nx(layers[i].x); nx(); ++nx) {
00299 Degree n_edges=0;
00300 for (DFA::Transitions t(dfa,nx.val()); t(); ++t)
00301 if (i_state(i,static_cast<StateIdx>(t.i_state())).i_deg != 0) {
00302 i_state(i,static_cast<StateIdx>(t.i_state())).o_deg++;
00303 o_state(i,static_cast<StateIdx>(t.o_state())).i_deg++;
00304 edges[n_edges].i_state = static_cast<StateIdx>(t.i_state());
00305 edges[n_edges].o_state = static_cast<StateIdx>(t.o_state());
00306 n_edges++;
00307 }
00308 assert(n_edges <= dfa.max_degree());
00309
00310 if (n_edges > 0) {
00311 Support& s = layers[i].support[j];
00312 s.val = static_cast<Val>(nx.val());
00313 s.n_edges = n_edges;
00314 s.edges = Heap::copy(home.alloc<Edge>(n_edges),edges,n_edges);
00315 j++;
00316 }
00317 }
00318 if ((layers[i].size = j) == 0)
00319 return ES_FAILED;
00320 }
00321
00322
00323 for (int s=dfa.final_fst(); s<dfa.final_lst(); s++)
00324 if (o_state(n-1,static_cast<StateIdx>(s)).i_deg != 0)
00325 o_state(n-1,static_cast<StateIdx>(s)).o_deg = 1;
00326
00327
00328 for (int i=n; i--; ) {
00329 ValSize k=0;
00330 for (ValSize j=0; j<layers[i].size; j++) {
00331 Support& s = layers[i].support[j];
00332 for (Degree d=s.n_edges; d--; )
00333 if (o_state(i,s.edges[d]).o_deg == 0) {
00334
00335 i_dec(i,s.edges[d]); o_dec(i,s.edges[d]);
00336
00337 s.edges[d] = s.edges[--s.n_edges];
00338 }
00339
00340 if (s.n_edges > 0)
00341 layers[i].support[k++]=s;
00342 }
00343 if ((layers[i].size = k) == 0)
00344 return ES_FAILED;
00345 LayerValues lv(layers[i]);
00346 GECODE_ME_CHECK(layers[i].x.narrow_v(home,lv,false));
00347 if (!layers[i].x.assigned())
00348 layers[i].x.subscribe(home, *new (home) Index(home,*this,c,i));
00349 }
00350
00351
00352 {
00353
00354 StateIdx* i_map = r.alloc<StateIdx>(max_states);
00355
00356 StateIdx* o_map = r.alloc<StateIdx>(max_states);
00357
00358 StateIdx i_n = 0;
00359
00360
00361
00362 unsigned int d = 0;
00363 for (StateIdx j=max_states; j--; )
00364 d += static_cast<unsigned int>(layers[n].states[j].i_deg);
00365
00366 if (d >
00367 static_cast<unsigned int>
00368 (Gecode::Support::IntTypeTraits<Degree>::max)) {
00369
00370 for (StateIdx j=max_states; j--; )
00371 if ((layers[n].states[j].o_deg != 0) ||
00372 (layers[n].states[j].i_deg != 0))
00373 i_map[j]=i_n++;
00374 } else {
00375 i_n = 1;
00376 for (StateIdx j=max_states; j--; ) {
00377 layers[n].states[j].init();
00378 i_map[j] = 0;
00379 }
00380 layers[n].states[0].i_deg = static_cast<Degree>(d);
00381 layers[n].states[0].o_deg = 1;
00382 }
00383 layers[n].n_states = i_n;
00384
00385
00386 n_states = i_n;
00387
00388 n_edges = 0;
00389
00390 StateIdx max_s = i_n;
00391
00392 for (int i=n; i--; ) {
00393
00394 std::swap(o_map,i_map); i_n=0;
00395
00396 for (StateIdx j=max_states; j--; )
00397 if ((layers[i].states[j].o_deg != 0) ||
00398 (layers[i].states[j].i_deg != 0))
00399 i_map[j]=i_n++;
00400 layers[i].n_states = i_n;
00401 n_states += i_n;
00402 max_s = std::max(max_s,i_n);
00403
00404
00405 for (ValSize j=layers[i].size; j--; ) {
00406 Support& ls = layers[i].support[j];
00407 n_edges += ls.n_edges;
00408 for (Degree deg=ls.n_edges; deg--; ) {
00409 ls.edges[deg].i_state = i_map[ls.edges[deg].i_state];
00410 ls.edges[deg].o_state = o_map[ls.edges[deg].o_state];
00411 }
00412 }
00413 }
00414
00415
00416 State* a_states = home.alloc<State>(n_states);
00417 for (int i=n+1; i--; ) {
00418 StateIdx k=0;
00419 for (StateIdx j=max_states; j--; )
00420 if ((layers[i].states[j].o_deg != 0) ||
00421 (layers[i].states[j].i_deg != 0))
00422 a_states[k++] = layers[i].states[j];
00423 assert(k == layers[i].n_states);
00424 layers[i].states = a_states;
00425 a_states += layers[i].n_states;
00426 }
00427
00428
00429 max_states = max_s;
00430 }
00431
00432
00433 if (c.empty())
00434 View::schedule(home,*this,ME_INT_VAL);
00435
00436 audit();
00437 return ES_OK;
00438 }
00439
00440 template<class View, class Val, class Degree, class StateIdx>
00441 ExecStatus
00442 LayeredGraph<View,Val,Degree,StateIdx>::advise(Space& home,
00443 Advisor& _a, const Delta& d) {
00444
00445 if (layers[0].states == NULL) {
00446 State* states = home.alloc<State>(n_states);
00447 for (unsigned int i=n_states; i--; )
00448 states[i].init();
00449 layers[n].states = states;
00450 states += layers[n].n_states;
00451 for (int i=n; i--; ) {
00452 layers[i].states = states;
00453 states += layers[i].n_states;
00454 for (ValSize j=layers[i].size; j--; ) {
00455 Support& s = layers[i].support[j];
00456 for (Degree deg=s.n_edges; deg--; ) {
00457 i_state(i,s.edges[deg]).o_deg++;
00458 o_state(i,s.edges[deg]).i_deg++;
00459 }
00460 }
00461 }
00462 }
00463
00464 Index& a = static_cast<Index&>(_a);
00465 const int i = a.i;
00466
00467 if (layers[i].size <= layers[i].x.size()) {
00468
00469 if (View::modevent(d) == ME_INT_VAL) {
00470 a.dispose(home,c);
00471 return c.empty() ? ES_NOFIX : ES_FIX;
00472 } else {
00473 return ES_FIX;
00474 }
00475 }
00476
00477 bool i_mod = false;
00478 bool o_mod = false;
00479
00480 if (View::modevent(d) == ME_INT_VAL) {
00481 Val n = static_cast<Val>(layers[i].x.val());
00482 ValSize j=0;
00483 for (; layers[i].support[j].val < n; j++) {
00484 Support& s = layers[i].support[j];
00485 n_edges -= s.n_edges;
00486
00487 for (Degree deg=s.n_edges; deg--; ) {
00488
00489 o_mod |= i_dec(i,s.edges[deg]);
00490 i_mod |= o_dec(i,s.edges[deg]);
00491 }
00492 }
00493 assert(layers[i].support[j].val == n);
00494 layers[i].support[0] = layers[i].support[j++];
00495 ValSize s=layers[i].size;
00496 layers[i].size = 1;
00497 for (; j<s; j++) {
00498 Support& ls = layers[i].support[j];
00499 n_edges -= ls.n_edges;
00500 for (Degree deg=ls.n_edges; deg--; ) {
00501
00502 o_mod |= i_dec(i,ls.edges[deg]);
00503 i_mod |= o_dec(i,ls.edges[deg]);
00504 }
00505 }
00506 } else if (layers[i].x.any(d)) {
00507 ValSize j=0;
00508 ValSize k=0;
00509 ValSize s=layers[i].size;
00510 for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
00511 Support& ls = layers[i].support[j];
00512 if (ls.val < static_cast<Val>(rx.min())) {
00513
00514 n_edges -= ls.n_edges;
00515 for (Degree deg=ls.n_edges; deg--; ) {
00516
00517 o_mod |= i_dec(i,ls.edges[deg]);
00518 i_mod |= o_dec(i,ls.edges[deg]);
00519 }
00520 ++j;
00521 } else if (ls.val > static_cast<Val>(rx.max())) {
00522 ++rx;
00523 } else {
00524 layers[i].support[k++]=ls;
00525 ++j;
00526 }
00527 }
00528 assert(k > 0);
00529 layers[i].size = k;
00530
00531 for (; j<s; j++) {
00532 Support& ls=layers[i].support[j];
00533 n_edges -= ls.n_edges;
00534 for (Degree deg=ls.n_edges; deg--; ) {
00535
00536 o_mod |= i_dec(i,ls.edges[deg]);
00537 i_mod |= o_dec(i,ls.edges[deg]);
00538 }
00539 }
00540 } else {
00541 Val min = static_cast<Val>(layers[i].x.min(d));
00542 ValSize j=0;
00543
00544 for (; layers[i].support[j].val < min; j++) {}
00545 Val max = static_cast<Val>(layers[i].x.max(d));
00546 ValSize k=j;
00547 ValSize s=layers[i].size;
00548
00549 for (; (j<s) && (layers[i].support[j].val <= max); j++) {
00550 Support& ls=layers[i].support[j];
00551 n_edges -= ls.n_edges;
00552 for (Degree deg=ls.n_edges; deg--; ) {
00553
00554 o_mod |= i_dec(i,ls.edges[deg]);
00555 i_mod |= o_dec(i,ls.edges[deg]);
00556 }
00557 }
00558
00559 while (j<s)
00560 layers[i].support[k++]=layers[i].support[j++];
00561 layers[i].size=k;
00562 assert(k > 0);
00563 }
00564
00565 audit();
00566
00567 bool fix = true;
00568 if (o_mod && (i > 0)) {
00569 o_ch.add(i-1); fix = false;
00570 }
00571 if (i_mod && (i+1 < n)) {
00572 i_ch.add(i+1); fix = false;
00573 }
00574 if (fix) {
00575 if (View::modevent(d) == ME_INT_VAL) {
00576 a.dispose(home,c);
00577 return c.empty() ? ES_NOFIX : ES_FIX;
00578 }
00579 return ES_FIX;
00580 } else {
00581 return (View::modevent(d) == ME_INT_VAL)
00582 ? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
00583 }
00584 }
00585
00586 template<class View, class Val, class Degree, class StateIdx>
00587 forceinline size_t
00588 LayeredGraph<View,Val,Degree,StateIdx>::dispose(Space& home) {
00589 c.dispose(home);
00590 (void) Propagator::dispose(home);
00591 return sizeof(*this);
00592 }
00593
00594 template<class View, class Val, class Degree, class StateIdx>
00595 void
00596 LayeredGraph<View,Val,Degree,StateIdx>::reschedule(Space& home) {
00597 View::schedule(home,*this,c.empty() ? ME_INT_VAL : ME_INT_DOM);
00598 }
00599
00600 template<class View, class Val, class Degree, class StateIdx>
00601 ExecStatus
00602 LayeredGraph<View,Val,Degree,StateIdx>::propagate(Space& home,
00603 const ModEventDelta&) {
00604
00605 for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
00606 bool i_mod = false;
00607 bool o_mod = false;
00608 ValSize j=0;
00609 ValSize k=0;
00610 ValSize ls=layers[i].size;
00611 do {
00612 Support& s=layers[i].support[j];
00613 n_edges -= s.n_edges;
00614 for (Degree d=s.n_edges; d--; )
00615 if (i_state(i,s.edges[d]).i_deg == 0) {
00616
00617 o_mod |= i_dec(i,s.edges[d]);
00618 i_mod |= o_dec(i,s.edges[d]);
00619
00620 s.edges[d] = s.edges[--s.n_edges];
00621 }
00622 n_edges += s.n_edges;
00623
00624 if (s.n_edges == 0) {
00625 layers[i].size--;
00626 GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00627 } else {
00628 layers[i].support[k++]=s;
00629 }
00630 } while (++j<ls);
00631 assert(k > 0);
00632
00633 if (o_mod && (i > 0))
00634 o_ch.add(i-1);
00635 if (i_mod && (i+1 < n))
00636 i_ch.add(i+1);
00637 }
00638
00639
00640 for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
00641 bool o_mod = false;
00642 ValSize j=0;
00643 ValSize k=0;
00644 ValSize ls=layers[i].size;
00645 do {
00646 Support& s=layers[i].support[j];
00647 n_edges -= s.n_edges;
00648 for (Degree d=s.n_edges; d--; )
00649 if (o_state(i,s.edges[d]).o_deg == 0) {
00650
00651 o_mod |= i_dec(i,s.edges[d]);
00652 (void) o_dec(i,s.edges[d]);
00653
00654 s.edges[d] = s.edges[--s.n_edges];
00655 }
00656 n_edges += s.n_edges;
00657
00658 if (s.n_edges == 0) {
00659 layers[i].size--;
00660 GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00661 } else {
00662 layers[i].support[k++]=s;
00663 }
00664 } while (++j<ls);
00665 assert(k > 0);
00666
00667 if (o_mod && (i > 0))
00668 o_ch.add(i-1);
00669 }
00670
00671 a_ch.add(i_ch); i_ch.reset();
00672 a_ch.add(o_ch); o_ch.reset();
00673
00674 audit();
00675
00676
00677 if (c.empty())
00678 return home.ES_SUBSUMED(*this);
00679 else
00680 return ES_FIX;
00681 }
00682
00683
00684 template<class View, class Val, class Degree, class StateIdx>
00685 template<class Var>
00686 ExecStatus
00687 LayeredGraph<View,Val,Degree,StateIdx>::post(Home home,
00688 const VarArgArray<Var>& x,
00689 const DFA& dfa) {
00690 if (x.size() == 0) {
00691
00692 if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
00693 return ES_OK;
00694 return ES_FAILED;
00695 }
00696 assert(x.size() > 0);
00697 for (int i=x.size(); i--; ) {
00698 DFA::Symbols s(dfa);
00699 typename VarTraits<Var>::View xi(x[i]);
00700 GECODE_ME_CHECK(xi.inter_v(home,s,false));
00701 }
00702 LayeredGraph<View,Val,Degree,StateIdx>* p =
00703 new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
00704 return p->initialize(home,x,dfa);
00705 }
00706
00707 template<class View, class Val, class Degree, class StateIdx>
00708 forceinline
00709 LayeredGraph<View,Val,Degree,StateIdx>
00710 ::LayeredGraph(Space& home, bool share,
00711 LayeredGraph<View,Val,Degree,StateIdx>& p)
00712 : Propagator(home,share,p),
00713 n(p.n), layers(home.alloc<Layer>(n+1)),
00714 max_states(p.max_states), n_states(p.n_states), n_edges(p.n_edges) {
00715 c.update(home,share,p.c);
00716
00717 layers[n].n_states = p.layers[n].n_states;
00718 layers[n].states = NULL;
00719
00720 Edge* edges = home.alloc<Edge>(n_edges);
00721
00722 for (int i=n; i--; ) {
00723 layers[i].x.update(home,share,p.layers[i].x);
00724 assert(layers[i].x.size() == p.layers[i].size);
00725 layers[i].size = p.layers[i].size;
00726 layers[i].support = home.alloc<Support>(layers[i].size);
00727 for (ValSize j=layers[i].size; j--; ) {
00728 layers[i].support[j].val = p.layers[i].support[j].val;
00729 layers[i].support[j].n_edges = p.layers[i].support[j].n_edges;
00730 assert(layers[i].support[j].n_edges > 0);
00731 layers[i].support[j].edges =
00732 Heap::copy(edges,p.layers[i].support[j].edges,
00733 layers[i].support[j].n_edges);
00734 edges += layers[i].support[j].n_edges;
00735 }
00736 layers[i].n_states = p.layers[i].n_states;
00737 layers[i].states = NULL;
00738 }
00739 audit();
00740 }
00741
00742 template<class View, class Val, class Degree, class StateIdx>
00743 PropCost
00744 LayeredGraph<View,Val,Degree,StateIdx>::cost(const Space&,
00745 const ModEventDelta&) const {
00746 return PropCost::linear(PropCost::HI,n);
00747 }
00748
00749 template<class View, class Val, class Degree, class StateIdx>
00750 Actor*
00751 LayeredGraph<View,Val,Degree,StateIdx>::copy(Space& home, bool share) {
00752
00753 {
00754 int k=0;
00755 while (layers[k].size == 1) {
00756 assert(layers[k].support[0].n_edges == 1);
00757 n_states -= layers[k].n_states;
00758 k++;
00759 }
00760 if (k > 0) {
00761
00762
00763
00764
00765
00766
00767
00768
00769 n -= k; layers += k;
00770
00771 n_edges -= static_cast<unsigned int>(k);
00772
00773 for (Advisors<Index> as(c); as(); ++as)
00774 as.advisor().i -= k;
00775
00776 a_ch.lshift(k);
00777 }
00778 }
00779 audit();
00780
00781
00782 if (!a_ch.empty()) {
00783 int f = a_ch.fst();
00784 int l = a_ch.lst();
00785 assert((f >= 0) && (l <= n));
00786 Region r(home);
00787
00788 StateIdx* i_map = r.alloc<StateIdx>(max_states);
00789
00790 StateIdx* o_map = r.alloc<StateIdx>(max_states);
00791
00792 StateIdx i_n = 0;
00793
00794 n_states -= layers[l].n_states;
00795
00796 for (StateIdx j=0; j<layers[l].n_states; j++)
00797 if ((layers[l].states[j].i_deg != 0) ||
00798 (layers[l].states[j].o_deg != 0)) {
00799 layers[l].states[i_n]=layers[l].states[j];
00800 i_map[j]=i_n++;
00801 }
00802 layers[l].n_states = i_n;
00803 n_states += layers[l].n_states;
00804 assert(i_n > 0);
00805
00806
00807 if (l < n)
00808 for (ValSize j=layers[l].size; j--; ) {
00809 Support& s = layers[l].support[j];
00810 for (Degree d=s.n_edges; d--; )
00811 s.edges[d].i_state = i_map[s.edges[d].i_state];
00812 }
00813
00814
00815 for (int i=l-1; i>=f; i--) {
00816
00817 std::swap(o_map,i_map); i_n=0;
00818
00819 n_states -= layers[i].n_states;
00820 for (StateIdx j=0; j<layers[i].n_states; j++)
00821 if ((layers[i].states[j].o_deg != 0) ||
00822 (layers[i].states[j].i_deg != 0)) {
00823 layers[i].states[i_n]=layers[i].states[j];
00824 i_map[j]=i_n++;
00825 }
00826 layers[i].n_states = i_n;
00827 n_states += layers[i].n_states;
00828 assert(i_n > 0);
00829
00830
00831 for (ValSize j=layers[i].size; j--; ) {
00832 Support& s = layers[i].support[j];
00833 for (Degree d=s.n_edges; d--; ) {
00834 s.edges[d].i_state = i_map[s.edges[d].i_state];
00835 s.edges[d].o_state = o_map[s.edges[d].o_state];
00836 }
00837 }
00838 }
00839
00840
00841 if (f > 0)
00842 for (ValSize j=layers[f-1].size; j--; ) {
00843 Support& s = layers[f-1].support[j];
00844 for (Degree d=s.n_edges; d--; )
00845 s.edges[d].o_state = i_map[s.edges[d].o_state];
00846 }
00847
00848 a_ch.reset();
00849 }
00850 audit();
00851
00852 return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,share,*this);
00853 }
00854
00856 template<class Var>
00857 forceinline ExecStatus
00858 post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
00859 Gecode::Support::IntType t_state_idx =
00860 Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
00861 Gecode::Support::IntType t_degree =
00862 Gecode::Support::u_type(dfa.max_degree());
00863 Gecode::Support::IntType t_val =
00864 std::max(Support::s_type(dfa.symbol_min()),
00865 Support::s_type(dfa.symbol_max()));
00866 switch (t_val) {
00867 case Gecode::Support::IT_CHAR:
00868 case Gecode::Support::IT_SHRT:
00869 switch (t_state_idx) {
00870 case Gecode::Support::IT_CHAR:
00871 switch (t_degree) {
00872 case Gecode::Support::IT_CHAR:
00873 return Extensional::LayeredGraph
00874 <typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
00875 ::post(home,x,dfa);
00876 case Gecode::Support::IT_SHRT:
00877 return Extensional::LayeredGraph
00878 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
00879 ::post(home,x,dfa);
00880 case Gecode::Support::IT_INT:
00881 return Extensional::LayeredGraph
00882 <typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
00883 ::post(home,x,dfa);
00884 default: GECODE_NEVER;
00885 }
00886 break;
00887 case Gecode::Support::IT_SHRT:
00888 switch (t_degree) {
00889 case Gecode::Support::IT_CHAR:
00890 return Extensional::LayeredGraph
00891 <typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
00892 ::post(home,x,dfa);
00893 case Gecode::Support::IT_SHRT:
00894 return Extensional::LayeredGraph
00895 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
00896 ::post(home,x,dfa);
00897 case Gecode::Support::IT_INT:
00898 return Extensional::LayeredGraph
00899 <typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
00900 ::post(home,x,dfa);
00901 default: GECODE_NEVER;
00902 }
00903 break;
00904 case Gecode::Support::IT_INT:
00905 switch (t_degree) {
00906 case Gecode::Support::IT_CHAR:
00907 return Extensional::LayeredGraph
00908 <typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
00909 ::post(home,x,dfa);
00910 case Gecode::Support::IT_SHRT:
00911 return Extensional::LayeredGraph
00912 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
00913 ::post(home,x,dfa);
00914 case Gecode::Support::IT_INT:
00915 return Extensional::LayeredGraph
00916 <typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
00917 ::post(home,x,dfa);
00918 default: GECODE_NEVER;
00919 }
00920 break;
00921 default: GECODE_NEVER;
00922 }
00923
00924 case Gecode::Support::IT_INT:
00925 switch (t_state_idx) {
00926 case Gecode::Support::IT_CHAR:
00927 switch (t_degree) {
00928 case Gecode::Support::IT_CHAR:
00929 return Extensional::LayeredGraph
00930 <typename VarTraits<Var>::View,int,unsigned char,unsigned char>
00931 ::post(home,x,dfa);
00932 case Gecode::Support::IT_SHRT:
00933 return Extensional::LayeredGraph
00934 <typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
00935 ::post(home,x,dfa);
00936 case Gecode::Support::IT_INT:
00937 return Extensional::LayeredGraph
00938 <typename VarTraits<Var>::View,int,unsigned int,unsigned char>
00939 ::post(home,x,dfa);
00940 default: GECODE_NEVER;
00941 }
00942 break;
00943 case Gecode::Support::IT_SHRT:
00944 switch (t_degree) {
00945 case Gecode::Support::IT_CHAR:
00946 return Extensional::LayeredGraph
00947 <typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
00948 ::post(home,x,dfa);
00949 case Gecode::Support::IT_SHRT:
00950 return Extensional::LayeredGraph
00951 <typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
00952 ::post(home,x,dfa);
00953 case Gecode::Support::IT_INT:
00954 return Extensional::LayeredGraph
00955 <typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
00956 ::post(home,x,dfa);
00957 default: GECODE_NEVER;
00958 }
00959 break;
00960 case Gecode::Support::IT_INT:
00961 switch (t_degree) {
00962 case Gecode::Support::IT_CHAR:
00963 return Extensional::LayeredGraph
00964 <typename VarTraits<Var>::View,int,unsigned char,unsigned int>
00965 ::post(home,x,dfa);
00966 case Gecode::Support::IT_SHRT:
00967 return Extensional::LayeredGraph
00968 <typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
00969 ::post(home,x,dfa);
00970 case Gecode::Support::IT_INT:
00971 return Extensional::LayeredGraph
00972 <typename VarTraits<Var>::View,int,unsigned int,unsigned int>
00973 ::post(home,x,dfa);
00974 default: GECODE_NEVER;
00975 }
00976 break;
00977 default: GECODE_NEVER;
00978 }
00979
00980 default: GECODE_NEVER;
00981 }
00982 return ES_OK;
00983 }
00984
00985 }}}
00986
00987
00988