ranges-union.hpp
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, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $ 00011 * $Revision: 11390 $ 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 <algorithm> 00039 00040 namespace Gecode { namespace Iter { namespace Ranges { 00041 00047 template<class I, class J> 00048 class Union : public MinMax { 00049 protected: 00051 I i; 00053 J j; 00054 public: 00056 00057 00058 Union(void); 00060 Union(I& i, J& j); 00062 void init(I& i, J& j); 00064 00066 00067 00068 void operator ++(void); 00070 }; 00071 00072 00078 template<class I> 00079 class NaryUnion : public RangeListIter { 00080 protected: 00082 RangeList* range(RangeList*& f, int min, int max); 00084 RangeList* range(RangeList*& f, I& i); 00085 public: 00087 00088 00089 NaryUnion(void); 00091 NaryUnion(Region& r, I* i, int n); 00093 void init(Region& r, I* i, int n); 00095 NaryUnion& operator =(const NaryUnion& m); 00097 }; 00098 00099 00100 00101 00102 /* 00103 * Binary union 00104 * 00105 */ 00106 00107 template<class I, class J> 00108 inline void 00109 Union<I,J>::operator ++(void) { 00110 if (!i() && !j()) { 00111 finish(); return; 00112 } 00113 00114 if (!i() || (j() && (j.max()+1 < i.min()))) { 00115 mi = j.min(); ma = j.max(); ++j; return; 00116 } 00117 if (!j() || (i() && (i.max()+1 < j.min()))) { 00118 mi = i.min(); ma = i.max(); ++i; return; 00119 } 00120 00121 mi = std::min(i.min(),j.min()); 00122 ma = std::max(i.max(),j.max()); 00123 00124 ++i; ++j; 00125 00126 next: 00127 if (i() && (i.min() <= ma+1)) { 00128 ma = std::max(ma,i.max()); ++i; 00129 goto next; 00130 } 00131 if (j() && (j.min() <= ma+1)) { 00132 ma = std::max(ma,j.max()); ++j; 00133 goto next; 00134 } 00135 } 00136 00137 00138 template<class I, class J> 00139 forceinline 00140 Union<I,J>::Union(void) {} 00141 00142 template<class I, class J> 00143 forceinline 00144 Union<I,J>::Union(I& i0, J& j0) 00145 : i(i0), j(j0) { 00146 operator ++(); 00147 } 00148 00149 template<class I, class J> 00150 forceinline void 00151 Union<I,J>::init(I& i0, J& j0) { 00152 i = i0; j = j0; 00153 operator ++(); 00154 } 00155 00156 00157 00158 /* 00159 * Nary Union 00160 * 00161 */ 00162 00163 template<class I> 00164 forceinline 00165 NaryUnion<I>::NaryUnion(void) {} 00166 00167 template<class I> 00168 forceinline RangeListIter::RangeList* 00169 NaryUnion<I>::range(RangeList*& f, int min, int max) { 00170 RangeList* t; 00171 // Take element from freelist if possible 00172 if (f != NULL) { 00173 t = f; f = f->next; 00174 } else { 00175 t = new (*rlio) RangeList; 00176 } 00177 t->min = min; t->max = max; 00178 return t; 00179 } 00180 00181 template<class I> 00182 forceinline RangeListIter::RangeList* 00183 NaryUnion<I>::range(RangeList*& f, I& i) { 00184 return range(f,i.min(),i.max()); 00185 } 00186 00187 template<class I> 00188 void 00189 NaryUnion<I>::init(Region& r, I* i, int n) { 00190 RangeListIter::init(r); 00191 00192 // Freelist for allocation 00193 RangeList* f = NULL; 00194 00195 // Rangelist for union 00196 RangeList* u = NULL; 00197 00198 int m = 0; 00199 while ((m < n) && !i[m]()) 00200 m++; 00201 00202 // Union is empty 00203 if (m >= n) 00204 return; 00205 00206 n--; 00207 while (!i[n]()) 00208 n--; 00209 00210 if (m == n) { 00211 // Union is just a single iterator 00212 RangeList** c = &u; 00213 00214 for ( ; i[m](); ++i[m]) { 00215 RangeList* t = range(f,i[m]); 00216 *c = t; c = &t->next; 00217 } 00218 *c = NULL; 00219 } else { 00220 // At least two iterators 00221 00222 // Compute the union for just two iterators 00223 { 00224 // The current rangelist 00225 RangeList** c = &u; 00226 00227 while (i[m]() && i[n]()) 00228 if (i[m].max()+1 < i[n].min()) { 00229 RangeList* t = range(f,i[m]); ++i[m]; 00230 *c = t; c = &t->next; 00231 } else if (i[n].max()+1 < i[m].min()) { 00232 RangeList* t = range(f,i[n]); ++i[n]; 00233 *c = t; c = &t->next; 00234 } else { 00235 int min = std::min(i[m].min(),i[n].min()); 00236 int max = std::max(i[m].max(),i[n].max()); 00237 ++i[m]; ++i[n]; 00238 00239 nexta: 00240 if (i[m]() && (i[m].min() <= max+1)) { 00241 max = std::max(max,i[m].max()); ++i[m]; 00242 goto nexta; 00243 } 00244 if (i[n]() && (i[n].min() <= max+1)) { 00245 max = std::max(max,i[n].max()); ++i[n]; 00246 goto nexta; 00247 } 00248 00249 RangeList* t = range(f,min,max); 00250 *c = t; c = &t->next; 00251 } 00252 for ( ; i[m](); ++i[m]) { 00253 RangeList* t = range(f,i[m]); 00254 *c = t; c = &t->next; 00255 } 00256 for ( ; i[n](); ++i[n]) { 00257 RangeList* t = range(f,i[n]); 00258 *c = t; c = &t->next; 00259 } 00260 *c = NULL; 00261 m++; n--; 00262 } 00263 00264 // Insert the remaining iterators 00265 for ( ; m<=n; m++) { 00266 // The current rangelist 00267 RangeList** c = &u; 00268 00269 while ((*c != NULL) && i[m]()) 00270 if ((*c)->max+1 < i[m].min()) { 00271 // Keep range from union 00272 c = &(*c)->next; 00273 } else if (i[m].max()+1 < (*c)->min) { 00274 // Copy range from iterator 00275 RangeList* t = range(f,i[m]); ++i[m]; 00276 // Insert 00277 t->next = *c; *c = t; c = &t->next; 00278 } else { 00279 // Ranges overlap 00280 // Compute new minimum 00281 (*c)->min = std::min((*c)->min,i[m].min()); 00282 // Compute new maximum 00283 int max = std::max((*c)->max,i[m].max()); 00284 00285 // Scan from the next range in the union 00286 RangeList* s = (*c)->next; 00287 ++i[m]; 00288 00289 nextb: 00290 if ((s != NULL) && (s->min <= max+1)) { 00291 max = std::max(max,s->max); 00292 RangeList* t = s; 00293 s = s->next; 00294 // Put deleted element into freelist 00295 t->next = f; f = t; 00296 goto nextb; 00297 } 00298 if (i[m]() && (i[m].min() <= max+1)) { 00299 max = std::max(max,i[m].max()); ++i[m]; 00300 goto nextb; 00301 } 00302 // Store computed max and shunt skipped ranges from union 00303 (*c)->max = max; (*c)->next = s; 00304 } 00305 if (*c == NULL) { 00306 // Copy remaining ranges from iterator 00307 for ( ; i[m](); ++i[m]) { 00308 RangeList* t = range(f,i[m]); 00309 *c = t; c = &t->next; 00310 } 00311 *c = NULL; 00312 } 00313 } 00314 } 00315 set(u); 00316 } 00317 00318 template<class I> 00319 forceinline 00320 NaryUnion<I>::NaryUnion(Region& r, I* i, int n) { 00321 init(r,i,n); 00322 } 00323 00324 template<class I> 00325 forceinline NaryUnion<I>& 00326 NaryUnion<I>::operator =(const NaryUnion<I>& m) { 00327 return static_cast<NaryUnion&>(RangeListIter::operator =(m)); 00328 } 00329 00330 }}} 00331 00332 // STATISTICS: iter-any 00333