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.hpp>
00213 #include <gecode/int/distinct/bilink.hpp>
00214 #include <gecode/int/distinct/edge.hpp>
00215 #include <gecode/int/distinct/node.hpp>
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(ViewNodeStack& 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 forceinline void
00276 DomCtrl<View>::ViewValGraph::init(Space& home, ViewNode<View>* x) {
00277 Edge<View>** edge_p = x->val_edges_ref();
00278 ViewValues<View> xi(x->view());
00279 ValNode<View>** v = &val;
00280 while (xi() && (*v != NULL)) {
00281 if ((*v)->val() == xi.val()) {
00282
00283 *edge_p = new (home) Edge<View>(*v,x);
00284 edge_p = (*edge_p)->next_edge_ref();
00285 v = (*v)->next_val_ref();
00286 ++xi;
00287 } else if ((*v)->val() < xi.val()) {
00288
00289 v = (*v)->next_val_ref();
00290 } else {
00291
00292 ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00293 *v = nv; v = nv->next_val_ref();
00294 *edge_p = new (home) Edge<View>(nv,x);
00295 edge_p = (*edge_p)->next_edge_ref();
00296 ++xi; n_val++;
00297 }
00298 }
00299
00300 while (xi()) {
00301 ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00302 *v = nv; v = nv->next_val_ref();
00303 *edge_p = new (home) Edge<View>(nv,x);
00304 edge_p = (*edge_p)->next_edge_ref();
00305 ++xi; n_val++;
00306 }
00307 *edge_p = NULL;
00308 }
00309
00310 template<class View>
00311 ExecStatus
00312 DomCtrl<View>::ViewValGraph::init(Space& home, int n, View* x) {
00313 n_view = n;
00314 view = home.alloc<ViewNode<View>*>(n_view);
00315
00316
00317 int min = x[n_view-1].min();
00318 int max = x[n_view-1].max();
00319 for (int i=n_view-1; i--; ) {
00320 min = std::min(min,x[i].min());
00321 max = std::max(max,x[i].max());
00322 }
00323
00324 unsigned int width = static_cast<unsigned int>(max-min+1);
00325
00326
00327 if (width < static_cast<unsigned int>(n_view))
00328 return ES_FAILED;
00329
00330
00331 for (int i=n; i--; )
00332 view[i] = new (home) ViewNode<View>(x[i]);
00333
00334 n_val = 0;
00335 val = NULL;
00336
00337 Region r(home);
00338
00339 if (static_cast<unsigned int>(n_view)*4 >= width) {
00340
00341 ValNode<View>** val2node = r.alloc<ValNode<View>* >(width);
00342
00343 for (unsigned int i=width; i--; )
00344 val2node[i]=NULL;
00345
00346 for (int i=n; i--; ) {
00347 Edge<View>** edge_p = view[i]->val_edges_ref();
00348 for (ViewValues<View> xi(x[i]); xi(); ++xi) {
00349 if (val2node[xi.val()-min] == NULL)
00350 val2node[xi.val()-min] = new (home) ValNode<View>(xi.val());
00351 *edge_p = new (home) Edge<View>(val2node[xi.val()-min],view[i]);
00352 edge_p = (*edge_p)->next_edge_ref();
00353 }
00354 *edge_p = NULL;
00355 }
00356
00357 for (unsigned int i=width; i--; )
00358 if (val2node[i] != NULL) {
00359 val2node[i]->next_val(val);
00360 val = val2node[i];
00361 n_val++;
00362 }
00363
00364 } else {
00365
00366 for (int i=n; i--; )
00367 init(home,view[i]);
00368 }
00369
00370 ViewNodeStack m(r,n_view);
00371 for (int i = n_view; i--; )
00372 if (!match(m,view[i]))
00373 return ES_FAILED;
00374 return ES_OK;
00375 }
00376
00377 template<class View>
00378 forceinline void
00379 DomCtrl<View>::ViewValGraph::mark(Space& home) {
00380 Region r(home);
00381 {
00382
00383
00384 Support::StaticStack<ValNode<View>*,Region> visit(r,n_val);
00385
00386
00387
00388 count++;
00389 {
00390 ValNode<View>** v = &val;
00391 while (*v != NULL)
00392 if (!(*v)->matching()) {
00393 if ((*v)->empty()) {
00394 *v = (*v)->next_val();
00395 n_val--;
00396 } else {
00397 (*v)->min = count;
00398 visit.push(*v);
00399 v = (*v)->next_val_ref();
00400 }
00401 } else {
00402 v = (*v)->next_val_ref();
00403 }
00404 }
00405
00406
00407 while (!visit.empty()) {
00408 ValNode<View>* n = visit.pop();
00409 for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e=e->next()) {
00410
00411 e->use();
00412 ViewNode<View>* x = e->view(n);
00413 if (x->min < count) {
00414 x->min = count;
00415 assert(x->edge_fst()->next() == x->edge_lst());
00416 ValNode<View>* m = x->edge_fst()->val(x);
00417 x->edge_fst()->use();
00418 if (m->min < count) {
00419 m->min = count;
00420 visit.push(m);
00421 }
00422 }
00423 }
00424 }
00425 }
00426
00427 {
00428 Support::StaticStack<Node<View>*,Region> scc(r,n_val+n_view);
00429 Support::StaticStack<Node<View>*,Region> visit(r,n_val+n_view);
00430
00431 count++;
00432 unsigned int cnt0 = count;
00433 unsigned int cnt1 = count;
00434
00435 for (int i = n_view; i--; )
00436 if (view[i]->min < count) {
00437 Node<View>* w = view[i];
00438 start:
00439 w->low = w->min = cnt0++;
00440 scc.push(w);
00441 Edge<View>* e = w->edge_fst();
00442 while (e != w->edge_lst()) {
00443 if (e->dst(w)->min < count) {
00444 visit.push(w); w->iter = e;
00445 w=e->dst(w);
00446 goto start;
00447 }
00448 next:
00449 if (e->dst(w)->low < w->min)
00450 w->min = e->dst(w)->low;
00451 e = e->next();
00452 }
00453 if (w->min < w->low) {
00454 w->low = w->min;
00455 } else {
00456 Node<View>* v;
00457 do {
00458 v = scc.pop();
00459 v->comp = cnt1;
00460 v->low = UINT_MAX;
00461 } while (v != w);
00462 cnt1++;
00463 }
00464 if (!visit.empty()) {
00465 w=visit.pop(); e=w->iter; goto next;
00466 }
00467 }
00468 count = cnt0+1;
00469 }
00470 }
00471
00473 template<class View>
00474 class PruneVal {
00475 protected:
00477 ViewNode<View>* x;
00479 Edge<View>* e;
00480 public:
00482
00483
00484 PruneVal(ViewNode<View>* y);
00486
00488
00489
00490 bool operator ()(void) const;
00492 void operator ++(void);
00494
00496
00497
00498 int val(void) const;
00500 };
00501
00502 template<class View>
00503 forceinline
00504 PruneVal<View>::PruneVal(ViewNode<View>* y)
00505 : x(y), e(y->val_edges()) {
00506 while ((e != NULL) && e->used(x))
00507 e = e->next_edge();
00508 }
00509 template<class View>
00510 forceinline bool
00511 PruneVal<View>::operator ()(void) const {
00512 return e != NULL;
00513 }
00514 template<class View>
00515 forceinline void
00516 PruneVal<View>::operator ++(void) {
00517 do {
00518 e = e->next_edge();
00519 } while ((e != NULL) && e->used(x));
00520 }
00521 template<class View>
00522 forceinline int
00523 PruneVal<View>::val(void) const {
00524 assert(!e->used(x));
00525 return e->val(x)->val();
00526 }
00527
00528 template<class View>
00529 forceinline ExecStatus
00530 DomCtrl<View>::ViewValGraph::tell(Space& home, bool& assigned) {
00531 assigned = false;
00532
00533 for (int i = n_view; i--; ) {
00534 ViewNode<View>* x = view[i];
00535 if (!x->edge_fst()->used(x)) {
00536 GECODE_ME_CHECK(x->view().eq(home,x->edge_fst()->val(x)->val()));
00537 x->edge_fst()->val(x)->matching(NULL);
00538 for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00539 e->unlink();
00540 view[i] = view[--n_view];
00541 assigned = true;
00542 } else {
00543 PruneVal<View> pv(view[i]);
00544 GECODE_ME_CHECK(view[i]->view().minus_v(home,pv,false));
00545 }
00546 }
00547 return ES_OK;
00548 }
00549
00550 template<class View>
00551 forceinline void
00552 DomCtrl<View>::ViewValGraph::purge(void) {
00553 if (count > (UINT_MAX >> 1)) {
00554 count = 1;
00555 for (int i=n_view; i--; )
00556 view[i]->min = 0;
00557 for (ValNode<View>* v = val; v != NULL; v = v->next_val())
00558 v->min = 0;
00559 }
00560 }
00561
00562 template<class View>
00563 bool
00564 DomCtrl<View>::ViewValGraph::sync(Space& home) {
00565 Region r(home);
00566
00567 ViewNodeStack re(r,n_view);
00568
00569 for (int i = n_view; i--; ) {
00570 ViewNode<View>* x = view[i];
00571 if (x->view().assigned()) {
00572 x->edge_fst()->val(x)->matching(NULL);
00573 for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00574 e->unlink();
00575 view[i] = view[--n_view];
00576 } else {
00577 ViewRanges<View> r(x->view());
00578 Edge<View>* m = x->edge_fst();
00579 Edge<View>** p = x->val_edges_ref();
00580 Edge<View>* e = *p;
00581 do {
00582 while (e->val(x)->val() < r.min()) {
00583
00584 e->unlink(); e->mark();
00585 e = e->next_edge();
00586 }
00587 *p = e;
00588 assert(r.min() == e->val(x)->val());
00589
00590 for (unsigned int j=r.width(); j--; ) {
00591 e->free();
00592 p = e->next_edge_ref();
00593 e = e->next_edge();
00594 }
00595 ++r;
00596 } while (r());
00597 *p = NULL;
00598 while (e != NULL) {
00599 e->unlink(); e->mark();
00600 e = e->next_edge();
00601 }
00602 if (m->marked()) {
00603
00604 m->val(x)->matching(NULL);
00605 re.push(x);
00606 }
00607 }
00608 }
00609 ViewNodeStack m(r,n_view);
00610 while (!re.empty())
00611 if (!match(m,re.pop()))
00612 return false;
00613 return true;
00614 }
00615
00616
00617
00618
00619
00620
00621
00622
00623 template<class View>
00624 forceinline
00625 DomCtrl<View>::DomCtrl(void) {}
00626
00627 template<class View>
00628 forceinline bool
00629 DomCtrl<View>::available(void) {
00630 return vvg.initialized();
00631 }
00632
00633 template<class View>
00634 forceinline ExecStatus
00635 DomCtrl<View>::init(Space& home, int n, View* x) {
00636 return vvg.init(home,n,x);
00637 }
00638
00639 template<class View>
00640 forceinline ExecStatus
00641 DomCtrl<View>::sync(Space& home) {
00642 vvg.purge();
00643 return vvg.sync(home) ? ES_OK : ES_FAILED;
00644 }
00645
00646 template<class View>
00647 forceinline ExecStatus
00648 DomCtrl<View>::propagate(Space& home, bool& assigned) {
00649 vvg.mark(home);
00650 return vvg.tell(home,assigned);
00651 }
00652
00653
00654
00655
00656
00657
00658
00659 template<class View>
00660 forceinline
00661 Dom<View>::Dom(Home home, ViewArray<View>& x)
00662 : NaryPropagator<View,PC_INT_DOM>(home,x) {}
00663
00664 template<class View>
00665 ExecStatus
00666 Dom<View>::post(Home home, ViewArray<View>& x) {
00667 if (x.size() == 2)
00668 return Rel::Nq<View>::post(home,x[0],x[1]);
00669 if (x.size() == 3)
00670 return TerDom<View>::post(home,x[0],x[1],x[2]);
00671 if (x.size() > 3) {
00672
00673 GECODE_ES_CHECK(prop_bnd<View>(home,x));
00674 (void) new (home) Dom<View>(home,x);
00675 }
00676 return ES_OK;
00677 }
00678
00679 template<class View>
00680 forceinline
00681 Dom<View>::Dom(Space& home, bool share, Dom<View>& p)
00682 : NaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00683
00684 template<class View>
00685 PropCost
00686 Dom<View>::cost(const Space&, const ModEventDelta& med) const {
00687 if (View::me(med) == ME_INT_VAL)
00688 return PropCost::linear(PropCost::LO, x.size());
00689 else
00690 return PropCost::quadratic(PropCost::HI, x.size());
00691 }
00692
00693 template<class View>
00694 Actor*
00695 Dom<View>::copy(Space& home, bool share) {
00696 return new (home) Dom<View>(home,share,*this);
00697 }
00698
00699 template<class View>
00700 ExecStatus
00701 Dom<View>::propagate(Space& home, const ModEventDelta& med) {
00702 if (View::me(med) == ME_INT_VAL) {
00703 ExecStatus es = prop_val<View,false>(home,x);
00704 GECODE_ES_CHECK(es);
00705 if (x.size() < 2)
00706 return ES_SUBSUMED(*this,home);
00707 if (es == ES_FIX)
00708 return ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00709 es = prop_bnd<View>(home,x);
00710 GECODE_ES_CHECK(es);
00711 if (x.size() < 2)
00712 return ES_SUBSUMED(*this,home);
00713 es = prop_val<View,true>(home,x);
00714 GECODE_ES_CHECK(es);
00715 if (x.size() < 2)
00716 return ES_SUBSUMED(*this,home);
00717 return ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00718 }
00719
00720 if (x.size() == 2)
00721 GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),x[0],x[1]));
00722 if (x.size() == 3)
00723 GECODE_REWRITE(*this,TerDom<View>::post(home(*this),x[0],x[1],x[2]));
00724
00725 if (dc.available()) {
00726 GECODE_ES_CHECK(dc.sync(home));
00727 } else {
00728 GECODE_ES_CHECK(dc.init(home,x.size(),&x[0]));
00729 }
00730
00731 bool assigned;
00732 GECODE_ES_CHECK(dc.propagate(home,assigned));
00733
00734 return ES_FIX;
00735 }
00736
00737 }}}
00738
00739
00740