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