element.hh
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 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2004 00009 * Guido Tack, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2010-05-03 18:31:57 +0200 (Mon, 03 May 2010) $ by $Author: schulte $ 00013 * $Revision: 10846 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 #ifndef __GECODE_INT_ELEMENT_HH__ 00041 #define __GECODE_INT_ELEMENT_HH__ 00042 00043 #include <gecode/int.hh> 00044 #include <gecode/int/rel.hh> 00045 00051 namespace Gecode { namespace Int { namespace Element { 00052 00059 template<class V0, class V1, class Idx, class Val> 00060 class Int : public Propagator { 00061 protected: 00070 class IdxVal { 00071 public: 00072 Idx idx_next; 00073 Idx val_next; 00074 Idx idx; 00075 Val val; 00076 00077 void mark(void); 00079 bool marked(void) const; 00080 }; 00087 class IterIdxUnmark { 00088 private: 00089 IdxVal* iv; 00090 Idx i; 00091 public: 00093 IterIdxUnmark(IdxVal* iv); 00095 bool operator ()(void) const; 00097 void operator ++(void); 00099 Idx val(void) const; 00100 }; 00107 class IterVal { 00108 private: 00109 IdxVal* iv; 00110 Idx i; 00111 public: 00113 IterVal(IdxVal* iv); 00115 bool operator ()(void) const; 00117 void operator ++(void); 00119 Val val(void) const; 00120 }; 00129 class IterValUnmark { 00130 private: 00131 IdxVal* iv; 00132 Idx i; 00133 public: 00135 IterValUnmark(IdxVal* iv); 00137 bool operator ()(void) const; 00139 void operator ++(void); 00141 Val val(void) const; 00142 }; 00144 class ByVal { 00145 protected: 00146 const IdxVal* iv; 00147 public: 00149 ByVal(const IdxVal* iv); 00151 bool operator ()(Idx& i, Idx& j); 00152 }; 00153 00155 V0 x0; 00157 typedef typename Gecode::Support::IntTypeTraits<Idx>::utype IdxSize; 00159 IdxSize s0; 00161 V1 x1; 00163 typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize; 00165 ValSize s1; 00167 IntSharedArray c; 00169 IdxVal* iv; 00171 void prune_idx(void); 00173 void prune_val(void); 00175 static ExecStatus assigned_val(Space& home, IntSharedArray& c, 00176 V0 x0, V1 x1); 00178 Int(Space& home, bool shared, Int& p); 00180 Int(Home home, IntSharedArray& i, V0 x0, V1 x1); 00181 public: 00183 virtual Actor* copy(Space& home, bool share); 00185 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00187 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00189 static ExecStatus post(Home home, IntSharedArray& i, V0 x0, V1 x1); 00191 virtual size_t dispose(Space& home); 00192 }; 00193 00195 template<class V0, class V1> 00196 ExecStatus post_int(Home home, IntSharedArray& c, V0 x0, V1 x1); 00197 00198 00203 template<class ViewB> class IdxView; 00204 00206 template<class View> 00207 class ViewToVarArg {}; 00208 00213 template<class View> 00214 class IdxViewArray { 00215 private: 00217 IdxView<View>* xs; 00219 int n; 00220 public: 00222 IdxViewArray(void); 00224 IdxViewArray(const IdxViewArray<View>&); 00226 IdxViewArray(Space& home, const typename ViewToVarArg<View>::argtype& x); 00228 IdxViewArray(Space& home, int n); 00229 00231 int size(void) const; 00233 void size(int n); 00234 00236 IdxView<View>& operator [](int n); 00238 const IdxView<View>& operator [](int) const; 00239 00244 void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true); 00249 void cancel(Space& home, Propagator& p, PropCond pc); 00250 00252 void update(Space& home, bool share, IdxViewArray<View>& x); 00253 }; 00254 00259 template<class VA, class VB, class VC, PropCond pc_ac> 00260 class View : public Propagator { 00261 protected: 00263 IdxViewArray<VA> iv; 00265 VB x0; 00267 VC x1; 00269 View(Space& home, bool share, View& p); 00271 View(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 00272 public: 00273 // Cost function (defined as low linear) 00274 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00276 virtual size_t dispose(Space& home); 00277 }; 00278 00279 00286 template<class VA, class VB, class VC> 00287 class ViewBnd : public View<VA,VB,VC,PC_INT_BND> { 00288 protected: 00289 using View<VA,VB,VC,PC_INT_BND>::iv; 00290 using View<VA,VB,VC,PC_INT_BND>::x0; 00291 using View<VA,VB,VC,PC_INT_BND>::x1; 00292 00294 ViewBnd(Space& home, bool share, ViewBnd& p); 00296 ViewBnd(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 00297 public: 00299 virtual Actor* copy(Space& home, bool share); 00301 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00303 static ExecStatus post(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 00304 }; 00305 00316 template<class VA, class VB, class VC> 00317 class ViewDom : public View<VA,VB,VC,PC_INT_DOM> { 00318 protected: 00319 using View<VA,VB,VC,PC_INT_DOM>::iv; 00320 using View<VA,VB,VC,PC_INT_DOM>::x0; 00321 using View<VA,VB,VC,PC_INT_DOM>::x1; 00322 00324 ViewDom(Space& home, bool share, ViewDom& p); 00326 ViewDom(Home home, IdxViewArray<VA>& iv, VB x0, VC x1); 00327 public: 00329 virtual Actor* copy(Space& home, bool share); 00337 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00339 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00341 static ExecStatus post(Home home, IdxViewArray<VA>& iv, 00342 VB x0, VC x1); 00343 }; 00344 00352 class GECODE_VTABLE_EXPORT Pair 00353 : public TernaryPropagator<IntView,PC_INT_DOM> { 00354 protected: 00355 using TernaryPropagator<IntView,PC_INT_DOM>::x0; 00356 using TernaryPropagator<IntView,PC_INT_DOM>::x1; 00357 using TernaryPropagator<IntView,PC_INT_DOM>::x2; 00359 int w; 00361 Pair(Space& home, bool share, Pair& p); 00362 public: 00364 Pair(Home home, IntView x0, IntView x1, IntView x2, int w); 00366 static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2, 00367 int w, int h); 00369 GECODE_INT_EXPORT virtual Actor* copy(Space& home, bool share); 00371 GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00372 }; 00373 00374 }}} 00375 00376 #include <gecode/int/element/int.hpp> 00377 #include <gecode/int/element/view.hpp> 00378 #include <gecode/int/element/pair.hpp> 00379 00380 #endif 00381 00382 00383 // STATISTICS: int-prop 00384