Generated on Mon Nov 30 23:53:35 2009 for Gecode by doxygen 1.6.1

match.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  *     Gabor Szokoli <szokoli@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Guido Tack, 2004
00010  *     Christian Schulte, 2004
00011  *     Gabor Szokoli, 2004
00012  *
00013  *  Last modified:
00014  *     $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00015  *     $Revision: 9878 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 
00043 
00044 #include <gecode/set.hh>
00045 #include <gecode/int.hh>
00046 #include <gecode/set/rel.hh>
00047 
00048 namespace Gecode { namespace Set { namespace Int {
00049 
00050   template<class View>
00051   forceinline
00052   Match<View>::Match(Home home, View y0, ViewArray< Gecode::Int::IntView >& ys)
00053     : Propagator(home), x0(y0), xs(ys) {
00054     x0.subscribe(home,*this, PC_SET_ANY);
00055     xs.subscribe(home,*this, Gecode::Int::PC_INT_BND);
00056   }
00057 
00058   template<class View>
00059   forceinline
00060   Match<View>::Match(Space& home, bool share, Match& p)
00061     : Propagator(home,share,p) {
00062     x0.update(home,share,p.x0);
00063     xs.update(home,share,p.xs);
00064   }
00065 
00066   template<class View>
00067   forceinline ExecStatus
00068   Match<View>::post(Home home, View x0, ViewArray<Gecode::Int::IntView>& xs) {
00069     unsigned int xs_size = xs.size();
00070     GECODE_ME_CHECK(x0.cardMin(home,xs_size));
00071     GECODE_ME_CHECK(x0.cardMax(home,xs_size));
00072     if (xs_size==1) {
00073       SingletonView sv(xs[0]);
00074       GECODE_ES_CHECK((Rel::Eq<View,
00075                        SingletonView>::post(home,x0, sv)));
00076     } else {
00077       // Sharing in xs is handled correctly in the propagator:
00078       // if two views in xs are shared, this leads to failure.
00079       (void) new (home) Match(home,x0,xs);
00080     }
00081     return ES_OK;
00082   }
00083 
00084   template<class View>
00085   PropCost
00086   Match<View>::cost(const Space&, const ModEventDelta&) const {
00087     return PropCost::linear(PropCost::LO, xs.size()+1);
00088   }
00089 
00090   template<class View>
00091   size_t
00092   Match<View>::dispose(Space& home) {
00093     assert(!home.failed());
00094     x0.cancel(home,*this, PC_SET_ANY);
00095     xs.cancel(home,*this, Gecode::Int::PC_INT_BND);
00096     (void) Propagator::dispose(home);
00097     return sizeof(*this);
00098   }
00099 
00100   template<class View>
00101   Actor*
00102   Match<View>::copy(Space& home, bool share) {
00103     return new (home) Match(home,share,*this);
00104   }
00105 
00106   template<class View>
00107   ExecStatus
00108   Match<View>::propagate(Space& home, const ModEventDelta&) {
00109 
00110     int xs_size = xs.size();
00111 
00112     bool loopFlag;
00113 
00114     do {
00115       loopFlag = false;
00116 
00117       // Order int vars in xs
00118       GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin()));
00119       for (int i=xs_size-1; i--; ) {
00120         GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i+1].gq(home,xs[i].min() + 1));
00121       }
00122 
00123       GECODE_ME_CHECK_MODIFIED(loopFlag, xs[xs_size-1].lq(home,x0.lubMax()));
00124       for (int i=xs_size-2; i--; ) {
00125         GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].lq(home,xs[i+1].max() - 1));
00126       }
00127 
00128       // if y from xs is assigned, add to glb(x0)
00129       for (int i=xs_size; i--; ) {
00130         if (xs[i].assigned()) {
00131           GECODE_ME_CHECK_MODIFIED(loopFlag, x0.include(home,xs[i].val()));
00132         }
00133       }
00134 
00135       // intersect every y in xs with lub(x0)
00136       for (int i=xs_size; i--; ) {
00137         LubRanges<View> ub(x0);
00138         GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].inter_r(home,ub,false));
00139       }
00140 
00141       // remove gaps between vars in xs from lub(x0)
00142       GECODE_ME_CHECK_MODIFIED(loopFlag,
00143                         x0.exclude(home,Limits::min,xs[0].min()-1));
00144       GECODE_ME_CHECK_MODIFIED(loopFlag,
00145                         x0.exclude(home,xs[xs_size-1].max()+1,
00146                                    Limits::max));
00147 
00148       for (int i=xs_size-1; i--; ) {
00149         int start = xs[i].max() + 1;
00150         int end   = xs[i+1].min() - 1;
00151         if (start<=end) {
00152           GECODE_ME_CHECK_MODIFIED(loopFlag, x0.exclude(home,start,end));
00153         }
00154       }
00155 
00156       // try to assign vars in xs from glb(x0)
00157       if (x0.glbSize()>0) {
00158 
00159         LubRanges<View> ub(x0);
00160         Iter::Ranges::ToValues<LubRanges<View> > ubv(ub);
00161         GlbRanges<View> lb(x0);
00162         Iter::Ranges::ToValues<GlbRanges<View> > lbv(lb);
00163 
00164         int i=0;
00165         for (; ubv() && lbv() && ubv.val()==lbv.val();
00166             ++ubv, ++lbv, i++) {
00167           GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,lbv.val()));
00168         }
00169 
00170         if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) {
00171           LubRanges<View> lbx0(x0);
00172           GlbRanges<View> ubx0(x0);
00173           Iter::Ranges::Inter<LubRanges<View>,GlbRanges<View> >
00174             inter(lbx0, ubx0);
00175 
00176           int to = x0.glbMax();
00177           int from = to;
00178           while (inter()) {
00179             from = inter.min();
00180             ++inter;
00181           }
00182 
00183           int i=xs_size-1;
00184           for (int j=to; j>=from;j--,i--) {
00185             GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,j));
00186           }
00187         }
00188       }
00189 
00190     } while (loopFlag);
00191 
00192     for (int i=xs_size; i--; )
00193       if (!xs[i].assigned())
00194         return ES_FIX;
00195     return ES_SUBSUMED(*this,home);
00196   }
00197 
00198 }}}
00199 
00200 // STATISTICS: set-prop