val.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * Guido Tack <tack@gecode.org> 00009 * 00010 * Copyright: 00011 * Patrick Pekczynski, 2005 00012 * Christian Schulte, 2009 00013 * Guido Tack, 2009 00014 * 00015 * Last modified: 00016 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00017 * $Revision: 11192 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 */ 00042 00043 namespace Gecode { namespace Int { namespace GCC { 00044 00045 template<class Card> 00046 forceinline 00047 Val<Card>::Val(Home home, 00048 ViewArray<IntView>& x0, ViewArray<Card>& k0) 00049 : Propagator(home), x(x0), k(k0){ 00050 x.subscribe(home, *this, PC_INT_VAL); 00051 k.subscribe(home, *this, PC_INT_VAL); 00052 } 00053 00054 template<class Card> 00055 forceinline 00056 Val<Card>::Val(Space& home, bool share, Val<Card>& p) 00057 : Propagator(home,share,p) { 00058 x.update(home,share, p.x); 00059 k.update(home,share, p.k); 00060 } 00061 00062 template<class Card> 00063 forceinline size_t 00064 Val<Card>::dispose(Space& home) { 00065 x.cancel(home,*this, PC_INT_VAL); 00066 k.cancel(home,*this, PC_INT_VAL); 00067 (void) Propagator::dispose(home); 00068 return sizeof(*this); 00069 } 00070 00071 template<class Card> 00072 Actor* 00073 Val<Card>::copy(Space& home, bool share) { 00074 return new (home) Val<Card>(home,share,*this); 00075 } 00076 00077 template<class Card> 00078 PropCost 00079 Val<Card>::cost(const Space&, const ModEventDelta&) const { 00080 /* 00081 * Complexity depends on the time needed for value lookup in \a k 00082 * which is O(n log n). 00083 */ 00084 return PropCost::linear(PropCost::HI,x.size()); 00085 } 00086 00087 template<class Card> 00088 ExecStatus 00089 prop_val(Space& home, Propagator& p, 00090 ViewArray<IntView>& x, ViewArray<Card>& k) { 00091 assert(x.size() > 0); 00092 00093 Region r(home); 00094 // count[i] denotes how often value k[i].card() occurs in x 00095 int* count = r.alloc<int>(k.size()); 00096 00097 // initialization 00098 int sum_min = 0; 00099 int removed = 0; 00100 for (int i = k.size(); i--; ) { 00101 removed += k[i].counter(); 00102 sum_min += k[i].min(); 00103 count[i] = 0; 00104 } 00105 00106 // less than or equal than the total number of free variables 00107 // to satisfy the required occurences 00108 for (int i = k.size(); i--; ) 00109 GECODE_ME_CHECK(k[i].lq(home, x.size()+removed-(sum_min - k[i].min()))); 00110 00111 // number of unassigned views 00112 int non = x.size(); 00113 00114 for (int i = x.size(); i--; ) 00115 if (x[i].assigned()) { 00116 int idx; 00117 if (!lookupValue(k,x[i].val(),idx)) { 00118 return ES_FAILED; 00119 } 00120 count[idx]++; 00121 non--; 00122 } 00123 00124 // check for subsumption 00125 if (non == 0) { 00126 for (int i = k.size(); i--; ) 00127 GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter()))); 00128 return home.ES_SUBSUMED(p); 00129 } 00130 00131 // total number of unsatisfied miminum occurences 00132 int req = 0; 00133 // number of values whose min requirements are not yet met 00134 int n_r = 0; 00135 // if only one value is unsatisified single holds the index of that value 00136 int single = -1; 00137 // total number of assigned views wrt. the original probem size 00138 int t_noa = 0; 00139 00140 for (int i = k.size(); i--; ) { 00141 int ci = count[i] + k[i].counter(); 00142 t_noa += ci; 00143 if (ci == 0) { // this works 00144 req += k[i].min(); 00145 n_r++; 00146 single = i; 00147 } 00148 00149 // number of unassigned views cannot satisfy 00150 // the required minimum occurence 00151 if (req > non) { 00152 return ES_FAILED; 00153 } 00154 } 00155 00156 // if only one unsatisfied occurences is left 00157 if ((req == non) && (n_r == 1)) { 00158 // This works as the x are not shared! 00159 for (int i = x.size(); i--; ) { 00160 // try to assign it 00161 if (!x[i].assigned()) { 00162 GECODE_ME_CHECK(x[i].eq(home, k[single].card())); 00163 assert((single >= 0) && (single < k.size())); 00164 count[single]++; 00165 } 00166 } 00167 assert((single >= 0) && (single < k.size())); 00168 00169 for (int i = k.size(); i--; ) 00170 GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter())); 00171 return home.ES_SUBSUMED(p); 00172 } 00173 00174 // Bitset for indexes that can be removed 00175 Support::BitSet<Region> rem(r,static_cast<unsigned int>(k.size())); 00176 00177 for (int i = k.size(); i--; ) { 00178 int ci = count[i] + k[i].counter(); 00179 if (ci == k[i].max()) { 00180 assert(!rem.get(i)); 00181 rem.set(static_cast<unsigned int>(i)); 00182 k[i].counter(ci); 00183 // the solution contains ci occurences of value k[i].card(); 00184 GECODE_ME_CHECK(k[i].eq(home, ci)); 00185 } else { 00186 if (ci > k[i].max()) { 00187 return ES_FAILED; 00188 } 00189 00190 // in case of variable cardinalities 00191 if (Card::propagate) { 00192 GECODE_ME_CHECK(k[i].gq(home, ci)); 00193 int occupied = t_noa - ci; 00194 GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied)); 00195 } 00196 } 00197 // reset counter 00198 count[i] = 0; 00199 } 00200 00201 // reduce the problem size 00202 { 00203 int n_x = x.size(); 00204 for (int i = n_x; i--; ) { 00205 if (x[i].assigned()) { 00206 int idx; 00207 if (!lookupValue(k,x[i].val(),idx)) { 00208 return ES_FAILED; 00209 } 00210 if (rem.get(static_cast<unsigned int>(idx))) 00211 x[i]=x[--n_x]; 00212 } 00213 } 00214 x.size(n_x); 00215 } 00216 00217 // remove values 00218 { 00219 // Values to prune 00220 int* p = r.alloc<int>(k.size()); 00221 // Number of values to prune 00222 int n_p = 0; 00223 for (Iter::Values::BitSet<Support::BitSet<Region> > i(rem); i(); ++i) 00224 p[n_p++] = k[i.val()].card(); 00225 Support::quicksort(p,n_p); 00226 for (int i = x.size(); i--;) { 00227 Iter::Values::Array pi(p,n_p); 00228 GECODE_ME_CHECK(x[i].minus_v(home, pi, false)); 00229 } 00230 } 00231 00232 { 00233 bool all_assigned = true; 00234 00235 for (int i = x.size(); i--; ) { 00236 if (x[i].assigned()) { 00237 int idx; 00238 if (!lookupValue(k,x[i].val(),idx)) { 00239 return ES_FAILED; 00240 } 00241 count[idx]++; 00242 } else { 00243 all_assigned = false; 00244 } 00245 } 00246 00247 if (all_assigned) { 00248 for (int i = k.size(); i--; ) 00249 GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter()))); 00250 return home.ES_SUBSUMED(p); 00251 } 00252 } 00253 00254 if (Card::propagate) { 00255 // check again consistency of cardinalities 00256 int reqmin = 0; 00257 int allmax = 0; 00258 for (int i = k.size(); i--; ) { 00259 if (k[i].counter() > k[i].max()) { 00260 return ES_FAILED; 00261 } 00262 allmax += k[i].max() - k[i].counter(); 00263 if (k[i].counter() < k[i].min()) 00264 reqmin += k[i].min() - k[i].counter(); 00265 GECODE_ME_CHECK((k[i].lq(home, x.size()+k[i].counter()))); 00266 } 00267 00268 if ((x.size() < reqmin) || (allmax < x.size())) { 00269 return ES_FAILED; 00270 } 00271 } 00272 00273 return ES_NOFIX; 00274 } 00275 00276 template<class Card> 00277 ExecStatus 00278 Val<Card>::propagate(Space& home, const ModEventDelta&) { 00279 return prop_val<Card>(home, *this, x, k); 00280 } 00281 00282 template<class Card> 00283 ExecStatus 00284 Val<Card>::post(Home home, 00285 ViewArray<IntView>& x, ViewArray<Card>& k) { 00286 GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k))); 00287 00288 if (isDistinct<Card>(home,x,k)) 00289 return Distinct::Val<IntView>::post(home,x); 00290 00291 (void) new (home) Val<Card>(home,x,k); 00292 return ES_OK; 00293 } 00294 00295 00296 }}} 00297 00298 // STATISTICS: int-prop 00299