Generated on Thu Apr 11 13:59:11 2019 for Gecode by doxygen 1.6.3

nvalues.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  *
00006  *  Copyright:
00007  *     Christian Schulte, 2011
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #ifndef __GECODE_INT_NVALUES_HH__
00035 #define __GECODE_INT_NVALUES_HH__
00036 
00037 #include <gecode/int.hh>
00038 #include <gecode/int/val-set.hh>
00039 
00045 namespace Gecode { namespace Int { namespace NValues {
00046 
00048   enum RangeEventType {
00050     RET_FST = 0,
00052     RET_LST = 1,
00054     RET_END = 2
00055   };
00056 
00058   class RangeEvent {
00059   public:
00061     RangeEventType ret;
00063     int val;
00065     int view;
00067     bool operator <(RangeEvent re) const;
00068   };
00069 
00071   class SymBitMatrix : public Support::BitSet<Region> {
00072   protected:
00074     int n;
00076     int pos(int x, int y) const;
00077   public:
00079     SymBitMatrix(Region& r, int n);
00081     bool get(int x, int y) const;
00083     void set(int x, int y);
00084   };
00085 
00086 }}}
00087 
00088 #include <gecode/int/nvalues/range-event.hpp>
00089 #include <gecode/int/nvalues/sym-bit-matrix.hpp>
00090 
00091 #include <gecode/int/view-val-graph.hh>
00092 
00093 namespace Gecode { namespace Int { namespace NValues {
00094 
00096   class Graph : public ViewValGraph::Graph<IntView> {
00097   protected:
00099     int n_matched;
00100   public:
00102     Graph(void);
00104     int size(void) const;
00106     void init(Space& home, const ValSet& vs, const ViewArray<IntView>& x);
00108     void sync(void);
00109     /*
00110      * \brief Mark all edges used that can appear in some maximal matching
00111      *
00112      * Return true, if any edge can be in fact pruned.
00113      */
00114     bool mark(void);
00116     ExecStatus prune(Space& home);
00117   };
00118 
00119 }}}
00120 
00121 #include <gecode/int/nvalues/graph.hpp>
00122 
00123 namespace Gecode { namespace Int { namespace NValues {
00124 
00131   template<class VY>
00132   class IntBase
00133     : public MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> {
00134   protected:
00135     using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::x;
00136     using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::y;
00138     ValSet vs;
00140     IntBase(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00142     IntBase(Space& home, IntBase<VY>& p);
00144     void add(Space& home);
00150     void disjoint(Space& home, Region& r, int*& dis, int& n_dis);
00152     void eliminate(Space& home);
00154     ExecStatus all_in_valset(Space& home);
00163     ExecStatus prune_lower(Space& home, int* dis, int n_dis);
00170     ExecStatus prune_upper(Space& home, Graph& g);
00171   public:
00173     virtual PropCost cost(const Space&, const ModEventDelta&) const;
00175     virtual size_t dispose(Space& home);
00176   };
00177 
00184   template<class VY>
00185   class EqInt : public IntBase<VY> {
00186   protected:
00187     using IntBase<VY>::x;
00188     using IntBase<VY>::y;
00189     using IntBase<VY>::vs;
00190     using IntBase<VY>::add;
00191     using IntBase<VY>::all_in_valset;
00192     using IntBase<VY>::disjoint;
00193     using IntBase<VY>::prune_lower;
00194     using IntBase<VY>::prune_upper;
00196     Graph g;
00198     EqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00200     EqInt(Space& home, EqInt<VY>& p);
00201   public:
00203     virtual Propagator* copy(Space& home);
00205     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00207     static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
00209     virtual size_t dispose(Space& home);
00210   };
00211 
00218   template<class VY>
00219   class LqInt : public IntBase<VY> {
00220   protected:
00221     using IntBase<VY>::x;
00222     using IntBase<VY>::y;
00223     using IntBase<VY>::vs;
00224     using IntBase<VY>::add;
00225     using IntBase<VY>::all_in_valset;
00226     using IntBase<VY>::disjoint;
00227     using IntBase<VY>::prune_lower;
00228     using IntBase<VY>::prune_upper;
00230     LqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00232     LqInt(Space& home, LqInt<VY>& p);
00233   public:
00235     virtual Propagator* copy(Space& home);
00237     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00239     static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
00241     virtual size_t dispose(Space& home);
00242   };
00243 
00250   template<class VY>
00251   class GqInt : public IntBase<VY> {
00252   protected:
00253     using IntBase<VY>::x;
00254     using IntBase<VY>::y;
00255     using IntBase<VY>::vs;
00256     using IntBase<VY>::add;
00257     using IntBase<VY>::all_in_valset;
00258     using IntBase<VY>::disjoint;
00259     using IntBase<VY>::prune_lower;
00260     using IntBase<VY>::prune_upper;
00261     using IntBase<VY>::eliminate;
00263     Graph g;
00265     GqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00267     GqInt(Space& home, GqInt<VY>& p);
00268   public:
00270     virtual Propagator* copy(Space& home);
00272     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00274     static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
00275   };
00276 
00277 }}}
00278 
00279 #include <gecode/int/nvalues/int-base.hpp>
00280 #include <gecode/int/nvalues/int-eq.hpp>
00281 #include <gecode/int/nvalues/int-lq.hpp>
00282 #include <gecode/int/nvalues/int-gq.hpp>
00283 
00284 namespace Gecode { namespace Int { namespace NValues {
00285 
00292   template<class VY>
00293   class BoolBase : public Propagator {
00294   protected:
00296     static const int VS_ZERO = 1 << 0;
00298     static const int VS_ONE  = 1 << 1;
00300     int status;
00302     Council<ViewAdvisor<BoolView> > c;
00304     VY y;
00306     BoolBase(Home home, int status, ViewArray<BoolView>& x, VY y);
00308     BoolBase(Space& home, BoolBase<VY>& p);
00309   public:
00311     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00313     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00315     virtual void reschedule(Space& home);
00317     virtual size_t dispose(Space& home);
00318   };
00319 
00326   template<class VY>
00327   class EqBool : public BoolBase<VY> {
00328   protected:
00329     using BoolBase<VY>::VS_ZERO;
00330     using BoolBase<VY>::VS_ONE;
00331     using BoolBase<VY>::status;
00332     using BoolBase<VY>::c;
00333     using BoolBase<VY>::y;
00335     EqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
00337     EqBool(Space& home, EqBool<VY>& p);
00338   public:
00340     virtual Actor* copy(Space& home);
00342     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00349     static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
00350   };
00351 
00358   template<class VY>
00359   class LqBool : public BoolBase<VY> {
00360   protected:
00361     using BoolBase<VY>::VS_ZERO;
00362     using BoolBase<VY>::VS_ONE;
00363     using BoolBase<VY>::status;
00364     using BoolBase<VY>::c;
00365     using BoolBase<VY>::y;
00367     LqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
00369     LqBool(Space& home, LqBool<VY>& p);
00370   public:
00372     virtual Actor* copy(Space& home);
00374     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00381     static  ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
00382   };
00383 
00390   template<class VY>
00391   class GqBool : public BoolBase<VY> {
00392   protected:
00393     using BoolBase<VY>::VS_ZERO;
00394     using BoolBase<VY>::VS_ONE;
00395     using BoolBase<VY>::status;
00396     using BoolBase<VY>::c;
00397     using BoolBase<VY>::y;
00399     GqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
00401     GqBool(Space& home, GqBool<VY>& p);
00402   public:
00404     virtual Actor* copy(Space& home);
00406     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00413     static  ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
00414   };
00415 
00416 }}}
00417 
00418 #include <gecode/int/nvalues/bool-base.hpp>
00419 #include <gecode/int/nvalues/bool-eq.hpp>
00420 #include <gecode/int/nvalues/bool-lq.hpp>
00421 #include <gecode/int/nvalues/bool-gq.hpp>
00422 
00423 #endif
00424 
00425 // STATISTICS: int-prop