1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * Guido Tack <tack@gecode.org> 6 * 7 * Copyright: 8 * Christian Schulte, 2002 9 * Guido Tack, 2004 10 * 11 * This file is part of Gecode, the generic constraint 12 * development environment: 13 * http://www.gecode.org 14 * 15 * Permission is hereby granted, free of charge, to any person obtaining 16 * a copy of this software and associated documentation files (the 17 * "Software"), to deal in the Software without restriction, including 18 * without limitation the rights to use, copy, modify, merge, publish, 19 * distribute, sublicense, and/or sell copies of the Software, and to 20 * permit persons to whom the Software is furnished to do so, subject to 21 * the following conditions: 22 * 23 * The above copyright notice and this permission notice shall be 24 * included in all copies or substantial portions of the Software. 25 * 26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 33 * 34 */ 35 36 #ifndef GECODE_INT_COUNT_HH 37 #define GECODE_INT_COUNT_HH 38 39 #include <gecode/int.hh> 40 41 /** 42 * \namespace Gecode::Int::Count 43 * \brief Counting propagators 44 */ 45 46 namespace Gecode { namespace Int { namespace Count { 47 48 /** 49 * Relations for domain consistent counting 50 * 51 */ 52 //@{ 53 /// Return whether \a y is an integer set 54 template<class VY> 55 bool isintset(VY y); 56 /// Return whether \a y is a value 57 template<class VY> 58 bool isval(VY y); 59 60 /// Subscribe propagator \a p to view \a y 61 template<class VY> 62 void subscribe(Space& home, Propagator& p, VY y); 63 /// Cancel propagator \a p for view \a y 64 template<class VY> 65 void cancel(Space& home, Propagator& p, VY y); 66 /// Schedule propagator \a p for view \a y 67 template<class VY> 68 void reschedule(Space& home, Propagator& p, VY y); 69 /// Update view \a y from \a py 70 template<class VY> 71 void update(VY& y, Space& home, bool shared, VY py); 72 73 /// Test whether \a x and \a y are equal 74 template<class VX> 75 RelTest holds(VX x, VX y); 76 /// Test whether \a x and \a y are equal 77 template<class VX> 78 RelTest holds(VX x, ConstIntView y); 79 /// Test whether \a x and \a y are equal 80 template<class VX> 81 RelTest holds(VX x, ZeroIntView y); 82 /// Test whether \a x and \a y are equal 83 template<class VX> 84 RelTest holds(VX x, const IntSet& y); 85 86 /// Post that all views in \a x are equal to \a y 87 template<class VX> 88 ExecStatus post_true(Home home, ViewArray<VX>& x, VX y); 89 /// Post that all views in \a x are equal to \a y 90 template<class VX> 91 ExecStatus post_true(Home home, ViewArray<VX>& x, ConstIntView y); 92 /// Post that all views in \a x are equal to \a y 93 template<class VX> 94 ExecStatus post_true(Home home, ViewArray<VX>& x, ZeroIntView y); 95 /// Post that all views in \a x are equal to \a y 96 template<class VX> 97 ExecStatus post_true(Home home, ViewArray<VX>& x, const IntSet& y); 98 99 /// Post that all views in \a x are not equal to \a y 100 template<class VX> 101 ExecStatus post_false(Home home, ViewArray<VX>& x, VX y); 102 /// Post that all views in \a x are not equal to \a y 103 template<class VX> 104 ExecStatus post_false(Home home, ViewArray<VX>& x, ConstIntView y); 105 /// Post that all views in \a x are not equal to \a y 106 template<class VX> 107 ExecStatus post_false(Home home, ViewArray<VX>& x, ZeroIntView y); 108 /// Post that all views in \a x are not equal to \a y 109 template<class VX> 110 ExecStatus post_false(Home home, ViewArray<VX>& x, const IntSet& y); 111 112 /// Prune that \a y is the union of \a x 113 template<class VX> 114 ExecStatus prune(Home home, ViewArray<VX>& x, VX y); 115 /// Prune that \a y is the union of \a x 116 template<class VX> 117 ExecStatus prune(Home home, ViewArray<VX>& x, ConstIntView y); 118 /// Prune that \a y is the union of \a x 119 template<class VX> 120 ExecStatus prune(Home home, ViewArray<VX>& x, ZeroIntView y); 121 /// Prune that \a y is the union of \a x 122 template<class VX> 123 ExecStatus prune(Home home, ViewArray<VX>& x, const IntSet& y); 124 //@} 125 126 }}} 127 128 #include <gecode/int/count/rel.hpp> 129 130 131 namespace Gecode { namespace Int { namespace Count { 132 133 /** 134 * \brief Baseclass for count propagators (integer) 135 * 136 */ 137 template<class VX, class VY> 138 class IntBase : public Propagator { 139 protected: 140 /// Views still to count 141 ViewArray<VX> x; 142 /// Views from x[0] ... x[n_s-1] have subscriptions 143 int n_s; 144 /// View to compare to 145 VY y; 146 /// Number of views which are equal and have been eliminated 147 int c; 148 /// Constructor for cloning \a p 149 IntBase(Space& home, IntBase& p); 150 /// Constructor for creation 151 IntBase(Home home, ViewArray<VX>& x, int n_s, VY y, int c); 152 public: 153 /// Cost function (defined as low linear) 154 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 155 /// Schedule function 156 virtual void reschedule(Space& home); 157 /// Delete propagator and return its size 158 virtual size_t dispose(Space& home); 159 }; 160 161 /** 162 * \brief %Propagator for counting views (equal integer to number of equal views) 163 * 164 * Not all combinations of views are possible. The types \a VX 165 * and \a VY must be either equal, or \a VY must be ConstIntView, 166 * ZeroIntView, or IntSet. 167 * 168 * Requires \code #include <gecode/int/count.hh> \endcode 169 * \ingroup FuncIntProp 170 */ 171 template<class VX, class VY> 172 class EqInt : public IntBase<VX,VY> { 173 protected: 174 using IntBase<VX,VY>::x; 175 using IntBase<VX,VY>::n_s; 176 using IntBase<VX,VY>::y; 177 using IntBase<VX,VY>::c; 178 /// Constructor for cloning \a p 179 EqInt(Space& home, EqInt& p); 180 /// Constructor for creation 181 EqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c); 182 public: 183 /// Create copy during cloning 184 virtual Actor* copy(Space& home); 185 /// Perform propagation 186 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 187 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}=c\f$ 188 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c); 189 }; 190 191 /** 192 * \brief %Propagator for counting views (greater or equal integer to number of equal views) 193 * 194 * Not all combinations of views are possible. The types \a VX 195 * and \a VY must be either equal, or \a VY must be ConstIntView, 196 * ZeroIntView, or IntSet. 197 * 198 * Requires \code #include <gecode/int/count.hh> \endcode 199 * \ingroup FuncIntProp 200 */ 201 template<class VX, class VY> 202 class GqInt : public IntBase<VX,VY> { 203 protected: 204 using IntBase<VX,VY>::x; 205 using IntBase<VX,VY>::n_s; 206 using IntBase<VX,VY>::y; 207 using IntBase<VX,VY>::c; 208 /// Constructor for cloning \a p 209 GqInt(Space& home, GqInt& p); 210 /// Constructor for creation 211 GqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c); 212 public: 213 /// Create copy during cloning 214 virtual Actor* copy(Space& home); 215 /// Perform propagation 216 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 217 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\geq c\f$ 218 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c); 219 }; 220 221 /** 222 * \brief %Propagator for counting views (less or equal integer to number of equal views) 223 * 224 * Not all combinations of views are possible. The types \a VX 225 * and \a VY must be either equal, or \a VY must be ConstIntView, 226 * ZeroIntView, or IntSet. 227 * 228 * Requires \code #include <gecode/int/count.hh> \endcode 229 * \ingroup FuncIntProp 230 */ 231 template<class VX, class VY> 232 class LqInt : public IntBase<VX,VY> { 233 protected: 234 using IntBase<VX,VY>::x; 235 using IntBase<VX,VY>::n_s; 236 using IntBase<VX,VY>::y; 237 using IntBase<VX,VY>::c; 238 /// Constructor for cloning \a p 239 LqInt(Space& home, LqInt& p); 240 /// Constructor for creation 241 LqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c); 242 public: 243 /// Create copy during cloning 244 virtual Actor* copy(Space& home); 245 /// Perform propagation 246 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 247 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\leq c\f$ 248 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c); 249 }; 250 251 }}} 252 253 #include <gecode/int/count/int-base.hpp> 254 #include <gecode/int/count/int-eq.hpp> 255 #include <gecode/int/count/int-gq.hpp> 256 #include <gecode/int/count/int-lq.hpp> 257 258 259 namespace Gecode { namespace Int { namespace Count { 260 261 /** 262 * \brief Base-class for count propagators (view) 263 * 264 */ 265 template<class VX, class VY, class VZ> 266 class ViewBase : public Propagator { 267 protected: 268 /// Views still to count 269 ViewArray<VX> x; 270 /// View to compare to 271 VY y; 272 /// View which yields result of counting 273 VZ z; 274 /// Number of views which are equal and have been eliminated 275 int c; 276 /// Constructor for cloning \a p 277 ViewBase(Space& home, ViewBase& p); 278 /// Constructor for creation 279 ViewBase(Home home, ViewArray<VX>& x, VY y, VZ z, int c); 280 public: 281 /// Delete propagator and return its size 282 virtual size_t dispose(Space& home); 283 /// Cost function (defined as low linear) 284 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 285 /// Schedule function 286 virtual void reschedule(Space& home); 287 protected: 288 /// Count how many views are equal now 289 void count(Space& home); 290 /// How many views are at least equal 291 int atleast(void) const; 292 /// How many views are at most equal 293 int atmost(void) const; 294 /// Test whether there is sharing of \a z with \a x or \a y 295 static bool sharing(const ViewArray<VX>& x, const VY& y, const VZ& z); 296 }; 297 298 /** 299 * \brief %Propagator for counting views (equal to number of equal views) 300 * 301 * Not all combinations of views are possible. The types \a VX 302 * and \a VY must be either equal, or \a VY must be ConstIntView, 303 * ZeroIntView, or IntSet. 304 * 305 * Requires \code #include <gecode/int/count.hh> \endcode 306 * \ingroup FuncIntProp 307 */ 308 template<class VX, class VY, class VZ, bool shr, bool dom> 309 class EqView : public ViewBase<VX,VY,VZ> { 310 protected: 311 using ViewBase<VX,VY,VZ>::x; 312 using ViewBase<VX,VY,VZ>::z; 313 using ViewBase<VX,VY,VZ>::c; 314 using ViewBase<VX,VY,VZ>::y; 315 using ViewBase<VX,VY,VZ>::count; 316 using ViewBase<VX,VY,VZ>::atleast; 317 using ViewBase<VX,VY,VZ>::atmost; 318 using ViewBase<VX,VY,VZ>::sharing; 319 320 /// Constructor for cloning \a p 321 EqView(Space& home, EqView& p); 322 public: 323 /// Constructor for creation 324 EqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c); 325 /// Create copy during cloning 326 virtual Actor* copy(Space& home); 327 /// Perform propagation 328 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 329 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}=z+c\f$ 330 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c); 331 }; 332 333 /** 334 * \brief %Propagator for counting views (less or equal to number of equal views) 335 * 336 * Not all combinations of views are possible. The types \a VX 337 * and \a VY must be either equal, or \a VY must be ConstIntView, 338 * ZeroIntView, or IntSet. 339 * 340 * Requires \code #include <gecode/int/count.hh> \endcode 341 * \ingroup FuncIntProp 342 */ 343 template<class VX, class VY, class VZ, bool shr> 344 class LqView : public ViewBase<VX,VY,VZ> { 345 protected: 346 using ViewBase<VX,VY,VZ>::x; 347 using ViewBase<VX,VY,VZ>::z; 348 using ViewBase<VX,VY,VZ>::c; 349 using ViewBase<VX,VY,VZ>::y; 350 using ViewBase<VX,VY,VZ>::count; 351 using ViewBase<VX,VY,VZ>::atleast; 352 using ViewBase<VX,VY,VZ>::atmost; 353 using ViewBase<VX,VY,VZ>::sharing; 354 355 /// Constructor for cloning \a p 356 LqView(Space& home, LqView& p); 357 public: 358 /// Constructor for creation 359 LqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c); 360 /// Create copy during cloning 361 virtual Actor* copy(Space& home); 362 /// Perform propagation 363 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 364 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\leq z+c\f$ 365 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c); 366 }; 367 368 /** 369 * \brief %Propagator for counting views (greater or equal to number of equal views) 370 * 371 * Not all combinations of views are possible. The types \a VX 372 * and \a VY must be either equal, or \a VY must be ConstIntView, 373 * ZeroIntView, or IntSet. 374 * 375 * Requires \code #include <gecode/int/count.hh> \endcode 376 * \ingroup FuncIntProp 377 */ 378 template<class VX, class VY, class VZ, bool shr, bool dom> 379 class GqView : public ViewBase<VX,VY,VZ> { 380 protected: 381 using ViewBase<VX,VY,VZ>::x; 382 using ViewBase<VX,VY,VZ>::z; 383 using ViewBase<VX,VY,VZ>::c; 384 using ViewBase<VX,VY,VZ>::y; 385 using ViewBase<VX,VY,VZ>::count; 386 using ViewBase<VX,VY,VZ>::atleast; 387 using ViewBase<VX,VY,VZ>::atmost; 388 using ViewBase<VX,VY,VZ>::sharing; 389 390 /// Constructor for cloning \a p 391 GqView(Space& home, GqView& p); 392 public: 393 /// Constructor for creation 394 GqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c); 395 /// Create copy during cloning 396 virtual Actor* copy(Space& home); 397 /// Perform propagation 398 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 399 /// Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\geq z+c\f$ 400 static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c); 401 }; 402 403 }}} 404 405 #include <gecode/int/count/view-base.hpp> 406 #include <gecode/int/count/view-eq.hpp> 407 #include <gecode/int/count/view-gq.hpp> 408 #include <gecode/int/count/view-lq.hpp> 409 410 #endif 411 412 // STATISTICS: int-prop 413 414