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 {
00219 int j=0;
00220 for (int i=n_dis; i--; )
00221 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
00222
00223 re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
00224
00225 re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
00226 }
00227
00228 re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
00229 assert(j+1 == n_re);
00230 }
00231
00232 Support::quicksort(re,n_re);
00233
00234
00235 Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
00236
00237 for (int i=0; true; i++)
00238 switch (re[i].ret) {
00239 case RET_FST:
00240
00241 for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur);
00242 j(); ++j) {
00243 int di = re[i].view, dj = j.val();
00244 if (!ovl.get(di,dj)) {
00245 ovl.set(di,dj);
00246 ovl_i[di][deg[di]++] = dj;
00247 ovl_i[dj][deg[dj]++] = di;
00248 }
00249 }
00250 cur.set(static_cast<unsigned int>(re[i].view));
00251 break;
00252 case RET_LST:
00253 cur.clear(static_cast<unsigned int>(re[i].view));
00254 break;
00255 case RET_END:
00256 goto done;
00257 default:
00258 GECODE_NEVER;
00259 }
00260 done:
00261 r.free<RangeEvent>(re,n_re);
00262 }
00263
00264
00265 for (int i=n_dis; i--; ) {
00266 assert(deg[dis[i]] < n_dis);
00267 n_ovl_i[dis[i]] = deg[dis[i]];
00268 }
00269
00270
00271 int* ind = r.alloc<int>(n_dis);
00272 int n_ind = 0;
00273
00274 while (n_dis > 0) {
00275 int i_min = n_dis-1;
00276 int d_min = deg[dis[i_min]];
00277 unsigned int s_min = x[dis[i_min]].size();
00278
00279
00280 for (int i=n_dis-1; i--; )
00281 if ((d_min > deg[dis[i]]) ||
00282 ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
00283 i_min = i;
00284 d_min = deg[dis[i]];
00285 s_min = x[dis[i]].size();
00286 }
00287
00288
00289 ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
00290
00291
00292 for (int i=n_dis; i--; )
00293 if (ovl.get(dis[i],ind[n_ind-1])) {
00294
00295 for (int j=n_ovl_i[dis[i]]; j--; )
00296 deg[ovl_i[dis[i]][j]]--;
00297
00298 dis[i] = dis[--n_dis];
00299 }
00300 }
00301
00302 GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
00303
00304
00305 if (vs.size() + n_ind == y.max()) {
00306
00307 ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
00308 for (int i=n_ind; i--; )
00309 r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
00310 Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
00311 ValSet::Ranges vsr(vs);
00312 v_ind |= vsr;
00313 for (int i=x.size(); i--; ) {
00314 v_ind.reset();
00315 GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
00316 }
00317 }
00318 return ES_OK;
00319 }
00320
00321 template<class VY>
00322 forceinline ExecStatus
00323 IntBase<VY>::prune_upper(Space& home, Graph& g) {
00324 if (!g) {
00325 g.init(home,vs,x);
00326 } else {
00327 g.purge();
00328 g.sync(home);
00329 }
00330 GECODE_ME_CHECK(y.lq(home, g.size()));
00331 if (y.min() == g.size()) {
00332
00333 if (vs.size() + x.size() == g.size()) {
00334
00335 for (int i=x.size(); i--; ) {
00336 ValSet::Ranges vsr(vs);
00337 GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
00338 }
00339 GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home(*this),x));
00340 }
00341 if (g.mark(home))
00342 GECODE_ES_CHECK(g.prune(home));
00343 }
00344 return ES_OK;
00345 }
00346
00347 }}}
00348
00349