integerset.cpp
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
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 #include <gecode/set.hh>
00037
00038 namespace Gecode { namespace Set {
00039
00040 BndSet::BndSet(Space& home, const IntSet& is) {
00041 if (is.ranges()==0) {
00042 fst(NULL); lst(NULL); _size = 0;
00043 } else {
00044 int n = is.ranges();
00045 RangeList* r = home.alloc<RangeList>(n);
00046 fst(r); lst(r+n-1);
00047 unsigned int s = 0;
00048 for (int i = n; i--; ) {
00049 s += is.width(i);
00050 r[i].min(is.min(i)); r[i].max(is.max(i));
00051 r[i].next(&r[i+1]);
00052 }
00053 r[n-1].next(NULL);
00054 _size = s;
00055 }
00056 assert(isConsistent());
00057 }
00058
00059 bool
00060 GLBndSet::include_full(Space& home, int mi, int ma, SetDelta& d) {
00061 assert(ma >= mi);
00062 assert(fst() != NULL);
00063
00064 RangeList* p = NULL;
00065 RangeList* c = fst();
00066
00067 while (c != NULL) {
00068 if (c->max() >= mi-1) {
00069 if (c->min() > ma+1) {
00070 _size+=(ma-mi+1);
00071 d._glbMin = mi;
00072 d._glbMax = ma;
00073 RangeList* q = new (home) RangeList(mi,ma,c);
00074 if (p==NULL)
00075
00076 fst(q);
00077 else
00078 p->next(q);
00079 return true;
00080 }
00081
00082 bool result = false;
00083 if (c->min()>mi) {
00084 _size+=(c->min()-mi);
00085 c->min(mi);
00086 d._glbMin = mi;
00087 result = true;
00088 } else {
00089 d._glbMin = c->max()+1;
00090 }
00091 assert(c->min()<=mi);
00092 assert(c->max()+1>=mi);
00093 if (c->max() >= ma) {
00094 d._glbMax = c->min()-1;
00095 return result;
00096 }
00097 RangeList* q = c;
00098
00099 int prevMax = c->max();
00100 int growth = 0;
00101
00102 while (q->next() != NULL && q->next()->min() <= ma+1) {
00103 q = q->next();
00104 growth += q->min()-prevMax-1;
00105 prevMax = q->max();
00106 }
00107 assert(growth>=0);
00108 _size+=growth;
00109 if (q->max() < ma) {
00110 _size += ma-q->max();
00111 d._glbMax = ma;
00112 } else {
00113 d._glbMax = q->min()-1;
00114 }
00115 c->max(std::max(ma,q->max()));
00116 if (c!=q) {
00117 RangeList* oldCNext = c->next();
00118 assert(oldCNext!=NULL);
00119 c->next(q->next());
00120 if (q->next()==NULL) {
00121 assert(q==lst());
00122 lst(c);
00123 }
00124 oldCNext->dispose(home,q);
00125 }
00126 return true;
00127 }
00128 RangeList* nc = c->next();
00129 p=c; c=nc;
00130 }
00131
00132 assert(mi>max()+1);
00133 RangeList* q = new (home) RangeList(mi, ma, NULL);
00134 lst()->next(q);
00135 lst(q);
00136 _size+= q->width();
00137 d._glbMin = mi;
00138 d._glbMax = ma;
00139 return true;
00140 }
00141
00142 bool
00143 LUBndSet::intersect_full(Space& home, int mi, int ma) {
00144 RangeList* p = NULL;
00145 RangeList* c = fst();
00146
00147 assert(c != NULL);
00148
00149
00150 while (c != NULL && c->max() < mi) {
00151 _size -= c->width();
00152 RangeList *nc = c->next();
00153 p=c; c=nc;
00154 }
00155 if (c == NULL) {
00156
00157 fst()->dispose(home, lst());
00158 fst(NULL); lst(NULL);
00159 return true;
00160 }
00161
00162 bool changed = false;
00163 if (c != fst()) {
00164 fst()->dispose(home, p);
00165 fst(c);
00166 p = NULL;
00167 changed = true;
00168 }
00169
00170 if (mi > c->min()) {
00171 _size -= mi-c->min();
00172 c->min(mi);
00173 changed = true;
00174 }
00175
00176 while (c != NULL && c->max() <= ma) {
00177 RangeList *nc = c->next();
00178 p=c; c=nc;
00179 }
00180
00181 if (c == NULL)
00182 return changed;
00183
00184 RangeList* newlst = p;
00185 if (ma >= c->min()) {
00186 _size -= c->max() - ma;
00187 c->max(ma);
00188 newlst = c;
00189 RangeList* nc = c->next();
00190 c->next(NULL);
00191 p=c; c=nc;
00192 } else if (p != NULL) {
00193 p->next(NULL);
00194 }
00195 if (c != NULL) {
00196 for (RangeList* cc = c ; cc != NULL; cc = cc->next())
00197 _size -= cc->width();
00198 c->dispose(home, lst());
00199 }
00200 lst(newlst);
00201 if (newlst==NULL)
00202 fst(NULL);
00203 return true;
00204 }
00205
00206 bool
00207 LUBndSet::exclude_full(Space& home, int mi, int ma, SetDelta& d) {
00208 assert(ma >= mi);
00209 assert(mi <= max() && ma >= min() &&
00210 (mi > min() || ma < max()));
00211 bool result=false;
00212
00213 RangeList* p = NULL;
00214 RangeList* c = fst();
00215 d._lubMin = Limits::max+1;
00216 while (c != NULL) {
00217 if (c->max() >= mi) {
00218 if (c->min() > ma) { return result; }
00219
00220 if (c->min()<mi && c->max() > ma) {
00221 RangeList* q =
00222 new (home) RangeList(ma+1,c->max(),c->next());
00223 c->max(mi-1);
00224 if (c == lst()) {
00225 lst(q);
00226 }
00227 c->next(q);
00228 _size -= (ma-mi+1);
00229 d._lubMin = mi;
00230 d._lubMax = ma;
00231 return true;
00232 }
00233
00234 if (c->max() > ma) {
00235 d._lubMin = std::min(d._lubMin, c->min());
00236 d._lubMax = ma;
00237 _size-=(ma-c->min()+1);
00238 c->min(ma+1);
00239 return true;
00240 }
00241
00242 if (c->min() < mi) {
00243 _size-=(c->max()-mi+1);
00244 d._lubMin = mi;
00245 d._lubMax = c->max();
00246 c->max(mi-1);
00247 result=true;
00248 } else {
00249 d._lubMin = c->min();
00250 _size-=c->width();
00251 RangeList *cend = c;
00252 while ((cend->next()!=NULL) && (cend->next()->max()<=ma)) {
00253 cend = cend->next();
00254 _size-=cend->width();
00255 }
00256 d._lubMax = cend->max();
00257 if (fst()==c) {
00258 fst(cend->next());
00259 } else {
00260 p->next(cend->next());
00261 }
00262 if (lst()==cend) {
00263 lst(p);
00264 }
00265 RangeList* nc=cend->next();
00266 c->dispose(home,cend);
00267 p=cend;
00268 c=nc;
00269 if (c != NULL && c->min() <= ma ) {
00270
00271 _size-=(ma-c->min()+1);
00272 c->min(ma+1);
00273 d._lubMax = ma;
00274 }
00275 return true;
00276 }
00277 }
00278 RangeList *nc = c->next();
00279 p=c; c=nc;
00280 }
00281 return result;
00282 }
00283
00284 #ifndef NDEBUG
00285 using namespace Gecode::Int;
00286 #endif
00287
00288 bool
00289 BndSet::isConsistent(void) const {
00290 #ifndef NDEBUG
00291 if (fst()==NULL) {
00292 if (lst()!=NULL || size()!=0) {
00293 std::cerr<<"Strange empty set.\n";
00294 return false;
00295 } else return true;
00296 }
00297
00298 if (fst()!=NULL && lst()==NULL) {
00299 std::cerr<<"First is not null, last is.\n";
00300 return false;
00301 }
00302
00303 RangeList *p=NULL;
00304 RangeList *c=fst();
00305
00306 int min = c->min();
00307 int max = c->max();
00308
00309 if (max<min) {
00310 std::cerr << "Single range list twisted: ("<<min<<","<<max<<")" ;
00311 return false;
00312 }
00313
00314 RangeList *nc=c->next();
00315 p=c; c=nc;
00316 while (c) {
00317 if (max<min) {
00318 std::cerr << "1";
00319 return false;
00320 }
00321 if ((max+1)>=c->min()) {
00322 std::cerr << "2";
00323 return false;
00324 }
00325 if (c->next()==NULL && c!=lst()) {
00326 std::cerr << "3";
00327 return false;
00328 }
00329
00330 min = c->min();
00331 max = c->max();
00332
00333 nc=c->next();
00334 p=c; c=nc;
00335 }
00336 #endif
00337 return true;
00338 }
00339
00340
00341 }}
00342
00343
00344