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