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
00040 namespace Gecode { namespace Int { namespace Distinct {
00041
00049 template <class T>
00050 class CombPtrFlag {
00051 private:
00053 ptrdiff_t cpf;
00054 public:
00056 CombPtrFlag(T* p1, T* p2);
00058 void init(T* p1, T* p2);
00060 T* ptr(T* p) const;
00062 int is_set(void) const;
00064 void set(void);
00066 void unset(void);
00067 };
00068
00073 class BiLink {
00074 private:
00075 BiLink* _prev; BiLink* _next;
00076 public:
00077 BiLink(void);
00078
00079 BiLink* prev(void) const; void prev(BiLink*);
00080 BiLink* next(void) const; void next(BiLink*);
00081
00082 void add(BiLink*);
00083 void unlink(void);
00084
00085 void mark(void);
00086 bool marked(void) const;
00087
00088 bool empty(void) const;
00089 };
00090
00091 template <class View> class Edge;
00092
00102 template <class View>
00103 class Node : public BiLink {
00104 public:
00105 unsigned int low, min, comp;
00106 Edge<View>* iter;
00107
00108 Node(void);
00109
00110 Edge<View>* edge_fst(void) const;
00111 Edge<View>* edge_lst(void) const;
00112
00113 static void operator delete(void*, size_t);
00114 static void operator delete(void*,Space*);
00115 static void* operator new(size_t, Space*);
00116 };
00117
00122 template <class View>
00123 class ValNode : public Node<View> {
00124 protected:
00126 const int _val;
00128 Edge<View>* _matching;
00130 ValNode<View>* _next_val;
00131 public:
00133 ValNode(int v);
00135 ValNode(int v, ValNode<View>* n);
00137 int val(void) const;
00139 void matching(Edge<View>* m);
00141 Edge<View>* matching(void) const;
00143 ValNode<View>** next_val_ref(void);
00145 ValNode<View>* next_val(void) const;
00147 void next_val(ValNode<View>* v);
00148 };
00149
00154 template <class View>
00155 class ViewNode : public Node<View> {
00156 protected:
00158 View _view;
00160 Edge<View>* _val_edges;
00161 public:
00163 ViewNode(View x);
00165 Edge<View>* val_edges(void) const;
00167 Edge<View>** val_edges_ref(void);
00169 View view(void) const;
00170 };
00171
00176 template <class View>
00177 class Edge : public BiLink {
00178 protected:
00180 Edge<View>* _next_edge;
00182 CombPtrFlag<Node<View> > sd;
00183 public:
00185 Edge(ValNode<View>* v, ViewNode<View>* x);
00187 Node<View>* dst(Node<View>* s) const;
00188
00190 ViewNode<View>* view(ValNode<View>* v) const;
00192 ValNode<View>* val(ViewNode<View>* x) const;
00193
00194 bool used(Node<View>*) const;
00195 void use(void);
00196 void free(void);
00197
00198 void revert(Node<View>*);
00199
00200 Edge<View>* next_edge(void) const;
00201 Edge<View>** next_edge_ref(void);
00202
00203 Edge<View>* next(void) const;
00204
00205 static void operator delete(void*, size_t);
00206 static void operator delete(void*,Space*);
00207 static void* operator new(size_t, Space*);
00208 };
00209
00210 }}}
00211
00212 #include "gecode/int/distinct/combptr.icc"
00213 #include "gecode/int/distinct/bilink.icc"
00214 #include "gecode/int/distinct/edge.icc"
00215 #include "gecode/int/distinct/node.icc"
00216
00217 namespace Gecode { namespace Int { namespace Distinct {
00218
00219
00220 template <class View>
00221 forceinline
00222 DomCtrl<View>::ViewValGraph::ViewValGraph(void)
00223 : view(NULL), val(NULL), count(1) {}
00224
00225 template <class View>
00226 forceinline bool
00227 DomCtrl<View>::ViewValGraph::initialized(void) const {
00228 return view != NULL;
00229 }
00230
00231 template <class View>
00232 forceinline bool
00233 DomCtrl<View>::ViewValGraph::match(MatchStack& m, ViewNode<View>* x) {
00234 count++;
00235 start:
00236
00237 {
00238 Edge<View>* e = x->val_edges();
00239
00240 assert(e != NULL);
00241 do {
00242 if (!e->val(x)->matching()) {
00243 e->revert(x); e->val(x)->matching(e);
00244
00245 while (!m.empty()) {
00246 x = m.pop(); e = x->iter;
00247 e->val(x)->matching()->revert(e->val(x));
00248 e->revert(x); e->val(x)->matching(e);
00249 }
00250 return true;
00251 }
00252 e = e->next_edge();
00253 } while (e != NULL);
00254 }
00255
00256 Edge<View>* e = x->val_edges();
00257 do {
00258 if (e->val(x)->matching()->view(e->val(x))->min < count) {
00259 e->val(x)->matching()->view(e->val(x))->min = count;
00260 m.push(x); x->iter = e;
00261 x = e->val(x)->matching()->view(e->val(x));
00262 goto start;
00263 }
00264 next:
00265 e = e->next_edge();
00266 } while (e != NULL);
00267 if (!m.empty()) {
00268 x = m.pop(); e = x->iter; goto next;
00269 }
00270
00271 return false;
00272 }
00273
00274 template <class View>
00275 ExecStatus
00276 DomCtrl<View>::ViewValGraph::init(Space* home, int n, View* x) {
00277 n_view = n;
00278 view = static_cast<ViewNode<View>**>
00279 (home->alloc(n_view*sizeof(ViewNode<View>*)));
00280
00281
00282 int min = x[n_view-1].min();
00283 int max = x[n_view-1].max();
00284 for (int i=n_view-1; i--; ) {
00285 min = std::min(min,x[i].min());
00286 max = std::max(max,x[i].max());
00287 }
00288
00289 unsigned int width = max-min+1;
00290
00291
00292 if (width < static_cast<unsigned int>(n_view))
00293 return ES_FAILED;
00294
00295 n_val = 0;
00296 val = NULL;
00297
00298 if (static_cast<unsigned int>(n_view)*4 >= width) {
00299
00300 GECODE_AUTOARRAY(ValNode<View>*,val2node,width);
00301
00302 for (unsigned int i=width; i--; )
00303 val2node[i]=NULL;
00304
00305 for (int i=n; i--; ) {
00306 view[i] = new (home) ViewNode<View>(x[i]);
00307 Edge<View>** edge_p = view[i]->val_edges_ref();
00308 ViewValues<View> xi(x[i]);
00309 while (xi()) {
00310 if (val2node[xi.val()-min] == NULL)
00311 val2node[xi.val()-min] = new (home) ValNode<View>(xi.val());
00312 *edge_p = new (home) Edge<View>(val2node[xi.val()-min],view[i]);
00313 edge_p = (*edge_p)->next_edge_ref();
00314 ++xi;
00315 }
00316 *edge_p = NULL;
00317 }
00318
00319 for (unsigned int i=width; i--; )
00320 if (val2node[i] != NULL) {
00321 val2node[i]->next_val(val);
00322 val = val2node[i];
00323 n_val++;
00324 }
00325
00326 } else {
00327
00328 for (int i=n; i--; ) {
00329 view[i] = new (home) ViewNode<View>(x[i]);
00330 Edge<View>** edge_p = view[i]->val_edges_ref();
00331 ViewValues<View> xi(x[i]);
00332 ValNode<View>** v = &val;
00333 while (xi() && (*v != NULL)) {
00334 if ((*v)->val() == xi.val()) {
00335
00336 *edge_p = new (home) Edge<View>(*v,view[i]);
00337 edge_p = (*edge_p)->next_edge_ref();
00338 v = (*v)->next_val_ref();
00339 ++xi;
00340 } else if ((*v)->val() < xi.val()) {
00341
00342 v = (*v)->next_val_ref();
00343 } else {
00344
00345 ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00346 *v = nv; v = nv->next_val_ref();
00347 *edge_p = new (home) Edge<View>(nv,view[i]);
00348 edge_p = (*edge_p)->next_edge_ref();
00349 ++xi; n_val++;
00350 }
00351 }
00352
00353 while (xi()) {
00354 ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00355 *v = nv; v = nv->next_val_ref();
00356 *edge_p = new (home) Edge<View>(nv,view[i]);
00357 edge_p = (*edge_p)->next_edge_ref();
00358 ++xi; n_val++;
00359 }
00360 *edge_p = NULL;
00361 }
00362 }
00363
00364 GECODE_AUTOSTACK(ViewNode<View>*,NULL,m,n_view);
00365 for (int i = n_view; i--; )
00366 if (!match(m,view[i]))
00367 return ES_FAILED;
00368 return ES_OK;
00369 }
00370
00371 template <class View>
00372 forceinline void
00373 DomCtrl<View>::ViewValGraph::mark(void) {
00374 {
00375
00376
00377 GECODE_AUTOSTACK(ValNode<View>*,NULL,visit,n_val);
00378
00379
00380
00381 count++;
00382 {
00383 ValNode<View>** v = &val;
00384 while (*v != NULL)
00385 if (!(*v)->matching()) {
00386 if ((*v)->empty()) {
00387 *v = (*v)->next_val();
00388 n_val--;
00389 } else {
00390 (*v)->min = count;
00391 visit.push(*v);
00392 v = (*v)->next_val_ref();
00393 }
00394 } else {
00395 v = (*v)->next_val_ref();
00396 }
00397 }
00398
00399
00400 while (!visit.empty()) {
00401 ValNode<View>* n = visit.pop();
00402 for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e=e->next()) {
00403
00404 e->use();
00405 ViewNode<View>* x = e->view(n);
00406 if (x->min < count) {
00407 x->min = count;
00408 assert(x->edge_fst()->next() == x->edge_lst());
00409 ValNode<View>* m = x->edge_fst()->val(x);
00410 x->edge_fst()->use();
00411 if (m->min < count) {
00412 m->min = count;
00413 visit.push(m);
00414 }
00415 }
00416 }
00417 }
00418 }
00419
00420 {
00421 GECODE_AUTOSTACK(Node<View>*,NULL,scc,n_val+n_view);
00422 GECODE_AUTOSTACK(Node<View>*,NULL,visit,n_val+n_view);
00423
00424 count++;
00425 unsigned int cnt0 = count;
00426 unsigned int cnt1 = count;
00427
00428 for (int i = n_view; i--; )
00429 if (view[i]->min < count) {
00430 Node<View>* w = view[i];
00431 start:
00432 w->low = w->min = cnt0++;
00433 scc.push(w);
00434 Edge<View>* e = w->edge_fst();
00435 while (e != w->edge_lst()) {
00436 if (e->dst(w)->min < count) {
00437 visit.push(w); w->iter = e;
00438 w=e->dst(w);
00439 goto start;
00440 }
00441 next:
00442 if (e->dst(w)->low < w->min)
00443 w->min = e->dst(w)->low;
00444 e = e->next();
00445 }
00446 if (w->min < w->low) {
00447 w->low = w->min;
00448 } else {
00449 Node<View>* v;
00450 do {
00451 v = scc.pop();
00452 v->comp = cnt1;
00453 v->low = UINT_MAX;
00454 } while (v != w);
00455 cnt1++;
00456 }
00457 if (!visit.empty()) {
00458 w=visit.pop(); e=w->iter; goto next;
00459 }
00460 }
00461 count = cnt0+1;
00462 }
00463 }
00464
00466 template <class View>
00467 class PruneVal {
00468 protected:
00470 ViewNode<View>* x;
00472 Edge<View>* e;
00473 public:
00475
00476
00477 PruneVal(ViewNode<View>* y);
00479
00481
00482
00483 bool operator()(void) const;
00485 void operator++(void);
00487
00489
00490
00491 int val(void) const;
00493 };
00494
00495 template <class View>
00496 forceinline
00497 PruneVal<View>::PruneVal(ViewNode<View>* y)
00498 : x(y), e(y->val_edges()) {
00499 while ((e != NULL) && e->used(x))
00500 e = e->next_edge();
00501 }
00502 template <class View>
00503 forceinline bool
00504 PruneVal<View>::operator()(void) const {
00505 return e != NULL;
00506 }
00507 template <class View>
00508 forceinline void
00509 PruneVal<View>::operator++(void) {
00510 do {
00511 e = e->next_edge();
00512 } while ((e != NULL) && e->used(x));
00513 }
00514 template <class View>
00515 forceinline int
00516 PruneVal<View>::val(void) const {
00517 assert(!e->used(x));
00518 return e->val(x)->val();
00519 }
00520
00521 template <class View>
00522 forceinline ExecStatus
00523 DomCtrl<View>::ViewValGraph::tell(Space* home, bool& assigned) {
00524 assigned = false;
00525
00526 for (int i = n_view; i--; ) {
00527 ViewNode<View>* x = view[i];
00528 if (!x->edge_fst()->used(x)) {
00529 GECODE_ME_CHECK(x->view().eq(home,x->edge_fst()->val(x)->val()));
00530 x->edge_fst()->val(x)->matching(NULL);
00531 view[i] = view[--n_view];
00532 assigned = true;
00533 } else {
00534 PruneVal<View> pv(view[i]);
00535 GECODE_ME_CHECK(view[i]->view().minus_v(home,pv,false));
00536 }
00537 }
00538 return ES_OK;
00539 }
00540
00541 template <class View>
00542 forceinline void
00543 DomCtrl<View>::ViewValGraph::purge(void) {
00544 if (count > (UINT_MAX >> 1)) {
00545 count = 1;
00546 for (int i=n_view; i--; )
00547 view[i]->min = 0;
00548 for (ValNode<View>* v = val; v != NULL; v = v->next_val())
00549 v->min = 0;
00550 }
00551 }
00552
00553 template <class View>
00554 bool
00555 DomCtrl<View>::ViewValGraph::sync(void) {
00556
00557 GECODE_AUTOSTACK(ViewNode<View>*,NULL,re,n_view);
00558
00559 for (int i = n_view; i--; ) {
00560 ViewNode<View>* x = view[i];
00561 if (x->view().assigned()) {
00562 x->edge_fst()->val(x)->matching(NULL);
00563 for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00564 e->unlink();
00565 view[i] = view[--n_view];
00566 } else {
00567 ViewRanges<View> r(x->view());
00568 Edge<View>* m = x->edge_fst();
00569 Edge<View>** p = x->val_edges_ref();
00570 Edge<View>* e = *p;
00571 do {
00572 while (e->val(x)->val() < r.min()) {
00573
00574 e->unlink(); e->mark();
00575 e = e->next_edge();
00576 }
00577 *p = e;
00578 assert(r.min() == e->val(x)->val());
00579
00580 for (unsigned int i=r.width(); i--; ) {
00581 e->free();
00582 p = e->next_edge_ref();
00583 e = e->next_edge();
00584 }
00585 ++r;
00586 } while (r());
00587 *p = NULL;
00588 while (e != NULL) {
00589 e->unlink(); e->mark();
00590 e = e->next_edge();
00591 }
00592 if (m->marked()) {
00593
00594 m->val(x)->matching(NULL);
00595 re.push(x);
00596 }
00597 }
00598 }
00599 GECODE_AUTOSTACK(ViewNode<View>*,NULL,m,n_view);
00600 while (!re.empty())
00601 if (!match(m,re.pop()))
00602 return false;
00603 return true;
00604 }
00605
00606
00607
00608
00609
00610
00611
00612
00613 template <class View>
00614 forceinline
00615 DomCtrl<View>::DomCtrl(void) {}
00616
00617 template <class View>
00618 forceinline bool
00619 DomCtrl<View>::available(void) {
00620 return vvg.initialized();
00621 }
00622
00623 template <class View>
00624 forceinline ExecStatus
00625 DomCtrl<View>::init(Space* home, int n, View* x) {
00626 return vvg.init(home,n,x);
00627 }
00628
00629 template <class View>
00630 forceinline ExecStatus
00631 DomCtrl<View>::sync(void) {
00632 vvg.purge();
00633 return vvg.sync() ? ES_OK : ES_FAILED;
00634 }
00635
00636 template <class View>
00637 forceinline ExecStatus
00638 DomCtrl<View>::propagate(Space* home, bool& assigned) {
00639 vvg.mark();
00640 return vvg.tell(home,assigned);
00641 }
00642
00643
00644
00645
00646
00647
00648
00649 template <class View>
00650 forceinline
00651 Dom<View>::Dom(Space* home, ViewArray<View>& x)
00652 : NaryPropagator<View,PC_INT_DOM>(home,x) {}
00653
00654 template <class View>
00655 ExecStatus
00656 Dom<View>::post(Space* home, ViewArray<View>& x) {
00657 if (x.size() == 2)
00658 return Rel::Nq<View>::post(home,x[0],x[1]);
00659 if (x.size() == 3)
00660 return TerDom<View>::post(home,x[0],x[1],x[2]);
00661 if (x.size() > 3) {
00662
00663 GECODE_ES_CHECK(prop_bnd<View>(home,x))
00664 (void) new (home) Dom<View>(home,x);
00665 }
00666 return ES_OK;
00667 }
00668
00669 template <class View>
00670 void
00671 Dom<View>::post(Space* home, Reflection::VarMap& vars,
00672 const Reflection::ActorSpec& spec) {
00673 spec.checkArity(1);
00674 ViewArray<View> x(home, vars, spec[0]);
00675 (void) new (home) Dom<View>(home, x);
00676 }
00677
00678 template <class View>
00679 forceinline
00680 Dom<View>::Dom(Space* home, bool share, Dom<View>& p)
00681 : NaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00682
00683 template <class View>
00684 PropCost
00685 Dom<View>::cost(ModEventDelta med) const {
00686 return cost_lo(x.size(),
00687 (View::me(med) == ME_INT_VAL)
00688 ? PC_LINEAR_LO : PC_CUBIC_LO);
00689 }
00690
00691 template <class View>
00692 Support::Symbol
00693 Dom<View>::ati(void) {
00694 return Reflection::mangle<View>("Gecode::Int::Distinct::Dom");
00695 }
00696
00697 template <class View>
00698 Reflection::ActorSpec
00699 Dom<View>::spec(const Space* home, Reflection::VarMap& m) const {
00700 return NaryPropagator<View,PC_INT_DOM>::spec(home, m, ati());
00701 }
00702
00703 template <class View>
00704 Actor*
00705 Dom<View>::copy(Space* home, bool share) {
00706 return new (home) Dom<View>(home,share,*this);
00707 }
00708
00709 template <class View>
00710 ExecStatus
00711 Dom<View>::propagate(Space* home, ModEventDelta med) {
00712 if (View::me(med) == ME_INT_VAL) {
00713 ExecStatus es = prop_val<View,false>(home,x);
00714 GECODE_ES_CHECK(es);
00715 if (x.size() < 2)
00716 return ES_SUBSUMED(this,home);
00717 if (es == ES_FIX)
00718 return ES_FIX_PARTIAL(this,View::med(ME_INT_DOM));
00719 es = prop_bnd<View>(home,x);
00720 if (x.size() < 2)
00721 return ES_SUBSUMED(this,home);
00722 GECODE_ES_CHECK(es);
00723 es = prop_val<View,true>(home,x);
00724 if (x.size() < 2)
00725 return ES_SUBSUMED(this,home);
00726 GECODE_ES_CHECK(es);
00727 return ES_FIX_PARTIAL(this,View::med(ME_INT_DOM));
00728 }
00729
00730 if (x.size() == 2)
00731 GECODE_REWRITE(this,Rel::Nq<View>::post(home,x[0],x[1]));
00732 if (x.size() == 3)
00733 GECODE_REWRITE(this,TerDom<View>::post(home,x[0],x[1],x[2]));
00734
00735 if (dc.available()) {
00736 GECODE_ES_CHECK(dc.sync());
00737 } else {
00738 GECODE_ES_CHECK(dc.init(home,x.size(),&x[0]));
00739 }
00740
00741 bool assigned;
00742 GECODE_ES_CHECK(dc.propagate(home,assigned));
00743
00744 return ES_FIX;
00745 }
00746
00747 }}}
00748
00749
00750