extensional.hh
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * 00007 * Copyright: 00008 * Mikael Lagerkvist, 2007 00009 * Christian Schulte, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00013 * $Revision: 11192 $ 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_EXTENSIONAL_HH__ 00041 #define __GECODE_INT_EXTENSIONAL_HH__ 00042 00043 #include <gecode/int.hh> 00044 00045 #include <gecode/int/rel.hh> 00046 00052 namespace Gecode { namespace Int { namespace Extensional { 00053 00068 template<class View, class Val, class Degree, class StateIdx> 00069 class LayeredGraph : public Propagator { 00070 protected: 00072 class State { 00073 public: 00074 Degree i_deg; 00075 Degree o_deg; 00076 00077 void init(void); 00078 }; 00080 class Edge { 00081 public: 00082 StateIdx i_state; 00083 StateIdx o_state; 00084 }; 00086 class Support { 00087 public: 00088 Val val; 00089 Degree n_edges; 00090 Edge* edges; 00091 }; 00093 typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize; 00095 class Layer { 00096 public: 00097 View x; 00098 StateIdx n_states; 00099 ValSize size; 00100 State* states; 00101 Support* support; 00102 }; 00104 class LayerValues { 00105 private: 00106 const Support* s1; 00107 const Support* s2; 00108 public: 00110 LayerValues(void); 00112 LayerValues(const Layer& l); 00114 void init(const Layer& l); 00116 bool operator ()(void) const; 00118 void operator ++(void); 00120 int val(void) const; 00121 }; 00123 class Index : public Advisor { 00124 public: 00126 int i; 00128 Index(Space& home, Propagator& p, Council<Index>& c, int i); 00130 Index(Space& home, bool share, Index& a); 00131 }; 00133 class IndexRange { 00134 private: 00135 int _fst; 00136 int _lst; 00137 public: 00139 IndexRange(void); 00141 void reset(void); 00143 void add(int i); 00145 void add(const IndexRange& ir); 00147 void lshift(int n); 00149 bool empty(void) const; 00151 int fst(void) const; 00153 int lst(void) const; 00154 }; 00156 Council<Index> c; 00158 int n; 00160 Layer* layers; 00162 StateIdx max_states; 00164 unsigned int n_states; 00166 unsigned int n_edges; 00168 IndexRange i_ch; 00170 IndexRange o_ch; 00172 IndexRange a_ch; 00174 State& i_state(int i, StateIdx is); 00176 State& i_state(int i, const Edge& e); 00178 bool i_dec(int i, const Edge& e); 00180 State& o_state(int i, StateIdx os); 00182 State& o_state(int i, const Edge& e); 00184 bool o_dec(int i, const Edge& e); 00186 void audit(void); 00188 template<class Var> 00189 ExecStatus initialize(Space& home, 00190 const VarArgArray<Var>& x, const DFA& dfa); 00192 LayeredGraph(Space& home, bool share, 00193 LayeredGraph<View,Val,Degree,StateIdx>& p); 00194 public: 00196 template<class Var> 00197 LayeredGraph(Home home, 00198 const VarArgArray<Var>& x, const DFA& dfa); 00200 virtual Actor* copy(Space& home, bool share); 00202 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00204 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d); 00206 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00208 virtual size_t dispose(Space& home); 00210 template<class Var> 00211 static ExecStatus post(Home home, 00212 const VarArgArray<Var>& x, const DFA& dfa); 00213 }; 00214 00216 template<class Var> 00217 ExecStatus post_lgp(Home home, 00218 const VarArgArray<Var>& x, const DFA& dfa); 00219 00220 }}} 00221 00222 #include <gecode/int/extensional/layered-graph.hpp> 00223 00224 00225 namespace Gecode { namespace Int { namespace Extensional { 00226 00227 typedef TupleSet::Tuple Tuple; 00228 typedef Support::BitSetBase BitSet; 00229 typedef Support::BitSetBase* Domain; 00230 00241 template<class View, bool subscribe = true> 00242 class Base : public Propagator { 00243 protected: 00244 ViewArray<View> x; 00245 TupleSet tupleSet; 00246 Tuple** last_data; 00247 00248 TupleSet::TupleSetI* ts(void); 00249 00251 Base(Space& home, bool share, Base<View,subscribe>& p); 00253 Base(Home home, ViewArray<View>& x, const TupleSet& t); 00255 void init_last(Space& home, Tuple** source); 00257 Tuple last(int i, int n); 00259 Tuple last_next(int i, int n); 00261 void init_dom(Space& home, Domain dom); 00263 bool valid(Tuple t, Domain dom); 00265 Tuple find_support(Domain dom, int i, int n); 00266 public: 00268 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00270 virtual size_t dispose(Space& home); 00271 protected: 00273 virtual ~Base(void) {} 00274 }; 00275 }}} 00276 00277 #include <gecode/int/extensional/base.hpp> 00278 00279 00280 namespace Gecode { namespace Int { namespace Extensional { 00281 00294 template<class View, bool shared> 00295 class Basic : public Base<View> { 00296 protected: 00297 using Base<View>::x; 00298 using Base<View>::tupleSet; 00299 using Base<View>::ts; 00300 using Base<View>::last; 00301 using Base<View>::last_next; 00302 using Base<View>::init_last; 00303 using Base<View>::init_dom; 00304 using Base<View>::find_support; 00305 00307 Basic(Space& home, bool share, Basic<View,shared>& p); 00309 Basic(Home home, ViewArray<View>& x, const TupleSet& t); 00310 00311 public: 00313 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00320 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00322 virtual Actor* copy(Space& home, bool share); 00324 static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t); 00325 }; 00326 00327 }}} 00328 00329 #include <gecode/int/extensional/basic.hpp> 00330 00331 00332 namespace Gecode { namespace Int { namespace Extensional { 00342 template<class View> 00343 class Incremental : public Base<View, false> { 00344 protected: 00345 using Base<View, false>::x; 00346 using Base<View, false>::tupleSet; 00347 using Base<View, false>::ts; 00348 using Base<View, false>::last; 00349 using Base<View, false>::last_next; 00350 using Base<View, false>::init_last; 00351 using Base<View, false>::init_dom; 00353 class SupportEntry : public FreeList { 00354 public: 00356 Tuple t; 00357 00359 00360 00361 SupportEntry* next(void) const; 00363 SupportEntry** nextRef(void); 00365 00367 00368 00369 SupportEntry(Tuple t); 00371 SupportEntry(Tuple t, SupportEntry* n); 00373 00375 00376 00377 void dispose(Space& home, SupportEntry* l); 00379 void dispose(Space& home); 00380 00382 static void* operator new(size_t s, Space& home); 00384 static void operator delete(void* p); 00386 static void operator delete(void* p, Space& home); 00388 }; 00390 class WorkEntry : public FreeList { 00391 public: 00393 int i; 00395 int n; 00396 00398 00399 00400 WorkEntry(int i, int n, WorkEntry* ne); 00402 00404 00405 00406 WorkEntry* next(void) const; 00408 void next(WorkEntry* n); 00410 00412 00413 00414 void dispose(Space& home); 00415 00417 static void* operator new(size_t s, Space& home); 00419 static void operator delete(void* p); 00421 static void operator delete(void* p, Space& home); 00423 }; 00425 class Work { 00426 private: 00428 WorkEntry* we; 00429 public: 00431 Work(void); 00433 bool empty(void) const; 00435 void push(Space& home, int i, int n); 00437 void pop(Space& home, int& i, int& n); 00438 }; 00440 Work w_support; 00442 Work w_remove; 00443 00445 SupportEntry** support_data; 00447 int unassigned; 00448 00450 Incremental(Space& home, bool share, Incremental<View>& p); 00452 Incremental(Home home, ViewArray<View>& x, const TupleSet& t); 00454 void init_support(Space& home); 00456 void find_support(Space& home, Domain dom, int i, int n); 00458 void add_support(Space& home, Tuple l); 00460 void remove_support(Space& home, Tuple l, int i, int n); 00462 SupportEntry* support(int i, int n); 00463 public: 00465 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00472 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00474 virtual Actor* copy(Space& home, bool share); 00476 static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t); 00478 size_t dispose(Space& home); 00479 private: 00481 class SupportAdvisor : public Advisor { 00482 public: 00484 int i; 00486 SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c, 00487 int i); 00489 SupportAdvisor(Space& home, bool share, SupportAdvisor& a); 00491 void dispose(Space& home, Council<SupportAdvisor>& c); 00492 }; 00494 Council<SupportAdvisor> ac; 00495 public: 00497 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d); 00498 }; 00499 00500 }}} 00501 00502 #include <gecode/int/extensional/incremental.hpp> 00503 00504 00505 #endif 00506 00507 // STATISTICS: int-prop 00508