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 StateIdx o_n = 0;
00361
00362
00363
00364 unsigned int d = 0;
00365 for (StateIdx j=max_states; j--; )
00366 d += static_cast<unsigned int>(layers[n].states[j].i_deg);
00367
00368 if (d >
00369 static_cast<unsigned int>
00370 (Gecode::Support::IntTypeTraits<Degree>::max)) {
00371
00372 for (StateIdx j=max_states; j--; )
00373 if ((layers[n].states[j].o_deg != 0) ||
00374 (layers[n].states[j].i_deg != 0))
00375 i_map[j]=i_n++;
00376 } else {
00377 i_n = 1;
00378 for (StateIdx j=max_states; j--; ) {
00379 layers[n].states[j].init();
00380 i_map[j] = 0;
00381 }
00382 layers[n].states[0].i_deg = static_cast<Degree>(d);
00383 layers[n].states[0].o_deg = 1;
00384 }
00385 layers[n].n_states = i_n;
00386
00387
00388 n_states = i_n;
00389
00390 n_edges = 0;
00391
00392 StateIdx max_s = i_n;
00393
00394 for (int i=n; i--; ) {
00395
00396 std::swap(o_map,i_map); o_n=i_n; i_n=0;
00397
00398 for (StateIdx j=max_states; j--; )
00399 if ((layers[i].states[j].o_deg != 0) ||
00400 (layers[i].states[j].i_deg != 0))
00401 i_map[j]=i_n++;
00402 layers[i].n_states = i_n;
00403 n_states += i_n;
00404 max_s = std::max(max_s,i_n);
00405
00406
00407 for (ValSize j=layers[i].size; j--; ) {
00408 Support& s = layers[i].support[j];
00409 n_edges += s.n_edges;
00410 for (Degree d=s.n_edges; d--; ) {
00411 s.edges[d].i_state = i_map[s.edges[d].i_state];
00412 s.edges[d].o_state = o_map[s.edges[d].o_state];
00413 }
00414 }
00415 }
00416
00417
00418 State* a_states = home.alloc<State>(n_states);
00419 for (int i=n+1; i--; ) {
00420 StateIdx k=0;
00421 for (StateIdx j=max_states; j--; )
00422 if ((layers[i].states[j].o_deg != 0) ||
00423 (layers[i].states[j].i_deg != 0))
00424 a_states[k++] = layers[i].states[j];
00425 assert(k == layers[i].n_states);
00426 layers[i].states = a_states;
00427 a_states += layers[i].n_states;
00428 }
00429
00430
00431 max_states = max_s;
00432 }
00433
00434
00435 if (c.empty())
00436 View::schedule(home,*this,ME_INT_VAL);
00437
00438 audit();
00439 return ES_OK;
00440 }
00441
00442 template<class View, class Val, class Degree, class StateIdx>
00443 ExecStatus
00444 LayeredGraph<View,Val,Degree,StateIdx>::advise(Space& home,
00445 Advisor& _a, const Delta& d) {
00446
00447 if (layers[0].states == NULL) {
00448 State* states = home.alloc<State>(n_states);
00449 for (unsigned int i=n_states; i--; )
00450 states[i].init();
00451 layers[n].states = states;
00452 states += layers[n].n_states;
00453 for (int i=n; i--; ) {
00454 layers[i].states = states;
00455 states += layers[i].n_states;
00456 for (ValSize j=layers[i].size; j--; ) {
00457 Support& s = layers[i].support[j];
00458 for (Degree d=s.n_edges; d--; ) {
00459 i_state(i,s.edges[d]).o_deg++;
00460 o_state(i,s.edges[d]).i_deg++;
00461 }
00462 }
00463 }
00464 }
00465
00466 Index& a = static_cast<Index&>(_a);
00467 const int i = a.i;
00468
00469 if (layers[i].size <= layers[i].x.size()) {
00470
00471 if (View::modevent(d) == ME_INT_VAL) {
00472 a.dispose(home,c);
00473 return c.empty() ? ES_NOFIX : ES_FIX;
00474 } else {
00475 return ES_FIX;
00476 }
00477 }
00478
00479 bool i_mod = false;
00480 bool o_mod = false;
00481
00482 if (View::modevent(d) == ME_INT_VAL) {
00483 Val n = static_cast<Val>(layers[i].x.val());
00484 ValSize j=0;
00485 for (; layers[i].support[j].val < n; j++) {
00486 Support& s = layers[i].support[j];
00487 n_edges -= s.n_edges;
00488
00489 for (Degree d=s.n_edges; d--; ) {
00490
00491 o_mod |= i_dec(i,s.edges[d]);
00492 i_mod |= o_dec(i,s.edges[d]);
00493 }
00494 }
00495 assert(layers[i].support[j].val == n);
00496 layers[i].support[0] = layers[i].support[j++];
00497 ValSize s=layers[i].size;
00498 layers[i].size = 1;
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 if (layers[i].x.any(d)) {
00509 ValSize j=0;
00510 ValSize k=0;
00511 ValSize s=layers[i].size;
00512 for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
00513 Support& s = layers[i].support[j];
00514 if (s.val < static_cast<Val>(rx.min())) {
00515
00516 n_edges -= s.n_edges;
00517 for (Degree d=s.n_edges; d--; ) {
00518
00519 o_mod |= i_dec(i,s.edges[d]);
00520 i_mod |= o_dec(i,s.edges[d]);
00521 }
00522 ++j;
00523 } else if (s.val > static_cast<Val>(rx.max())) {
00524 ++rx;
00525 } else {
00526 layers[i].support[k++]=s;
00527 ++j;
00528 }
00529 }
00530 assert(k > 0);
00531 layers[i].size = k;
00532
00533 for (; j<s; j++) {
00534 Support& s=layers[i].support[j];
00535 n_edges -= s.n_edges;
00536 for (Degree d=s.n_edges; d--; ) {
00537
00538 o_mod |= i_dec(i,s.edges[d]);
00539 i_mod |= o_dec(i,s.edges[d]);
00540 }
00541 }
00542 } else {
00543 Val min = static_cast<Val>(layers[i].x.min(d));
00544 ValSize j=0;
00545
00546 for (; layers[i].support[j].val < min; j++) {}
00547 Val max = static_cast<Val>(layers[i].x.max(d));
00548 ValSize k=j;
00549 ValSize s=layers[i].size;
00550
00551 for (; (j<s) && (layers[i].support[j].val <= max); j++) {
00552 Support& s=layers[i].support[j];
00553 n_edges -= s.n_edges;
00554 for (Degree d=s.n_edges; d--; ) {
00555
00556 o_mod |= i_dec(i,s.edges[d]);
00557 i_mod |= o_dec(i,s.edges[d]);
00558 }
00559 }
00560
00561 while (j<s)
00562 layers[i].support[k++]=layers[i].support[j++];
00563 layers[i].size =k;
00564 assert(k > 0);
00565 }
00566
00567 audit();
00568
00569 bool fix = true;
00570 if (o_mod && (i > 0)) {
00571 o_ch.add(i-1); fix = false;
00572 }
00573 if (i_mod && (i+1 < n)) {
00574 i_ch.add(i+1); fix = false;
00575 }
00576 if (fix) {
00577 if (View::modevent(d) == ME_INT_VAL) {
00578 a.dispose(home,c);
00579 return c.empty() ? ES_NOFIX : ES_FIX;
00580 }
00581 return ES_FIX;
00582 } else {
00583 return (View::modevent(d) == ME_INT_VAL)
00584 ? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
00585 }
00586 }
00587
00588 template<class View, class Val, class Degree, class StateIdx>
00589 forceinline size_t
00590 LayeredGraph<View,Val,Degree,StateIdx>::dispose(Space& home) {
00591 c.dispose(home);
00592 (void) Propagator::dispose(home);
00593 return sizeof(*this);
00594 }
00595
00596 template<class View, class Val, class Degree, class StateIdx>
00597 ExecStatus
00598 LayeredGraph<View,Val,Degree,StateIdx>::propagate(Space& home,
00599 const ModEventDelta&) {
00600
00601 for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
00602 bool i_mod = false;
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 (i_state(i,s.edges[d]).i_deg == 0) {
00612
00613 o_mod |= i_dec(i,s.edges[d]);
00614 i_mod |= 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 if (i_mod && (i+1 < n))
00632 i_ch.add(i+1);
00633 }
00634
00635
00636 for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
00637 bool o_mod = false;
00638 ValSize j=0;
00639 ValSize k=0;
00640 ValSize s=layers[i].size;
00641 do {
00642 Support& s=layers[i].support[j];
00643 n_edges -= s.n_edges;
00644 for (Degree d=s.n_edges; d--; )
00645 if (o_state(i,s.edges[d]).o_deg == 0) {
00646
00647 o_mod |= i_dec(i,s.edges[d]);
00648 (void) o_dec(i,s.edges[d]);
00649
00650 s.edges[d] = s.edges[--s.n_edges];
00651 }
00652 n_edges += s.n_edges;
00653
00654 if (s.n_edges == 0) {
00655 layers[i].size--;
00656 GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00657 } else {
00658 layers[i].support[k++]=s;
00659 }
00660 } while (++j<s);
00661 assert(k > 0);
00662
00663 if (o_mod && (i > 0))
00664 o_ch.add(i-1);
00665 }
00666
00667 a_ch.add(i_ch); i_ch.reset();
00668 a_ch.add(o_ch); o_ch.reset();
00669
00670 audit();
00671
00672
00673 if (c.empty())
00674 return home.ES_SUBSUMED(*this);
00675 else
00676 return ES_FIX;
00677 }
00678
00679
00680 template<class View, class Val, class Degree, class StateIdx>
00681 template<class Var>
00682 ExecStatus
00683 LayeredGraph<View,Val,Degree,StateIdx>::post(Home home,
00684 const VarArgArray<Var>& x,
00685 const DFA& dfa) {
00686 if (x.size() == 0) {
00687
00688 if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
00689 return ES_OK;
00690 return ES_FAILED;
00691 }
00692 assert(x.size() > 0);
00693 for (int i=x.size(); i--; ) {
00694 DFA::Symbols s(dfa);
00695 typename VarTraits<Var>::View xi(x[i]);
00696 GECODE_ME_CHECK(xi.inter_v(home,s,false));
00697 }
00698 LayeredGraph<View,Val,Degree,StateIdx>* p =
00699 new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
00700 return p->initialize(home,x,dfa);
00701 }
00702
00703 template<class View, class Val, class Degree, class StateIdx>
00704 forceinline
00705 LayeredGraph<View,Val,Degree,StateIdx>
00706 ::LayeredGraph(Space& home, bool share,
00707 LayeredGraph<View,Val,Degree,StateIdx>& p)
00708 : Propagator(home,share,p),
00709 n(p.n), layers(home.alloc<Layer>(n+1)),
00710 max_states(p.max_states), n_states(p.n_states), n_edges(p.n_edges) {
00711 c.update(home,share,p.c);
00712
00713 layers[n].n_states = p.layers[n].n_states;
00714 layers[n].states = NULL;
00715
00716 Edge* edges = home.alloc<Edge>(n_edges);
00717
00718 for (int i=n; i--; ) {
00719 layers[i].x.update(home,share,p.layers[i].x);
00720 assert(layers[i].x.size() == p.layers[i].size);
00721 layers[i].size = p.layers[i].size;
00722 layers[i].support = home.alloc<Support>(layers[i].size);
00723 for (ValSize j=layers[i].size; j--; ) {
00724 layers[i].support[j].val = p.layers[i].support[j].val;
00725 layers[i].support[j].n_edges = p.layers[i].support[j].n_edges;
00726 assert(layers[i].support[j].n_edges > 0);
00727 layers[i].support[j].edges =
00728 Heap::copy(edges,p.layers[i].support[j].edges,
00729 layers[i].support[j].n_edges);
00730 edges += layers[i].support[j].n_edges;
00731 }
00732 layers[i].n_states = p.layers[i].n_states;
00733 layers[i].states = NULL;
00734 }
00735 audit();
00736 }
00737
00738 template<class View, class Val, class Degree, class StateIdx>
00739 PropCost
00740 LayeredGraph<View,Val,Degree,StateIdx>::cost(const Space&,
00741 const ModEventDelta&) const {
00742 return PropCost::linear(PropCost::HI,n);
00743 }
00744
00745 template<class View, class Val, class Degree, class StateIdx>
00746 Actor*
00747 LayeredGraph<View,Val,Degree,StateIdx>::copy(Space& home, bool share) {
00748
00749 {
00750 int k=0;
00751 while (layers[k].size == 1) {
00752 assert(layers[k].support[0].n_edges == 1);
00753 n_states -= layers[k].n_states;
00754 k++;
00755 }
00756 if (k > 0) {
00757
00758
00759
00760
00761
00762
00763
00764
00765 n -= k; layers += k;
00766
00767 n_edges -= static_cast<unsigned int>(k);
00768
00769 for (Advisors<Index> as(c); as(); ++as)
00770 as.advisor().i -= k;
00771
00772 a_ch.lshift(k);
00773 }
00774 }
00775 audit();
00776
00777
00778 if (!a_ch.empty()) {
00779 int f = a_ch.fst();
00780 int l = a_ch.lst();
00781 assert((f >= 0) && (l <= n));
00782 Region r(home);
00783
00784 StateIdx* i_map = r.alloc<StateIdx>(max_states);
00785
00786 StateIdx* o_map = r.alloc<StateIdx>(max_states);
00787
00788 StateIdx i_n = 0;
00789
00790 StateIdx o_n = 0;
00791
00792 n_states -= layers[l].n_states;
00793
00794 for (StateIdx j=0; j<layers[l].n_states; j++)
00795 if ((layers[l].states[j].i_deg != 0) ||
00796 (layers[l].states[j].o_deg != 0)) {
00797 layers[l].states[i_n]=layers[l].states[j];
00798 i_map[j]=i_n++;
00799 }
00800 layers[l].n_states = i_n;
00801 n_states += layers[l].n_states;
00802 assert(i_n > 0);
00803
00804
00805 if (l < n)
00806 for (ValSize j=layers[l].size; j--; ) {
00807 Support& s = layers[l].support[j];
00808 for (Degree d=s.n_edges; d--; )
00809 s.edges[d].i_state = i_map[s.edges[d].i_state];
00810 }
00811
00812
00813 for (int i=l-1; i>=f; i--) {
00814
00815 std::swap(o_map,i_map); o_n=i_n; i_n=0;
00816
00817 n_states -= layers[i].n_states;
00818 for (StateIdx j=0; j<layers[i].n_states; j++)
00819 if ((layers[i].states[j].o_deg != 0) ||
00820 (layers[i].states[j].i_deg != 0)) {
00821 layers[i].states[i_n]=layers[i].states[j];
00822 i_map[j]=i_n++;
00823 }
00824 layers[i].n_states = i_n;
00825 n_states += layers[i].n_states;
00826 assert(i_n > 0);
00827
00828
00829 for (ValSize j=layers[i].size; j--; ) {
00830 Support& s = layers[i].support[j];
00831 for (Degree d=s.n_edges; d--; ) {
00832 s.edges[d].i_state = i_map[s.edges[d].i_state];
00833 s.edges[d].o_state = o_map[s.edges[d].o_state];
00834 }
00835 }
00836 }
00837
00838
00839 if (f > 0)
00840 for (ValSize j=layers[f-1].size; j--; ) {
00841 Support& s = layers[f-1].support[j];
00842 for (Degree d=s.n_edges; d--; )
00843 s.edges[d].o_state = i_map[s.edges[d].o_state];
00844 }
00845
00846 a_ch.reset();
00847 }
00848 audit();
00849
00850 return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,share,*this);
00851 }
00852
00854 template<class Var>
00855 forceinline ExecStatus
00856 post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
00857 Gecode::Support::IntType t_state_idx =
00858 Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
00859 Gecode::Support::IntType t_degree =
00860 Gecode::Support::u_type(dfa.max_degree());
00861 Gecode::Support::IntType t_val =
00862 std::max(Support::s_type(dfa.symbol_min()),
00863 Support::s_type(dfa.symbol_max()));
00864 switch (t_val) {
00865 case Gecode::Support::IT_CHAR:
00866 case Gecode::Support::IT_SHRT:
00867 switch (t_state_idx) {
00868 case Gecode::Support::IT_CHAR:
00869 switch (t_degree) {
00870 case Gecode::Support::IT_CHAR:
00871 return Extensional::LayeredGraph
00872 <typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
00873 ::post(home,x,dfa);
00874 case Gecode::Support::IT_SHRT:
00875 return Extensional::LayeredGraph
00876 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
00877 ::post(home,x,dfa);
00878 case Gecode::Support::IT_INT:
00879 return Extensional::LayeredGraph
00880 <typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
00881 ::post(home,x,dfa);
00882 default: GECODE_NEVER;
00883 }
00884 break;
00885 case Gecode::Support::IT_SHRT:
00886 switch (t_degree) {
00887 case Gecode::Support::IT_CHAR:
00888 return Extensional::LayeredGraph
00889 <typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
00890 ::post(home,x,dfa);
00891 case Gecode::Support::IT_SHRT:
00892 return Extensional::LayeredGraph
00893 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
00894 ::post(home,x,dfa);
00895 case Gecode::Support::IT_INT:
00896 return Extensional::LayeredGraph
00897 <typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
00898 ::post(home,x,dfa);
00899 default: GECODE_NEVER;
00900 }
00901 break;
00902 case Gecode::Support::IT_INT:
00903 switch (t_degree) {
00904 case Gecode::Support::IT_CHAR:
00905 return Extensional::LayeredGraph
00906 <typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
00907 ::post(home,x,dfa);
00908 case Gecode::Support::IT_SHRT:
00909 return Extensional::LayeredGraph
00910 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
00911 ::post(home,x,dfa);
00912 case Gecode::Support::IT_INT:
00913 return Extensional::LayeredGraph
00914 <typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
00915 ::post(home,x,dfa);
00916 default: GECODE_NEVER;
00917 }
00918 break;
00919 default: GECODE_NEVER;
00920 }
00921
00922 case Gecode::Support::IT_INT:
00923 switch (t_state_idx) {
00924 case Gecode::Support::IT_CHAR:
00925 switch (t_degree) {
00926 case Gecode::Support::IT_CHAR:
00927 return Extensional::LayeredGraph
00928 <typename VarTraits<Var>::View,int,unsigned char,unsigned char>
00929 ::post(home,x,dfa);
00930 case Gecode::Support::IT_SHRT:
00931 return Extensional::LayeredGraph
00932 <typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
00933 ::post(home,x,dfa);
00934 case Gecode::Support::IT_INT:
00935 return Extensional::LayeredGraph
00936 <typename VarTraits<Var>::View,int,unsigned int,unsigned char>
00937 ::post(home,x,dfa);
00938 default: GECODE_NEVER;
00939 }
00940 break;
00941 case Gecode::Support::IT_SHRT:
00942 switch (t_degree) {
00943 case Gecode::Support::IT_CHAR:
00944 return Extensional::LayeredGraph
00945 <typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
00946 ::post(home,x,dfa);
00947 case Gecode::Support::IT_SHRT:
00948 return Extensional::LayeredGraph
00949 <typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
00950 ::post(home,x,dfa);
00951 case Gecode::Support::IT_INT:
00952 return Extensional::LayeredGraph
00953 <typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
00954 ::post(home,x,dfa);
00955 default: GECODE_NEVER;
00956 }
00957 break;
00958 case Gecode::Support::IT_INT:
00959 switch (t_degree) {
00960 case Gecode::Support::IT_CHAR:
00961 return Extensional::LayeredGraph
00962 <typename VarTraits<Var>::View,int,unsigned char,unsigned int>
00963 ::post(home,x,dfa);
00964 case Gecode::Support::IT_SHRT:
00965 return Extensional::LayeredGraph
00966 <typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
00967 ::post(home,x,dfa);
00968 case Gecode::Support::IT_INT:
00969 return Extensional::LayeredGraph
00970 <typename VarTraits<Var>::View,int,unsigned int,unsigned int>
00971 ::post(home,x,dfa);
00972 default: GECODE_NEVER;
00973 }
00974 break;
00975 default: GECODE_NEVER;
00976 }
00977
00978 default: GECODE_NEVER;
00979 }
00980 return ES_OK;
00981 }
00982
00983 }}}
00984
00985
00986