virtual-ranges-union.icc
Go to the documentation of this file.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 namespace Gecode { namespace Iter { namespace Ranges { namespace Virt {
00039
00046 class Union : public MinMax, public Iterator {
00048 Iterator* i;
00050 Iterator* j;
00051 Union(const Union&);
00052 public:
00054
00055
00056 Union(void);
00058 Union(Iterator* i, Iterator* j);
00060 ~Union(void);
00062
00064
00065
00066 virtual int min(void) const;
00068 virtual int max(void) const;
00070 virtual unsigned int width(void) const;
00072
00074
00075
00076 void operator++(void);
00078 virtual bool operator()(void);
00080 };
00081
00082
00088 class NaryUnion : public MinMax, public Iterator {
00089 private:
00090 NaryUnion(const NaryUnion&);
00091 protected:
00093 class RangeUnionOrder {
00094 public:
00095 bool operator()(const Iterator*, const Iterator*) const;
00096 };
00098 RangeUnionOrder order;
00100 Support::PQueue<Iterator*,RangeUnionOrder> r;
00101 public:
00103
00104
00105 NaryUnion(void);
00107 NaryUnion(Iterator** i, int n);
00109
00111
00112
00113 virtual int min(void) const;
00115 virtual int max(void) const;
00117 virtual unsigned int width(void) const;
00119
00121
00122
00123 void operator++(void);
00125 virtual bool operator()(void);
00127 };
00128
00129
00130
00131
00132
00133
00134
00135
00136 forceinline void
00137 Union::operator++(void) {
00138 if (!(*i)() && !(*j)()) {
00139 finish(); return;
00140 }
00141 if (!(*i)()) {
00142 mi = j->min(); ma = j->max(); ++(*j); return;
00143 }
00144 if (!(*j)()) {
00145 mi = i->min(); ma = i->max(); ++(*i); return;
00146 }
00147 if (i->min() < j->min()) {
00148 mi = i->min(); ma = i->max(); ++(*i);
00149 } else {
00150 mi = j->min(); ma = j->max(); ++(*j);
00151 }
00152 bool goOn;
00153 do {
00154 goOn = false;
00155 if ((*i)() && (i->min() <= ma+1)) {
00156 ma = std::max(ma,i->max()); ++(*i); goOn=true;
00157 }
00158 if ((*j)() && (j->min() <= ma+1)) {
00159 ma = std::max(ma,j->max()); ++(*j); goOn=true;
00160 }
00161 } while (goOn);
00162 }
00163
00164
00165 forceinline
00166 Union::Union(void) {}
00167
00168 forceinline
00169 Union::Union(Iterator* i0, Iterator* j0)
00170 : i(i0), j(j0) {
00171 operator++();
00172 }
00173
00174 forceinline
00175 Union::~Union(void) { delete i; delete j; }
00176
00177 forceinline bool
00178 Union::operator()(void) { return MinMax::operator()(); }
00179
00180 forceinline int
00181 Union::min(void) const { return MinMax::min(); }
00182
00183 forceinline int
00184 Union::max(void) const { return MinMax::max(); }
00185
00186 forceinline unsigned int
00187 Union::width(void) const { return MinMax::width(); }
00188
00189
00190
00191
00192
00193
00194 forceinline bool
00195 NaryUnion::RangeUnionOrder::operator()(const Iterator* a,
00196 const Iterator* b) const {
00197 return a->min() > b->min();
00198 }
00199
00200 inline void
00201 NaryUnion::operator++(void) {
00202 if (r.empty()) {
00203 finish(); return;
00204 }
00205 mi = r.top()->min();
00206 ma = r.top()->max();
00207 do {
00208 if (ma < r.top()->max())
00209 ma = r.top()->max();
00210 ++(*(r.top()));
00211 if (!((*r.top()))()) {
00212 r.remove();
00213 if (r.empty())
00214 return;
00215 } else {
00216 r.fix();
00217 }
00218 } while (ma+1 >= r.top()->min());
00219 }
00220
00221
00222 forceinline
00223 NaryUnion::NaryUnion(void) {}
00224
00225 inline
00226 NaryUnion::NaryUnion(Iterator** r0, int n)
00227 : order(), r(n,order) {
00228 for (int i = n; i--; )
00229 if ((*(r0[i]))())
00230 r.insert(r0[i]);
00231 operator++();
00232 }
00233
00234 forceinline bool
00235 NaryUnion::operator()(void) { return MinMax::operator()(); }
00236
00237 forceinline int
00238 NaryUnion::min(void) const { return MinMax::min(); }
00239
00240 forceinline int
00241 NaryUnion::max(void) const { return MinMax::max(); }
00242
00243 forceinline unsigned int
00244 NaryUnion::width(void) const { return MinMax::width(); }
00245
00246 }}}}
00247
00248
00249