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

disjoint.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  *  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 SView, class RView>
00039   forceinline
00040   ElementDisjoint<SView,RView>::ElementDisjoint(Home home,
00041                                                 IdxViewArray& iv0,
00042                                                 RView y1)
00043     : Propagator(home), iv(iv0), x1(y1) {
00044 
00045     x1.subscribe(home,*this, PC_SET_ANY);
00046     iv.subscribe(home,*this, PC_SET_ANY);
00047   }
00048 
00049   template<class SView, class RView>
00050   forceinline
00051   ElementDisjoint<SView,RView>::ElementDisjoint(Space& home,
00052                                                 ElementDisjoint& p)
00053     : Propagator(home,p) {
00054     x1.update(home,p.x1);
00055     iv.update(home,p.iv);
00056   }
00057 
00058   template<class SView, class RView>
00059   forceinline ExecStatus
00060   ElementDisjoint<SView,RView>::post(Home home, IdxViewArray& xs,
00061                                      RView x1) {
00062     int n = xs.size();
00063 
00064     // s2 \subseteq {0,...,n-1}
00065     Iter::Ranges::Singleton s(0, n-1);
00066     GECODE_ME_CHECK(x1.intersectI(home,s));
00067     (void) new (home)
00068       ElementDisjoint(home,xs,x1);
00069     return ES_OK;
00070   }
00071 
00072   template<class SView, class RView>
00073   PropCost
00074   ElementDisjoint<SView,RView>::cost(const Space&, const ModEventDelta&) const {
00075     return PropCost::quadratic(PropCost::LO, iv.size()+2);
00076   }
00077 
00078   template<class SView, class RView>
00079   void
00080   ElementDisjoint<SView,RView>::reschedule(Space& home) {
00081     x1.reschedule(home,*this, PC_SET_ANY);
00082     iv.reschedule(home,*this, PC_SET_ANY);
00083   }
00084 
00085   template<class SView, class RView>
00086   forceinline size_t
00087   ElementDisjoint<SView,RView>::dispose(Space& home) {
00088     x1.cancel(home,*this, PC_SET_ANY);
00089     iv.cancel(home,*this,PC_SET_ANY);
00090     (void) Propagator::dispose(home);
00091     return sizeof(*this);
00092   }
00093 
00094   template<class SView, class RView>
00095   Actor*
00096   ElementDisjoint<SView,RView>::copy(Space& home) {
00097     return new (home) ElementDisjoint(home,*this);
00098   }
00099 
00100   template<class SView, class RView>
00101   ExecStatus
00102   ElementDisjoint<SView,RView>::propagate(Space& home, const ModEventDelta&) {
00103     int n = iv.size();
00104 
00105     Region r;
00106 
00107     bool fix_flag = false;
00108     do {
00109       fix_flag = false;
00110       // Compute union of all selected elements' lower bounds
00111       GlbRanges<RView> x1lb(x1);
00112       Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
00113       GLBndSet unionOfSelected(home);
00114       for(int i=0; vx1lb(); ++vx1lb) {
00115         while (iv[i].idx < vx1lb.val()) i++;
00116         GlbRanges<SView> clb(iv[i].view);
00117         unionOfSelected.includeI(home,clb);
00118       }
00119 
00120       {
00121         LubRanges<RView> x1ub(x1);
00122         Iter::Ranges::ToValues<LubRanges<RView> > vx1ub(x1ub);
00123         int i=0;
00124         int j=0;
00125         // Cancel all elements that are no longer in the upper bound
00126         while (vx1ub()) {
00127           if (iv[i].idx < vx1ub.val()) {
00128             iv[i].view.cancel(home,*this, PC_SET_ANY);
00129             i++;
00130             continue;
00131           }
00132           iv[j] = iv[i];
00133           ++vx1ub;
00134           ++i; ++j;
00135         }
00136 
00137         // cancel the variables with index greater than
00138         // max of lub(x1)
00139         for (int k=i; k<n; k++) {
00140           iv[k].view.cancel(home,*this, PC_SET_ANY);
00141         }
00142         n = j;
00143         iv.size(n);
00144       }
00145 
00146       {
00147       UnknownRanges<RView> x1u(x1);
00148       Iter::Ranges::Cache x1uc(r,x1u);
00149       Iter::Ranges::ToValues<Iter::Ranges::Cache>
00150         vx1u(x1uc);
00151       int i=0;
00152       int j=0;
00153       while (vx1u()) {
00154         while (iv[i].idx < vx1u.val()) {
00155           iv[j] = iv[i];
00156           i++; j++;
00157         }
00158         assert(iv[i].idx == vx1u.val());
00159 
00160         SView candidate = iv[i].view;
00161         int candidateInd = iv[i].idx;
00162 
00163         GlbRanges<SView> clb(candidate);
00164         BndSetRanges uos(unionOfSelected);
00165         Iter::Ranges::Inter<GlbRanges<SView>, BndSetRanges>
00166           inter(clb, uos);
00167         if (inter()) {
00168           ModEvent me = x1.exclude(home,candidateInd);
00169           fix_flag |= me_modified(me);
00170           GECODE_ME_CHECK(me);
00171 
00172           candidate.cancel(home,*this, PC_SET_ANY);
00173           ++i;
00174           ++vx1u;
00175           continue;
00176         }
00177         iv[j] = iv[i];
00178         ++vx1u;
00179         ++i; ++j;
00180       }
00181 
00182       unionOfSelected.dispose(home);
00183 
00184       // copy remaining variables
00185       for (int k=i; k<n; k++) {
00186         iv[j] = iv[k];
00187         j++;
00188       }
00189       n = j;
00190       iv.size(n);
00191       }
00192 
00193       if (x1.cardMax()==0) {
00194         // Selector is empty, we're done
00195         return home.ES_SUBSUMED(*this);
00196       }
00197 
00198       {
00199         // remove all elements in a selected variable from
00200         // all other selected variables
00201         GlbRanges<RView> x1lb(x1);
00202         Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
00203         int i=0;
00204         for (; vx1lb(); ++vx1lb) {
00205           while (iv[i].idx < vx1lb.val()) i++;
00206           assert(iv[i].idx==vx1lb.val());
00207           GlbRanges<RView> x1lb2(x1);
00208           Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb2(x1lb2);
00209           for (int j=0; vx1lb2(); ++vx1lb2) {
00210             while (iv[j].idx < vx1lb2.val()) j++;
00211             assert(iv[j].idx==vx1lb2.val());
00212             if (iv[i].idx!=iv[j].idx) {
00213               GlbRanges<SView> xilb(iv[i].view);
00214               ModEvent me = iv[j].view.excludeI(home,xilb);
00215               fix_flag |= me_modified(me);
00216               GECODE_ME_CHECK(me);
00217             }
00218           }
00219         }
00220       }
00221 
00222       // remove all elements from the selector that overlap
00223       // with all other possibly selected elements, if
00224       // at least two more elements need to be selected
00225       if (x1.cardMin()-x1.glbSize() > 1) {
00226         UnknownRanges<RView> x1u(x1);
00227         Iter::Ranges::Cache x1uc(r,x1u);
00228         Iter::Ranges::ToValues<Iter::Ranges::Cache>
00229           vx1u(x1uc);
00230 
00231         for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
00232           int i = 0;
00233           while (iv[i].idx < vx1u.val()) i++;
00234           assert(iv[i].idx == vx1u.val());
00235           bool flag=true;
00236 
00237           UnknownRanges<RView> x1u2(x1);
00238           Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
00239           for (; vx1u2(); ++vx1u2) {
00240             int j = 0;
00241             while (iv[j].idx < vx1u2.val()) j++;
00242             assert(iv[j].idx == vx1u2.val());
00243             if (iv[i].idx!=iv[j].idx) {
00244               GlbRanges<SView> xjlb(iv[j].view);
00245               GlbRanges<SView> xilb(iv[i].view);
00246               Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
00247                 inter(xjlb, xilb);
00248               if (!inter()) {
00249                 flag = false;
00250                 goto here;
00251               }
00252             }
00253           }
00254         here:
00255           if (flag) {
00256             ModEvent me = x1.exclude(home,iv[i].idx);
00257             fix_flag |= me_modified(me);
00258             GECODE_ME_CHECK(me);
00259           }
00260         }
00261       }
00262 
00263       // if exactly two more elements need to be selected
00264       // and there is a possible element i such that all other pairs of
00265       // elements overlap, select i
00266       UnknownRanges<RView> x1u(x1);
00267       Iter::Ranges::Cache x1uc(r,x1u);
00268       Iter::Ranges::ToValues<Iter::Ranges::Cache>
00269         vx1u(x1uc);
00270 
00271       for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
00272         int i = 0;
00273         while (iv[i].idx < vx1u.val()) i++;
00274         assert (iv[i].idx == vx1u.val());
00275         bool flag=true;
00276 
00277         UnknownRanges<RView> x1u2(x1);
00278         Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
00279         for (; vx1u2(); ++vx1u2) {
00280           int j = 0;
00281           while (iv[j].idx < vx1u2.val()) j++;
00282           assert (iv[j].idx == vx1u2.val());
00283           if (iv[i].idx!=iv[j].idx) {
00284             UnknownRanges<RView> x1u3(x1);
00285             Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u3(x1u3);
00286             for (; vx1u3(); ++vx1u3) {
00287               int k = 0;
00288               while (iv[k].idx < vx1u3.val()) k++;
00289               assert (iv[k].idx == vx1u3.val());
00290               if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
00291                 GlbRanges<SView> xjlb(iv[j].view);
00292                 GlbRanges<SView> xilb(iv[k].view);
00293                 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
00294                   inter(xjlb, xilb);
00295                 if (!inter()) {
00296                   flag = false;
00297                   goto here2;
00298                 }
00299               }
00300             }
00301           }
00302         }
00303       here2:
00304         if (flag) {
00305           ModEvent me = x1.include(home,iv[i].idx);
00306           fix_flag |= me_modified(me);
00307           GECODE_ME_CHECK(me);
00308         }
00309       }
00310     } while (fix_flag);
00311 
00312     for (int i=iv.size(); i--;)
00313       if (!iv[i].view.assigned())
00314         return ES_FIX;
00315     if (!x1.assigned())
00316       return ES_FIX;
00317     return home.ES_SUBSUMED(*this);
00318   }
00319 
00320 
00321 }}}
00322 
00323 // STATISTICS: set-prop