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& s = layers[i].support[j];
00407 n_edges += s.n_edges;
00408 for (Degree d=s.n_edges; d--; ) {
00409 s.edges[d].i_state = i_map[s.edges[d].i_state];
00410 s.edges[d].o_state = o_map[s.edges[d].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 d=s.n_edges; d--; ) {
00457 i_state(i,s.edges[d]).o_deg++;
00458 o_state(i,s.edges[d]).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 d=s.n_edges; d--; ) {
00488
00489 o_mod |= i_dec(i,s.edges[d]);
00490 i_mod |= o_dec(i,s.edges[d]);
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& s = layers[i].support[j];
00499 n_edges -= s.n_edges;
00500 for (Degree d=s.n_edges; d--; ) {
00501
00502 o_mod |= i_dec(i,s.edges[d]);
00503 i_mod |= o_dec(i,s.edges[d]);
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& s = layers[i].support[j];
00512 if (s.val < static_cast<Val>(rx.min())) {
00513
00514 n_edges -= s.n_edges;
00515 for (Degree d=s.n_edges; d--; ) {
00516
00517 o_mod |= i_dec(i,s.edges[d]);
00518 i_mod |= o_dec(i,s.edges[d]);
00519 }
00520 ++j;
00521 } else if (s.val > static_cast<Val>(rx.max())) {
00522 ++rx;
00523 } else {
00524 layers[i].support[k++]=s;
00525 ++j;
00526 }
00527 }
00528 assert(k > 0);
00529 layers[i].size = k;
00530
00531 for (; j<s; j++) {
00532 Support& s=layers[i].support[j];
00533 n_edges -= s.n_edges;
00534 for (Degree d=s.n_edges; d--; ) {
00535
00536 o_mod |= i_dec(i,s.edges[d]);
00537 i_mod |= o_dec(i,s.edges[d]);
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& s=layers[i].support[j];
00551 n_edges -= s.n_edges;
00552 for (Degree d=s.n_edges; d--; ) {
00553
00554 o_mod |= i_dec(i,s.edges[d]);
00555 i_mod |= o_dec(i,s.edges[d]);
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 ExecStatus
00596 LayeredGraph<View,Val,Degree,StateIdx>::propagate(Space& home,
00597 const ModEventDelta&) {
00598
00599 for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
00600 bool i_mod = false;
00601 bool o_mod = false;
00602 ValSize j=0;
00603 ValSize k=0;
00604 ValSize s=layers[i].size;
00605 do {
00606 Support& s=layers[i].support[j];
00607 n_edges -= s.n_edges;
00608 for (Degree d=s.n_edges; d--; )
00609 if (i_state(i,s.edges[d]).i_deg == 0) {
00610
00611 o_mod |= i_dec(i,s.edges[d]);
00612 i_mod |= o_dec(i,s.edges[d]);
00613
00614 s.edges[d] = s.edges[--s.n_edges];
00615 }
00616 n_edges += s.n_edges;
00617
00618 if (s.n_edges == 0) {
00619 layers[i].size--;
00620 GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00621 } else {
00622 layers[i].support[k++]=s;
00623 }
00624 } while (++j<s);
00625 assert(k > 0);
00626
00627 if (o_mod && (i > 0))
00628 o_ch.add(i-1);
00629 if (i_mod && (i+1 < n))
00630 i_ch.add(i+1);
00631 }
00632
00633
00634 for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
00635 bool o_mod = false;
00636 ValSize j=0;
00637 ValSize k=0;
00638 ValSize s=layers[i].size;
00639 do {
00640 Support& s=layers[i].support[j];
00641 n_edges -= s.n_edges;
00642 for (Degree d=s.n_edges; d--; )
00643 if (o_state(i,s.edges[d]).o_deg == 0) {
00644
00645 o_mod |= i_dec(i,s.edges[d]);
00646 (void) o_dec(i,s.edges[d]);
00647
00648 s.edges[d] = s.edges[--s.n_edges];
00649 }
00650 n_edges += s.n_edges;
00651
00652 if (s.n_edges == 0) {
00653 layers[i].size--;
00654 GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
00655 } else {
00656 layers[i].support[k++]=s;
00657 }
00658 } while (++j<s);
00659 assert(k > 0);
00660
00661 if (o_mod && (i > 0))
00662 o_ch.add(i-1);
00663 }
00664
00665 a_ch.add(i_ch); i_ch.reset();
00666 a_ch.add(o_ch); o_ch.reset();
00667
00668 audit();
00669
00670
00671 if (c.empty())
00672 return home.ES_SUBSUMED(*this);
00673 else
00674 return ES_FIX;
00675 }
00676
00677
00678 template<class View, class Val, class Degree, class StateIdx>
00679 template<class Var>
00680 ExecStatus
00681 LayeredGraph<View,Val,Degree,StateIdx>::post(Home home,
00682 const VarArgArray<Var>& x,
00683 const DFA& dfa) {
00684 if (x.size() == 0) {
00685
00686 if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
00687 return ES_OK;
00688 return ES_FAILED;
00689 }
00690 assert(x.size() > 0);
00691 for (int i=x.size(); i--; ) {
00692 DFA::Symbols s(dfa);
00693 typename VarTraits<Var>::View xi(x[i]);
00694 GECODE_ME_CHECK(xi.inter_v(home,s,false));
00695 }
00696 LayeredGraph<View,Val,Degree,StateIdx>* p =
00697 new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
00698 return p->initialize(home,x,dfa);
00699 }
00700
00701 template<class View, class Val, class Degree, class StateIdx>
00702 forceinline
00703 LayeredGraph<View,Val,Degree,StateIdx>
00704 ::LayeredGraph(Space& home, bool share,
00705 LayeredGraph<View,Val,Degree,StateIdx>& p)
00706 : Propagator(home,share,p),
00707 n(p.n), layers(home.alloc<Layer>(n+1)),
00708 max_states(p.max_states), n_states(p.n_states), n_edges(p.n_edges) {
00709 c.update(home,share,p.c);
00710
00711 layers[n].n_states = p.layers[n].n_states;
00712 layers[n].states = NULL;
00713
00714 Edge* edges = home.alloc<Edge>(n_edges);
00715
00716 for (int i=n; i--; ) {
00717 layers[i].x.update(home,share,p.layers[i].x);
00718 assert(layers[i].x.size() == p.layers[i].size);
00719 layers[i].size = p.layers[i].size;
00720 layers[i].support = home.alloc<Support>(layers[i].size);
00721 for (ValSize j=layers[i].size; j--; ) {
00722 layers[i].support[j].val = p.layers[i].support[j].val;
00723 layers[i].support[j].n_edges = p.layers[i].support[j].n_edges;
00724 assert(layers[i].support[j].n_edges > 0);
00725 layers[i].support[j].edges =
00726 Heap::copy(edges,p.layers[i].support[j].edges,
00727 layers[i].support[j].n_edges);
00728 edges += layers[i].support[j].n_edges;
00729 }
00730 layers[i].n_states = p.layers[i].n_states;
00731 layers[i].states = NULL;
00732 }
00733 audit();
00734 }
00735
00736 template<class View, class Val, class Degree, class StateIdx>
00737 PropCost
00738 LayeredGraph<View,Val,Degree,StateIdx>::cost(const Space&,
00739 const ModEventDelta&) const {
00740 return PropCost::linear(PropCost::HI,n);
00741 }
00742
00743 template<class View, class Val, class Degree, class StateIdx>
00744 Actor*
00745 LayeredGraph<View,Val,Degree,StateIdx>::copy(Space& home, bool share) {
00746
00747 {
00748 int k=0;
00749 while (layers[k].size == 1) {
00750 assert(layers[k].support[0].n_edges == 1);
00751 n_states -= layers[k].n_states;
00752 k++;
00753 }
00754 if (k > 0) {
00755
00756
00757
00758
00759
00760
00761
00762
00763 n -= k; layers += k;
00764
00765 n_edges -= static_cast<unsigned int>(k);
00766
00767 for (Advisors<Index> as(c); as(); ++as)
00768 as.advisor().i -= k;
00769
00770 a_ch.lshift(k);
00771 }
00772 }
00773 audit();
00774
00775
00776 if (!a_ch.empty()) {
00777 int f = a_ch.fst();
00778 int l = a_ch.lst();
00779 assert((f >= 0) && (l <= n));
00780 Region r(home);
00781
00782 StateIdx* i_map = r.alloc<StateIdx>(max_states);
00783
00784 StateIdx* o_map = r.alloc<StateIdx>(max_states);
00785
00786 StateIdx i_n = 0;
00787
00788 n_states -= layers[l].n_states;
00789
00790 for (StateIdx j=0; j<layers[l].n_states; j++)
00791 if ((layers[l].states[j].i_deg != 0) ||
00792 (layers[l].states[j].o_deg != 0)) {
00793 layers[l].states[i_n]=layers[l].states[j];
00794 i_map[j]=i_n++;
00795 }
00796 layers[l].n_states = i_n;
00797 n_states += layers[l].n_states;
00798 assert(i_n > 0);
00799
00800
00801 if (l < n)
00802 for (ValSize j=layers[l].size; j--; ) {
00803 Support& s = layers[l].support[j];
00804 for (Degree d=s.n_edges; d--; )
00805 s.edges[d].i_state = i_map[s.edges[d].i_state];
00806 }
00807
00808
00809 for (int i=l-1; i>=f; i--) {
00810
00811 std::swap(o_map,i_map); i_n=0;
00812
00813 n_states -= layers[i].n_states;
00814 for (StateIdx j=0; j<layers[i].n_states; j++)
00815 if ((layers[i].states[j].o_deg != 0) ||
00816 (layers[i].states[j].i_deg != 0)) {
00817 layers[i].states[i_n]=layers[i].states[j];
00818 i_map[j]=i_n++;
00819 }
00820 layers[i].n_states = i_n;
00821 n_states += layers[i].n_states;
00822 assert(i_n > 0);
00823
00824
00825 for (ValSize j=layers[i].size; j--; ) {
00826 Support& s = layers[i].support[j];
00827 for (Degree d=s.n_edges; d--; ) {
00828 s.edges[d].i_state = i_map[s.edges[d].i_state];
00829 s.edges[d].o_state = o_map[s.edges[d].o_state];
00830 }
00831 }
00832 }
00833
00834
00835 if (f > 0)
00836 for (ValSize j=layers[f-1].size; j--; ) {
00837 Support& s = layers[f-1].support[j];
00838 for (Degree d=s.n_edges; d--; )
00839 s.edges[d].o_state = i_map[s.edges[d].o_state];
00840 }
00841
00842 a_ch.reset();
00843 }
00844 audit();
00845
00846 return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,share,*this);
00847 }
00848
00850 template<class Var>
00851 forceinline ExecStatus
00852 post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
00853 Gecode::Support::IntType t_state_idx =
00854 Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
00855 Gecode::Support::IntType t_degree =
00856 Gecode::Support::u_type(dfa.max_degree());
00857 Gecode::Support::IntType t_val =
00858 std::max(Support::s_type(dfa.symbol_min()),
00859 Support::s_type(dfa.symbol_max()));
00860 switch (t_val) {
00861 case Gecode::Support::IT_CHAR:
00862 case Gecode::Support::IT_SHRT:
00863 switch (t_state_idx) {
00864 case Gecode::Support::IT_CHAR:
00865 switch (t_degree) {
00866 case Gecode::Support::IT_CHAR:
00867 return Extensional::LayeredGraph
00868 <typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
00869 ::post(home,x,dfa);
00870 case Gecode::Support::IT_SHRT:
00871 return Extensional::LayeredGraph
00872 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
00873 ::post(home,x,dfa);
00874 case Gecode::Support::IT_INT:
00875 return Extensional::LayeredGraph
00876 <typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
00877 ::post(home,x,dfa);
00878 default: GECODE_NEVER;
00879 }
00880 break;
00881 case Gecode::Support::IT_SHRT:
00882 switch (t_degree) {
00883 case Gecode::Support::IT_CHAR:
00884 return Extensional::LayeredGraph
00885 <typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
00886 ::post(home,x,dfa);
00887 case Gecode::Support::IT_SHRT:
00888 return Extensional::LayeredGraph
00889 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
00890 ::post(home,x,dfa);
00891 case Gecode::Support::IT_INT:
00892 return Extensional::LayeredGraph
00893 <typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
00894 ::post(home,x,dfa);
00895 default: GECODE_NEVER;
00896 }
00897 break;
00898 case Gecode::Support::IT_INT:
00899 switch (t_degree) {
00900 case Gecode::Support::IT_CHAR:
00901 return Extensional::LayeredGraph
00902 <typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
00903 ::post(home,x,dfa);
00904 case Gecode::Support::IT_SHRT:
00905 return Extensional::LayeredGraph
00906 <typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
00907 ::post(home,x,dfa);
00908 case Gecode::Support::IT_INT:
00909 return Extensional::LayeredGraph
00910 <typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
00911 ::post(home,x,dfa);
00912 default: GECODE_NEVER;
00913 }
00914 break;
00915 default: GECODE_NEVER;
00916 }
00917
00918 case Gecode::Support::IT_INT:
00919 switch (t_state_idx) {
00920 case Gecode::Support::IT_CHAR:
00921 switch (t_degree) {
00922 case Gecode::Support::IT_CHAR:
00923 return Extensional::LayeredGraph
00924 <typename VarTraits<Var>::View,int,unsigned char,unsigned char>
00925 ::post(home,x,dfa);
00926 case Gecode::Support::IT_SHRT:
00927 return Extensional::LayeredGraph
00928 <typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
00929 ::post(home,x,dfa);
00930 case Gecode::Support::IT_INT:
00931 return Extensional::LayeredGraph
00932 <typename VarTraits<Var>::View,int,unsigned int,unsigned char>
00933 ::post(home,x,dfa);
00934 default: GECODE_NEVER;
00935 }
00936 break;
00937 case Gecode::Support::IT_SHRT:
00938 switch (t_degree) {
00939 case Gecode::Support::IT_CHAR:
00940 return Extensional::LayeredGraph
00941 <typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
00942 ::post(home,x,dfa);
00943 case Gecode::Support::IT_SHRT:
00944 return Extensional::LayeredGraph
00945 <typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
00946 ::post(home,x,dfa);
00947 case Gecode::Support::IT_INT:
00948 return Extensional::LayeredGraph
00949 <typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
00950 ::post(home,x,dfa);
00951 default: GECODE_NEVER;
00952 }
00953 break;
00954 case Gecode::Support::IT_INT:
00955 switch (t_degree) {
00956 case Gecode::Support::IT_CHAR:
00957 return Extensional::LayeredGraph
00958 <typename VarTraits<Var>::View,int,unsigned char,unsigned int>
00959 ::post(home,x,dfa);
00960 case Gecode::Support::IT_SHRT:
00961 return Extensional::LayeredGraph
00962 <typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
00963 ::post(home,x,dfa);
00964 case Gecode::Support::IT_INT:
00965 return Extensional::LayeredGraph
00966 <typename VarTraits<Var>::View,int,unsigned int,unsigned int>
00967 ::post(home,x,dfa);
00968 default: GECODE_NEVER;
00969 }
00970 break;
00971 default: GECODE_NEVER;
00972 }
00973
00974 default: GECODE_NEVER;
00975 }
00976 return ES_OK;
00977 }
00978
00979 }}}
00980
00981
00982