int.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2002 00008 * 00009 * Last modified: 00010 * $Date: 2009-05-13 23:51:57 +0200 (Wed, 13 May 2009) $ by $Author: tack $ 00011 * $Revision: 9094 $ 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 #include <gecode/int.hh> 00039 00040 namespace Gecode { namespace Int { 00041 00042 forceinline bool 00043 IntVarImp::closer_min(int n) const { 00044 unsigned int l = static_cast<unsigned int>(n - dom.min()); 00045 unsigned int r = static_cast<unsigned int>(dom.max() - n); 00046 return l < r; 00047 } 00048 00049 int 00050 IntVarImp::med(void) const { 00051 // Computes the median 00052 if (fst() == NULL) 00053 return (dom.min()+dom.max())/2 - ((dom.min()+dom.max())%2 < 0 ? 1 : 0); 00054 unsigned int i = size() / 2; 00055 if (size() % 2 == 0) 00056 i--; 00057 const RangeList* p = NULL; 00058 const RangeList* c = fst(); 00059 while (i >= c->width()) { 00060 i -= c->width(); 00061 const RangeList* n=c->next(p); p=c; c=n; 00062 } 00063 return c->min() + static_cast<int>(i); 00064 } 00065 00066 bool 00067 IntVarImp::in_full(int m) const { 00068 if (closer_min(m)) { 00069 const RangeList* p = NULL; 00070 const RangeList* c = fst(); 00071 while (m > c->max()) { 00072 const RangeList* n=c->next(p); p=c; c=n; 00073 } 00074 return (m >= c->min()); 00075 } else { 00076 const RangeList* n = NULL; 00077 const RangeList* c = lst(); 00078 while (m < c->min()) { 00079 const RangeList* p=c->prev(n); n=c; c=p; 00080 } 00081 return (m <= c->max()); 00082 } 00083 } 00084 00085 /* 00086 * "Standard" tell operations 00087 * 00088 */ 00089 00090 ModEvent 00091 IntVarImp::lq_full(Space& home, int m) { 00092 assert((m >= dom.min()) && (m <= dom.max())); 00093 IntDelta d(m+1,dom.max()); 00094 ModEvent me = ME_INT_BND; 00095 if (range()) { // Is already range... 00096 dom.max(m); 00097 if (assigned()) me = ME_INT_VAL; 00098 } else if (m < fst()->next(NULL)->min()) { // Becomes range... 00099 dom.max(std::min(m,fst()->max())); 00100 fst()->dispose(home,NULL,lst()); 00101 fst(NULL); holes = 0; 00102 if (assigned()) me = ME_INT_VAL; 00103 } else { // Stays non-range... 00104 RangeList* n = NULL; 00105 RangeList* c = lst(); 00106 unsigned int h = 0; 00107 while (m < c->min()) { 00108 RangeList* p = c->prev(n); c->fix(n); 00109 h += (c->min() - p->max() - 1); 00110 n=c; c=p; 00111 } 00112 holes -= h; 00113 int max_c = std::min(m,c->max()); 00114 dom.max(max_c); c->max(max_c); 00115 if (c != lst()) { 00116 lst()->dispose(home,n); 00117 c->next(n,NULL); lst(c); 00118 } 00119 } 00120 return notify(home,me,d); 00121 } 00122 00123 ModEvent 00124 IntVarImp::gq_full(Space& home, int m) { 00125 assert((m >= dom.min()) && (m <= dom.max())); 00126 IntDelta d(dom.min(),m-1); 00127 ModEvent me = ME_INT_BND; 00128 if (range()) { // Is already range... 00129 dom.min(m); 00130 if (assigned()) me = ME_INT_VAL; 00131 } else if (m > lst()->prev(NULL)->max()) { // Becomes range... 00132 dom.min(std::max(m,lst()->min())); 00133 fst()->dispose(home,NULL,lst()); 00134 fst(NULL); holes = 0; 00135 if (assigned()) me = ME_INT_VAL; 00136 } else { // Stays non-range... 00137 RangeList* p = NULL; 00138 RangeList* c = fst(); 00139 unsigned int h = 0; 00140 while (m > c->max()) { 00141 RangeList* n = c->next(p); c->fix(n); 00142 h += (n->min() - c->max() - 1); 00143 p=c; c=n; 00144 } 00145 holes -= h; 00146 int min_c = std::max(m,c->min()); 00147 dom.min(min_c); c->min(min_c); 00148 if (c != fst()) { 00149 fst()->dispose(home,p); 00150 c->prev(p,NULL); fst(c); 00151 } 00152 } 00153 return notify(home,me,d); 00154 } 00155 00156 ModEvent 00157 IntVarImp::eq_full(Space& home, int m) { 00158 dom.min(m); dom.max(m); 00159 if (!range()) { 00160 bool failed = false; 00161 RangeList* p = NULL; 00162 RangeList* c = fst(); 00163 while (m > c->max()) { 00164 RangeList* n=c->next(p); c->fix(n); p=c; c=n; 00165 } 00166 if (m < c->min()) 00167 failed = true; 00168 while (c != NULL) { 00169 RangeList* n=c->next(p); c->fix(n); p=c; c=n; 00170 } 00171 assert(p == lst()); 00172 fst()->dispose(home,p); 00173 fst(NULL); holes = 0; 00174 if (failed) 00175 return ME_INT_FAILED; 00176 } 00177 IntDelta d; 00178 return notify(home,ME_INT_VAL,d); 00179 } 00180 00181 ModEvent 00182 IntVarImp::nq_full(Space& home, int m) { 00183 assert(!((m < dom.min()) || (m > dom.max()))); 00184 ModEvent me = ME_INT_DOM; 00185 if (range()) { 00186 if ((m == dom.min()) && (m == dom.max())) 00187 return ME_INT_FAILED; 00188 if (m == dom.min()) { 00189 dom.min(m+1); 00190 me = assigned() ? ME_INT_VAL : ME_INT_BND; 00191 } else if (m == dom.max()) { 00192 dom.max(m-1); 00193 me = assigned() ? ME_INT_VAL : ME_INT_BND; 00194 } else { 00195 RangeList* f = new (home) RangeList(dom.min(),m-1); 00196 RangeList* l = new (home) RangeList(m+1,dom.max()); 00197 f->prevnext(NULL,l); 00198 l->prevnext(f,NULL); 00199 fst(f); lst(l); holes = 1; 00200 } 00201 } else if (m < fst()->next(NULL)->min()) { // Concerns the first range... 00202 int f_max = fst()->max(); 00203 if (m > f_max) 00204 return ME_INT_NONE; 00205 int f_min = dom.min(); 00206 if ((m == f_min) && (m == f_max)) { 00207 RangeList* f_next = fst()->next(NULL); 00208 dom.min(f_next->min()); 00209 if (f_next == lst()) { // Turns into range 00210 // Works as at the ends there are only NULL pointers 00211 fst()->dispose(home,f_next); 00212 fst(NULL); holes = 0; 00213 me = assigned() ? ME_INT_VAL : ME_INT_BND; 00214 } else { // Remains non-range 00215 f_next->prev(fst(),NULL); 00216 fst()->dispose(home); fst(f_next); 00217 holes -= dom.min() - f_min - 1; 00218 me = ME_INT_BND; 00219 } 00220 } else if (m == f_min) { 00221 dom.min(m+1); fst()->min(m+1); 00222 me = ME_INT_BND; 00223 } else if (m == f_max) { 00224 fst()->max(m-1); holes += 1; 00225 } else { 00226 // Create new hole 00227 RangeList* f = new (home) RangeList(f_min,m-1); 00228 f->prevnext(NULL,fst()); 00229 fst()->min(m+1); fst()->prev(NULL,f); 00230 fst(f); holes += 1; 00231 } 00232 } else if (m > lst()->prev(NULL)->max()) { // Concerns the last range... 00233 int l_min = lst()->min(); 00234 if (m < l_min) 00235 return ME_INT_NONE; 00236 int l_max = dom.max(); 00237 if ((m == l_min) && (m == l_max)) { 00238 RangeList* l_prev = lst()->prev(NULL); 00239 dom.max(l_prev->max()); 00240 if (l_prev == fst()) { 00241 // Turns into range 00242 l_prev->dispose(home,lst()); 00243 fst(NULL); holes = 0; 00244 me = assigned() ? ME_INT_VAL : ME_INT_BND; 00245 } else { // Remains non-range 00246 l_prev->next(lst(),NULL); 00247 lst()->dispose(home); lst(l_prev); 00248 holes -= l_max - dom.max() - 1; 00249 me = ME_INT_BND; 00250 } 00251 } else if (m == l_max) { 00252 dom.max(m-1); lst()->max(m-1); 00253 me = ME_INT_BND; 00254 } else if (m == l_min) { 00255 lst()->min(m+1); holes += 1; 00256 } else { // Create new hole 00257 RangeList* l = new (home) RangeList(m+1,l_max); 00258 l->prevnext(lst(),NULL); 00259 lst()->max(m-1); lst()->next(NULL,l); 00260 lst(l); holes += 1; 00261 } 00262 } else { // Concerns element in the middle of the list of ranges 00263 RangeList* p; 00264 RangeList* c; 00265 RangeList* n; 00266 if (closer_min(m)) { 00267 assert(m > fst()->max()); 00268 p = NULL; 00269 c = fst(); 00270 do { 00271 n=c->next(p); p=c; c=n; 00272 } while (m > c->max()); 00273 if (m < c->min()) 00274 return ME_INT_NONE; 00275 n=c->next(p); 00276 } else { 00277 assert(m < lst()->min()); 00278 n = NULL; 00279 c = lst(); 00280 do { 00281 p=c->prev(n); n=c; c=p; 00282 } while (m < c->min()); 00283 if (m > c->max()) 00284 return ME_INT_NONE; 00285 p=c->prev(n); 00286 } 00287 assert((fst() != c) && (lst() != c)); 00288 assert((m >= c->min()) && (m <= c->max())); 00289 holes += 1; 00290 int c_min = c->min(); 00291 int c_max = c->max(); 00292 if ((c_min == m) && (c_max == m)) { 00293 c->dispose(home); 00294 p->next(c,n); n->prev(c,p); 00295 } else if (c_min == m) { 00296 c->min(m+1); 00297 } else { 00298 c->max(m-1); 00299 if (c_max != m) { 00300 RangeList* l = new (home) RangeList(m+1,c_max); 00301 l->prevnext(c,n); 00302 c->next(n,l); 00303 n->prev(c,l); 00304 } 00305 } 00306 } 00307 IntDelta d(m,m); 00308 return notify(home,me,d); 00309 } 00310 00311 00312 00313 /* 00314 * Copying variables 00315 * 00316 */ 00317 00318 forceinline 00319 IntVarImp::IntVarImp(Space& home, bool share, IntVarImp& x) 00320 : IntVarImpBase(home,share,x), dom(x.dom.min(),x.dom.max()) { 00321 holes = x.holes; 00322 if (holes) { 00323 int m = 1; 00324 // Compute length 00325 { 00326 RangeList* s_p = x.fst(); 00327 RangeList* s_c = s_p->next(NULL); 00328 do { 00329 m++; 00330 RangeList* s_n = s_c->next(s_p); s_p=s_c; s_c=s_n; 00331 } while (s_c != NULL); 00332 } 00333 RangeList* d_c = home.alloc<RangeList>(m); 00334 fst(d_c); lst(d_c+m-1); 00335 d_c->min(x.fst()->min()); 00336 d_c->max(x.fst()->max()); 00337 d_c->prevnext(NULL,NULL); 00338 RangeList* s_p = x.fst(); 00339 RangeList* s_c = s_p->next(NULL); 00340 do { 00341 RangeList* d_n = d_c + 1; 00342 d_c->next(NULL,d_n); 00343 d_n->prevnext(d_c,NULL); 00344 d_n->min(s_c->min()); d_n->max(s_c->max()); 00345 d_c = d_n; 00346 RangeList* s_n=s_c->next(s_p); s_p=s_c; s_c=s_n; 00347 } while (s_c != NULL); 00348 d_c->next(NULL,NULL); 00349 } else { 00350 fst(NULL); 00351 } 00352 } 00353 00354 IntVarImp* 00355 IntVarImp::perform_copy(Space& home, bool share) { 00356 return new (home) IntVarImp(home,share,*this); 00357 } 00358 00359 }} 00360 00361 // STATISTICS: int-var