link-multi.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2007 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10364 $ 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 #include <gecode/int/channel.hh> 00039 00040 namespace Gecode { namespace Int { namespace Channel { 00041 00043 class BoolIter { 00044 private: 00046 const ViewArray<BoolView>& x; 00048 const int o; 00050 int i; 00051 public: 00053 BoolIter(const ViewArray<BoolView>& x0, int o0); 00055 bool operator ()(void) const; 00057 int val(void) const; 00059 void operator ++(void); 00060 }; 00061 00062 forceinline 00063 BoolIter::BoolIter(const ViewArray<BoolView>& x0, int o0) : 00064 x(x0), o(o0), i(0) { 00065 while ((i<x.size()) && !x[i].zero()) 00066 i++; 00067 } 00068 forceinline bool 00069 BoolIter::operator ()(void) const { 00070 return i<x.size(); 00071 } 00072 forceinline int 00073 BoolIter::val(void) const { 00074 assert(x[i].zero()); 00075 return i+o; 00076 } 00077 forceinline void 00078 BoolIter::operator ++(void) { 00079 do { 00080 i++; 00081 } while ((i<x.size()) && !x[i].zero()); 00082 } 00083 00084 00085 forceinline 00086 LinkMulti::LinkMulti(Space& home, bool share, LinkMulti& p) 00087 : MixNaryOnePropagator<BoolView,PC_BOOL_VAL,IntView,PC_INT_DOM> 00088 (home,share,p), o(p.o) {} 00089 00090 Actor* 00091 LinkMulti::copy(Space& home, bool share) { 00092 return new (home) LinkMulti(home,share,*this); 00093 } 00094 00095 PropCost 00096 LinkMulti::cost(const Space&, const ModEventDelta& med) const { 00097 if (IntView::me(med) == ME_INT_VAL) 00098 return PropCost::unary(PropCost::LO); 00099 else 00100 return PropCost::linear(PropCost::LO, x.size()); 00101 } 00102 00103 ExecStatus 00104 LinkMulti::propagate(Space& home, const ModEventDelta& med) { 00105 int n = x.size(); 00106 00107 // Always maintain the invariant that y lies inside the x-array 00108 assert((y.min()-o >= 0) && (y.max()-o < n)); 00109 00110 if (y.assigned()) { 00111 int j=y.val()-o; 00112 GECODE_ME_CHECK(x[j].one(home)); 00113 for (int i=0; i<j; i++) 00114 GECODE_ME_CHECK(x[i].zero(home)); 00115 for (int i=j+1; i<n; i++) 00116 GECODE_ME_CHECK(x[i].zero(home)); 00117 return home.ES_SUBSUMED(*this); 00118 } 00119 00120 redo: 00121 00122 // Assign all Boolean views to zero that are outside bounds 00123 { 00124 int min=y.min()-o; 00125 for (int i=0; i<min; i++) 00126 GECODE_ME_CHECK(x[i].zero(home)); 00127 x.drop_fst(min); o += min; n = x.size(); 00128 00129 int max=y.max()-o; 00130 for (int i=max+1; i<n; i++) 00131 GECODE_ME_CHECK(x[i].zero(home)); 00132 x.drop_lst(max); n = x.size(); 00133 } 00134 00135 { 00136 // Remove zeros on the left 00137 int i=0; 00138 while ((i < n) && x[i].zero()) i++; 00139 if (i >= n) 00140 return ES_FAILED; 00141 x.drop_fst(i); o += i; n = x.size(); 00142 } 00143 00144 { 00145 // Remove zeros on the right 00146 int i=n-1; 00147 while ((i >= 0) && x[i].zero()) i--; 00148 assert(i >= 0); 00149 x.drop_lst(i); n = x.size(); 00150 } 00151 00152 assert(n >= 1); 00153 00154 // Is there only one left? 00155 if (n == 1) { 00156 GECODE_ME_CHECK(x[0].one(home)); 00157 GECODE_ME_CHECK(y.eq(home,o)); 00158 return home.ES_SUBSUMED(*this); 00159 } 00160 00161 // Update bounds 00162 GECODE_ME_CHECK(y.gq(home,o)); 00163 GECODE_ME_CHECK(y.lq(home,o+n-1)); 00164 if ((y.min() > o) || (y.max() < o+n-1)) 00165 goto redo; 00166 00167 // Check whether there is a one somewhere else 00168 for (int i=n; i--; ) 00169 if (x[i].one()) { 00170 for (int j=0; j<i; j++) 00171 GECODE_ME_CHECK(x[j].zero(home)); 00172 for (int j=i+1; j<n; j++) 00173 GECODE_ME_CHECK(x[j].zero(home)); 00174 GECODE_ME_CHECK(y.eq(home,i+o)); 00175 return home.ES_SUBSUMED(*this); 00176 } 00177 00178 assert((n >= 2) && x[0].none() && x[n-1].none()); 00179 assert((y.min()-o == 0) && (y.max()-o == n-1)); 00180 00181 // Propagate from y to Boolean views 00182 if ((IntView::me(med) == ME_INT_BND) || (IntView::me(med) == ME_INT_DOM)) { 00183 ViewValues<IntView> v(y); 00184 int i=0; 00185 do { 00186 int j = v.val()-o; 00187 if (i < j) { 00188 GECODE_ME_CHECK(x[i].zero(home)); 00189 ++i; 00190 } else if (i > j) { 00191 ++v; 00192 } else { 00193 assert(i == j); 00194 ++i; ++v; 00195 } 00196 } while (v() && (i < n)); 00197 } 00198 00199 // Propagate from Boolean views to y 00200 if (BoolView::me(med) == ME_BOOL_VAL) { 00201 BoolIter bv(x,o); 00202 GECODE_ME_CHECK(y.minus_v(home,bv,false)); 00203 } 00204 return ES_FIX; 00205 } 00206 00207 }}} 00208 00209 // STATISTICS: int-prop 00210