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  *  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_REL_HH__
00041 #define __GECODE_INT_REL_HH__
00042 
00043 #include <gecode/int.hh>
00044 
00050 namespace Gecode { namespace Int { namespace Rel {
00051 
00052   /*
00053    * Equality propagators
00054    *
00055    */
00056 
00066   template<class View0,class View1>
00067   class EqDom :
00068     public MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM> {
00069   protected:
00070     using MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>::x0;
00071     using MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>::x1;
00072 
00074     EqDom(Space& home, EqDom<View0,View1>& p);
00075   public:
00077     EqDom(Home home, View0 x0, View1 x1);
00079     EqDom(Space& home, Propagator& p, View0 x0, View1 x1);
00081     virtual Actor* copy(Space& home);
00089     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00091     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00093     static  ExecStatus post(Home home, View0 x0, View1 x1);
00094   };
00095 
00102   template<class View0, class View1>
00103   class EqVal :
00104     public MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL> {
00105   protected:
00106     using MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL>::x0;
00107     using MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL>::x1;
00108 
00110     EqVal(Space& home, EqVal<View0,View1>& p);
00111   public:
00113     EqVal(Home home, View0 x0, View1 x1);
00115     EqVal(Space& home, Propagator& p, View0 x0, View1 x1);
00117     virtual Actor* copy(Space& home);
00119     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00121     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00123     static  ExecStatus post(Home home, View0 x0, View1 x1);
00124   };
00125 
00132   template<class View0, class View1>
00133   class EqBnd :
00134     public MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND> {
00135   protected:
00136     using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x0;
00137     using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x1;
00138 
00140     EqBnd(Space& home, EqBnd<View0,View1>& p);
00141   public:
00143     EqBnd(Home home, View0 x0, View1 x1);
00145     EqBnd(Space& home, Propagator& p, View0 x0, View1 x1);
00147     virtual Actor* copy(Space& home);
00149     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00151     static  ExecStatus post(Home home, View0 x0, View1 x1);
00152   };
00153 
00163   template<class View>
00164   class NaryEqDom : public NaryPropagator<View,PC_INT_DOM> {
00165   protected:
00166     using NaryPropagator<View,PC_INT_DOM>::x;
00167 
00169     NaryEqDom(Space& home, NaryEqDom<View>& p);
00171     NaryEqDom(Home home, ViewArray<View>&);
00172   public:
00174     virtual Actor* copy(Space& home);
00182     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00184     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00186     static  ExecStatus post(Home home, ViewArray<View>& x);
00187   };
00188 
00195   template<class View>
00196   class NaryEqBnd : public NaryPropagator<View,PC_INT_BND> {
00197   protected:
00198     using NaryPropagator<View,PC_INT_BND>::x;
00199 
00201     NaryEqBnd(Space& home, NaryEqBnd<View>& p);
00203     NaryEqBnd(Home home, ViewArray<View>&);
00204   public:
00206     virtual Actor* copy(Space& home);
00213     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00215     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00217     static  ExecStatus post(Home home, ViewArray<View>& x);
00218   };
00219 
00229   template<class View, int o>
00230   class NaryLqLe : public NaryPropagator<View,PC_INT_NONE> {
00231   protected:
00232     using NaryPropagator<View,PC_INT_NONE>::x;
00234     class Index : public Advisor {
00235     public:
00237       int i;
00239       Index(Space& home, Propagator& p, Council<Index>& c, int i);
00241       Index(Space& home, Index& a);
00242     };
00244     Council<Index> c;
00246     class Pos : public FreeList {
00247     public:
00249       int p;
00250 
00252 
00253 
00254       Pos(int p, Pos* n);
00256 
00258 
00259 
00260       Pos* next(void) const;
00262 
00264 
00265 
00266       void dispose(Space& home);
00267 
00269       static void* operator new(size_t s, Space& home);
00271       static void operator delete(void* p);
00273       static void operator delete(void* p, Space& home);
00275     };
00277     Pos* pos;
00279     bool empty(void) const;
00281     int pop(Space& home);
00283     void push(Space& home, int p);
00285     bool run;
00287     int n_subsumed;
00289     static const int n_threshold = 7;
00291     NaryLqLe(Space& home, NaryLqLe<View,o>& p);
00293     NaryLqLe(Home home, ViewArray<View>&);
00294   public:
00296     virtual Actor* copy(Space& home);
00298     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00300     virtual void reschedule(Space& home);
00302     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00304     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00306     virtual size_t dispose(Space& home);
00308     static ExecStatus post(Home home, ViewArray<View>& x);
00309   };
00310 
00317   template<class View>
00318   class NaryNq : public NaryPropagator<View,PC_INT_VAL> {
00319   protected:
00320     using NaryPropagator<View,PC_INT_VAL>::x;
00322     NaryNq(Home home, ViewArray<View>& x);
00324     NaryNq(Space& home, NaryNq<View>& p);
00325   public:
00327     virtual Actor* copy(Space& home);
00329     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00331     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00333     static  ExecStatus post(Home home, ViewArray<View>& x);
00335     virtual size_t dispose(Space& home);
00336   };
00337 
00338 
00345   template<class View, class CtrlView, ReifyMode rm>
00346   class ReEqDom : public ReBinaryPropagator<View,PC_INT_DOM,CtrlView> {
00347   protected:
00348     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
00349     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x1;
00350     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::b;
00351 
00353     ReEqDom(Space& home, ReEqDom& p);
00355     ReEqDom(Home home, View x0, View x1, CtrlView b);
00356   public:
00358     virtual Actor* copy(Space& home);
00360     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00362     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00363   };
00364 
00371   template<class View, class CtrlView, ReifyMode rm>
00372   class ReEqBnd : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
00373   protected:
00374     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00375     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
00376     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
00377 
00379     ReEqBnd(Space& home, ReEqBnd& p);
00381     ReEqBnd(Home home, View x0, View x1, CtrlView b);
00382   public:
00384     virtual Actor*     copy(Space& home);
00386     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00388     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00389   };
00390 
00397   template<class View, class CtrlView, ReifyMode rm>
00398   class ReEqDomInt : public ReUnaryPropagator<View,PC_INT_DOM,CtrlView> {
00399   protected:
00400     using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
00401     using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::b;
00402 
00404     int c;
00406     ReEqDomInt(Space& home, ReEqDomInt& p);
00408     ReEqDomInt(Home home, View x, int c, CtrlView b);
00409   public:
00411     virtual Actor* copy(Space& home);
00413     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00415     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00416   };
00417 
00424   template<class View, class CtrlView, ReifyMode rm>
00425   class ReEqBndInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
00426   protected:
00427     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00428     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
00429 
00431     int c;
00433     ReEqBndInt(Space& home, ReEqBndInt& p);
00435     ReEqBndInt(Home home, View x, int c, CtrlView b);
00436   public:
00438     virtual Actor* copy(Space& home);
00440     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00442     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00443   };
00444 
00445 
00446 
00447 
00448   /*
00449    * Disequality propagators
00450    *
00451    */
00452 
00459   template<class V0, class V1>
00460   class Nq : public MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL> {
00461   protected:
00462     using MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>::x0;
00463     using MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>::x1;
00464 
00466     Nq(Space& home, Nq<V0,V1>& p);
00468     Nq(Home home, V0 x0, V1 x1);
00469   public:
00471     virtual Actor* copy(Space& home);
00473     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00475     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00477     static  ExecStatus post(Home home, V0 x0, V1 x1);
00478   };
00479 
00480   /*
00481    * Order propagators
00482    *
00483    */
00484 
00492   template<class V0, class V1>
00493   class Lq : public MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND> {
00494   protected:
00495     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x0;
00496     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x1;
00498     Lq(Space& home, Lq& p);
00500     Lq(Home home, V0 x0, V1 x1);
00501   public:
00503     virtual Actor* copy(Space& home);
00505     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00507     static  ExecStatus post(Home home, V0 x0, V1 x1);
00508   };
00509 
00516   template<class V0, class V1>
00517   class Le : public MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND> {
00518   protected:
00519     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x0;
00520     using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x1;
00522     Le(Space& home, Le& p);
00524     Le(Home home, V0 x0, V1 x1);
00525   public:
00527     virtual Actor* copy(Space& home);
00529     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00531     static  ExecStatus post(Home home, V0 x0, V1 x1);
00532   };
00533 
00534 
00535   /*
00536    * Reified order propagators
00537    *
00538    */
00539 
00547   template<class View, class CtrlView, ReifyMode rm>
00548   class ReLq : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
00549   protected:
00550     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00551     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
00552     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
00553 
00555     ReLq(Space& home, ReLq& p);
00557     ReLq(Home home, View x0, View x1, CtrlView b);
00558   public:
00560     virtual Actor* copy(Space& home);
00562     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00564     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00565   };
00566 
00574   template<class View, class CtrlView, ReifyMode rm>
00575   class ReLqInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
00576   protected:
00577     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00578     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
00579 
00581     int c;
00583     ReLqInt(Space& home, ReLqInt& p);
00585     ReLqInt(Home home, View x, int c, CtrlView b);
00586   public:
00588     virtual Actor* copy(Space& home);
00590     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00592     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00593    };
00594 
00595 
00596 
00597 
00598 
00622   template<class VX, class VY>
00623   class LexLqLe : public Propagator {
00624   protected:
00626     ViewArray<VX> x;
00627     ViewArray<VY> y;
00629     bool strict;
00631     LexLqLe(Space& home, LexLqLe<VX,VY>& p);
00633     LexLqLe(Home home, ViewArray<VX>& x, ViewArray<VY>& y, bool strict);
00634   public:
00636     virtual Actor* copy(Space& home);
00638     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00640     virtual void reschedule(Space& home);
00642     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00644     static ExecStatus post(Home home, ViewArray<VX>& x, ViewArray<VY>& y,
00645                            bool strict);
00647     virtual size_t dispose(Space& home);
00648   };
00649 
00656   template<class VX, class VY>
00657   class LexNq : public Propagator {
00658   protected:
00660     VX x0;
00662     VY y0;
00664     VX x1;
00666     VY y1;
00668     ViewArray<VX> x;
00670     ViewArray<VY> y;
00672     ExecStatus resubscribe(Space& home,
00673                            RelTest rt, VX& x0, VY& y0, VX x1, VY y1);
00675     LexNq(Home home, ViewArray<VX>& x, ViewArray<VY>& y);
00677     LexNq(Space& home, LexNq<VX,VY>& p);
00678   public:
00680     virtual Actor* copy(Space& home);
00682     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00684     virtual void reschedule(Space& home);
00686     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00688     static  ExecStatus post(Home home, ViewArray<VX>& x, ViewArray<VY>& y);
00690     virtual size_t dispose(Space& home);
00691   };
00692 
00693 }}}
00694 
00695 #include <gecode/int/rel/eq.hpp>
00696 #include <gecode/int/rel/nq.hpp>
00697 #include <gecode/int/rel/lq-le.hpp>
00698 #include <gecode/int/rel/lex.hpp>
00699 
00700 #endif
00701 
00702 
00703 // STATISTICS: int-prop
00704