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 Iter::Ranges::NaryUnion
00128 u(r,ValSet::Ranges(vs),ViewRanges<IntView>(x[x.size()-1]));
00129 for (int i=x.size()-1; i--; )
00130 u |= ViewRanges<IntView>(x[i]);
00131 unsigned int s = Iter::Ranges::size(u);
00132
00133
00134 if (static_cast<unsigned int>(x.size()+vs.size()) < s)
00135 return x.size() + vs.size();
00136 else
00137 return static_cast<int>(s);
00138 }
00139
00140 template<class VY>
00141 ExecStatus
00142 IntBase<VY>::all_in_valset(Space& home) {
00143 for (int i=x.size(); i--; ) {
00144 ValSet::Ranges vsr(vs);
00145 GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
00146 }
00147 return home.ES_SUBSUMED(*this);
00148 }
00149
00150 template<class VY>
00151 ExecStatus
00152 IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
00153 assert(n_dis > 0);
00154
00155
00156 GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
00157
00158 Region r(home);
00159
00160
00161 if (y.max() == vs.size() + 1) {
00162
00163 ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
00164 for (int i=n_dis; i--; )
00165 r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
00166 Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
00167
00168 if (!iv())
00169 return ES_FAILED;
00170 ValSet::Ranges vsr(vs);
00171 Iter::Ranges::NaryUnion pv(r,iv,vsr);
00172
00173 for (int i=x.size(); i--; ) {
00174 pv.reset();
00175 GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
00176 }
00177 return ES_OK;
00178 }
00179
00180
00181
00182 SymBitMatrix ovl(r,x.size());
00183
00184 int* deg = r.alloc<int>(x.size());
00185
00186 int** ovl_i = r.alloc<int*>(x.size());
00187
00188 int* n_ovl_i = r.alloc<int>(x.size());
00189 {
00190 #ifndef NDEBUG
00191
00192 for (int i=x.size(); i--; )
00193 ovl_i[i] = NULL;
00194 #endif
00195
00196 int* m = r.alloc<int>(n_dis*(n_dis-1));
00197 for (int i=n_dis; i--; ) {
00198 deg[dis[i]] = 0;
00199 ovl_i[dis[i]] = m; m += n_dis-1;
00200 }
00201 }
00202
00203
00204 {
00205
00206
00207 int n_re = 1;
00208
00209 for (int i=n_dis; i--; )
00210 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
00211 n_re += 2;
00212
00213
00214 RangeEvent* re = r.alloc<RangeEvent>(n_re);
00215 int j=0;
00216 for (int i=n_dis; i--; )
00217 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
00218
00219 re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
00220
00221 re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
00222 }
00223
00224 re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
00225 assert(j+1 == n_re);
00226
00227 Support::quicksort(re,n_re);
00228
00229
00230 Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
00231
00232 for (int i=0; true; i++)
00233 switch (re[i].ret) {
00234 case RET_FST:
00235
00236 for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur);
00237 j(); ++j) {
00238 int di = re[i].view, dj = j.val();
00239 if (!ovl.get(di,dj)) {
00240 ovl.set(di,dj);
00241 ovl_i[di][deg[di]++] = dj;
00242 ovl_i[dj][deg[dj]++] = di;
00243 }
00244 }
00245 cur.set(static_cast<unsigned int>(re[i].view));
00246 break;
00247 case RET_LST:
00248 cur.clear(static_cast<unsigned int>(re[i].view));
00249 break;
00250 case RET_END:
00251 goto done;
00252 default:
00253 GECODE_NEVER;
00254 }
00255 done:
00256 r.free<RangeEvent>(re,n_re);
00257 }
00258
00259
00260 for (int i=n_dis; i--; ) {
00261 assert(deg[dis[i]] < n_dis);
00262 n_ovl_i[dis[i]] = deg[dis[i]];
00263 }
00264
00265
00266 int* ind = r.alloc<int>(n_dis);
00267 int n_ind = 0;
00268
00269 while (n_dis > 0) {
00270 int i_min = n_dis-1;
00271 int d_min = deg[dis[i_min]];
00272 unsigned int s_min = x[dis[i_min]].size();
00273
00274
00275 for (int i=n_dis-1; i--; )
00276 if ((d_min > deg[dis[i]]) ||
00277 ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
00278 i_min = i;
00279 d_min = deg[dis[i]];
00280 s_min = x[dis[i]].size();
00281 }
00282
00283
00284 ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
00285
00286
00287 for (int i=n_dis; i--; )
00288 if (ovl.get(dis[i],ind[n_ind-1])) {
00289
00290 for (int j=n_ovl_i[dis[i]]; j--; )
00291 deg[ovl_i[dis[i]][j]]--;
00292
00293 dis[i] = dis[--n_dis];
00294 }
00295 }
00296
00297 GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
00298
00299
00300 if (vs.size() + n_ind == y.max()) {
00301
00302 ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
00303 for (int i=n_ind; i--; )
00304 r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
00305 Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
00306 ValSet::Ranges vsr(vs);
00307 v_ind |= vsr;
00308 for (int i=x.size(); i--; ) {
00309 v_ind.reset();
00310 GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
00311 }
00312 }
00313 return ES_OK;
00314 }
00315
00316 template<class VY>
00317 forceinline ExecStatus
00318 IntBase<VY>::prune_upper(Space& home, Graph& g) {
00319 if (!g.initialized()) {
00320 g.init(home,vs,x);
00321 } else {
00322 g.purge();
00323 g.sync(home);
00324 }
00325 GECODE_ME_CHECK(y.lq(home, g.size()));
00326 if (y.min() == g.size()) {
00327
00328 if (vs.size() + x.size() == g.size()) {
00329
00330 for (int i=x.size(); i--; ) {
00331 ValSet::Ranges vsr(vs);
00332 GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
00333 }
00334 GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home,x));
00335 }
00336 if (g.mark(home))
00337 GECODE_ES_CHECK(g.prune(home));
00338 }
00339 return ES_OK;
00340 }
00341
00342 }}}
00343
00344