1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Guido Tack <tack@gecode.org> 5 * Christian Schulte <schulte@gecode.org> 6 * 7 * Contributing authors: 8 * Gabor Szokoli <szokoli@gecode.org> 9 * 10 * Copyright: 11 * Guido Tack, 2004 12 * Christian Schulte, 2004 13 * Gabor Szokoli, 2004 14 * 15 * This file is part of Gecode, the generic constraint 16 * development environment: 17 * http://www.gecode.org 18 * 19 * Permission is hereby granted, free of charge, to any person obtaining 20 * a copy of this software and associated documentation files (the 21 * "Software"), to deal in the Software without restriction, including 22 * without limitation the rights to use, copy, modify, merge, publish, 23 * distribute, sublicense, and/or sell copies of the Software, and to 24 * permit persons to whom the Software is furnished to do so, subject to 25 * the following conditions: 26 * 27 * The above copyright notice and this permission notice shall be 28 * included in all copies or substantial portions of the Software. 29 * 30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 37 * 38 */ 39 40 #ifndef GECODE_SET_REL_HH 41 #define GECODE_SET_REL_HH 42 43 #include <gecode/set.hh> 44 45 namespace Gecode { namespace Set { namespace Rel { 46 47 /** 48 * \namespace Gecode::Set::Rel 49 * \brief Standard set relation propagators 50 */ 51 52 /// Test whether two views are in fact the same 53 template<class VX, class VY> 54 bool same(VX c, VY y); 55 56 /** 57 * \brief %Propagator for the subset constraint 58 * 59 * Requires \code #include <gecode/set/rel.hh> \endcode 60 * \ingroup FuncSetProp 61 */ 62 63 template<class View0, class View1> 64 class Subset : 65 public MixBinaryPropagator<View0,PC_SET_CGLB,View1,PC_SET_CLUB> { 66 protected: 67 using MixBinaryPropagator<View0,PC_SET_CGLB,View1,PC_SET_CLUB>::x0; 68 using MixBinaryPropagator<View0,PC_SET_CGLB,View1,PC_SET_CLUB>::x1; 69 /// Constructor for cloning \a p 70 Subset(Space& home, Subset& p); 71 /// Constructor for posting 72 Subset(Home home, View0 x0, View1 x1); 73 public: 74 /// Copy propagator during cloning 75 virtual Actor* copy(Space& home); 76 /// Perform propagation 77 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 78 /// Post propagator \f$ x\subseteq y\f$ 79 static ExecStatus post(Home home, View0 x, View1 y); 80 }; 81 82 /** 83 * \brief %Propagator for the negated subset constraint 84 * 85 * Requires \code #include <gecode/set/rel.hh> \endcode 86 * \ingroup FuncSetProp 87 */ 88 89 template<class View0, class View1> 90 class NoSubset : 91 public MixBinaryPropagator<View0,PC_SET_CLUB,View1,PC_SET_CGLB> { 92 protected: 93 using MixBinaryPropagator<View0,PC_SET_CLUB,View1,PC_SET_CGLB>::x0; 94 using MixBinaryPropagator<View0,PC_SET_CLUB,View1,PC_SET_CGLB>::x1; 95 /// Constructor for cloning \a p 96 NoSubset(Space& home, NoSubset& p); 97 /// Constructor for posting 98 NoSubset(Home home, View0 x0, View1 x1); 99 public: 100 /// Copy propagator during cloning 101 virtual Actor* copy(Space& home); 102 /// Perform propagation 103 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 104 /// Post propagator \f$ x\subseteq y\f$ 105 static ExecStatus post(Home home,View0 x,View1 y); 106 }; 107 108 /** 109 * \brief %Reified subset propagator 110 * 111 * Requires \code #include <gecode/set/rel.hh> \endcode 112 * \ingroup FuncSetProp 113 */ 114 template<class View0, class View1, class CtrlView, ReifyMode rm> 115 class ReSubset : public Propagator { 116 protected: 117 /// Variable view 118 View0 x0; 119 /// Variable view 120 View1 x1; 121 /// Boolean control view 122 CtrlView b; 123 /// Constructor for cloning \a p 124 ReSubset(Space& home, ReSubset& p); 125 /// Constructor for posting 126 ReSubset(Home home, View0 x0, View1 x1, CtrlView b); 127 public: 128 /// Copy propagator during cloning 129 virtual Actor* copy(Space& home); 130 /// Cost function (defined as ternary low) 131 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 132 /// Schedule function 133 virtual void reschedule(Space& home); 134 /// Delete propagator and return its size 135 virtual size_t dispose(Space& home); 136 /// Perform propagation 137 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 138 /// Post propagator for \f$ (x\subseteq y) \Leftrightarrow b \f$ 139 static ExecStatus post(Home home, View0 x, View1 y, 140 CtrlView b); 141 }; 142 143 /** 144 * \brief %Propagator for set equality 145 * 146 * Requires \code #include <gecode/set/rel.hh> \endcode 147 * \ingroup FuncSetProp 148 */ 149 template<class View0, class View1> 150 class Eq : public MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY> { 151 protected: 152 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x0; 153 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x1; 154 /// Constructor for cloning \a p 155 Eq(Space& home, Eq& p); 156 /// Constructor for posting 157 Eq(Home home, View0 x0, View1 x1); 158 public: 159 /// Copy propagator during cloning 160 virtual Actor* copy(Space& home); 161 /// Perform propagation 162 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 163 /// Post propagator \f$ x=y \f$ 164 static ExecStatus post(Home home, View0 x, View1 y); 165 }; 166 167 /** 168 * \brief %Reified equality propagator 169 * 170 * Requires \code #include <gecode/set/rel.hh> \endcode 171 * \ingroup FuncSetProp 172 */ 173 template<class View0, class View1, class CtrlView, ReifyMode rm> 174 class ReEq : public Propagator { 175 protected: 176 View0 x0; 177 View1 x1; 178 CtrlView b; 179 /// Constructor for cloning \a p 180 ReEq(Space& home, ReEq&); 181 /// Constructor for posting 182 ReEq(Home home, View0 x0, View1 x1, CtrlView b); 183 public: 184 /// Copy propagator during cloning 185 virtual Actor* copy(Space& home); 186 /// Cost function (defined as PC_TERNARY_LO) 187 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 188 /// Schedule function 189 virtual void reschedule(Space& home); 190 /// Delete propagator and return its size 191 virtual size_t dispose(Space& home); 192 /// Perform propagation 193 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 194 /// Post propagator for \f$ (x=y) \Leftrightarrow b\f$ 195 static ExecStatus post(Home home, View0 x, View1 y, 196 CtrlView b); 197 }; 198 199 /** 200 * \brief %Propagator for set less than or equal 201 * 202 * Propagates strict inequality if \a strict is true. 203 * 204 * Requires \code #include <gecode/set/rel.hh> \endcode 205 * \ingroup FuncSetProp 206 */ 207 template<class View0, class View1, bool strict=false> 208 class Lq : public MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY> { 209 protected: 210 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x0; 211 using MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>::x1; 212 /// Constructor for cloning \a p 213 Lq(Space& home, Lq& p); 214 /// Constructor for posting 215 Lq(Home home, View0 x0, View1 x1); 216 public: 217 /// Copy propagator during cloning 218 virtual Actor* copy(Space& home); 219 /// Perform propagation 220 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 221 /// Post propagator \f$ x\leq y \f$ 222 static ExecStatus post(Home home, View0 x, View1 y); 223 }; 224 225 /** 226 * \brief %Reified propagator for set less than or equal 227 * 228 * Propagates strict inequality if \a strict is true. 229 * 230 * Requires \code #include <gecode/set/rel.hh> \endcode 231 * \ingroup FuncSetProp 232 */ 233 template<class View0, class View1, ReifyMode rm, bool strict=false> 234 class ReLq : public Propagator { 235 protected: 236 View0 x0; 237 View1 x1; 238 Gecode::Int::BoolView b; 239 /// Constructor for cloning \a p 240 ReLq(Space& home, ReLq& p); 241 /// Constructor for posting 242 ReLq(Home home, View0 x0, View1 x1, Gecode::Int::BoolView b); 243 public: 244 /// Copy propagator during cloning 245 virtual Actor* copy(Space& home); 246 /// Cost function (defined as PC_TERNARY_LO) 247 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 248 /// Schedule function 249 virtual void reschedule(Space& home); 250 /// Delete propagator and return its size 251 virtual size_t dispose(Space& home); 252 /// Perform propagation 253 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 254 /// Post propagator for \f$ (x\leq y) \Leftrightarrow b\f$ 255 static ExecStatus post(Home home, View0 x, View1 y, 256 Gecode::Int::BoolView b); 257 }; 258 259 /** 260 * \brief %Propagator for negated equality 261 * 262 * Requires \code #include <gecode/set/rel.hh> \endcode 263 * \ingroup FuncSetProp 264 */ 265 266 template<class View0, class View1> 267 class Distinct : 268 public MixBinaryPropagator<View0,PC_SET_VAL,View1,PC_SET_VAL> { 269 protected: 270 using MixBinaryPropagator<View0,PC_SET_VAL,View1,PC_SET_VAL>::x0; 271 using MixBinaryPropagator<View0,PC_SET_VAL,View1,PC_SET_VAL>::x1; 272 /// Constructor for cloning \a p 273 Distinct(Space& home, Distinct& p); 274 /// Constructor for posting 275 Distinct(Home home, View0 x0, View1 x1); 276 public: 277 /// Copy propagator during cloning 278 virtual Actor* copy(Space& home); 279 /// Perform propagation 280 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 281 /// Post propagator \f$ x\neq y \f$ 282 static ExecStatus post(Home home, View0 x, View1 y); 283 }; 284 285 /** 286 * \brief %Propagator for negated equality 287 * 288 * This propagator actually propagates the distinctness, after the 289 * Distinct propagator waited for one variable to become 290 * assigned. 291 * 292 * Requires \code #include <gecode/set/rel.hh> \endcode 293 * \ingroup FuncSetProp 294 */ 295 template<class View0> 296 class DistinctDoit : public UnaryPropagator<View0,PC_SET_ANY> { 297 protected: 298 using UnaryPropagator<View0,PC_SET_ANY>::x0; 299 /// The view that is already assigned 300 ConstSetView y; 301 /// Constructor for cloning \a p 302 DistinctDoit(Space& home, DistinctDoit&); 303 /// Constructor for posting 304 DistinctDoit(Home home, View0 x0, ConstSetView y); 305 public: 306 /// Copy propagator during cloning 307 virtual Actor* copy(Space& home); 308 /// Perform propagation 309 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 310 /// Post propagator \f$ x\neq y \f$ 311 static ExecStatus post(Home home, View0 x, ConstSetView y); 312 }; 313 314 }}} 315 316 #include <gecode/set/rel/common.hpp> 317 #include <gecode/set/rel/subset.hpp> 318 #include <gecode/set/rel/nosubset.hpp> 319 #include <gecode/set/rel/re-subset.hpp> 320 #include <gecode/set/rel/eq.hpp> 321 #include <gecode/set/rel/re-eq.hpp> 322 #include <gecode/set/rel/nq.hpp> 323 #include <gecode/set/rel/lq.hpp> 324 #include <gecode/set/rel/re-lq.hpp> 325 326 #endif 327 328 // STATISTICS: set-prop 329