basic.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * Mikael Lagerkvist, 2007 00011 * Christian Schulte, 2008 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 namespace Gecode { namespace Int { namespace Extensional { 00043 00044 /* 00045 * The propagator proper 00046 * 00047 */ 00048 00049 template<class View, bool shared> 00050 forceinline 00051 Basic<View,shared>::Basic(Home home, ViewArray<View>& x, 00052 const TupleSet& t) 00053 : Base<View>(home,x,t) { 00054 } 00055 00056 template<class View, bool shared> 00057 forceinline ExecStatus 00058 Basic<View,shared>::post(Home home, ViewArray<View>& x, 00059 const TupleSet& t) { 00060 // All variables in the correct domain 00061 for (int i = x.size(); i--; ) { 00062 GECODE_ME_CHECK(x[i].gq(home, t.min())); 00063 GECODE_ME_CHECK(x[i].lq(home, t.max())); 00064 } 00065 (void) new (home) Basic<View,shared>(home,x,t); 00066 return ES_OK; 00067 } 00068 00069 template<class View, bool shared> 00070 forceinline 00071 Basic<View,shared>::Basic(Space& home, bool share, Basic<View,shared>& p) 00072 : Base<View>(home,share,p) { 00073 } 00074 00075 template<class View, bool shared> 00076 PropCost 00077 Basic<View,shared>::cost(const Space&, const ModEventDelta& med) const { 00078 if (View::me(med) == ME_INT_VAL) 00079 return PropCost::quadratic(PropCost::HI,x.size()); 00080 else 00081 return PropCost::cubic(PropCost::HI,x.size()); 00082 } 00083 00084 template<class View, bool shared> 00085 Actor* 00086 Basic<View,shared>::copy(Space& home, bool share) { 00087 return new (home) Basic<View,shared>(home,share,*this); 00088 } 00089 00090 template<class View, bool shared> 00091 ExecStatus 00092 Basic<View,shared>::propagate(Space& home, const ModEventDelta&) { 00093 // Set up datastructures 00094 00095 // Bit-sets for amortized O(1) access to domains 00096 Region r(home); 00097 BitSet* dom = r.alloc<BitSet>(x.size()); 00098 init_dom(home, dom); 00099 00100 // Bit-sets for processed values. 00101 BitSet* has_support = r.alloc<BitSet>(x.size()); 00102 for (int i = x.size(); i--; ) 00103 has_support[i].init(home, ts()->domsize); 00104 00105 00106 // Values to prune 00107 Support::StaticStack<int,Region> nq(r,static_cast<int>(ts()->domsize)); 00108 00109 // Run algorithm 00110 00111 // Check consistency for each view-value pair 00112 for (int i = x.size(); i--; ) { 00113 for (ViewValues<View> vv(x[i]); vv(); ++vv) { 00114 // Value offset for indexing 00115 int val = vv.val() - ts()->min; 00116 if (!has_support[i].get(static_cast<unsigned int>(val))) { 00117 // Find support for value vv.val() in view 00118 Tuple l = find_support(dom, i, val); 00119 if (l == NULL) { 00120 // No possible supports left 00121 nq.push(vv.val()); 00122 } else { 00123 // Mark values as supported 00124 // Only forward direction marking is needed since all 00125 // previous values have been checked 00126 for (int j = i; j--; ) { 00127 has_support[j].set(static_cast<unsigned int>(l[j]- ts()->min)); 00128 assert(has_support[j].get(l[j] - ts()->min)); 00129 } 00130 } 00131 } 00132 } 00133 00134 // Prune values for x[i] which do not have support anymore 00135 while (!nq.empty()) 00136 GECODE_ME_CHECK(x[i].nq(home,nq.pop())); 00137 } 00138 00139 for (int i = x.size(); i--; ) 00140 if (!x[i].assigned()) 00141 return shared ? ES_NOFIX : ES_FIX; 00142 return home.ES_SUBSUMED(*this); 00143 } 00144 00145 }}} 00146 00147 // STATISTICS: int-prop 00148