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