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