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