Generated on Mon May 5 05:54:04 2008 for Gecode by doxygen 1.5.5

inter.icc

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: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
00013  *     $Revision: 6017 $
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 Select {
00041 
00042   template <class SView, class RView>
00043   forceinline
00044   SelectIntersection<SView,RView>::
00045   SelectIntersection(Space* home, SView y0,
00046                      IdxViewArray<SView>& iv0,
00047                      RView y1,
00048                      const IntSet& theUniverse)
00049     : Propagator(home), universe(theUniverse), x0(y0), iv(iv0), x1(y1) {
00050     force(home);
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   SelectIntersection<SView,RView>::
00059   SelectIntersection(Space* home, bool share,
00060                      SelectIntersection<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   SelectIntersection<SView,RView>::cost(ModEventDelta) const {
00071     return PC_LINEAR_HI;
00072   }
00073 
00074   template <class SView, class RView>
00075   Support::Symbol
00076   SelectIntersection<SView,RView>::ati(void) {
00077     return Reflection::mangle<SView,RView>("Gecode::Set::Select::Intersection");
00078   }
00079 
00080   template <class SView, class RView>
00081   Reflection::ActorSpec
00082   SelectIntersection<SView,RView>::spec(const Space* home,
00083                                         Reflection::VarMap& m) const {
00084     Reflection::ActorSpec s(ati());
00085     int count = 0;
00086     for (IntSetRanges ur(universe); ur(); ++ur)
00087       count++;
00088     Reflection::IntArrayArg* a = Reflection::Arg::newIntArray(count*2);
00089     count = 0;
00090     for (IntSetRanges ur(universe); ur(); ++ur) {
00091       (*a)[count++] = ur.min();
00092       (*a)[count++] = ur.max();
00093     }
00094     return s << a
00095              << x0.spec(home, m)
00096              << iv.spec(home, m)
00097              << x1.spec(home, m);
00098   }
00099 
00100   template <class SView, class RView>
00101   void
00102   SelectIntersection<SView,RView>::post(Space* home,
00103                                         Reflection::VarMap& vars,
00104                                         const Reflection::ActorSpec& spec) {
00105     spec.checkArity(4);
00106     Reflection::IntArrayArgRanges ur(spec[0]->toIntArray());
00107     IntSet universe(ur);
00108     SView x0(home, vars, spec[1]);
00109     IdxViewArray<SView> iv(home, vars, spec[2]);
00110     RView x1(home, vars, spec[3]);
00111     (void) new (home) SelectIntersection(home, x0, iv, x1, universe);
00112   }
00113 
00114   template <class SView, class RView>
00115   size_t
00116   SelectIntersection<SView,RView>::dispose(Space* home) {
00117     unforce(home);
00118     if (!home->failed()) {
00119       x0.cancel(home,this, PC_SET_ANY);
00120       x1.cancel(home,this, PC_SET_ANY);
00121       iv.cancel(home,this,PC_SET_ANY);
00122     }
00123     universe.~IntSet();
00124     (void) Propagator::dispose(home);
00125     return sizeof(*this);
00126   }
00127 
00128   template <class SView, class RView>
00129   ExecStatus
00130   SelectIntersection<SView,RView>::
00131   post(Space* home, SView x0, IdxViewArray<SView>& xs,
00132        RView x1, const IntSet& universe) {
00133     int n = xs.size();
00134 
00135     // s2 \subseteq {1,...,n}
00136     Iter::Ranges::Singleton s(0, n-1);
00137     GECODE_ME_CHECK(x1.intersectI(home,s));
00138     (void) new (home)
00139       SelectIntersection<SView,RView>(home,x0,xs,x1,universe);
00140     return ES_OK;
00141   }
00142 
00143   template <class SView, class RView>
00144   Actor*
00145   SelectIntersection<SView,RView>::copy(Space* home, bool share) {
00146     return new (home) SelectIntersection<SView,RView>(home,share,*this);
00147   }
00148 
00149   template <class SView, class RView>
00150   ExecStatus
00151   SelectIntersection<SView,RView>::propagate(Space* home, ModEventDelta) {
00152     int n = iv.size();
00153 
00154     bool loopVar;
00155     do {
00156       loopVar = false;
00157 
00158       // Cache the upper bound iterator, as we have to
00159       // modify the upper bound while iterating
00160       LubRanges<RView> x1ub(x1);
00161       Iter::Ranges::Cache<LubRanges<RView> > x1ubc(x1ub);
00162       Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > >
00163         vx1ub(x1ubc);
00164 
00165       GlbRanges<RView> x1lb(x1);
00166       Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(x1lb);
00167       Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > >
00168         vx1(x1lbc);
00169 
00170       // In the first iteration, compute in before[i] the intersection
00171       // of all the lower bounds of the x_i. At the same time,
00172       // exclude inconsistent x_i from x1 and remove them from
00173       // the list, cancel their dependencies.
00174 
00175       LUBndSet sofarBefore(home,universe);
00176       GECODE_AUTOARRAY(LUBndSet, before, n);
00177 
00178       int j = 0;
00179       int i = 0;
00180       while ( vx1ub() ) {
00181 
00182         // Remove vars at indices not in the upper bound
00183         if (iv[i].idx < vx1ub.val()) {
00184           iv[i].var.cancel(home,this, PC_SET_ANY);
00185           ++i;
00186           continue;
00187         }
00188         assert(iv[i].idx == vx1ub.val());
00189         iv[j] = iv[i];
00190 
00191         SView candidate = iv[j].var;
00192         int candidateInd = iv[j].idx;
00193 
00194         // inter = glb(x0) & complement(lub(candidate))
00195         GlbRanges<SView> x0lb(x0);
00196         LubRanges<SView> candub(candidate);
00197         RangesCompl<LubRanges<SView> > candubc(candub);
00198         Iter::Ranges::Inter<GlbRanges<SView>,
00199           RangesCompl<LubRanges<SView> > > inter(x0lb, candubc);
00200 
00201         // exclude inconsistent x_i
00202         // an x_i is inconsistent if
00203         //  * its max cardinality is less than minCard of x0
00204         //  * inter is not empty (there are elements in x_0
00205         //    that can't be in x_i)
00206         if (candidate.cardMax() < x0.cardMin() ||
00207             inter()) {
00208           ModEvent me = (x1.exclude(home,candidateInd));
00209           loopVar |= me_modified(me);
00210           GECODE_ME_CHECK(me);
00211 
00212           iv[j].var.cancel(home,this, PC_SET_ANY);
00213           ++i;
00214           ++vx1ub;
00215           continue;
00216         } else {
00217           // if x_i is consistent, check whether we know
00218           // that its index is in x1
00219           if (vx1() && vx1.val()==candidateInd) {
00220             // x0 <= candidate, candidate >= x0
00221             GlbRanges<SView> x0lb(x0);
00222             ModEvent me = candidate.includeI(home,x0lb);
00223             loopVar |= me_modified(me);
00224             GECODE_ME_CHECK(me);
00225 
00226             LubRanges<SView> candub(candidate);
00227             me = x0.intersectI(home,candub);
00228             loopVar |= me_modified(me);
00229             GECODE_ME_CHECK(me);
00230             ++vx1;
00231           }
00232           new (&before[j]) LUBndSet(home);
00233           before[j].update(home,sofarBefore);
00234           GlbRanges<SView> clb(candidate);
00235           sofarBefore.intersectI(home,clb);
00236         }
00237 
00238         ++vx1ub;
00239         ++i; ++j;
00240       }
00241 
00242       // cancel the variables with index greater than
00243       // max of lub(x1)
00244       for (int k=i; k<n; k++) {
00245         iv[k].var.cancel(home,this, PC_SET_ANY);
00246       }
00247       n = j;
00248       iv.size(n);
00249 
00250       if (x1.cardMax()==0) {
00251         // Selector is empty, hence the result must be universe
00252         {
00253           IntSetRanges uniI(universe);
00254           GECODE_ME_CHECK(x0.includeI(home,uniI));
00255         }
00256         {
00257           IntSetRanges uniI(universe);
00258           GECODE_ME_CHECK(x0.intersectI(home,uniI));
00259         }
00260         for (int i=n; i--;)
00261           before[i].dispose(home);
00262         return ES_SUBSUMED(this,home);
00263       }
00264 
00265       {
00266         // x0 >= sofarBefore
00267         BndSetRanges sfB(sofarBefore);
00268         ModEvent me = x0.includeI(home,sfB);
00269         loopVar |= me_modified(me);
00270         GECODE_ME_CHECK(me);
00271       }
00272 
00273       sofarBefore.dispose(home);
00274 
00275       LUBndSet sofarAfter(home, universe);
00276 
00277       // In the second iteration, this time backwards, compute
00278       // sofarAfter as the intersection of all glb(x_j) with j>i
00279       for (int i=n; i--;) {
00280         if (sofarAfter.size() == 0) break;
00281         
00282         // extra = inter(before[i], sofarAfter) - lub(x0)
00283         BndSetRanges b(before[i]);
00284         BndSetRanges s(sofarAfter);
00285         LubRanges<SView> x0ub(x0);
00286         Iter::Ranges::Inter<BndSetRanges, BndSetRanges> inter(b,s);
00287         Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00288           BndSetRanges>, LubRanges<SView> > diff(inter, x0ub);
00289         if (diff()) {
00290           ModEvent me = (x1.include(home,iv[i].idx));
00291           loopVar |= me_modified(me);
00292           GECODE_ME_CHECK(me);
00293 
00294           // candidate != extra
00295           me = iv[i].var.excludeI(home,diff);
00296           loopVar |= me_modified(me);
00297           GECODE_ME_CHECK(me);
00298         }
00299 
00300         GlbRanges<SView> ivilb(iv[i].var);
00301         sofarAfter.intersectI(home,ivilb);
00302         before[i].dispose(home);
00303       }
00304       sofarAfter.dispose(home);
00305 
00306     } while (loopVar);
00307 
00308     // Test whether we determined x1 without determining x0
00309     if (x1.assigned() && !x0.assigned()) {
00310       int ubsize = x1.lubSize();
00311       if (ubsize > 2) {
00312         assert(ubsize==n);
00313         ViewArray<SView> is(home,ubsize);
00314         for (int i=n; i--;)
00315           is[i]=iv[i].var;
00316         GECODE_REWRITE(this,(RelOp::IntersectionN<SView, SView>
00317                         ::post(home,is,x0)));
00318       } else if (ubsize == 2) {
00319         assert(n==2);
00320         SView a = iv[0].var;
00321         SView b = iv[1].var;
00322         GECODE_REWRITE(this,(RelOp::Intersection<SView, SView, SView>
00323                        ::post(home,a,b,x0)));
00324       } else if (ubsize == 1) {
00325         assert(n==1);
00326         GECODE_REWRITE(this,(Rel::Eq<SView,SView>::post(home,x0,iv[0].var)));
00327       } else {
00328         GECODE_ME_CHECK(x0.cardMax(home, 0));
00329         return ES_SUBSUMED(this,home);
00330       }
00331     }
00332 
00333     bool allAssigned = true;
00334     for (int i=iv.size(); i--;) {
00335       if (!iv[i].var.assigned()) {
00336         allAssigned = false;
00337         break;
00338       }
00339     }
00340     if (x0.assigned() && x1.assigned() && allAssigned) {
00341       return ES_SUBSUMED(this,home);
00342     }
00343 
00344     return ES_FIX;
00345   }
00346 
00347 }}}
00348 
00349 // STATISTICS: set-prop