00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include <climits>
00023
00024 #include "support/dynamic-array.hh"
00025 #include "support/static-stack.hh"
00026
00027 #include "iter.hh"
00028
00029 namespace Gecode { namespace Int { namespace Distinct {
00030
00038 template <class T>
00039 class CombPtrFlag {
00040 private:
00042 ptrdiff_t cpf;
00043 public:
00045 CombPtrFlag(T* p1, T* p2);
00047 void init(T* p1, T* p2);
00049 T* ptr(T* p) const;
00051 int is_set(void) const;
00053 void set(void);
00055 void unset(void);
00056 };
00057
00062 class BiLink {
00063 private:
00064 BiLink* _prev; BiLink* _next;
00065 public:
00066 BiLink(void);
00067
00068 BiLink* prev(void) const; void prev(BiLink*);
00069 BiLink* next(void) const; void next(BiLink*);
00070
00071 void add(BiLink*);
00072 void unlink(void);
00073
00074 void mark(void);
00075 bool marked(void) const;
00076
00077 bool empty(void) const;
00078 };
00079
00080 template <class View> class Edge;
00081
00091 template <class View>
00092 class Node : public BiLink {
00093 public:
00094 unsigned int pre, low, comp;
00095
00096 Node(void);
00097
00098 Edge<View>* edge_fst(void) const;
00099 Edge<View>* edge_lst(void) const;
00100
00101 static void* operator new(size_t, void*);
00102 };
00103
00108 template <class View>
00109 class ValNode : public Node<View> {
00110 protected:
00111 const int _val; Edge<View>* _matching;
00112 public:
00113 ValNode(int);
00114 int val(void) const;
00115 void matching(Edge<View>*);
00116 Edge<View>* matching(void) const;
00117 };
00118
00123 template <class View>
00124 class ViewNode : public Node<View> {
00125 protected:
00126 Edge<View>* _val_edges; View _view;
00127 public:
00128 ViewNode(View);
00129 Edge<View>* val_edges(void) const;
00130 Edge<View>** val_edges_ref(void);
00131
00132 View view(void) const;
00133 };
00134
00139 template <class View>
00140 class Edge : public BiLink {
00141 protected:
00142 Edge<View>* _next_edge;
00143 CombPtrFlag<Node<View> > sd;
00144 public:
00145 Edge(Node<View>*, Node<View>*);
00146
00147 Node<View>* dst(Node<View>*) const;
00148
00149 ViewNode<View>* view(ValNode<View>*) const;
00150 ValNode<View>* val(ViewNode<View>*) const;
00151
00152 bool used(Node<View>*) const;
00153 void use(void);
00154 void free(void);
00155
00156 void revert(Node<View>*);
00157
00158 Edge<View>* next_edge(void) const;
00159 Edge<View>** next_edge_ref(void);
00160
00161 Edge<View>* next(void) const;
00162 static void* operator new(size_t, void*);
00163 };
00164
00165 }}}
00166
00167 #include "int/distinct/combptr.icc"
00168 #include "int/distinct/bilink.icc"
00169 #include "int/distinct/node.icc"
00170 #include "int/distinct/edge.icc"
00171
00172 namespace Gecode { namespace Int { namespace Distinct {
00173
00178 template <class View>
00179 class Dom<View>::ViewValGraph {
00180 protected:
00181 ViewNode<View>** view; int n_view;
00182 ValNode<View>** val; int n_val;
00183 char* mem;
00184 unsigned int count;
00185 unsigned int cnt0;
00186 unsigned int cnt1;
00187 Support::StaticStack<Node<View>*> n_s;
00188 public:
00189 ViewValGraph(ViewArray<View>&, const int*, int, unsigned int);
00190 ~ViewValGraph(void);
00191
00192 size_t size;
00193
00194 bool initial_match(void);
00195
00196 void mark(void);
00197 bool tell(Space*);
00198
00199 bool overflow(void) const;
00200
00201 bool sync(void);
00202
00203 protected:
00204 bool search_match(ViewNode<View>*);
00205 bool match(ViewNode<View>*);
00206 void scc(Node<View>*);
00207
00208 public:
00209
00210 static void* operator new(size_t);
00211 static void operator delete(void*);
00212 };
00213
00214
00215 template <class View>
00216 Dom<View>::ViewValGraph::ViewValGraph(ViewArray<View>& x, const int* val_inf,
00217 int n_val0, unsigned int n_edges)
00218 : n_view(x.size()), n_val(n_val0),
00219 count(0), cnt0(0), cnt1(0), n_s(n_view+n_val)
00220 {
00221 size_t edge_size = sizeof(Edge<View>) * n_edges;
00222 size_t views_size = sizeof(ViewNode<View>) * n_view;
00223 size_t view_size = sizeof(ViewNode<View>*) * n_view;
00224 size_t vals_size = sizeof(ValNode<View>) * n_val;
00225 size_t val_size = sizeof(ValNode<View>*) * n_val;
00226 size_t size = edge_size +
00227 views_size + view_size + vals_size + val_size;
00228 mem = reinterpret_cast<char*>(Memory::malloc(size));
00229 Edge<View>* edges = reinterpret_cast<Edge<View>*>(mem);
00230 ViewNode<View>* view_nodes = reinterpret_cast<ViewNode<View>*>
00231 (mem+edge_size);
00232 ValNode<View>* val_nodes = reinterpret_cast<ValNode<View>*>
00233 (mem+edge_size+views_size);
00234 view = reinterpret_cast<ViewNode<View>**>
00235 (mem+edge_size+views_size+vals_size);
00236 val = reinterpret_cast<ValNode<View>**>
00237 (mem+edge_size+views_size+vals_size+view_size);
00238
00239
00240 for (int i = n_val; i--; )
00241 val[i] = new (val_nodes + i) ValNode<View>(val_inf[i]);
00242
00243
00244 for (int i = n_view; i--; ) {
00245 view[i] = new (view_nodes + i) ViewNode<View>(x[i]);
00246 Edge<View>** edge_p = view[i]->val_edges_ref();
00247 ViewValues<View> x_i(x[i]);
00248 int j = 0;
00249 while (x_i()) {
00250 while (val_inf[j] < x_i.val())
00251 j++;
00252 *edge_p = new (edges++) Edge<View>(val_nodes+j,view_nodes+i);
00253 edge_p = (*edge_p)->next_edge_ref();
00254 ++x_i;
00255 }
00256 *edge_p = NULL;
00257 }
00258 }
00259
00260 template <class View>
00261 bool
00262 Dom<View>::ViewValGraph::search_match(ViewNode<View>* x) {
00263 for (Edge<View>* e = x->val_edges(); e; e = e->next_edge())
00264 if (!e->val(x)->matching()) {
00265 e->revert(x); e->val(x)->matching(e);
00266 return true;
00267 }
00268 x->comp = count;
00269 for (Edge<View>* e = x->val_edges(); e; e = e->next_edge()) {
00270 ValNode<View>* n = e->val(x);
00271 ViewNode<View>* y = n->matching()->view(n);
00272 if ((y->comp < count) && search_match(y)) {
00273 n->matching()->revert(n);
00274 e->revert(x); n->matching(e);
00275 return true;
00276 }
00277 }
00278 return false;
00279 }
00280
00281 template <class View>
00282 forceinline bool
00283 Dom<View>::ViewValGraph::match(ViewNode<View>* x) {
00284 assert(x->edge_fst() == x->edge_lst());
00285 count++;
00286 return search_match(x);
00287 }
00288
00289 template <class View>
00290 bool
00291 Dom<View>::ViewValGraph::initial_match(void) {
00292 for (int i = n_view; i--; )
00293 if (!match(view[i]))
00294 return false;
00295 return true;
00296 }
00297
00298 template <class View>
00299 void
00300 Dom<View>::ViewValGraph::scc(Node<View>* w) {
00301 w->pre = cnt0;
00302 w->low = cnt0;
00303 unsigned int min = cnt0++;
00304 n_s.push(w);
00305 for (Edge<View>* e = w->edge_fst(); e != w->edge_lst(); e = e->next()) {
00306 Node<View>* v = e->dst(w);
00307 if (v->pre < count)
00308 scc(v);
00309 if (v->low < min)
00310 min = v->low;
00311 }
00312 if (min < w->low) {
00313 w->low = min;
00314 return;
00315 }
00316 do {
00317 Node<View>* v = n_s.pop();
00318 v->comp = cnt1;
00319 v->low = UINT_MAX;
00320 } while (n_s.last() != w);
00321 cnt1++;
00322 }
00323
00324 template <class View>
00325 forceinline void
00326 Dom<View>::ViewValGraph::mark(void) {
00327
00328
00329 n_s.reset();
00330
00331
00332 count++;
00333 for (int i = n_val; i--; )
00334 if (!val[i]->matching())
00335
00336 if (val[i]->empty()) {
00337 val[i] = val[--n_val];
00338 } else {
00339 val[i]->comp = count;
00340 n_s.push(val[i]);
00341 }
00342
00343
00344 while (!n_s.empty()) {
00345 ValNode<View>* n = static_cast<ValNode<View>*>(n_s.pop());
00346 for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e = e->next()) {
00347
00348 e->use();
00349 ViewNode<View>* x = e->view(n);
00350 if (x->comp < count) {
00351 x->comp = count;
00352 assert(x->edge_fst()->next() == x->edge_lst());
00353 ValNode<View>* m = x->edge_fst()->val(x);
00354 x->edge_fst()->use();
00355 if (m->comp < count) {
00356 m->comp = count;
00357 n_s.push(m);
00358 }
00359 }
00360 }
00361 }
00362
00363 count++;
00364 cnt0 = count;
00365 cnt1 = count;
00366 n_s.reset();
00367 for (int i = n_view; i--; )
00368 if (view[i]->comp < count)
00369 scc(view[i]);
00370 count = cnt0+1;
00371 }
00372
00373 template <class View>
00374 forceinline bool
00375 Dom<View>::ViewValGraph::tell(Space* home) {
00376 bool shared = false;
00377
00378 for (int i = n_view; i--; )
00379 if (!view[i]->edge_fst()->used(view[i])) {
00380 shared |= view[i]->view().modified();
00381 view[i]->view().eq(home,view[i]->edge_fst()->val(view[i])->val());
00382 view[i]->edge_fst()->val(view[i])->matching(NULL);
00383 view[i] = view[--n_view];
00384 } else {
00385 for (Edge<View>* e = view[i]->val_edges(); e; e = e->next_edge())
00386 if (!e->used(view[i])) {
00387 shared |= view[i]->view().modified();
00388 view[i]->view().nq(home,e->val(view[i])->val());
00389 }
00390 }
00391 return shared;
00392 }
00393
00394 template <class View>
00395 forceinline bool
00396 Dom<View>::ViewValGraph::overflow(void) const {
00397 return count > (UINT_MAX >> 1);
00398 }
00399
00400 template <class View>
00401 bool
00402 Dom<View>::ViewValGraph::sync(void) {
00403
00404 GECODE_AUTOARRAY(ViewNode<View>*,re,n_view);
00405 int n_re = 0;
00406
00407 for (int i = n_view; i--; ) {
00408 ViewNode<View>* x = view[i];
00409 if (x->view().assigned()) {
00410 x->edge_fst()->val(x)->matching(NULL);
00411 for (Edge<View>* e = x->val_edges(); e; e = e->next_edge())
00412 e->unlink();
00413 view[i] = view[--n_view];
00414 } else {
00415 ViewValues<View> n(x->view());
00416 Edge<View>* m = x->edge_fst();
00417 Edge<View>** p = x->val_edges_ref();
00418 Edge<View>* e = *p;
00419 do {
00420 while (e->val(x)->val() < n.val()) {
00421
00422 e->unlink(); e->mark();
00423 e = e->next_edge();
00424 *p = e;
00425 }
00426 assert(n.val() == e->val(x)->val());
00427
00428 e->free();
00429 ++n;
00430 p = e->next_edge_ref();
00431 e = e->next_edge();
00432 } while (n());
00433 *p = NULL;
00434 while (e) {
00435 e->unlink(); e->mark();
00436 e = e->next_edge();
00437 }
00438 if (m->marked()) {
00439
00440 m->val(x)->matching(NULL);
00441 re[n_re++] = x;
00442 }
00443 }
00444 }
00445 while (n_re--)
00446 if (!match(re[n_re]))
00447 return false;
00448 return true;
00449 }
00450
00451 template <class View>
00452 Dom<View>::ViewValGraph::~ViewValGraph(void) {
00453 Memory::free(mem);
00454 }
00455
00456 template <class View>
00457 forceinline void*
00458 Dom<View>::ViewValGraph::operator new(size_t s) {
00459 return Memory::malloc(s);
00460 }
00461 template <class View>
00462 forceinline void
00463 Dom<View>::ViewValGraph::operator delete(void* p) {
00464 Memory::free(p);
00465 }
00466
00467
00468
00469
00470
00471
00472
00473
00474 template <class View>
00475 forceinline
00476 Dom<View>::Dom(Space* home, ViewArray<View>& x)
00477 : NaryPropagator<View,PC_INT_DOM>(home,x,true),
00478 vvg(NULL) {}
00479
00480 template <class View>
00481 ExecStatus
00482 Dom<View>::post(Space* home, ViewArray<View>& x) {
00483 if (x.size() == 2)
00484 return Rel::Nq<View>::post(home,x[0],x[1]);
00485 if (x.size() > 2) {
00486 if (x.same())
00487 return ES_FAILED;
00488
00489 if (prop_bnd<View,false>(home,x) == ES_FAILED)
00490 return ES_FAILED;
00491 (void) new (home) Dom<View>(home,x);
00492 }
00493 return ES_OK;
00494 }
00495
00496 template <class View>
00497 forceinline
00498 Dom<View>::Dom(Space* home, bool share, Dom<View>& p)
00499 : NaryPropagator<View,PC_INT_DOM>(home,share,p), vvg(NULL) {}
00500
00501 template <class View>
00502 Dom<View>::~Dom(void) {
00503 delete vvg;
00504 }
00505
00506 template <class View>
00507 void
00508 Dom<View>::flush(void) {
00509 delete vvg; vvg = NULL;
00510 }
00511
00512 template <class View>
00513 size_t
00514 Dom<View>::size(void) const {
00515 return (vvg != NULL) ? vvg->size : 0;
00516 }
00517
00518 template <class View>
00519 PropCost
00520 Dom<View>::cost(void) const {
00521 return cost_lo(x.size(),
00522 (View::pme(this) == ME_INT_VAL)
00523 ? PC_LINEAR_LO : PC_CUBIC_LO);
00524 }
00525
00526 template <class View>
00527 Actor*
00528 Dom<View>::copy(Space* home, bool share) {
00529 return new (home) Dom<View>(home,share,*this);
00530 }
00531
00532 template <class View>
00533 ExecStatus
00534 Dom<View>::propagate(Space* home) {
00535 if (View::pme(this) == ME_INT_VAL) {
00536 ExecStatus es = prop_val<View,false>(home,x);
00537 if ((es == ES_FAILED) || (es == ES_SUBSUMED))
00538 return es;
00539 if (es == ES_FIX)
00540 return this->ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00541 if (prop_bnd<View,false>(home,x) == ES_FAILED)
00542 return ES_FAILED;
00543 es = prop_val<View,true>(home,x);
00544 if ((es == ES_FAILED) || (es == ES_SUBSUMED))
00545 return es;
00546 return this->ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00547 }
00548
00549 if (x.size() == 2) {
00550 GECODE_ES_CHECK(Rel::Nq<View>::post(home,x[0],x[1]));
00551 return ES_SUBSUMED;
00552 }
00553
00554 if ((vvg != NULL) && vvg->overflow()) {
00555 delete vvg;
00556 vvg = NULL;
00557 }
00558
00559 if (vvg == NULL) {
00560
00561 Support::DynamicArray<int> val_inf(64);
00562 int n_val = 0;
00563 unsigned int size = 0;
00564
00565 {
00566 GECODE_AUTOARRAY(ViewRanges<View>,x_r,x.size());
00567 for (int i = x.size(); i--; ) {
00568 ViewRanges<View> r(x[i]); x_r[i] = r;
00569 size += x[i].size();
00570 }
00571 Iter::Ranges::NaryUnion<ViewRanges<View> > xu(x_r, x.size());
00572 while (xu()) {
00573 for (int v = xu.min(); v <= xu.max(); v++)
00574 val_inf[n_val++] = v;
00575 ++xu;
00576 }
00577 }
00578
00579 if (n_val < x.size())
00580 return ES_FAILED;
00581
00582 vvg = new ViewValGraph(x,val_inf,n_val,size);
00583 if (!vvg->initial_match())
00584 return ES_FAILED;
00585 } else {
00586 if (!vvg->sync())
00587 return ES_FAILED;
00588 }
00589
00590 vvg->mark();
00591 return vvg->tell(home) ? ES_NOFIX : ES_FIX;
00592
00593 }
00594
00595 }}}
00596
00597
00598