eq.hpp
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, 2004 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 namespace Gecode { namespace Int { namespace Bool { 00039 00040 template<class BVA, class BVB> 00041 forceinline 00042 Eq<BVA,BVB>::Eq(Home home, BVA b0, BVB b1) 00043 : BoolBinary<BVA,BVB>(home,b0,b1) {} 00044 00045 template<class BVA, class BVB> 00046 forceinline 00047 Eq<BVA,BVB>::Eq(Space& home, bool share, Eq<BVA,BVB>& p) 00048 : BoolBinary<BVA,BVB>(home,share,p) {} 00049 00050 template<class BVA, class BVB> 00051 forceinline 00052 Eq<BVA,BVB>::Eq(Space& home, bool share, Propagator& p, 00053 BVA b0, BVB b1) 00054 : BoolBinary<BVA,BVB>(home,share,p,b0,b1) {} 00055 00056 template<class BVA, class BVB> 00057 Actor* 00058 Eq<BVA,BVB>::copy(Space& home, bool share) { 00059 return new (home) Eq<BVA,BVB>(home,share,*this); 00060 } 00061 00062 template<class BVA, class BVB> 00063 inline ExecStatus 00064 Eq<BVA,BVB>::post(Home home, BVA b0, BVB b1) { 00065 switch (bool_test(b0,b1)) { 00066 case BT_SAME: return ES_OK; 00067 case BT_COMP: return ES_FAILED; 00068 case BT_NONE: 00069 if (b0.zero()) { 00070 GECODE_ME_CHECK(b1.zero(home)); 00071 } else if (b0.one()) { 00072 GECODE_ME_CHECK(b1.one(home)); 00073 } else if (b1.zero()) { 00074 GECODE_ME_CHECK(b0.zero(home)); 00075 } else if (b1.one()) { 00076 GECODE_ME_CHECK(b0.one(home)); 00077 } else { 00078 (void) new (home) Eq<BVA,BVB>(home,b0,b1); 00079 } 00080 break; 00081 default: GECODE_NEVER; 00082 } 00083 return ES_OK; 00084 } 00085 00086 template<class BVA, class BVB> 00087 ExecStatus 00088 Eq<BVA,BVB>::propagate(Space& home, const ModEventDelta&) { 00089 #define GECODE_INT_STATUS(S0,S1) \ 00090 ((BVA::S0<<(1*BVA::BITS))|(BVB::S1<<(0*BVB::BITS))) 00091 switch ((x0.status() << (1*BVA::BITS)) | (x1.status() << (0*BVB::BITS))) { 00092 case GECODE_INT_STATUS(NONE,NONE): 00093 GECODE_NEVER; 00094 case GECODE_INT_STATUS(NONE,ZERO): 00095 GECODE_ME_CHECK(x0.zero_none(home)); break; 00096 case GECODE_INT_STATUS(NONE,ONE): 00097 GECODE_ME_CHECK(x0.one_none(home)); break; 00098 case GECODE_INT_STATUS(ZERO,NONE): 00099 GECODE_ME_CHECK(x1.zero_none(home)); break; 00100 case GECODE_INT_STATUS(ZERO,ZERO): 00101 break; 00102 case GECODE_INT_STATUS(ZERO,ONE): 00103 return ES_FAILED; 00104 case GECODE_INT_STATUS(ONE,NONE): 00105 GECODE_ME_CHECK(x1.one_none(home)); break; 00106 case GECODE_INT_STATUS(ONE,ZERO): 00107 return ES_FAILED; 00108 case GECODE_INT_STATUS(ONE,ONE): 00109 break; 00110 default: 00111 GECODE_NEVER; 00112 } 00113 return home.ES_SUBSUMED(*this); 00114 #undef GECODE_INT_STATUS 00115 } 00116 00117 template<class BV> 00118 forceinline 00119 NaryEq<BV>::NaryEq(Home home, ViewArray<BV>& x) 00120 : NaryPropagator<BV,PC_BOOL_VAL>(home,x) {} 00121 00122 template<class BV> 00123 forceinline 00124 NaryEq<BV>::NaryEq(Space& home, bool share, NaryEq<BV>& p) 00125 : NaryPropagator<BV,PC_BOOL_VAL>(home,share,p) {} 00126 00127 template<class BV> 00128 Actor* 00129 NaryEq<BV>::copy(Space& home, bool share) { 00130 return new (home) NaryEq<BV>(home,share,*this); 00131 } 00132 00133 template<class BV> 00134 inline ExecStatus 00135 NaryEq<BV>::post(Home home, ViewArray<BV>& x) { 00136 x.unique(home); 00137 int n = x.size(); 00138 if (n < 2) 00139 return ES_OK; 00140 if (n == 2) 00141 return Eq<BV,BV>::post(home,x[0],x[1]); 00142 for (int i=n; i--; ) 00143 if (x[i].assigned()) { 00144 if (x[i].one()) { 00145 for (int j=i; j--; ) 00146 GECODE_ME_CHECK(x[j].one(home)); 00147 for (int j=i+1; j<n; j++) 00148 GECODE_ME_CHECK(x[j].one_none(home)); 00149 } else { 00150 for (int j=i; j--; ) 00151 GECODE_ME_CHECK(x[j].zero(home)); 00152 for (int j=i+1; j<n; j++) 00153 GECODE_ME_CHECK(x[j].zero_none(home)); 00154 } 00155 return ES_OK; 00156 } 00157 (void) new (home) NaryEq<BV>(home,x); 00158 return ES_OK; 00159 } 00160 00161 template<class BV> 00162 PropCost 00163 NaryEq<BV>::cost(const Space&, const ModEventDelta&) const { 00164 return PropCost::unary(PropCost::LO); 00165 } 00166 00167 template<class BV> 00168 ExecStatus 00169 NaryEq<BV>::propagate(Space& home, const ModEventDelta&) { 00170 int n=x.size(); 00171 int i=0; 00172 while (true) { 00173 if (x[i].assigned()) { 00174 if (x[i].one()) { 00175 for (int j=0; j<i; j++) 00176 GECODE_ME_CHECK(x[j].one_none(home)); 00177 for (int j=i+1; j<n; j++) 00178 GECODE_ME_CHECK(x[j].one(home)); 00179 } else { 00180 for (int j=0; j<i; j++) 00181 GECODE_ME_CHECK(x[j].zero_none(home)); 00182 for (int j=i+1; j<n; j++) 00183 GECODE_ME_CHECK(x[j].zero(home)); 00184 } 00185 return home.ES_SUBSUMED(*this); 00186 } 00187 i++; 00188 } 00189 GECODE_NEVER; 00190 return ES_FIX; 00191 } 00192 00193 }}} 00194 00195 // STATISTICS: int-prop 00196