00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "int.hh"
00023
00024 #include "limits.hh"
00025
00026 namespace Gecode { namespace Int {
00027
00028 forceinline bool
00029 IntVarImp::closer_min(int n) const {
00030 unsigned int l = n - dom.min();
00031 unsigned int r = dom.max() - n;
00032 return l < r;
00033 }
00034
00035 int
00036 IntVarImp::med(void) const {
00037
00038 if (fst() == NULL)
00039 return (dom.min()+dom.max())/2;
00040 unsigned int i = size() / 2;
00041 const RangeList* p = NULL;
00042 const RangeList* c = fst();
00043 while (i >= c->width()) {
00044 i -= c->width();
00045 const RangeList* n=c->next(p); p=c; c=n;
00046 }
00047 return c->min() + static_cast<int>(i);
00048 }
00049
00050 bool
00051 IntVarImp::in_full(int m) const {
00052 if (closer_min(m)) {
00053 const RangeList* p = NULL;
00054 const RangeList* c = fst();
00055 while (m > c->max()) {
00056 const RangeList* n=c->next(p); p=c; c=n;
00057 }
00058 return (m >= c->min());
00059 } else {
00060 const RangeList* n = NULL;
00061 const RangeList* c = lst();
00062 while (m < c->min()) {
00063 const RangeList* p=c->prev(n); n=c; c=p;
00064 }
00065 return (m <= c->max());
00066 }
00067 }
00068
00069
00070
00071
00072
00073
00074 void
00075 IntVarImp::lq_full(Space* home, int m) {
00076 assert((m >= dom.min()) && (m <= dom.max()));
00077 if (range()) {
00078 dom.max(m);
00079 if (assigned()) goto notify_val;
00080 } else if (m < fst()->next(NULL)->min()) {
00081 dom.max(std::min(m,fst()->max()));
00082 fst()->dispose(home,NULL,lst());
00083 fst(NULL); holes = 0;
00084 if (assigned()) goto notify_val;
00085 } else {
00086 RangeList* n = NULL;
00087 RangeList* c = lst();
00088 unsigned int h = 0;
00089 while (m < c->min()) {
00090 RangeList* p = c->prev(n); c->fix(n);
00091 h += (c->min() - p->max() - 1);
00092 n=c; c=p;
00093 }
00094 holes -= h;
00095 int max_c = std::min(m,c->max());
00096 dom.max(max_c); c->max(max_c);
00097 if (c != lst()) {
00098 lst()->dispose(home,n);
00099 c->next(n,NULL); lst(c);
00100 }
00101 }
00102 notify(home,ME_INT_BND);
00103 return;
00104 notify_val:
00105 notify(home,ME_INT_VAL);
00106 }
00107
00108 void
00109 IntVarImp::gq_full(Space* home, int m) {
00110 assert((m >= dom.min()) && (m <= dom.max()));
00111 if (range()) {
00112 dom.min(m);
00113 if (assigned()) goto notify_val;
00114 } else if (m > lst()->prev(NULL)->max()) {
00115 dom.min(std::max(m,lst()->min()));
00116 fst()->dispose(home,NULL,lst());
00117 fst(NULL); holes = 0;
00118 if (assigned()) goto notify_val;
00119 } else {
00120 RangeList* p = NULL;
00121 RangeList* c = fst();
00122 unsigned int h = 0;
00123 while (m > c->max()) {
00124 RangeList* n = c->next(p); c->fix(n);
00125 h += (n->min() - c->max() - 1);
00126 p=c; c=n;
00127 }
00128 holes -= h;
00129 int min_c = std::max(m,c->min());
00130 dom.min(min_c); c->min(min_c);
00131 if (c != fst()) {
00132 fst()->dispose(home,p);
00133 c->prev(p,NULL); fst(c);
00134 }
00135 }
00136 notify(home,ME_INT_BND);
00137 return;
00138 notify_val:
00139 notify(home,ME_INT_VAL);
00140 }
00141
00142 void
00143 IntVarImp::eq_full(Space* home, int m) {
00144 if (!range()) {
00145 RangeList* p = NULL;
00146 RangeList* c = fst();
00147 while (m > c->max()) {
00148 RangeList* n=c->next(p); c->fix(n); p=c; c=n;
00149 }
00150 if (m < c->min()) {
00151 dom.min(Limits::Int::int_max+1);
00152 return;
00153 }
00154 while (c != NULL) {
00155 RangeList* n=c->next(p); c->fix(n); p=c; c=n;
00156 }
00157 assert(p == lst());
00158 fst()->dispose(home,p);
00159 fst(NULL); holes = 0;
00160 }
00161 dom.min(m); dom.max(m);
00162 notify(home,ME_INT_VAL);
00163 }
00164
00165 ModEvent
00166 IntVarImp::nq_full(Space* home, int m) {
00167 assert(!((m < dom.min()) || (m > dom.max())));
00168 if (range()) {
00169 if ((m == dom.min()) && (m == dom.max()))
00170 return ME_INT_FAILED;
00171 if (m == dom.min()) {
00172 dom.min(m+1); goto notify_bnd_or_val;
00173 }
00174 if (m == dom.max()) {
00175 dom.max(m-1); goto notify_bnd_or_val;
00176 }
00177 RangeList* f = new (home) RangeList(dom.min(),m-1);
00178 RangeList* l = new (home) RangeList(m+1,dom.max());
00179 f->prevnext(NULL,l);
00180 l->prevnext(f,NULL);
00181 fst(f); lst(l); holes = 1;
00182 } else if (m < fst()->next(NULL)->min()) {
00183 int f_max = fst()->max();
00184 if (m > f_max)
00185 return ME_INT_NONE;
00186 int f_min = dom.min();
00187 if ((m == f_min) && (m == f_max)) {
00188 RangeList* f_next = fst()->next(NULL);
00189 dom.min(f_next->min());
00190 if (f_next == lst()) {
00191
00192 fst()->dispose(home,f_next);
00193 fst(NULL); holes = 0;
00194 goto notify_bnd_or_val;
00195 } else {
00196 f_next->prev(fst(),NULL);
00197 fst()->dispose(home); fst(f_next);
00198 holes -= dom.min() - f_min - 1;
00199 goto notify_bnd;
00200 }
00201 } else if (m == f_min) {
00202 dom.min(m+1); fst()->min(m+1);
00203 goto notify_bnd;
00204 } else if (m == f_max) {
00205 fst()->max(m-1); holes += 1;
00206 } else {
00207
00208 RangeList* f = new (home) RangeList(f_min,m-1);
00209 f->prevnext(NULL,fst());
00210 fst()->min(m+1); fst()->prev(NULL,f);
00211 fst(f); holes += 1;
00212 }
00213 } else if (m > lst()->prev(NULL)->max()) {
00214 int l_min = lst()->min();
00215 if (m < l_min)
00216 return ME_INT_NONE;
00217 int l_max = dom.max();
00218 if ((m == l_min) && (m == l_max)) {
00219 RangeList* l_prev = lst()->prev(NULL);
00220 dom.max(l_prev->max());
00221 if (l_prev == fst()) {
00222
00223 l_prev->dispose(home,lst());
00224 fst(NULL); holes = 0;
00225 goto notify_bnd_or_val;
00226 } else {
00227 l_prev->next(lst(),NULL);
00228 lst()->dispose(home); lst(l_prev);
00229 holes -= l_max - dom.max() - 1;
00230 goto notify_bnd;
00231 }
00232 } else if (m == l_max) {
00233 dom.max(m-1); lst()->max(m-1);
00234 goto notify_bnd;
00235 } else if (m == l_min) {
00236 lst()->min(m+1); holes += 1;
00237 } else {
00238 RangeList* l = new (home) RangeList(m+1,l_max);
00239 l->prevnext(lst(),NULL);
00240 lst()->max(m-1); lst()->next(NULL,l);
00241 lst(l); holes += 1;
00242 }
00243 } else {
00244 RangeList* p;
00245 RangeList* c;
00246 RangeList* n;
00247 if (closer_min(m)) {
00248 assert(m > fst()->max());
00249 p = NULL;
00250 c = fst();
00251 do {
00252 n=c->next(p); p=c; c=n;
00253 } while (m > c->max());
00254 if (m < c->min())
00255 return ME_INT_NONE;
00256 n=c->next(p);
00257 } else {
00258 assert(m < lst()->min());
00259 n = NULL;
00260 c = lst();
00261 do {
00262 p=c->prev(n); n=c; c=p;
00263 } while (m < c->min());
00264 if (m > c->max())
00265 return ME_INT_NONE;
00266 p=c->prev(n);
00267 }
00268 assert((fst() != c) && (lst() != c));
00269 assert((m >= c->min()) && (m <= c->max()));
00270 holes += 1;
00271 int c_min = c->min();
00272 int c_max = c->max();
00273 if ((c_min == m) && (c_max == m)) {
00274 c->dispose(home);
00275 p->next(c,n); n->prev(c,p);
00276 } else if (c_min == m) {
00277 c->min(m+1);
00278 } else {
00279 c->max(m-1);
00280 if (c_max != m) {
00281 RangeList* l = new (home) RangeList(m+1,c_max);
00282 l->prevnext(c,n);
00283 c->next(n,l);
00284 n->prev(c,l);
00285 }
00286 }
00287 }
00288 notify(home,ME_INT_DOM);
00289 return ME_INT_DOM;
00290 notify_bnd_or_val:
00291 if (assigned()) {
00292 notify(home,ME_INT_VAL);
00293 return ME_INT_VAL;
00294 }
00295 notify_bnd:
00296 notify(home,ME_INT_BND);
00297 return ME_INT_BND;
00298 }
00299
00300
00301
00302
00303
00304
00305
00306
00307 forceinline
00308 IntVarImp::IntVarImp(Space* home, bool share, IntVarImp& x)
00309 : Variable<VTI_INT,PC_INT_DOM>(home,share,x),
00310 dom(x.dom.min(),x.dom.max()), holes(x.holes) {
00311 if (holes) {
00312 int m = 1;
00313
00314 {
00315 RangeList* s_p = x.fst();
00316 RangeList* s_c = s_p->next(NULL);
00317 do {
00318 m++;
00319 RangeList* s_n = s_c->next(s_p); s_p=s_c; s_c=s_n;
00320 } while (s_c != NULL);
00321 }
00322 RangeList* d_c =
00323 reinterpret_cast<RangeList*>(home->alloc(m*sizeof(RangeList)));
00324 fst(d_c); lst(d_c+m-1);
00325 d_c->min(x.fst()->min());
00326 d_c->max(x.fst()->max());
00327 d_c->prevnext(NULL,NULL);
00328 RangeList* s_p = x.fst();
00329 RangeList* s_c = s_p->next(NULL);
00330 do {
00331 RangeList* d_n = d_c + 1;
00332 d_c->next(NULL,d_n);
00333 d_n->prevnext(d_c,NULL);
00334 d_n->min(s_c->min()); d_n->max(s_c->max());
00335 d_c = d_n;
00336 RangeList* s_n=s_c->next(s_p); s_p=s_c; s_c=s_n;
00337 } while (s_c != NULL);
00338 d_c->next(NULL,NULL);
00339 } else {
00340 fst(NULL);
00341 }
00342 }
00343
00344 IntVarImp*
00345 IntVarImp::perform_copy(Space* home, bool share) {
00346 return new (home) IntVarImp(home,share,*this);
00347 }
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357 forceinline
00358 IntVarImp::Processor::Processor(void) {
00359
00360 mec(ME_INT_BND, ME_INT_DOM, ME_INT_BND);
00361
00362 mepc(ME_INT_BND, PC_INT_BND);
00363 mepc(ME_INT_BND, PC_INT_DOM);
00364 mepc(ME_INT_DOM, PC_INT_DOM);
00365
00366 enter();
00367 }
00368
00369 IntVarImp::Processor IntVarImp::ivp;
00370
00371
00372
00373
00374
00375
00376
00377
00378 void
00379 IntVarImp::subscribe(Space* home, Propagator* p, PropCond pc) {
00380 Variable<VTI_INT,PC_INT_DOM>::subscribe(home,p,pc,
00381 dom.min()==dom.max(), ME_INT_BND);
00382 }
00383
00384 }}
00385
00386
00387
00388
00389
00390
00391