dom.icc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "iter.hh"
00023
00024 #include "support/static-stack.hh"
00025 #include "support/block-allocator.hh"
00026
00027 namespace Gecode { namespace Int { namespace Regular {
00028
00029 template <class View>
00030 forceinline
00031 Dom<View>::Dom(Space* home, ViewArray<View>& x, DFA& d)
00032 : NaryPropagator<View,PC_INT_DOM>(home,x,true),
00033 dfa(d), lg(NULL) {
00034 }
00035
00036 template <class View>
00037 ExecStatus
00038 Dom<View>::post(Space* home, ViewArray<View>& x, DFA& d) {
00039 (void) new (home) Dom<View>(home,x,d);
00040 return ES_OK;
00041 }
00042
00043 template <class View>
00044 forceinline
00045 Dom<View>::Dom(Space* home, bool share, Dom<View>& p)
00046 : NaryPropagator<View,PC_INT_DOM>(home,share,p), lg(NULL) {
00047 dfa.update(share,p.dfa);
00048 }
00049
00050 template <class View>
00051 Dom<View>::~Dom(void) {
00052 delete lg;
00053 }
00054
00055 template <class View>
00056 void
00057 Dom<View>::flush(void) {
00058 delete lg; lg = NULL;
00059 }
00060
00061 template <class View>
00062 size_t
00063 Dom<View>::size(void) const {
00064 return (lg != NULL) ? lg->size() : 0;
00065 }
00066
00067 template <class View>
00068 PropCost
00069 Dom<View>::cost(void) const {
00070 return cost_hi(this->x.size(), PC_LINEAR_HI);
00071 }
00072
00073 template <class View>
00074 Actor*
00075 Dom<View>::copy(Space* home, bool share) {
00076 return new (home) Dom<View>(home,share,*this);
00077 }
00078
00079
00080
00081
00082
00083
00087 class State {
00088 public:
00089 unsigned int i_deg;
00090 unsigned int o_deg;
00091 };
00092
00093 class Edge;
00094 typedef Support::BlockAllocator<Edge> EdgeAllocator;
00095
00099 class Edge : public Support::BlockClient<Edge> {
00100 public:
00101 int val;
00102 State* i_state;
00103 State* o_state;
00104 Edge* next;
00105 };
00106
00111 const int MOD_NONE = 0;
00112 const int MOD_IDEG = 1;
00113 const int MOD_ODEG = 2;
00114
00115
00119 class Layer {
00120 public:
00121 Edge* edges;
00122 unsigned int size;
00123 int modified;
00124 };
00125
00127 template <class View>
00128 class Dom<View>::LayeredGraph {
00129 private:
00130 unsigned int n_unassigned;
00131 EdgeAllocator ea;
00132 size_t state_size;
00133 State* state_mem;
00134 Layer _layer;
00135 Layer layers[2];
00136 public:
00138 LayeredGraph(ViewArray<View> x, const DFA& d);
00140 ~LayeredGraph(void);
00141
00143 ExecStatus prune_initial(Space* home, ViewArray<View> x);
00145 ExecStatus prune(Space* home, ViewArray<View> x);
00146
00148 size_t size(void) const;
00149 static void* operator new(size_t,int);
00150 static void operator delete(void*);
00151 static void operator delete(void*,int);
00152 };
00153
00154
00155
00160 class EdgeRanges {
00161 private:
00162 const Edge* e1; const Edge* e2;
00163 public:
00164 EdgeRanges(void);
00165 EdgeRanges(const Edge*);
00166 void init(const Edge*);
00167 bool operator()(void) const;
00168 void operator++(void);
00169 int min(void) const;
00170 int max(void) const;
00171 unsigned int width(void) const;
00172 };
00173
00174 forceinline
00175 EdgeRanges::EdgeRanges(void) {}
00176 forceinline
00177 EdgeRanges::EdgeRanges(const Edge* e)
00178 : e1(e), e2(e) {
00179 assert(e1);
00180
00181 while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
00182 e2 = e2->next;
00183 }
00184 forceinline void
00185 EdgeRanges::init(const Edge* e) {
00186 e1=e; e2=e;
00187 assert(e1);
00188
00189 while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
00190 e2 = e2->next;
00191 }
00192
00193 forceinline bool
00194 EdgeRanges::operator()(void) const {
00195 return e1 != NULL;
00196 }
00197
00198 forceinline void
00199 EdgeRanges::operator++(void) {
00200 e1 = e2->next;
00201 if (e1 != NULL) {
00202 e2 = e1;
00203 while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
00204 e2 = e2->next;
00205 }
00206 }
00207
00208 forceinline int
00209 EdgeRanges::min(void) const {
00210 return e1->val;
00211 }
00212 forceinline int
00213 EdgeRanges::max(void) const {
00214 return e2->val;
00215 }
00216 forceinline unsigned int
00217 EdgeRanges::width(void) const {
00218 return max()-min()+1;
00219 }
00220
00221
00222
00223
00224
00225
00226
00227
00228 template <class View>
00229 forceinline
00230 Dom<View>::LayeredGraph::LayeredGraph(ViewArray<View> x, const DFA& dfa)
00231 : n_unassigned(x.size()) {
00232 int n = x.size();
00233 unsigned int n_states = dfa.n_states();
00234
00235
00236 state_size = sizeof(State)*(n+1)*n_states;
00237 state_mem = reinterpret_cast<State*>(Memory::malloc(state_size));
00238
00239
00240
00241 for (int i = (n+1)*n_states; i--; ) {
00242 state_mem[i].i_deg = 0;
00243 state_mem[i].o_deg = 0;
00244 }
00245
00246
00247 state_mem[0].i_deg = 1;
00248
00249
00250 for (int s = dfa.final_fst(); s < dfa.final_lst(); s++)
00251 state_mem[n*n_states + s].o_deg = 1;
00252
00253
00254 for (int i = 0; i < n; i++) {
00255 Edge** p = &layers[i].edges;
00256
00257 DFA::Transitions t_a(dfa);
00258 ViewRanges<View> rx(x[i]);
00259 while (rx() && t_a()) {
00260 const DFA::Transition* t = t_a.transition();
00261
00262 State* i_state = state_mem + (i )*n_states + t->i_state;
00263 State* o_state = state_mem + (i+1)*n_states + t->o_state;
00264 if (t->symbol > rx.max()) {
00265 ++rx;
00266 } else if ((t->symbol >= rx.min()) && (i_state->i_deg > 0)) {
00267
00268 i_state->o_deg++; o_state->i_deg++;
00269 Edge* e = new (ea) Edge;
00270 e->i_state = i_state;
00271 e->val = t->symbol;
00272 e->o_state = o_state;
00273 *p = e;
00274 p = &e->next;
00275 ++t_a;
00276 } else {
00277 ++t_a;
00278 }
00279 }
00280
00281 *p = NULL;
00282 }
00283 }
00284
00285 template <class View>
00286 forceinline ExecStatus
00287 Dom<View>::LayeredGraph::prune_initial(Space* home, ViewArray<View> x) {
00288
00289 for (int i = x.size(); i--; ) {
00290 Edge** p = &layers[i].edges;
00291 Edge* e = *p;
00292 while (e != NULL) {
00293 if (e->o_state->o_deg != 0) {
00294
00295 p = &e->next;
00296 } else {
00297
00298 *p = e->next;
00299 e->i_state->o_deg--; e->o_state->i_deg--;
00300 }
00301 e = e->next;
00302 }
00303 *p = NULL;
00304 }
00305
00306
00307 ExecStatus es = ES_FIX;
00308 for (int i=x.size(); i--; ) {
00309 if (layers[i].edges == NULL)
00310 return ES_FAILED;
00311 if (x[i].modified())
00312 es = ES_NOFIX;
00313 EdgeRanges er(layers[i].edges);
00314 if (x[i].modified()) {
00315 GECODE_ME_CHECK(x[i].inter(home,er));
00316 } else {
00317 x[i].narrow(home,er);
00318 }
00319
00320 layers[i].modified = MOD_NONE;
00321 layers[i].size = x[i].size();
00322 if (layers[i].size == 1)
00323 n_unassigned--;
00324 }
00325 return (n_unassigned == 0) ? ES_SUBSUMED : es;
00326 }
00327
00328 template <class View>
00329 forceinline ExecStatus
00330 Dom<View>::LayeredGraph::prune(Space* home, ViewArray<View> x) {
00331 int n = x.size();
00332
00333 for (int i = 0; i < n; i++)
00334 if (layers[i].size != x[i].size()) {
00335 layers[i].size = x[i].size();
00336 if (layers[i].size == 1)
00337 n_unassigned--;
00338 Edge** p = &layers[i].edges;
00339 Edge* e = *p;
00340 ViewRanges<View> rx(x[i]);
00341 while (rx() && (e != NULL)) {
00342 if (e->val > rx.max()) {
00343 ++rx;
00344 } else if ((e->val < rx.min()) || (e->i_state->i_deg == 0)) {
00345
00346 if ((--e->i_state->o_deg) == 0)
00347 layers[i-1].modified |= MOD_ODEG;
00348 if ((--e->o_state->i_deg) == 0)
00349 layers[i+1].modified |= MOD_IDEG;
00350
00351 *p = e->next; e = e->next;
00352 } else {
00353
00354 p = &e->next; e = e->next;
00355 }
00356 }
00357 *p = NULL;
00358
00359 while (e != NULL) {
00360
00361 if (--e->i_state->o_deg == 0)
00362 layers[i-1].modified |= MOD_ODEG;
00363 if (--e->o_state->i_deg == 0)
00364 layers[i+1].modified |= MOD_IDEG;
00365 e = e->next;
00366 }
00367
00368 } else if (layers[i].modified & MOD_IDEG) {
00369 assert(layers[i].size == x[i].size());
00370 Edge** p = &layers[i].edges;
00371 Edge* e = *p;
00372 while (e != NULL) {
00373 if (e->i_state->i_deg == 0) {
00374
00375 if (--e->i_state->o_deg == 0)
00376 layers[i-1].modified |= MOD_ODEG;
00377 if (--e->o_state->i_deg == 0)
00378 layers[i+1].modified |= MOD_IDEG;
00379
00380 *p = e->next;
00381 } else {
00382
00383 p = &e->next;
00384 }
00385 e = e->next;
00386 }
00387
00388 *p = NULL;
00389 }
00390
00391 for (int i=n; i--; )
00392 if (layers[i].modified & MOD_ODEG) {
00393 Edge** p = &layers[i].edges;
00394 Edge* e = *p;
00395 while (e != NULL) {
00396 if (e->o_state->o_deg != 0) {
00397
00398 p = &e->next;
00399 } else {
00400
00401 if (--e->i_state->o_deg == 0)
00402 layers[i-1].modified |= MOD_ODEG;
00403 --e->o_state->i_deg;
00404 *p = e->next;
00405 }
00406 e = e->next;
00407 }
00408 *p = NULL;
00409 }
00410
00411 ExecStatus es = ES_FIX;
00412 for (int i=n; i--; )
00413 if (layers[i].modified) {
00414 layers[i].modified = MOD_NONE;
00415 if (layers[i].edges == NULL)
00416 return ES_FAILED;
00417 if (x[i].modified())
00418 es = ES_NOFIX;
00419 EdgeRanges er(layers[i].edges);
00420 if (x[i].modified()) {
00421 GECODE_ME_CHECK(x[i].inter(home,er));
00422 } else {
00423 x[i].narrow(home,er);
00424 }
00425 if (layers[i].size != x[i].size()) {
00426 layers[i].size = x[i].size();
00427 if (layers[i].size == 1)
00428 n_unassigned--;
00429 }
00430 }
00431 return (n_unassigned == 0) ? ES_SUBSUMED : es;
00432 }
00433
00434 template <class View>
00435 forceinline
00436 Dom<View>::LayeredGraph::~LayeredGraph(void) {
00437 Memory::free(state_mem);
00438 }
00439
00440 template <class View>
00441 forceinline size_t
00442 Dom<View>::LayeredGraph::size(void) const {
00443 return state_size + ea.size();
00444 }
00445
00446 template <class View>
00447 forceinline void
00448 Dom<View>::LayeredGraph::operator delete(void* p) {
00449 Memory::free(p);
00450 }
00451
00452 template <class View>
00453 forceinline void
00454 Dom<View>::LayeredGraph::operator delete(void* p, int) {
00455 Memory::free(p);
00456 }
00457
00458 template <class View>
00459 forceinline void*
00460 Dom<View>::LayeredGraph::operator new(size_t s, int n) {
00461
00462 return Memory::malloc(sizeof(LayeredGraph) + n*sizeof(Layer));
00463 }
00464
00465 template <class View>
00466 ExecStatus
00467 Dom<View>::propagate(Space* home) {
00468 if (lg == NULL) {
00469 lg = new (this->x.size()) LayeredGraph(this->x,dfa);
00470 return lg->prune_initial(home,this->x);
00471 } else {
00472 return lg->prune(home,this->x);
00473 }
00474 }
00475
00476 }}}
00477
00478
00479