Generated on Wed Jul 27 2011 15:08:42 for Gecode by doxygen 1.7.4
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