Generated on Mon May 10 06:46:45 2010 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: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00013  *     $Revision: 10364 $
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 SView, class RView>
00043   forceinline
00044   ElementUnion<SView,RView>::
00045   ElementUnion(Home home, SView y0,
00046                      IdxViewArray& iv0,
00047                      RView y1)
00048     : Propagator(home), x0(y0), iv(iv0), x1(y1) {
00049     home.notice(*this,AP_DISPOSE);
00050     x0.subscribe(home,*this, PC_SET_ANY);
00051     x1.subscribe(home,*this, PC_SET_ANY);
00052     iv.subscribe(home,*this, PC_SET_ANY);
00053   }
00054 
00055   template<class SView, class RView>
00056   forceinline
00057   ElementUnion<SView,RView>::
00058   ElementUnion(Space& home, bool share,
00059                      ElementUnion<SView,RView>& p)
00060     : Propagator(home,share,p) {
00061     x0.update(home,share,p.x0);
00062     x1.update(home,share,p.x1);
00063     iv.update(home,share,p.iv);
00064   }
00065 
00066   template<class SView, class RView>
00067   PropCost
00068   ElementUnion<SView,RView>::cost(const Space&, const ModEventDelta&) const {
00069     return PropCost::linear(PropCost::HI, iv.size()+2);
00070   }
00071 
00072   template<class SView, class RView>
00073   forceinline size_t
00074   ElementUnion<SView,RView>::dispose(Space& home) {
00075     home.ignore(*this,AP_DISPOSE);
00076     if (!home.failed()) {
00077       x0.cancel(home,*this,PC_SET_ANY);
00078       x1.cancel(home,*this,PC_SET_ANY);
00079       iv.cancel(home,*this,PC_SET_ANY);
00080     }
00081     (void) Propagator::dispose(home);
00082     return sizeof(*this);
00083   }
00084 
00085   template<class SView, class RView>
00086   ExecStatus
00087   ElementUnion<SView,RView>::
00088   post(Home home, SView x0, IdxViewArray& xs,
00089        RView x1) {
00090     int n = xs.size();
00091 
00092     // s2 \subseteq {1,...,n}
00093     Iter::Ranges::Singleton s(0, n-1);
00094     GECODE_ME_CHECK(x1.intersectI(home,s));
00095     (void) new (home)
00096       ElementUnion<SView,RView>(home,x0,xs,x1);
00097     return ES_OK;
00098   }
00099 
00100   template<class SView, class RView>
00101   Actor*
00102   ElementUnion<SView,RView>::copy(Space& home, bool share) {
00103     return new (home) ElementUnion<SView,RView>(home,share,*this);
00104   }
00105 
00106   template<class SView, class RView>
00107   ExecStatus
00108   ElementUnion<SView,RView>::propagate(Space& home, const ModEventDelta&) {
00109     Region r(home);
00110     int n = iv.size();
00111 
00112     bool loopVar;
00113     do {
00114       loopVar = false;
00115 
00116       // Cache the upper bound iterator, as we have to
00117       // modify the upper bound while iterating
00118       LubRanges<RView> x1ub(x1);
00119       Iter::Ranges::Cache<LubRanges<RView> > x1ubc(x1ub);
00120       Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > >
00121         vx1ub(x1ubc);
00122 
00123       GlbRanges<RView> x1lb(x1);
00124       Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(x1lb);
00125       Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > >
00126         vx1(x1lbc);
00127 
00128       // In the first iteration, compute in before[i] the union
00129       // of all the upper bounds of the x_i. At the same time,
00130       // exclude inconsistent x_i from x1 and remove them from
00131       // the list, cancel their dependencies.
00132 
00133       GLBndSet sofarBefore(home);
00134       LUBndSet selectedInter(home, IntSet (Limits::min,
00135                                    Limits::max));
00136       GLBndSet* before =
00137         static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n));
00138 
00139       int j = 0;
00140       int i = 0;
00141 
00142       unsigned int maxCard = 0;
00143       unsigned int minCard = Limits::card;
00144 
00145       while ( vx1ub() ) {
00146 
00147         // Remove vars at indices not in the upper bound
00148         if (iv[i].idx < vx1ub.val()) {
00149           iv[i].view.cancel(home,*this, PC_SET_ANY);
00150           ++i;
00151           continue;
00152         }
00153         assert(iv[i].idx == vx1ub.val());
00154         iv[j] = iv[i];
00155 
00156         SView candidate = iv[j].view;
00157         int candidateInd = iv[j].idx;
00158 
00159         // inter = glb(candidate) & complement(lub(x0))
00160         GlbRanges<SView> candlb(candidate);
00161         LubRanges<SView> x0ub(x0);
00162         Iter::Ranges::Diff<GlbRanges<SView>,
00163           LubRanges<SView> > diff(candlb, x0ub);
00164 
00165         bool selectSingleInconsistent = false;
00166         if (x1.cardMax() <= 1) {
00167           GlbRanges<SView> x0lb(x0);
00168           LubRanges<SView> candub(candidate);
00169           Iter::Ranges::Diff<GlbRanges<SView>,
00170                              LubRanges<SView> > diff2(x0lb, candub);
00171           selectSingleInconsistent = diff2() || candidate.cardMax() < x0.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 x0
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() > x0.cardMax() ||
00184             diff()) {
00185           ModEvent me = (x1.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           ++vx1ub;
00192           continue;
00193         } else {
00194           // if x_i is consistent, check whether we know
00195           // that its index is in x1
00196           if (vx1() && vx1.val()==candidateInd) {
00197             // x0 >= candidate, candidate <= x0
00198             GlbRanges<SView> candlb(candidate);
00199             ModEvent me = x0.includeI(home,candlb);
00200             loopVar |= me_modified(me);
00201             GECODE_ME_CHECK(me);
00202 
00203             LubRanges<SView> x0ub(x0);
00204             me = candidate.intersectI(home,x0ub);
00205             loopVar |= me_modified(me);
00206             GECODE_ME_CHECK(me);
00207             ++vx1;
00208           }
00209           new (&before[j]) GLBndSet(home);
00210           before[j].update(home,sofarBefore);
00211           LubRanges<SView> cub(candidate);
00212           sofarBefore.includeI(home,cub);
00213           GlbRanges<SView> clb(candidate);
00214           selectedInter.intersectI(home,clb);
00215           maxCard = std::max(maxCard, candidate.cardMax());
00216           minCard = std::min(minCard, candidate.cardMin());
00217         }
00218 
00219         ++vx1ub;
00220         ++i; ++j;
00221       }
00222 
00223       // cancel the variables with index greater than
00224       // max of lub(x1)
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 (x1.cardMax()==0) {
00232         // Selector is empty, hence the result must be empty
00233         {
00234           GECODE_ME_CHECK(x0.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 (x1.cardMin() > 0) {
00242         // Selector is not empty, hence the intersection of the
00243         // possibly selected lower bounds is contained in x0
00244         BndSetRanges si(selectedInter);
00245         ModEvent me = x0.includeI(home, si);
00246         loopVar |= me_modified(me);
00247         GECODE_ME_CHECK(me);
00248         me = x0.cardMin(home, minCard);
00249         loopVar |= me_modified(me);
00250         GECODE_ME_CHECK(me);
00251       }
00252       selectedInter.dispose(home);
00253 
00254       if (x1.cardMax() <= 1) {
00255         ModEvent me = x0.cardMax(home, maxCard);
00256         loopVar |= me_modified(me);
00257         GECODE_ME_CHECK(me);
00258       }
00259 
00260       {
00261         // x0 <= sofarBefore
00262         BndSetRanges sfB(sofarBefore);
00263         ModEvent me = x0.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(x0)
00279         BndSetRanges b(before[i]);
00280         BndSetRanges s(sofarAfter);
00281         GlbRanges<SView> x0lb(x0);
00282         Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s);
00283         Iter::Ranges::Diff<GlbRanges<SView>,
00284           Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x0lb, inter);
00285         if (diff()) {
00286           ModEvent me = (x1.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<SView> 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 x1 without determining x0
00305     if (x1.assigned() && !x0.assigned()) {
00306       int ubsize = x1.lubSize();
00307       if (ubsize > 2) {
00308         assert(ubsize==n);
00309         ViewArray<SView> is(home,ubsize);
00310         for (int i=n; i--;)
00311           is[i]=iv[i].view;
00312         GECODE_REWRITE(*this,(RelOp::UnionN<SView, SView>
00313                         ::post(home(*this),is,x0)));
00314       } else if (ubsize == 2) {
00315         assert(n==2);
00316         SView a = iv[0].view;
00317         SView b = iv[1].view;
00318         GECODE_REWRITE(*this,(RelOp::Union<SView, SView, SView>
00319                        ::post(home(*this),a,b,x0)));
00320       } else if (ubsize == 1) {
00321         assert(n==1);
00322         GECODE_REWRITE(*this,(Rel::Eq<SView,SView>::post(home(*this),x0,iv[0].view)));
00323       } else {
00324         GECODE_ME_CHECK(x0.cardMax(home, 0));
00325         return home.ES_SUBSUMED(*this);
00326       }
00327     }
00328 
00329     bool allAssigned = true;
00330     for (int i=iv.size(); i--;) {
00331       if (!iv[i].view.assigned()) {
00332         allAssigned = false;
00333         break;
00334       }
00335     }
00336     if (x0.assigned() && x1.assigned() && allAssigned) {
00337       return home.ES_SUBSUMED(*this);
00338     }
00339 
00340     return ES_FIX;
00341   }
00342 
00343 }}}
00344 
00345 // STATISTICS: set-prop