integerset.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2009-01-20 23:44:27 +0100 (Tue, 20 Jan 2009) $ by $Author: schulte $ 00011 * $Revision: 8082 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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) { //in a hole before c 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 //the new range is the first 00080 fst(q); 00081 else 00082 p->next(q); 00083 return true; 00084 } 00085 //if the range starts before c, update c->min and size 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 //sum up the size of holes eaten 00103 int prevMax = c->max(); 00104 int growth = 0; 00105 // invariant: q->min()<=ma+1 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); //q would have stayed c if c was last. 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 //the new range is disjoint from the old domain and we add it as last: 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); // Never intersect with an empty set 00152 00153 // Skip ranges that are before mi 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 // Delete entire domain 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 // We have found the first range that intersects with [mi,ma] 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; } //in a hole 00223 00224 if (c->min()<mi && c->max() > ma) { //Range split: 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) { //start of range clipped, end remains 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) { //end of range clipped, start remains 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 { //range *c destroyed 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(); //performs loop step! 00270 c->dispose(home,cend); 00271 p=cend; 00272 c=nc; 00273 if (c != NULL && c->min() <= ma ) { 00274 //start of range clipped, end remains 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 // STATISTICS: set-var 00348