Generated on Wed Jan 4 17:49:14 2006 for Gecode by doxygen 1.4.6

inter.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *     Christian Schulte, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-11-29 18:00:25 +0100 (Tue, 29 Nov 2005) $ by $Author: tack $
00012  *     $Revision: 2664 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 namespace Gecode { namespace Set { namespace Select {
00025 
00026   template <class SView, class RView>
00027   forceinline
00028   SelectIntersection<SView,RView>::
00029   SelectIntersection(Space* home, SView y0,
00030                      IdxViewArray<SView>& iv0,
00031                      RView y1,
00032                      const IntSet& theUniverse)
00033     : Propagator(home, true), universe(theUniverse), x0(y0), iv(iv0), x1(y1) {
00034 
00035     x0.subscribe(home,this, PC_SET_ANY);
00036     x1.subscribe(home,this, PC_SET_ANY);
00037     iv.subscribe(home,this, PC_SET_ANY);
00038   }
00039 
00040   template <class SView, class RView>
00041   forceinline
00042   SelectIntersection<SView,RView>::
00043   SelectIntersection(Space* home, bool share,
00044                      SelectIntersection<SView,RView>& p)
00045     : Propagator(home,share,p) {
00046     x0.update(home,share,p.x0);
00047     x1.update(home,share,p.x1);
00048     iv.update(home,share,p.iv);
00049     universe.update(share,p.universe);
00050   }
00051 
00052   template <class SView, class RView>
00053   PropCost
00054   SelectIntersection<SView,RView>::cost(void) const {
00055     return PC_LINEAR_HI;
00056   }
00057 
00058   template <class SView, class RView>
00059   SelectIntersection<SView,RView>::~SelectIntersection(void) {
00060     x0.cancel(this, PC_SET_ANY);
00061     x1.cancel(this, PC_SET_ANY);
00062     iv.cancel(this,PC_SET_ANY);
00063   }
00064 
00065   template <class SView, class RView>
00066   ExecStatus
00067   SelectIntersection<SView,RView>::
00068   post(Space* home, SView x0, IdxViewArray<SView>& xs,
00069        RView x1, const IntSet& universe) {
00070     int n = xs.size();
00071 
00072     // s2 \subseteq {1,...,n}
00073     Iter::Ranges::Singleton s(0, n-1);
00074     GECODE_ME_CHECK(x1.intersectI(home,s));
00075     (void) new (home)
00076       SelectIntersection<SView,RView>(home,x0,xs,x1,universe);
00077     return ES_OK;
00078   }
00079 
00080   template <class SView, class RView>
00081   Actor*
00082   SelectIntersection<SView,RView>::copy(Space* home, bool share) {
00083     return new (home) SelectIntersection<SView,RView>(home,share,*this);
00084   }
00085 
00086   template <class SView, class RView>
00087   ExecStatus
00088   SelectIntersection<SView,RView>::propagate(Space* home) {
00089     int n = iv.size();
00090 
00091     bool loopVar;
00092     do {
00093       loopVar = false;
00094 
00095       // Cache the upper bound iterator, as we have to
00096       // modify the upper bound while iterating
00097       LubRanges<RView> x1ub(x1);
00098       Iter::Ranges::Cache<LubRanges<RView> > x1ubc(x1ub);
00099       Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > >
00100         vx1ub(x1ubc);
00101 
00102       GlbRanges<RView> x1lb(x1);
00103       Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(x1lb);
00104       Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > >
00105         vx1(x1lbc);
00106 
00107       // In the first iteration, compute in before[i] the intersection
00108       // of all the lower bounds of the x_i. At the same time,
00109       // exclude inconsistent x_i from x1 and remove them from
00110       // the list, cancel their dependencies.
00111 
00112       LUBndSet sofarBefore(home,universe);
00113       GECODE_AUTOARRAY(LUBndSet, before, n);
00114 
00115       int j = 0;
00116       int i = 0;
00117       while ( vx1ub() ) {
00118 
00119         // Remove vars at indices not in the upper bound
00120         if (iv[i].idx < vx1ub.val()) {
00121           iv[i].var.cancel(this, PC_SET_ANY);
00122           ++i;
00123           continue;
00124         }
00125         assert(iv[i].idx == vx1ub.val());
00126         iv[j] = iv[i];
00127 
00128         SView candidate = iv[j].var;
00129         int candidateInd = iv[j].idx;
00130 
00131         // inter = glb(x0) & complement(lub(candidate))
00132         GlbRanges<SView> x0lb(x0);
00133         LubRanges<SView> candub(candidate);
00134         RangesCompl<LubRanges<SView> > candubc(candub);
00135         Iter::Ranges::Inter<GlbRanges<SView>,
00136           RangesCompl<LubRanges<SView> > > inter(x0lb, candubc);
00137 
00138         // exclude inconsistent x_i
00139         // an x_i is inconsistent if
00140         //  * its max cardinality is less than minCard of x0
00141         //  * inter is not empty (there are elements in x_0
00142         //    that can't be in x_i)
00143         if (candidate.cardMax() < x0.cardMin() ||
00144             inter()) {
00145           ModEvent me = (x1.exclude(home,candidateInd));
00146           loopVar |= me_modified(me);
00147           GECODE_ME_CHECK(me);
00148 
00149           iv[j].var.cancel(this, PC_SET_ANY);
00150           ++i;
00151           ++vx1ub;
00152           continue;
00153         } else {
00154           // if x_i is consistent, check whether we know
00155           // that its index is in x1
00156           if (vx1() && vx1.val()==candidateInd) {
00157             // x0 <= candidate, candidate >= x0
00158             GlbRanges<SView> x0lb(x0);
00159             ModEvent me = candidate.includeI(home,x0lb);
00160             loopVar |= me_modified(me);
00161             GECODE_ME_CHECK(me);
00162 
00163             LubRanges<SView> candub(candidate);
00164             me = x0.intersectI(home,candub);
00165             loopVar |= me_modified(me);
00166             GECODE_ME_CHECK(me);
00167             ++vx1;
00168           }
00169           before[j].init(home);
00170           before[j].update(home,sofarBefore);
00171           GlbRanges<SView> clb(candidate);
00172           sofarBefore.intersectI(home,clb);
00173         }
00174 
00175         ++vx1ub;
00176         ++i; ++j;
00177       }
00178 
00179       // cancel the variables with index greater than
00180       // max of lub(x1)
00181       for (int k=i; k<n; k++) {
00182         iv[k].var.cancel(this, PC_SET_ANY);
00183       }
00184       n = j;
00185       iv.size(n);
00186 
00187       if (x1.cardMax()==0) {
00188         // Selector is empty, hence the result must be universe
00189         {
00190           IntSetRanges uniI(universe);
00191           GECODE_ME_CHECK(x0.includeI(home,uniI));
00192         }
00193         {
00194           IntSetRanges uniI(universe);
00195           GECODE_ME_CHECK(x0.intersectI(home,uniI));
00196         }
00197         for (int i=n; i--;)
00198           before[i].dispose(home);
00199         return ES_SUBSUMED;
00200       }
00201 
00202       {
00203         // x0 >= sofarBefore
00204         BndSetRanges sfB(sofarBefore);
00205         ModEvent me = x0.includeI(home,sfB);
00206         loopVar |= me_modified(me);
00207         GECODE_ME_CHECK(me);
00208       }
00209 
00210       sofarBefore.dispose(home);
00211 
00212       LUBndSet sofarAfter(home, universe);
00213 
00214       // In the second iteration, this time backwards, compute
00215       // sofarAfter as the intersection of all glb(x_j) with j>i
00216       for (int i=n; i--;) {
00217         if (sofarAfter.size() == 0) break;
00218         
00219         // extra = inter(before[i], sofarAfter) - lub(x0)
00220         BndSetRanges b(before[i]);
00221         BndSetRanges s(sofarAfter);
00222         LubRanges<SView> x0ub(x0);
00223         Iter::Ranges::Inter<BndSetRanges, BndSetRanges> inter(b,s);
00224         Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00225           BndSetRanges>, LubRanges<SView> > diff(inter, x0ub);
00226         if (diff()) {
00227           ModEvent me = (x1.include(home,iv[i].idx));
00228           loopVar |= me_modified(me);
00229           GECODE_ME_CHECK(me);
00230 
00231           // candidate != extra
00232           me = iv[i].var.excludeI(home,diff);
00233           loopVar |= me_modified(me);
00234           GECODE_ME_CHECK(me);
00235         }
00236 
00237         GlbRanges<SView> ivilb(iv[i].var);
00238         sofarAfter.intersectI(home,ivilb);
00239         before[i].dispose(home);
00240       }
00241       sofarAfter.dispose(home);
00242 
00243     } while(loopVar);
00244 
00245     // Test whether we determined x1 without determining x0
00246     if(x1.assigned() && !x0.assigned()) {
00247       int ubsize = x1.lubSize();
00248       if (ubsize > 2) {
00249         assert(ubsize==n);
00250         ViewArray<SView> is(home,ubsize);
00251         for (int i=n; i--;) {
00252           is[i] = iv[i].var;
00253         }
00254         GECODE_ES_CHECK((RelOp::IntersectionN<SView, SView>
00255                          ::post(home,is,x0)));
00256         return ES_SUBSUMED;
00257 
00258       } else if (ubsize == 2) {
00259         assert(n==2);
00260         SView a = iv[0].var;
00261         SView b = iv[1].var;
00262 
00263         GECODE_ES_CHECK((RelOp::Intersection<SView, SView, SView>
00264                            ::post(home,a,b,x0)));
00265         return ES_SUBSUMED;
00266       } else if (ubsize == 1) {
00267         assert(n==1);
00268         GECODE_ES_CHECK(
00269           (Rel::Eq<SView,SView>::post(home,x0,iv[0].var)));
00270         return ES_SUBSUMED;
00271       } else {
00272         GECODE_ME_CHECK(x0.exclude(home,Limits::Set::int_min,
00273                                    Limits::Set::int_max));
00274         return ES_SUBSUMED;
00275       }
00276     }
00277 
00278     bool allAssigned = true;
00279     for (int i=iv.size(); i--;) {
00280       if (!iv[i].var.assigned()) {
00281         allAssigned = false;
00282         break;
00283       }
00284     }
00285     if (x0.assigned() && x1.assigned() && allAssigned) {
00286       return ES_SUBSUMED;
00287     }
00288 
00289     return ES_FIX;
00290   }
00291 
00292 }}}
00293 
00294 // STATISTICS: set-prop