Generated on Sun Feb 17 15:24:29 2019 for Gecode by doxygen 1.6.3

union.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Guido Tack, 2004,2006
00009  *     Christian Schulte, 2004
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 namespace Gecode { namespace Set { namespace Element {
00037 
00038   template<class View, class View0, class View1>
00039   forceinline
00040   ElementUnion<View,View0,View1>::
00041   ElementUnion(Home home, IdxViewArray& iv0, View0 y0, View1 y1)
00042     : Propagator(home), iv(iv0), x0(y0), x1(y1) {
00043     home.notice(*this,AP_DISPOSE);
00044     x0.subscribe(home,*this, PC_SET_ANY);
00045     x1.subscribe(home,*this, PC_SET_ANY);
00046     iv.subscribe(home,*this, PC_SET_ANY);
00047   }
00048 
00049   template<class View, class View0, class View1>
00050   forceinline
00051   ElementUnion<View,View0,View1>::
00052   ElementUnion(Space& home, ElementUnion<View,View0,View1>& p)
00053     : Propagator(home,p) {
00054     x0.update(home,p.x0);
00055     x1.update(home,p.x1);
00056     iv.update(home,p.iv);
00057   }
00058 
00059   template<class View, class View0, class View1>
00060   PropCost
00061   ElementUnion<View,View0,View1>::cost(const Space&,
00062                                        const ModEventDelta&) const {
00063     return PropCost::linear(PropCost::HI, iv.size()+2);
00064   }
00065 
00066   template<class View, class View0, class View1>
00067   void
00068   ElementUnion<View,View0,View1>::reschedule(Space& home) {
00069     x0.reschedule(home,*this, PC_SET_ANY);
00070     x1.reschedule(home,*this, PC_SET_ANY);
00071     iv.reschedule(home,*this, PC_SET_ANY);
00072   }
00073 
00074   template<class View, class View0, class View1>
00075   forceinline size_t
00076   ElementUnion<View,View0,View1>::dispose(Space& home) {
00077     home.ignore(*this,AP_DISPOSE);
00078     if (!home.failed()) {
00079       x0.cancel(home,*this,PC_SET_ANY);
00080       x1.cancel(home,*this,PC_SET_ANY);
00081       iv.cancel(home,*this,PC_SET_ANY);
00082     }
00083     (void) Propagator::dispose(home);
00084     return sizeof(*this);
00085   }
00086 
00087   template<class View, class View0, class View1>
00088   ExecStatus
00089   ElementUnion<View,View0,View1>::
00090   post(Home home, IdxViewArray& xs, View0 x0, View1 x1) {
00091     int n = xs.size();
00092 
00093     // x0 \subseteq {1,...,n}
00094     Iter::Ranges::Singleton s(0, n-1);
00095     GECODE_ME_CHECK(x0.intersectI(home,s));
00096     (void) new (home)
00097       ElementUnion<View,View0,View1>(home,xs,x0,x1);
00098     return ES_OK;
00099   }
00100 
00101   template<class View, class View0, class View1>
00102   Actor*
00103   ElementUnion<View,View0,View1>::copy(Space& home) {
00104     return new (home) ElementUnion<View,View0,View1>(home,*this);
00105   }
00106 
00107   template<class View, class View0, class View1>
00108   ExecStatus
00109   ElementUnion<View,View0,View1>::propagate(Space& home, const ModEventDelta&) {
00110     Region r;
00111     int n = iv.size();
00112 
00113     bool loopVar;
00114     do {
00115       loopVar = false;
00116 
00117       // Cache the upper bound iterator, as we have to
00118       // modify the upper bound while iterating
00119       LubRanges<View0> x0ub(x0);
00120       Iter::Ranges::Cache x0ubc(r,x0ub);
00121       Iter::Ranges::ToValues<Iter::Ranges::Cache> vx0ub(x0ubc);
00122 
00123       GlbRanges<View0> x0lb(x0);
00124       Iter::Ranges::Cache x0lbc(r,x0lb);
00125       Iter::Ranges::ToValues<Iter::Ranges::Cache> vx0(x0lbc);
00126 
00127       // In the first iteration, compute in before[i] the union
00128       // of all the upper bounds of the x_i. At the same time,
00129       // exclude inconsistent x_i from x0 and remove them from
00130       // the list, cancel their dependencies.
00131 
00132       GLBndSet sofarBefore(home);
00133       LUBndSet selectedInter(home, IntSet (Limits::min,
00134                                    Limits::max));
00135       GLBndSet* before =
00136         static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n));
00137 
00138       int j = 0;
00139       int i = 0;
00140 
00141       unsigned int maxCard = 0;
00142       unsigned int minCard = Limits::card;
00143 
00144       while ( vx0ub() ) {
00145 
00146         // Remove vars at indices not in the upper bound
00147         if (iv[i].idx < vx0ub.val()) {
00148           iv[i].view.cancel(home,*this, PC_SET_ANY);
00149           ++i;
00150           continue;
00151         }
00152         assert(iv[i].idx == vx0ub.val());
00153         iv[j] = iv[i];
00154 
00155         View candidate = iv[j].view;
00156         int candidateInd = iv[j].idx;
00157 
00158         // inter = glb(candidate) & complement(lub(x1))
00159         GlbRanges<View> candlb(candidate);
00160         LubRanges<View1> x1ub(x1);
00161         Iter::Ranges::Diff<GlbRanges<View>, LubRanges<View1> >
00162           diff(candlb, x1ub);
00163 
00164         bool selectSingleInconsistent = false;
00165         if (x0.cardMax() <= 1) {
00166           GlbRanges<View1> x1lb(x1);
00167           LubRanges<View> candub(candidate);
00168           Iter::Ranges::Diff<GlbRanges<View1>,
00169                              LubRanges<View> > diff2(x1lb, candub);
00170           selectSingleInconsistent =
00171             diff2() || candidate.cardMax() < x1.cardMin();
00172         }
00173 
00174         // exclude inconsistent x_i
00175         // an x_i is inconsistent if
00176         //  * at most one x_i can be selected and there are
00177         //    elements in x_0 that can't be in x_i
00178         //    (selectSingleInconsistent)
00179         //  * its min cardinality is greater than maxCard of x1
00180         //  * inter is not empty (there are elements in x_i
00181         //    that can't be in x_0)
00182         if (selectSingleInconsistent ||
00183             candidate.cardMin() > x1.cardMax() ||
00184             diff()) {
00185           ModEvent me = (x0.exclude(home,candidateInd));
00186           loopVar |= me_modified(me);
00187           GECODE_ME_CHECK(me);
00188 
00189           iv[j].view.cancel(home,*this, PC_SET_ANY);
00190           ++i;
00191           ++vx0ub;
00192           continue;
00193         } else {
00194           // if x_i is consistent, check whether we know
00195           // that its index is in x0
00196           if (vx0() && vx0.val()==candidateInd) {
00197             // x1 >= candidate, candidate <= x1
00198             GlbRanges<View> candlb(candidate);
00199             ModEvent me = x1.includeI(home,candlb);
00200             loopVar |= me_modified(me);
00201             GECODE_ME_CHECK(me);
00202 
00203             LubRanges<View1> x1ub(x1);
00204             me = candidate.intersectI(home,x1ub);
00205             loopVar |= me_modified(me);
00206             GECODE_ME_CHECK(me);
00207             ++vx0;
00208           }
00209           new (&before[j]) GLBndSet(home);
00210           before[j].update(home,sofarBefore);
00211           LubRanges<View> cub(candidate);
00212           sofarBefore.includeI(home,cub);
00213           GlbRanges<View> clb(candidate);
00214           selectedInter.intersectI(home,clb);
00215           maxCard = std::max(maxCard, candidate.cardMax());
00216           minCard = std::min(minCard, candidate.cardMin());
00217         }
00218 
00219         ++vx0ub;
00220         ++i; ++j;
00221       }
00222 
00223       // cancel the variables with index greater than
00224       // max of lub(x0)
00225       for (int k=i; k<n; k++) {
00226         iv[k].view.cancel(home,*this, PC_SET_ANY);
00227       }
00228       n = j;
00229       iv.size(n);
00230 
00231       if (x0.cardMax()==0) {
00232         // Selector is empty, hence the result must be empty
00233         {
00234           GECODE_ME_CHECK(x1.cardMax(home,0));
00235         }
00236         for (int i=n; i--;)
00237           before[i].dispose(home);
00238         return home.ES_SUBSUMED(*this);
00239       }
00240 
00241       if (x0.cardMin() > 0) {
00242         // Selector is not empty, hence the intersection of the
00243         // possibly selected lower bounds is contained in x1
00244         BndSetRanges si(selectedInter);
00245         ModEvent me = x1.includeI(home, si);
00246         loopVar |= me_modified(me);
00247         GECODE_ME_CHECK(me);
00248         me = x1.cardMin(home, minCard);
00249         loopVar |= me_modified(me);
00250         GECODE_ME_CHECK(me);
00251       }
00252       selectedInter.dispose(home);
00253 
00254       if (x0.cardMax() <= 1) {
00255         ModEvent me = x1.cardMax(home, maxCard);
00256         loopVar |= me_modified(me);
00257         GECODE_ME_CHECK(me);
00258       }
00259 
00260       {
00261         // x1 <= sofarBefore
00262         BndSetRanges sfB(sofarBefore);
00263         ModEvent me = x1.intersectI(home,sfB);
00264         loopVar |= me_modified(me);
00265         GECODE_ME_CHECK(me);
00266       }
00267 
00268       sofarBefore.dispose(home);
00269 
00270       GLBndSet sofarAfter(home);
00271 
00272       // In the second iteration, this time backwards, compute
00273       // sofarAfter as the union of all lub(x_j) with j>i
00274       for (int i=n; i--;) {
00275         // TODO: check for size of universe here?
00276         // if (sofarAfter.size() == 0) break;
00277 
00278         // extra = inter(before[i], sofarAfter) - lub(x1)
00279         BndSetRanges b(before[i]);
00280         BndSetRanges s(sofarAfter);
00281         GlbRanges<View1> x1lb(x1);
00282         Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s);
00283         Iter::Ranges::Diff<GlbRanges<View1>,
00284           Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x1lb, inter);
00285         if (diff()) {
00286           ModEvent me = (x0.include(home,iv[i].idx));
00287           loopVar |= me_modified(me);
00288           GECODE_ME_CHECK(me);
00289 
00290           // candidate != extra
00291           me = iv[i].view.includeI(home,diff);
00292           loopVar |= me_modified(me);
00293           GECODE_ME_CHECK(me);
00294         }
00295 
00296         LubRanges<View> iviub(iv[i].view);
00297         sofarAfter.includeI(home,iviub);
00298         before[i].dispose(home);
00299       }
00300       sofarAfter.dispose(home);
00301 
00302     } while (loopVar);
00303 
00304     // Test whether we determined x0 without determining x1
00305     if (x0.assigned() && !x1.assigned()) {
00306       int ubsize = static_cast<int>(x0.lubSize());
00307       if (ubsize > 2) {
00308         assert(ubsize==n);
00309         ViewArray<View> is(home,ubsize);
00310         for (int i=n; i--;)
00311           is[i]=iv[i].view;
00312         GECODE_REWRITE(*this,(RelOp::UnionN<View, View1>
00313                         ::post(home(*this),is,x1)));
00314       } else if (ubsize == 2) {
00315         assert(n==2);
00316         View a = iv[0].view;
00317         View b = iv[1].view;
00318         GECODE_REWRITE(*this,(RelOp::Union<View,View,View1>
00319                        ::post(home(*this),a,b,x1)));
00320       } else if (ubsize == 1) {
00321         assert(n==1);
00322         GECODE_REWRITE(*this,
00323           (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
00324       } else {
00325         GECODE_ME_CHECK(x1.cardMax(home, 0));
00326         return home.ES_SUBSUMED(*this);
00327       }
00328     }
00329 
00330     for (int i=iv.size(); i--;)
00331       if (!iv[i].view.assigned())
00332         return ES_FIX;
00333     if (!x1.assigned() || !x0.assigned())
00334       return ES_FIX;
00335     return home.ES_SUBSUMED(*this);
00336   }
00337 
00338 }}}
00339 
00340 // STATISTICS: set-prop