Generated on Tue May 22 09:40:14 2018 for Gecode by doxygen 1.6.3

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