Generated on Tue Jul 27 2010 21:59:18 for Gecode by doxygen 1.7.1

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