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 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
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
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
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
00193 RangeList* f = NULL;
00194
00195
00196 RangeList* u = NULL;
00197
00198 int m = 0;
00199 while ((m < n) && !i[m]())
00200 m++;
00201
00202
00203 if (m >= n)
00204 return;
00205
00206 n--;
00207 while (!i[n]())
00208 n--;
00209
00210 if (m == n) {
00211
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
00221
00222
00223 {
00224
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
00265 for ( ; m<=n; m++) {
00266
00267 RangeList** c = &u;
00268
00269 while ((*c != NULL) && i[m]())
00270 if ((*c)->max+1 < i[m].min()) {
00271
00272 c = &(*c)->next;
00273 } else if (i[m].max()+1 < (*c)->min) {
00274
00275 RangeList* t = range(f,i[m]); ++i[m];
00276
00277 t->next = *c; *c = t; c = &t->next;
00278 } else {
00279
00280
00281 (*c)->min = std::min((*c)->min,i[m].min());
00282
00283 int max = std::max((*c)->max,i[m].max());
00284
00285
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
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
00303 (*c)->max = max; (*c)->next = s;
00304 }
00305 if (*c == NULL) {
00306
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
00333