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, 2004 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_ELEMENT_HH 37 #define GECODE_INT_ELEMENT_HH 38 39 #include <gecode/int.hh> 40 #include <gecode/int/rel.hh> 41 #include <gecode/int/idx-view.hh> 42 43 /** 44 * \namespace Gecode::Int::Element 45 * \brief %Element propagators 46 */ 47 48 namespace Gecode { namespace Int { namespace Element { 49 50 /** 51 * \brief %Element propagator for array of integers 52 * 53 * Requires \code #include <gecode/int/element.hh> \endcode 54 * \ingroup FuncIntProp 55 */ 56 template<class V0, class V1, class Idx, class Val> 57 class Int : public Propagator { 58 protected: 59 /** 60 * \brief Linked index-value pairs 61 * 62 * Data structure linking pairs of index and value (index,value) 63 * where pairs are linked in order of both index and 64 * value (to allow for easy removal while keeping both index and 65 * value sorted). 66 */ 67 class IdxVal { 68 public: 69 Idx idx_next; ///< The position of the next pair in index order 70 Idx val_next; ///< The position of the next pair in value order 71 Idx idx; ///< The index 72 Val val; ///< The value 73 /// Mark that this pair should be removed 74 void mark(void); 75 /// Return whether this pair is marked for removal 76 bool marked(void) const; 77 }; 78 /** 79 * \brief Value iterator for indices in index-value map 80 * 81 * The iterator also removes marked index-value pairs. 82 * 83 */ 84 class IterIdxUnmark { 85 private: 86 IdxVal* iv; ///< The index value data structure 87 Idx i; ///< Current index value pair 88 public: 89 /// Initialize with start 90 IterIdxUnmark(IdxVal* iv); 91 /// Test whether more pairs to be iterated 92 bool operator ()(void) const; 93 /// Move to next index value pair (next index) 94 void operator ++(void); 95 /// Return index of current index value pair 96 Idx val(void) const; 97 }; 98 /** 99 * \brief Value iterator for values in index-value map 100 * 101 * Note that the iterated value sequence is not strictly 102 * increasing (might contain duplicates). 103 */ 104 class IterVal { 105 private: 106 IdxVal* iv; ///< The index value data structure 107 Idx i; ///< Current index value pair 108 public: 109 /// Initialize with start 110 IterVal(IdxVal* iv); 111 /// Test whether more pairs to be iterated 112 bool operator ()(void) const; 113 /// Move to next index value pair (next value) 114 void operator ++(void); 115 /// Return value of current index value pair 116 Val val(void) const; 117 }; 118 /** 119 * \brief Value iterator for values in index-value map 120 * 121 * Note that the iterated value sequence is not strictly 122 * increasing (might contain duplicates). 123 * 124 * The iterator also removes marked index-value pairs. 125 */ 126 class IterValUnmark { 127 private: 128 IdxVal* iv; ///< The index value data structure 129 Idx i; ///< Current index value pair 130 public: 131 /// Initialize with start 132 IterValUnmark(IdxVal* iv); 133 /// Test whether more pairs to be iterated 134 bool operator ()(void) const; 135 /// Move to next index value pair (next value) 136 void operator ++(void); 137 /// Return value of current index value pair 138 Val val(void) const; 139 }; 140 /// Sorting pointers to (index,value) pairs in value order 141 class ByVal { 142 protected: 143 const IdxVal* iv; ///< Index-value pairs 144 public: 145 /// Initialize with index value pairs 146 ByVal(const IdxVal* iv); 147 /// Compare pairs at positions \a i and \a j 148 bool operator ()(Idx& i, Idx& j); 149 }; 150 151 /// View for index 152 V0 x0; 153 /// Type for index size 154 typedef typename Gecode::Support::IntTypeTraits<Idx>::utype IdxSize; 155 /// Size of \a x0 at last execution 156 IdxSize s0; 157 /// View for result 158 V1 x1; 159 /// Type for value size 160 typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize; 161 /// Size of \a x1 at last execution 162 ValSize s1; 163 /// Shared array of integer values 164 IntSharedArray c; 165 /// The index-value data structure 166 IdxVal* iv; 167 /// Prune index according to \a x0 168 void prune_idx(void); 169 /// Prune values according to \a x1 170 void prune_val(void); 171 /// Prune when \a x1 is assigned 172 static ExecStatus assigned_val(Space& home, IntSharedArray& c, 173 V0 x0, V1 x1); 174 /// Constructor for cloning \a p 175 Int(Space& home, Int& p); 176 /// Constructor for creation 177 Int(Home home, IntSharedArray& i, V0 x0, V1 x1); 178 public: 179 /// Perform copying during cloning 180 virtual Actor* copy(Space& home); 181 /// Cost function (defined as high binary) 182 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 183 /// Schedule function 184 virtual void reschedule(Space& home); 185 /// Perform propagation 186 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 187 /// Post propagator for \f$i_{x_0}=x_1\f$ 188 static ExecStatus post(Home home, IntSharedArray& i, V0 x0, V1 x1); 189 /// Delete propagator and return its size 190 virtual size_t dispose(Space& home); 191 }; 192 193 /// Post propagator with apropriate index and value types 194 template<class V0, class V1> 195 ExecStatus post_int(Home home, IntSharedArray& c, V0 x0, V1 x1); 196 197 198 /** 199 * \brief Base-class for element propagator for array of views 200 * 201 */ 202 template<class VA, class VB, class VC, PropCond pc_ac> 203 class View : public Propagator { 204 protected: 205 /// Current index-view map 206 IdxViewArray<VA> iv; 207 /// View for index 208 VB x0; 209 /// View for result 210 VC x1; 211 /// Constructor for cloning \a p 212 View(Space& home, View& p); 213 /// Constructor for creation 214 View(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 215 public: 216 // Cost function (defined as low linear) 217 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 218 /// Schedule function 219 virtual void reschedule(Space& home); 220 /// Delete propagator and return its size 221 virtual size_t dispose(Space& home); 222 }; 223 224 225 /** 226 * \brief Bounds consistent element propagator for array of views 227 * 228 * Requires \code #include <gecode/int/element.hh> \endcode 229 * \ingroup FuncIntProp 230 */ 231 template<class VA, class VB, class VC> 232 class ViewBnd : public View<VA,VB,VC,PC_INT_BND> { 233 protected: 234 using View<VA,VB,VC,PC_INT_BND>::iv; 235 using View<VA,VB,VC,PC_INT_BND>::x0; 236 using View<VA,VB,VC,PC_INT_BND>::x1; 237 238 /// Constructor for cloning \a p 239 ViewBnd(Space& home, ViewBnd& p); 240 /// Constructor for creation 241 ViewBnd(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 242 public: 243 /// Perform copying 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$iv_{x_0}=x_1\f$ 248 static ExecStatus post(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 249 }; 250 251 /** 252 * \brief Domain consistent element propagator for array of views 253 * 254 * The propagator uses staging: first it uses 255 * bounds-propagation on the array of views and the uses 256 * domain-propagation on the array of views. 257 * 258 * Requires \code #include <gecode/int/element.hh> \endcode 259 * \ingroup FuncIntProp 260 */ 261 template<class VA, class VB, class VC> 262 class ViewDom : public View<VA,VB,VC,PC_INT_DOM> { 263 protected: 264 using View<VA,VB,VC,PC_INT_DOM>::iv; 265 using View<VA,VB,VC,PC_INT_DOM>::x0; 266 using View<VA,VB,VC,PC_INT_DOM>::x1; 267 268 /// Constructor for cloning \a p 269 ViewDom(Space& home, ViewDom& p); 270 /// Constructor for creation 271 ViewDom(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 272 public: 273 /// Perform copying during cloning 274 virtual Actor* copy(Space& home); 275 /** 276 * \brief Cost function 277 * 278 * If in stage for bounds-propagation defined as low linear, 279 * otherwise as high linear. 280 * 281 */ 282 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 283 /// Perform propagation 284 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 285 /// Post propagator for \f$iv_{x_0}=x_1\f$ 286 static ExecStatus post(Home home, IdxViewArray<VA>& iv, 287 VB x0, VC x1); 288 }; 289 290 /** 291 * \brief Domain consistent pair propagator 292 * 293 * Requires \code #include <gecode/int/element.hh> \endcode 294 * 295 * \ingroup FuncIntProp 296 */ 297 class GECODE_VTABLE_EXPORT Pair 298 : public TernaryPropagator<IntView,PC_INT_DOM> { 299 protected: 300 using TernaryPropagator<IntView,PC_INT_DOM>::x0; 301 using TernaryPropagator<IntView,PC_INT_DOM>::x1; 302 using TernaryPropagator<IntView,PC_INT_DOM>::x2; 303 /// Width 304 int w; 305 /// Constructor for cloning \a p 306 Pair(Space& home, Pair& p); 307 public: 308 /// Constructor for posting 309 Pair(Home home, IntView x0, IntView x1, IntView x2, int w); 310 /// Post propagator \f$x_0+x_1\cdot w=x_2\f$ 311 static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2, 312 int w, int h); 313 /// Copy propagator during cloning 314 GECODE_INT_EXPORT virtual Actor* copy(Space& home); 315 /// Perform propagation 316 GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 317 }; 318 319 /** 320 * \brief Domain consistent pair-with-offsets propagator 321 * 322 * Requires \code #include <gecode/int/element.hh> \endcode 323 * 324 * \ingroup FuncIntProp 325 */ 326 class GECODE_VTABLE_EXPORT PairWithOffsets 327 : public TernaryPropagator<OffsetView,PC_INT_DOM> { 328 protected: 329 using TernaryPropagator<OffsetView,PC_INT_DOM>::x0; 330 using TernaryPropagator<OffsetView,PC_INT_DOM>::x1; 331 using TernaryPropagator<OffsetView,PC_INT_DOM>::x2; 332 /// Width 333 int w; 334 /// Constructor for cloning \a p 335 PairWithOffsets(Space& home, PairWithOffsets& p); 336 public: 337 /// Constructor for posting 338 PairWithOffsets(Home home, OffsetView x0, OffsetView x1, IntView x2, int w); 339 /// Post propagator \f$x_0+x_1\cdot w=x_2\f$ 340 static ExecStatus post(Home home, OffsetView x0, OffsetView x1, IntView x2, 341 int w, int h); 342 /// Copy propagator during cloning 343 GECODE_INT_EXPORT virtual Actor* copy(Space& home); 344 /// Perform propagation 345 GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 346 }; 347 348 }}} 349 350 #include <gecode/int/element/int.hpp> 351 #include <gecode/int/element/view.hpp> 352 #include <gecode/int/element/pair.hpp> 353 354 #endif 355 356 357 // STATISTICS: int-prop 358 359