rel.hh

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: 2016-11-08 17:23:24 +0100 (Tue, 08 Nov 2016) $ by $Author: schulte $
00017  *     $Revision: 15253 $
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_REL_HH__
00045 #define __GECODE_INT_REL_HH__
00046 
00047 #include <gecode/int.hh>
00048 
00054 namespace Gecode { namespace Int { namespace Rel {
00055 
00056   /*
00057    * Equality propagators
00058    *
00059    */
00060 
00070   template<class View0,class View1>
00071   class EqDom :
00072     public MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM> {
00073   protected:
00074     using MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>::x0;
00075     using MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>::x1;
00076 
00078     EqDom(Space& home, bool share, EqDom<View0,View1>& p);
00079   public:
00081     EqDom(Home home, View0 x0, View1 x1);
00083     EqDom(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
00085     virtual Actor* copy(Space& home, bool share);
00093     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00095     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00097     static  ExecStatus post(Home home, View0 x0, View1 x1);
00098   };
00099 
00106   template<class View0, class View1>
00107   class EqVal :
00108     public MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL> {
00109   protected:
00110     using MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL>::x0;
00111     using MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL>::x1;
00112 
00114     EqVal(Space& home, bool share, EqVal<View0,View1>& p);
00115   public:
00117     EqVal(Home home, View0 x0, View1 x1);
00119     EqVal(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
00121     virtual Actor* copy(Space& home, bool share);
00123     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00125     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00127     static  ExecStatus post(Home home, View0 x0, View1 x1);
00128   };
00129 
00136   template<class View0, class View1>
00137   class EqBnd :
00138     public MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND> {
00139   protected:
00140     using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x0;
00141     using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x1;
00142 
00144     EqBnd(Space& home, bool share, EqBnd<View0,View1>& p);
00145   public:
00147     EqBnd(Home home, View0 x0, View1 x1);
00149     EqBnd(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
00151     virtual Actor* copy(Space& home, bool share);
00153     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00155     static  ExecStatus post(Home home, View0 x0, View1 x1);
00156   };
00157 
00167   template<class View>
00168   class NaryEqDom : public NaryPropagator<View,PC_INT_DOM> {
00169   protected:
00170     using NaryPropagator<View,PC_INT_DOM>::x;
00171 
00173     NaryEqDom(Space& home, bool share, NaryEqDom<View>& p);
00175     NaryEqDom(Home home, ViewArray<View>&);
00176   public:
00178     virtual Actor* copy(Space& home, bool share);
00186     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00188     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00190     static  ExecStatus post(Home home, ViewArray<View>& x);
00191   };
00192 
00199   template<class View>
00200   class NaryEqBnd : public NaryPropagator<View,PC_INT_BND> {
00201   protected:
00202     using NaryPropagator<View,PC_INT_BND>::x;
00203 
00205     NaryEqBnd(Space& home, bool share, NaryEqBnd<View>& p);
00207     NaryEqBnd(Home home, ViewArray<View>&);
00208   public:
00210     virtual Actor* copy(Space& home, bool share);
00217     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00219     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00221     static  ExecStatus post(Home home, ViewArray<View>& x);
00222   };
00223 
00233   template<class View, int o>
00234   class NaryLqLe : public NaryPropagator<View,PC_INT_NONE> {
00235   protected:
00236     using NaryPropagator<View,PC_INT_NONE>::x;
00238     class Index : public Advisor {
00239     public:
00241       int i;
00243       Index(Space& home, Propagator& p, Council<Index>& c, int i);
00245       Index(Space& home, bool share, Index& a);
00246     };
00248     Council<Index> c;
00250     class Pos : public FreeList {
00251     public:
00253       int p;
00254 
00256 
00257 
00258       Pos(int p, Pos* n);
00260 
00262 
00263 
00264       Pos* next(void) const;
00266 
00268 
00269 
00270       void dispose(Space& home);
00271 
00273       static void* operator new(size_t s, Space& home);
00275       static void operator delete(void* p);
00277       static void operator delete(void* p, Space& home);
00279     };
00281     Pos* pos;
00283     bool empty(void) const;
00285     int pop(Space& home);
00287     void push(Space& home, int p);
00289     bool run;
00291     int n_subsumed;
00293     static const int n_threshold = 7;
00295     NaryLqLe(Space& home, bool share, NaryLqLe<View,o>& p);
00297     NaryLqLe(Home home, ViewArray<View>&);
00298   public:
00300     virtual Actor* copy(Space& home, bool share);
00302     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00304     virtual void reschedule(Space& home);
00306     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00308     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00310     virtual size_t dispose(Space& home);
00312     static ExecStatus post(Home home, ViewArray<View>& x);
00313   };
00314 
00321   template<class View>
00322   class NaryNq : public NaryPropagator<View,PC_INT_VAL> {
00323   protected:
00324     using NaryPropagator<View,PC_INT_VAL>::x;
00326     NaryNq(Home home, ViewArray<View>& x);
00328     NaryNq(Space& home, bool share, NaryNq<View>& p);
00329   public:
00331     virtual Actor* copy(Space& home, bool share);
00333     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00335     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00337     static  ExecStatus post(Home home, ViewArray<View>& x);
00339     virtual size_t dispose(Space& home);
00340   };
00341 
00342 
00349   template<class View, class CtrlView, ReifyMode rm>
00350   class ReEqDom : public ReBinaryPropagator<View,PC_INT_DOM,CtrlView> {
00351   protected:
00352     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
00353     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x1;
00354     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::b;
00355 
00357     ReEqDom(Space& home, bool share, ReEqDom& p);
00359     ReEqDom(Home home, View x0, View x1, CtrlView b);
00360   public:
00362     virtual Actor* copy(Space& home, bool share);
00364     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00366     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00367   };
00368 
00375   template<class View, class CtrlView, ReifyMode rm>
00376   class ReEqBnd : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
00377   protected:
00378     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00379     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
00380     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
00381 
00383     ReEqBnd(Space& home, bool share, ReEqBnd& p);
00385     ReEqBnd(Home home, View x0, View x1, CtrlView b);
00386   public:
00388     virtual Actor*     copy(Space& home, bool share);
00390     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00392     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00393   };
00394 
00401   template<class View, class CtrlView, ReifyMode rm>
00402   class ReEqDomInt : public ReUnaryPropagator<View,PC_INT_DOM,CtrlView> {
00403   protected:
00404     using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
00405     using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::b;
00406 
00408     int c;
00410     ReEqDomInt(Space& home, bool share, ReEqDomInt& p);
00412     ReEqDomInt(Home home, View x, int c, CtrlView b);
00413   public:
00415     virtual Actor* copy(Space& home, bool share);
00417     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00419     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00420   };
00421 
00428   template<class View, class CtrlView, ReifyMode rm>
00429   class ReEqBndInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
00430   protected:
00431     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00432     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
00433 
00435     int c;
00437     ReEqBndInt(Space& home, bool share, ReEqBndInt& p);
00439     ReEqBndInt(Home home, View x, int c, CtrlView b);
00440   public:
00442     virtual Actor* copy(Space& home, bool share);
00444     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00446     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00447   };
00448 
00449 
00450 
00451 
00452   /*
00453    * Disequality propagators
00454    *
00455    */
00456 
00463   template<class V0, class V1>
00464   class Nq : public MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL> {
00465   protected:
00466     using MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>::x0;
00467     using MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>::x1;
00468 
00470     Nq(Space& home, bool share, Nq<V0,V1>& p);
00472     Nq(Home home, V0 x0, V1 x1);
00473   public:
00475     virtual Actor* copy(Space& home, bool share);
00477     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00479     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00481     static  ExecStatus post(Home home, V0 x0, V1 x1);
00482   };
00483 
00484   /*
00485    * Order propagators
00486    *
00487    */
00488 
00496   template<class V0, class V1>
00497   class Lq : public MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND> {
00498   protected:
00499     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x0;
00500     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x1;
00502     static bool same(V0 x0, V1 x1);
00504     Lq(Space& home, bool share, Lq& p);
00506     Lq(Home home, V0 x0, V1 x1);
00507   public:
00509     virtual Actor* copy(Space& home, bool share);
00511     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00513     static  ExecStatus post(Home home, V0 x0, V1 x1);
00514   };
00515 
00522   template<class V0, class V1>
00523   class Le : public MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND> {
00524   protected:
00525     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x0;
00526     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x1;
00528     static bool same(V0 x0, V1 x1);
00530     Le(Space& home, bool share, Le& p);
00532     Le(Home home, V0 x0, V1 x1);
00533   public:
00535     virtual Actor* copy(Space& home, bool share);
00537     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00539     static  ExecStatus post(Home home, V0 x0, V1 x1);
00540   };
00541 
00542 
00543   /*
00544    * Reified order propagators
00545    *
00546    */
00547 
00555   template<class View, class CtrlView, ReifyMode rm>
00556   class ReLq : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
00557   protected:
00558     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00559     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
00560     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
00561 
00563     ReLq(Space& home, bool share, ReLq& p);
00565     ReLq(Home home, View x0, View x1, CtrlView b);
00566   public:
00568     virtual Actor* copy(Space& home, bool share);
00570     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00572     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00573   };
00574 
00582   template<class View, class CtrlView, ReifyMode rm>
00583   class ReLqInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
00584   protected:
00585     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00586     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
00587 
00589     int c;
00591     ReLqInt(Space& home, bool share, ReLqInt& p);
00593     ReLqInt(Home home, View x, int c, CtrlView b);
00594   public:
00596     virtual Actor* copy(Space& home, bool share);
00598     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00600     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00601    };
00602 
00603 
00604 
00605 
00606 
00630   template<class VX, class VY>
00631   class LexLqLe : public Propagator {
00632   protected:
00634     ViewArray<VX> x;
00635     ViewArray<VY> y;
00637     bool strict;
00639     LexLqLe(Space& home, bool share, LexLqLe<VX,VY>& p);
00641     LexLqLe(Home home, ViewArray<VX>& x, ViewArray<VY>& y, bool strict);
00642   public:
00644     virtual Actor* copy(Space& home, bool share);
00646     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00648     virtual void reschedule(Space& home);
00650     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00652     static ExecStatus post(Home home, ViewArray<VX>& x, ViewArray<VY>& y,
00653                            bool strict);
00655     virtual size_t dispose(Space& home);
00656   };
00657 
00664   template<class VX, class VY>
00665   class LexNq : public Propagator {
00666   protected:
00668     VX x0;
00670     VY y0;
00672     VX x1;
00674     VY y1;
00676     ViewArray<VX> x;
00678     ViewArray<VY> y;
00680     ExecStatus resubscribe(Space& home,
00681                            RelTest rt, VX& x0, VY& y0, VX x1, VY y1);
00683     LexNq(Home home, ViewArray<VX>& x, ViewArray<VY>& y);
00685     LexNq(Space& home, bool share, LexNq<VX,VY>& p);
00686   public:
00688     virtual Actor* copy(Space& home, bool share);
00690     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00692     virtual void reschedule(Space& home);
00694     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00696     static  ExecStatus post(Home home, ViewArray<VX>& x, ViewArray<VY>& y);
00698     virtual size_t dispose(Space& home);
00699   };
00700 
00701 }}}
00702 
00703 #include <gecode/int/rel/eq.hpp>
00704 #include <gecode/int/rel/nq.hpp>
00705 #include <gecode/int/rel/lq-le.hpp>
00706 #include <gecode/int/rel/lex.hpp>
00707 
00708 #endif
00709 
00710 
00711 // STATISTICS: int-prop
00712