gecode » set » element
disjoint.hpp

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