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 <gecode/int/distinct.hh>
00039
00040 namespace Gecode { namespace Int { namespace NValues {
00041
00042 template<class VY>
00043 forceinline
00044 IntBase<VY>::IntBase(Home home, ValSet& vs0, ViewArray<IntView>& x, VY y)
00045 : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home,x,y),
00046 vs(vs0) {}
00047
00048 template<class VY>
00049 forceinline
00050 IntBase<VY>::IntBase(Space& home, bool share, IntBase<VY>& p)
00051 : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home, share, p) {
00052 vs.update(home, share, p.vs);
00053 }
00054
00055 template<class VY>
00056 forceinline size_t
00057 IntBase<VY>::dispose(Space& home) {
00058 vs.dispose(home);
00059 (void) MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>
00060 ::dispose(home);
00061 return sizeof(*this);
00062 }
00063
00064 template<class VY>
00065 PropCost
00066 IntBase<VY>::cost(const Space&, const ModEventDelta&) const {
00067 return PropCost::quadratic(PropCost::HI, x.size());
00068 }
00069
00070 template<class VY>
00071 void
00072 IntBase<VY>::add(Space& home) {
00073 int n=x.size();
00074 for (int i=n; i--; )
00075 if (x[i].assigned()) {
00076 vs.add(home, x[i].val());
00077 x[i] = x[--n];
00078 }
00079 x.size(n);
00080 }
00081
00082 template<class VY>
00083 void
00084 IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) {
00085
00086 int n=x.size();
00087 dis = r.alloc<int>(n); n_dis = 0;
00088
00089 int i=0;
00090 while (i < n)
00091 switch (vs.compare(x[i])) {
00092 case Iter::Ranges::CS_SUBSET:
00093
00094 x[i].cancel(home, *this, PC_INT_DOM);
00095 x[i] = x[--n];
00096 break;
00097 case Iter::Ranges::CS_DISJOINT:
00098 dis[n_dis++] = i++;
00099 break;
00100 case Iter::Ranges::CS_NONE:
00101 i++;
00102 break;
00103 default:
00104 GECODE_NEVER;
00105 }
00106 x.size(n);
00107 }
00108
00109 template<class VY>
00110 void
00111 IntBase<VY>::eliminate(Space& home) {
00112 int n=x.size();
00113 for (int i=n; i--; )
00114 if (vs.subset(x[i])) {
00115
00116 x[i].cancel(home, *this, PC_INT_DOM);
00117 x[i] = x[--n];
00118 }
00119 x.size(n);
00120 }
00121
00122 template<class VY>
00123 int
00124 IntBase<VY>::size(Space& home) const {
00125 Region r(home);
00126 assert(x.size() > 0);
00127 ValSet::Ranges vsr(vs);
00128 ViewRanges<IntView> xr(x[x.size()-1]);
00129 Iter::Ranges::NaryUnion u(r,vsr,xr);
00130 for (int i=x.size()-1; i--; ) {
00131 ViewRanges<IntView> xir(x[i]);
00132 u |= xir;
00133 }
00134 unsigned int s = Iter::Ranges::size(u);
00135
00136
00137 if (static_cast<unsigned int>(x.size()+vs.size()) < s)
00138 return x.size() + vs.size();
00139 else
00140 return static_cast<int>(s);
00141 }
00142
00143 template<class VY>
00144 ExecStatus
00145 IntBase<VY>::all_in_valset(Space& home) {
00146 for (int i=x.size(); i--; ) {
00147 ValSet::Ranges vsr(vs);
00148 GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
00149 }
00150 return home.ES_SUBSUMED(*this);
00151 }
00152
00153 template<class VY>
00154 ExecStatus
00155 IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
00156 assert(n_dis > 0);
00157
00158
00159 GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
00160
00161 Region r(home);
00162
00163
00164 if (y.max() == vs.size() + 1) {
00165
00166 ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
00167 for (int i=n_dis; i--; )
00168 r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
00169 Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
00170
00171 if (!iv())
00172 return ES_FAILED;
00173 ValSet::Ranges vsr(vs);
00174 Iter::Ranges::NaryUnion pv(r,iv,vsr);
00175
00176 for (int i=x.size(); i--; ) {
00177 pv.reset();
00178 GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
00179 }
00180 return ES_OK;
00181 }
00182
00183
00184
00185 SymBitMatrix ovl(r,x.size());
00186
00187 int* deg = r.alloc<int>(x.size());
00188
00189 int** ovl_i = r.alloc<int*>(x.size());
00190
00191 int* n_ovl_i = r.alloc<int>(x.size());
00192 {
00193 #ifndef NDEBUG
00194
00195 for (int i=x.size(); i--; )
00196 ovl_i[i] = NULL;
00197 #endif
00198
00199 int* m = r.alloc<int>(n_dis*(n_dis-1));
00200 for (int i=n_dis; i--; ) {
00201 deg[dis[i]] = 0;
00202 ovl_i[dis[i]] = m; m += n_dis-1;
00203 }
00204 }
00205
00206
00207 {
00208
00209
00210 int n_re = 1;
00211
00212 for (int i=n_dis; i--; )
00213 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
00214 n_re += 2;
00215
00216
00217 RangeEvent* re = r.alloc<RangeEvent>(n_re);
00218 int j=0;
00219 for (int i=n_dis; i--; )
00220 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
00221
00222 re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
00223
00224 re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
00225 }
00226
00227 re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
00228 assert(j+1 == n_re);
00229
00230 Support::quicksort(re,n_re);
00231
00232
00233 Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
00234
00235 for (int i=0; true; i++)
00236 switch (re[i].ret) {
00237 case RET_FST:
00238
00239 for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur);
00240 j(); ++j) {
00241 int di = re[i].view, dj = j.val();
00242 if (!ovl.get(di,dj)) {
00243 ovl.set(di,dj);
00244 ovl_i[di][deg[di]++] = dj;
00245 ovl_i[dj][deg[dj]++] = di;
00246 }
00247 }
00248 cur.set(static_cast<unsigned int>(re[i].view));
00249 break;
00250 case RET_LST:
00251 cur.clear(static_cast<unsigned int>(re[i].view));
00252 break;
00253 case RET_END:
00254 goto done;
00255 default:
00256 GECODE_NEVER;
00257 }
00258 done:
00259 r.free<RangeEvent>(re,n_re);
00260 }
00261
00262
00263 for (int i=n_dis; i--; ) {
00264 assert(deg[dis[i]] < n_dis);
00265 n_ovl_i[dis[i]] = deg[dis[i]];
00266 }
00267
00268
00269 int* ind = r.alloc<int>(n_dis);
00270 int n_ind = 0;
00271
00272 while (n_dis > 0) {
00273 int i_min = n_dis-1;
00274 int d_min = deg[dis[i_min]];
00275 unsigned int s_min = x[dis[i_min]].size();
00276
00277
00278 for (int i=n_dis-1; i--; )
00279 if ((d_min > deg[dis[i]]) ||
00280 ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
00281 i_min = i;
00282 d_min = deg[dis[i]];
00283 s_min = x[dis[i]].size();
00284 }
00285
00286
00287 ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
00288
00289
00290 for (int i=n_dis; i--; )
00291 if (ovl.get(dis[i],ind[n_ind-1])) {
00292
00293 for (int j=n_ovl_i[dis[i]]; j--; )
00294 deg[ovl_i[dis[i]][j]]--;
00295
00296 dis[i] = dis[--n_dis];
00297 }
00298 }
00299
00300 GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
00301
00302
00303 if (vs.size() + n_ind == y.max()) {
00304
00305 ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
00306 for (int i=n_ind; i--; )
00307 r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
00308 Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
00309 ValSet::Ranges vsr(vs);
00310 v_ind |= vsr;
00311 for (int i=x.size(); i--; ) {
00312 v_ind.reset();
00313 GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
00314 }
00315 }
00316 return ES_OK;
00317 }
00318
00319 template<class VY>
00320 forceinline ExecStatus
00321 IntBase<VY>::prune_upper(Space& home, Graph& g) {
00322 if (!g.initialized()) {
00323 g.init(home,vs,x);
00324 } else {
00325 g.purge();
00326 g.sync(home);
00327 }
00328 GECODE_ME_CHECK(y.lq(home, g.size()));
00329 if (y.min() == g.size()) {
00330
00331 if (vs.size() + x.size() == g.size()) {
00332
00333 for (int i=x.size(); i--; ) {
00334 ValSet::Ranges vsr(vs);
00335 GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
00336 }
00337 GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home,x));
00338 }
00339 if (g.mark(home))
00340 GECODE_ES_CHECK(g.prune(home));
00341 }
00342 return ES_OK;
00343 }
00344
00345 }}}
00346
00347