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 #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 class NaryUnion : public RangeListIter {
00079 protected:
00081 RangeList* f;
00083 template<class I, class J>
00084 RangeList* two(I& i, J& j);
00086 template<class I>
00087 void insert(I& i, RangeList*& u);
00088 public:
00090
00091
00092 NaryUnion(void);
00094 template<class I>
00095 NaryUnion(Region& r, I& i);
00097 template<class I, class J>
00098 NaryUnion(Region& r, I& i, J& j);
00100 template<class I>
00101 NaryUnion(Region& r, I* i, int n);
00103 template<class I>
00104 void init(Region& r, I& i);
00106 template<class I, class J>
00107 void init(Region& r, I& i, J& j);
00109 template<class I>
00110 void init(Region& r, I* i, int n);
00112 template<class I>
00113 void operator |=(I& i);
00115 NaryUnion& operator =(const NaryUnion& m);
00117 };
00118
00119
00120
00121
00122
00123
00124
00125
00126 template<class I, class J>
00127 inline void
00128 Union<I,J>::operator ++(void) {
00129 if (!i() && !j()) {
00130 finish(); return;
00131 }
00132
00133 if (!i() || (j() && (j.max()+1 < i.min()))) {
00134 mi = j.min(); ma = j.max(); ++j; return;
00135 }
00136 if (!j() || (i() && (i.max()+1 < j.min()))) {
00137 mi = i.min(); ma = i.max(); ++i; return;
00138 }
00139
00140 mi = std::min(i.min(),j.min());
00141 ma = std::max(i.max(),j.max());
00142
00143 ++i; ++j;
00144
00145 next:
00146 if (i() && (i.min() <= ma+1)) {
00147 ma = std::max(ma,i.max()); ++i;
00148 goto next;
00149 }
00150 if (j() && (j.min() <= ma+1)) {
00151 ma = std::max(ma,j.max()); ++j;
00152 goto next;
00153 }
00154 }
00155
00156
00157 template<class I, class J>
00158 forceinline
00159 Union<I,J>::Union(void) {}
00160
00161 template<class I, class J>
00162 forceinline
00163 Union<I,J>::Union(I& i0, J& j0)
00164 : i(i0), j(j0) {
00165 operator ++();
00166 }
00167
00168 template<class I, class J>
00169 forceinline void
00170 Union<I,J>::init(I& i0, J& j0) {
00171 i = i0; j = j0;
00172 operator ++();
00173 }
00174
00175
00176
00177
00178
00179
00180
00181
00182 template<class I, class J>
00183 RangeListIter::RangeList*
00184 NaryUnion::two(I& i, J& j) {
00185 RangeList* h;
00186 RangeList** c = &h;
00187
00188 while (i() && j())
00189 if (i.max()+1 < j.min()) {
00190 RangeList* t = range(i); ++i;
00191 *c = t; c = &t->next;
00192 } else if (j.max()+1 < i.min()) {
00193 RangeList* t = range(j); ++j;
00194 *c = t; c = &t->next;
00195 } else {
00196 int min = std::min(i.min(),j.min());
00197 int max = std::max(i.max(),j.max());
00198 ++i; ++j;
00199
00200 nexta:
00201 if (i() && (i.min() <= max+1)) {
00202 max = std::max(max,i.max()); ++i;
00203 goto nexta;
00204 }
00205 if (j() && (j.min() <= max+1)) {
00206 max = std::max(max,j.max()); ++j;
00207 goto nexta;
00208 }
00209
00210 RangeList* t = range(min,max);
00211 *c = t; c = &t->next;
00212 }
00213 for ( ; i(); ++i) {
00214 RangeList* t = range(i);
00215 *c = t; c = &t->next;
00216 }
00217 for ( ; j(); ++j) {
00218 RangeList* t = range(j);
00219 *c = t; c = &t->next;
00220 }
00221 *c = NULL;
00222 return h;
00223 }
00224
00225 template<class I>
00226 void
00227 NaryUnion::insert(I& i, RangeList*& u) {
00228
00229 RangeList** c = &u;
00230
00231 while ((*c != NULL) && i())
00232 if ((*c)->max+1 < i.min()) {
00233
00234 c = &(*c)->next;
00235 } else if (i.max()+1 < (*c)->min) {
00236
00237 RangeList* t = range(i,f); ++i;
00238
00239 t->next = *c; *c = t; c = &t->next;
00240 } else {
00241
00242
00243 (*c)->min = std::min((*c)->min,i.min());
00244
00245 int max = std::max((*c)->max,i.max());
00246
00247
00248 RangeList* s = (*c)->next;
00249 ++i;
00250
00251 nextb:
00252 if ((s != NULL) && (s->min <= max+1)) {
00253 max = std::max(max,s->max);
00254 RangeList* t = s;
00255 s = s->next;
00256
00257 t->next = f; f = t;
00258 goto nextb;
00259 }
00260 if (i() && (i.min() <= max+1)) {
00261 max = std::max(max,i.max()); ++i;
00262 goto nextb;
00263 }
00264
00265 (*c)->max = max; (*c)->next = s;
00266 }
00267 if (*c == NULL) {
00268
00269 for ( ; i(); ++i) {
00270 RangeList* t = range(i,f);
00271 *c = t; c = &t->next;
00272 }
00273 *c = NULL;
00274 }
00275 }
00276
00277
00278 forceinline
00279 NaryUnion::NaryUnion(void)
00280 : f(NULL) {}
00281
00282 template<class I>
00283 forceinline void
00284 NaryUnion::init(Region& r, I& i) {
00285 RangeListIter::init(r);
00286 f = NULL;
00287 set(copy(i));
00288 }
00289
00290 template<class I, class J>
00291 forceinline void
00292 NaryUnion::init(Region& r, I& i, J& j) {
00293 RangeListIter::init(r);
00294 f = NULL;
00295 set(two(i,j));
00296 }
00297
00298 template<class I>
00299 forceinline void
00300 NaryUnion::init(Region& r, I* i, int n) {
00301 f = NULL;
00302 RangeListIter::init(r);
00303
00304 int m = 0;
00305 while ((m < n) && !i[m]())
00306 m++;
00307
00308
00309 if (m >= n)
00310 return;
00311
00312 n--;
00313 while (!i[n]())
00314 n--;
00315
00316 if (m == n) {
00317
00318 set(copy(i[m]));
00319 } else {
00320
00321 RangeList* u = two(i[m++],i[n--]);
00322
00323 for ( ; m<=n; m++)
00324 insert(i[m], u);
00325 set(u);
00326 }
00327 }
00328
00329 template<class I>
00330 forceinline
00331 NaryUnion::NaryUnion(Region& r, I& i) {
00332 init(r, i);
00333 }
00334 template<class I, class J>
00335 forceinline
00336 NaryUnion::NaryUnion(Region& r, I& i, J& j) {
00337 init(r, i, j);
00338 }
00339 template<class I>
00340 forceinline
00341 NaryUnion::NaryUnion(Region& r, I* i, int n) {
00342 init(r, i, n);
00343 }
00344
00345 template<class I>
00346 forceinline void
00347 NaryUnion::operator |=(I& i) {
00348 RangeList* u = get();
00349 insert(i, u);
00350 set(u);
00351 }
00352
00353 forceinline NaryUnion&
00354 NaryUnion::operator =(const NaryUnion& m) {
00355 f = NULL;
00356 return static_cast<NaryUnion&>(RangeListIter::operator =(m));
00357 }
00358
00359 }}}
00360
00361
00362