Generated on Sat Feb 12 2011 17:41:03 for Gecode by doxygen 1.7.3

inter.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
00009  *     Christian Schulte, 2004
00010  *
00011  *  Last modified:
00012  *     $Date: 2010-07-28 16:13:53 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $
00013  *     $Revision: 11292 $
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   ElementIntersection<SView,RView>::
00045   ElementIntersection(Home home, RView y0,
00046                      IdxViewArray& iv0,
00047                      RView y1,
00048                      const IntSet& theUniverse)
00049     : Propagator(home), universe(theUniverse), x0(y0), iv(iv0), x1(y1) {
00050     home.notice(*this,AP_DISPOSE);
00051     x0.subscribe(home,*this, PC_SET_ANY);
00052     x1.subscribe(home,*this, PC_SET_ANY);
00053     iv.subscribe(home,*this, PC_SET_ANY);
00054   }
00055 
00056   template<class SView, class RView>
00057   forceinline
00058   ElementIntersection<SView,RView>::
00059   ElementIntersection(Space& home, bool share,
00060                      ElementIntersection<SView,RView>& p)
00061     : Propagator(home,share,p) {
00062     x0.update(home,share,p.x0);
00063     x1.update(home,share,p.x1);
00064     iv.update(home,share,p.iv);
00065     universe.update(home,share,p.universe);
00066   }
00067 
00068   template<class SView, class RView>
00069   PropCost
00070   ElementIntersection<SView,RView>::cost(const Space&,
00071                                          const ModEventDelta&) const {
00072     return PropCost::linear(PropCost::HI, iv.size()+2);
00073   }
00074 
00075   template<class SView, class RView>
00076   forceinline size_t
00077   ElementIntersection<SView,RView>::dispose(Space& home) {
00078     home.ignore(*this,AP_DISPOSE);
00079     if (!home.failed()) {
00080       x0.cancel(home,*this, PC_SET_ANY);
00081       x1.cancel(home,*this, PC_SET_ANY);
00082       iv.cancel(home,*this,PC_SET_ANY);
00083     }
00084     universe.~IntSet();
00085     (void) Propagator::dispose(home);
00086     return sizeof(*this);
00087   }
00088 
00089   template<class SView, class RView>
00090   ExecStatus
00091   ElementIntersection<SView,RView>::
00092   post(Home home, RView x0, IdxViewArray& xs,
00093        RView x1, const IntSet& universe) {
00094     int n = xs.size();
00095 
00096     // s2 \subseteq {1,...,n}
00097     Iter::Ranges::Singleton s(0, n-1);
00098     GECODE_ME_CHECK(x1.intersectI(home,s));
00099     (void) new (home)
00100       ElementIntersection<SView,RView>(home,x0,xs,x1,universe);
00101     return ES_OK;
00102   }
00103 
00104   template<class SView, class RView>
00105   Actor*
00106   ElementIntersection<SView,RView>::copy(Space& home, bool share) {
00107     return new (home) ElementIntersection<SView,RView>(home,share,*this);
00108   }
00109 
00110   template<class SView, class RView>
00111   ExecStatus
00112   ElementIntersection<SView,RView>::propagate(Space& home, const ModEventDelta&) {
00113     Region r(home);
00114     int n = iv.size();
00115 
00116     bool loopVar;
00117     do {
00118       loopVar = false;
00119 
00120       // Cache the upper bound iterator, as we have to
00121       // modify the upper bound while iterating
00122       LubRanges<RView> x1ub(x1);
00123       Iter::Ranges::Cache<LubRanges<RView> > x1ubc(r,x1ub);
00124       Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > >
00125         vx1ub(x1ubc);
00126 
00127       GlbRanges<RView> x1lb(x1);
00128       Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(r,x1lb);
00129       Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > >
00130         vx1(x1lbc);
00131 
00132       // In the first iteration, compute in before[i] the intersection
00133       // of all the lower bounds of the x_i. At the same time,
00134       // exclude inconsistent x_i from x1 and remove them from
00135       // the list, cancel their dependencies.
00136 
00137       LUBndSet sofarBefore(home,universe);
00138       LUBndSet* before = r.alloc<LUBndSet>(n);
00139 
00140       int j = 0;
00141       int i = 0;
00142       while ( vx1ub() ) {
00143 
00144         // Remove vars at indices not in the upper bound
00145         if (iv[i].idx < vx1ub.val()) {
00146           iv[i].view.cancel(home,*this, PC_SET_ANY);
00147           ++i;
00148           continue;
00149         }
00150         assert(iv[i].idx == vx1ub.val());
00151         iv[j] = iv[i];
00152 
00153         SView candidate = iv[j].view;
00154         int candidateInd = iv[j].idx;
00155 
00156         // inter = glb(x0) & complement(lub(candidate))
00157         GlbRanges<RView> x0lb(x0);
00158         LubRanges<SView> candub(candidate);
00159         Iter::Ranges::Diff<GlbRanges<RView>,LubRanges<SView> >
00160           inter(x0lb, candub);
00161 
00162         // exclude inconsistent x_i
00163         // an x_i is inconsistent if
00164         //  * its max cardinality is less than minCard of x0
00165         //  * inter is not empty (there are elements in x_0
00166         //    that can't be in x_i)
00167         if (candidate.cardMax() < x0.cardMin() ||
00168             inter()) {
00169           ModEvent me = (x1.exclude(home,candidateInd));
00170           loopVar |= me_modified(me);
00171           GECODE_ME_CHECK(me);
00172 
00173           iv[j].view.cancel(home,*this, PC_SET_ANY);
00174           ++i;
00175           ++vx1ub;
00176           continue;
00177         } else {
00178           // if x_i is consistent, check whether we know
00179           // that its index is in x1
00180           if (vx1() && vx1.val()==candidateInd) {
00181             // x0 <= candidate, candidate >= x0
00182             GlbRanges<RView> x0lb(x0);
00183             ModEvent me = candidate.includeI(home,x0lb);
00184             loopVar |= me_modified(me);
00185             GECODE_ME_CHECK(me);
00186 
00187             LubRanges<SView> candub(candidate);
00188             me = x0.intersectI(home,candub);
00189             loopVar |= me_modified(me);
00190             GECODE_ME_CHECK(me);
00191             ++vx1;
00192           }
00193           new (&before[j]) LUBndSet(home);
00194           before[j].update(home,sofarBefore);
00195           GlbRanges<SView> clb(candidate);
00196           sofarBefore.intersectI(home,clb);
00197         }
00198 
00199         ++vx1ub;
00200         ++i; ++j;
00201       }
00202 
00203       // cancel the variables with index greater than
00204       // max of lub(x1)
00205       for (int k=i; k<n; k++) {
00206         iv[k].view.cancel(home,*this, PC_SET_ANY);
00207       }
00208       n = j;
00209       iv.size(n);
00210 
00211       if (x1.cardMax()==0) {
00212         // Elementor is empty, hence the result must be universe
00213         {
00214           IntSetRanges uniI(universe);
00215           GECODE_ME_CHECK(x0.includeI(home,uniI));
00216         }
00217         {
00218           IntSetRanges uniI(universe);
00219           GECODE_ME_CHECK(x0.intersectI(home,uniI));
00220         }
00221         for (int i=n; i--;)
00222           before[i].dispose(home);
00223         return home.ES_SUBSUMED(*this);
00224       }
00225 
00226       {
00227         // x0 >= sofarBefore
00228         BndSetRanges sfB(sofarBefore);
00229         ModEvent me = x0.includeI(home,sfB);
00230         loopVar |= me_modified(me);
00231         GECODE_ME_CHECK(me);
00232       }
00233 
00234       sofarBefore.dispose(home);
00235 
00236       LUBndSet sofarAfter(home, universe);
00237 
00238       // In the second iteration, this time backwards, compute
00239       // sofarAfter as the intersection of all glb(x_j) with j>i
00240       for (int i=n; i--;) {
00241         if (sofarAfter.size() == 0) break;
00242 
00243         // extra = inter(before[i], sofarAfter) - lub(x0)
00244         BndSetRanges b(before[i]);
00245         BndSetRanges s(sofarAfter);
00246         LubRanges<RView> x0ub(x0);
00247         Iter::Ranges::Inter<BndSetRanges, BndSetRanges> inter(b,s);
00248         Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00249           BndSetRanges>, LubRanges<RView> > diff(inter, x0ub);
00250         if (diff()) {
00251           ModEvent me = (x1.include(home,iv[i].idx));
00252           loopVar |= me_modified(me);
00253           GECODE_ME_CHECK(me);
00254 
00255           // candidate != extra
00256           me = iv[i].view.excludeI(home,diff);
00257           loopVar |= me_modified(me);
00258           GECODE_ME_CHECK(me);
00259         }
00260 
00261         GlbRanges<SView> ivilb(iv[i].view);
00262         sofarAfter.intersectI(home,ivilb);
00263         before[i].dispose(home);
00264       }
00265       sofarAfter.dispose(home);
00266 
00267     } while (loopVar);
00268 
00269     // Test whether we determined x1 without determining x0
00270     if (x1.assigned() && !x0.assigned()) {
00271       int ubsize = static_cast<int>(x1.lubSize());
00272       if (ubsize > 2) {
00273         assert(ubsize==n);
00274         ViewArray<SView> is(home,ubsize);
00275         for (int i=n; i--;)
00276           is[i]=iv[i].view;
00277         GECODE_REWRITE(*this,(RelOp::IntersectionN<SView, RView>
00278                         ::post(home(*this),is,x0)));
00279       } else if (ubsize == 2) {
00280         assert(n==2);
00281         SView a = iv[0].view;
00282         SView b = iv[1].view;
00283         GECODE_REWRITE(*this,(RelOp::Intersection<SView, SView, RView>
00284                        ::post(home(*this),a,b,x0)));
00285       } else if (ubsize == 1) {
00286         assert(n==1);
00287         GECODE_REWRITE(*this,(Rel::Eq<RView,SView>::post(home(*this),x0,iv[0].view)));
00288       } else {
00289         GECODE_ME_CHECK(x0.cardMax(home, 0));
00290         return home.ES_SUBSUMED(*this);
00291       }
00292     }
00293 
00294     bool allAssigned = true;
00295     for (int i=iv.size(); i--;) {
00296       if (!iv[i].view.assigned()) {
00297         allAssigned = false;
00298         break;
00299       }
00300     }
00301     if (x0.assigned() && x1.assigned() && allAssigned) {
00302       return home.ES_SUBSUMED(*this);
00303     }
00304 
00305     return ES_FIX;
00306   }
00307 
00308 }}}
00309 
00310 // STATISTICS: set-prop