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: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00015 * $Revision: 11192 $ 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 = static_cast<unsigned int>(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 forceinline size_t 00092 Match<View>::dispose(Space& home) { 00093 x0.cancel(home,*this, PC_SET_ANY); 00094 xs.cancel(home,*this, Gecode::Int::PC_INT_BND); 00095 (void) Propagator::dispose(home); 00096 return sizeof(*this); 00097 } 00098 00099 template<class View> 00100 Actor* 00101 Match<View>::copy(Space& home, bool share) { 00102 return new (home) Match(home,share,*this); 00103 } 00104 00105 template<class View> 00106 ExecStatus 00107 Match<View>::propagate(Space& home, const ModEventDelta&) { 00108 00109 int xs_size = xs.size(); 00110 00111 bool loopFlag; 00112 00113 do { 00114 loopFlag = false; 00115 00116 // Order int vars in xs 00117 GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin())); 00118 for (int i=xs_size-1; i--; ) { 00119 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i+1].gq(home,xs[i].min() + 1)); 00120 } 00121 00122 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[xs_size-1].lq(home,x0.lubMax())); 00123 for (int i=xs_size-2; i--; ) { 00124 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].lq(home,xs[i+1].max() - 1)); 00125 } 00126 00127 // if y from xs is assigned, add to glb(x0) 00128 for (int i=xs_size; i--; ) { 00129 if (xs[i].assigned()) { 00130 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.include(home,xs[i].val())); 00131 } 00132 } 00133 00134 // intersect every y in xs with lub(x0) 00135 for (int i=xs_size; i--; ) { 00136 LubRanges<View> ub(x0); 00137 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].inter_r(home,ub,false)); 00138 } 00139 00140 // remove gaps between vars in xs from lub(x0) 00141 GECODE_ME_CHECK_MODIFIED(loopFlag, 00142 x0.exclude(home,Limits::min,xs[0].min()-1)); 00143 GECODE_ME_CHECK_MODIFIED(loopFlag, 00144 x0.exclude(home,xs[xs_size-1].max()+1, 00145 Limits::max)); 00146 00147 for (int i=xs_size-1; i--; ) { 00148 int start = xs[i].max() + 1; 00149 int end = xs[i+1].min() - 1; 00150 if (start<=end) { 00151 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.exclude(home,start,end)); 00152 } 00153 } 00154 00155 // try to assign vars in xs from glb(x0) 00156 if (x0.glbSize()>0) { 00157 00158 LubRanges<View> ub(x0); 00159 Iter::Ranges::ToValues<LubRanges<View> > ubv(ub); 00160 GlbRanges<View> lb(x0); 00161 Iter::Ranges::ToValues<GlbRanges<View> > lbv(lb); 00162 00163 int i=0; 00164 for (; ubv() && lbv() && ubv.val()==lbv.val(); 00165 ++ubv, ++lbv, i++) { 00166 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,lbv.val())); 00167 } 00168 00169 if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) { 00170 LubRanges<View> lbx0(x0); 00171 GlbRanges<View> ubx0(x0); 00172 Iter::Ranges::Inter<LubRanges<View>,GlbRanges<View> > 00173 inter(lbx0, ubx0); 00174 00175 int to = x0.glbMax(); 00176 int from = to; 00177 while (inter()) { 00178 from = inter.min(); 00179 ++inter; 00180 } 00181 00182 int i=xs_size-1; 00183 for (int j=to; j>=from;j--,i--) { 00184 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,j)); 00185 } 00186 } 00187 } 00188 00189 } while (loopFlag); 00190 00191 for (int i=xs_size; i--; ) 00192 if (!xs[i].assigned()) 00193 return ES_FIX; 00194 return home.ES_SUBSUMED(*this); 00195 } 00196 00197 }}} 00198 00199 // STATISTICS: set-prop