distinct.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 * Contributing authors: 00008 * Gabor Szokoli <szokoli@gecode.org> 00009 * 00010 * Copyright: 00011 * Christian Schulte, 2002 00012 * Guido Tack, 2004 00013 * Gabor Szokoli, 2003 00014 * 00015 * Last modified: 00016 * $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $ 00017 * $Revision: 9878 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 #ifndef __GECODE_INT_DISTINCT_HH__ 00045 #define __GECODE_INT_DISTINCT_HH__ 00046 00047 #include <gecode/int.hh> 00048 00049 #include <gecode/int/rel.hh> 00050 00056 namespace Gecode { namespace Int { namespace Distinct { 00057 00066 template<class View> 00067 class Val : public NaryPropagator<View,PC_INT_VAL> { 00068 protected: 00069 using NaryPropagator<View,PC_INT_VAL>::x; 00070 00072 Val(Home home, ViewArray<View>& x); 00074 Val(Space& home, bool share, Val<View>& p); 00075 public: 00077 virtual Actor* copy(Space& home, bool share); 00079 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00081 static ExecStatus post(Home home, ViewArray<View>& x); 00082 }; 00083 00097 template<class View, bool complete> 00098 ExecStatus prop_val(Space& home, ViewArray<View>&); 00099 00100 00101 00127 template<class View> 00128 class Bnd : public Propagator { 00129 protected: 00131 ViewArray<View> x; 00133 ViewArray<View> y; 00135 Bnd(Home home, ViewArray<View>& x); 00137 Bnd(Space& home, bool share, Bnd<View>& p); 00138 public: 00140 static ExecStatus post(Home home, ViewArray<View>& x); 00142 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00149 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00151 virtual Actor* copy(Space& home, bool share); 00153 virtual size_t dispose(Space& home); 00154 }; 00155 00164 template<class View> 00165 ExecStatus prop_bnd(Space& home, ViewArray<View>& x, int m); 00166 00167 template<class View> class ViewNode; 00168 template<class View> class ValNode; 00169 00180 template<class View> 00181 class DomCtrl { 00182 protected: 00184 class ViewValGraph { 00185 public: 00187 ViewNode<View>** view; 00189 int n_view; 00191 ValNode<View>* val; 00193 int n_val; 00195 unsigned int count; 00196 public: 00198 ViewValGraph(void); 00200 bool initialized(void) const; 00202 void init(Space& home, ViewNode<View>* x); 00204 ExecStatus init(Space& home, int n, View* x); 00206 void mark(Space& home); 00208 ExecStatus tell(Space& home, bool& assigned); 00210 void purge(void); 00212 bool sync(Space& home); 00213 public: 00215 typedef Support::StaticStack<ViewNode<View>*,Region> ViewNodeStack; 00217 bool match(ViewNodeStack& m, ViewNode<View>* x); 00218 }; 00220 ViewValGraph vvg; 00221 public: 00223 DomCtrl(void); 00225 bool available(void); 00227 ExecStatus init(Space& home, int n, View* x); 00229 ExecStatus sync(Space& home); 00231 ExecStatus propagate(Space& home, bool& assigned); 00232 }; 00233 00249 template<class View> 00250 class Dom : public NaryPropagator<View,PC_INT_DOM> { 00251 protected: 00252 using NaryPropagator<View,PC_INT_DOM>::x; 00254 DomCtrl<View> dc; 00256 Dom(Space& home, bool share, Dom<View>& p); 00258 Dom(Home home, ViewArray<View>& x); 00259 public: 00261 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00268 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00270 virtual Actor* copy(Space& home, bool share); 00272 static ExecStatus post(Home home, ViewArray<View>& x); 00273 }; 00274 00281 template<class View> 00282 class TerDom : public TernaryPropagator<View,PC_INT_DOM> { 00283 protected: 00284 using TernaryPropagator<View,PC_INT_DOM>::x0; 00285 using TernaryPropagator<View,PC_INT_DOM>::x1; 00286 using TernaryPropagator<View,PC_INT_DOM>::x2; 00287 00289 TerDom(Space& home, bool share, TerDom<View>& p); 00291 TerDom(Home home, View x0, View x1, View x2); 00292 public: 00294 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00296 virtual Actor* copy(Space& home, bool share); 00298 static ExecStatus post(Home home, View x0, View x1, View x2); 00299 }; 00300 00301 }}} 00302 00303 #include <gecode/int/distinct/val.hpp> 00304 #include <gecode/int/distinct/bnd.hpp> 00305 #include <gecode/int/distinct/ter-dom.hpp> 00306 #include <gecode/int/distinct/dom.hpp> 00307 00308 #endif 00309 00310 // STATISTICS: int-prop 00311