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: 2011-07-06 21:56:28 +0200 (Wed, 06 Jul 2011) $ by $Author: schulte $
00017  *     $Revision: 12151 $
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 EqBnd :
00108     public MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND> {
00109   protected:
00110     using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x0;
00111     using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x1;
00112 
00114     EqBnd(Space& home, bool share, EqBnd<View0,View1>& p);
00115   public:
00117     EqBnd(Home home, View0 x0, View1 x1);
00119     EqBnd(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
00121     virtual Actor* copy(Space& home, bool share);
00123     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00125     static  ExecStatus post(Home home, View0 x0, View1 x1);
00126   };
00127 
00137   template<class View>
00138   class NaryEqDom : public NaryPropagator<View,PC_INT_DOM> {
00139   protected:
00140     using NaryPropagator<View,PC_INT_DOM>::x;
00141 
00143     NaryEqDom(Space& home, bool share, NaryEqDom<View>& p);
00145     NaryEqDom(Home home, ViewArray<View>&);
00146   public:
00148     virtual Actor* copy(Space& home, bool share);
00156     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00158     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00160     static  ExecStatus post(Home home, ViewArray<View>& x);
00161   };
00162 
00169   template<class View>
00170   class NaryEqBnd : public NaryPropagator<View,PC_INT_BND> {
00171   protected:
00172     using NaryPropagator<View,PC_INT_BND>::x;
00173 
00175     NaryEqBnd(Space& home, bool share, NaryEqBnd<View>& p);
00177     NaryEqBnd(Home home, ViewArray<View>&);
00178   public:
00180     virtual Actor* copy(Space& home, bool share);
00187     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00189     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00191     static  ExecStatus post(Home home, ViewArray<View>& x);
00192   };
00193 
00203   template<class View, int o>
00204   class NaryLqLe : public NaryPropagator<View,PC_INT_NONE> {
00205   protected:
00206     using NaryPropagator<View,PC_INT_NONE>::x;
00208     class Index : public Advisor {
00209     public:
00211       int i;
00213       Index(Space& home, Propagator& p, Council<Index>& c, int i);
00215       Index(Space& home, bool share, Index& a);
00216     };
00218     Council<Index> c;
00220     class Pos : public FreeList {
00221     public:
00223       int p;
00224 
00226 
00227 
00228       Pos(int p, Pos* n);
00230 
00232 
00233 
00234       Pos* next(void) const;
00236 
00238 
00239 
00240       void dispose(Space& home);
00241 
00243       static void* operator new(size_t s, Space& home);
00245       static void operator delete(void* p);
00247       static void operator delete(void* p, Space& home);
00249     };
00251     Pos* pos;
00253     bool empty(void) const;
00255     int pop(Space& home);
00257     void push(Space& home, int p);
00259     bool run;
00261     int n_subsumed;
00263     static const int n_threshold = 7;
00265     NaryLqLe(Space& home, bool share, NaryLqLe<View,o>& p);
00267     NaryLqLe(Home home, ViewArray<View>&);
00268   public:
00270     virtual Actor* copy(Space& home, bool share);
00272     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00274     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00276     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00278     virtual size_t dispose(Space& home);
00280     static ExecStatus post(Home home, ViewArray<View>& x);
00281   };
00282 
00289   template<class View>
00290   class NaryNq : public NaryPropagator<View,PC_INT_VAL> {
00291   protected:
00292     using NaryPropagator<View,PC_INT_VAL>::x;
00294     NaryNq(Home home, ViewArray<View>& x);
00296     NaryNq(Space& home, bool share, NaryNq<View>& p);
00297   public:
00299     virtual Actor* copy(Space& home, bool share);
00301     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00303     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00305     static  ExecStatus post(Home home, ViewArray<View>& x);
00307     virtual size_t dispose(Space& home);
00308   };
00309 
00310 
00317   template<class View, class CtrlView>
00318   class ReEqDom : public ReBinaryPropagator<View,PC_INT_DOM,CtrlView> {
00319   protected:
00320     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
00321     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x1;
00322     using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::b;
00323 
00325     ReEqDom(Space& home, bool share, ReEqDom& p);
00327     ReEqDom(Home home, View x0, View x1, CtrlView b);
00328   public:
00330     virtual Actor* copy(Space& home, bool share);
00332     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00334     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00335   };
00336 
00343   template<class View, class CtrlView>
00344   class ReEqBnd : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
00345   protected:
00346     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00347     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
00348     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
00349 
00351     ReEqBnd(Space& home, bool share, ReEqBnd& p);
00353     ReEqBnd(Home home, View x0, View x1, CtrlView b);
00354   public:
00356     virtual Actor*     copy(Space& home, bool share);
00358     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00360     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00361   };
00362 
00369   template<class View, class CtrlView>
00370   class ReEqDomInt : public ReUnaryPropagator<View,PC_INT_DOM,CtrlView> {
00371   protected:
00372     using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
00373     using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::b;
00374 
00376     int c;
00378     ReEqDomInt(Space& home, bool share, ReEqDomInt& p);
00380     ReEqDomInt(Home home, View x, int c, CtrlView b);
00381   public:
00383     virtual Actor* copy(Space& home, bool share);
00385     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00387     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00388   };
00389 
00396   template<class View, class CtrlView>
00397   class ReEqBndInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
00398   protected:
00399     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00400     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
00401 
00403     int c;
00405     ReEqBndInt(Space& home, bool share, ReEqBndInt& p);
00407     ReEqBndInt(Home home, View x, int c, CtrlView b);
00408   public:
00410     virtual Actor* copy(Space& home, bool share);
00412     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00414     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00415   };
00416 
00417 
00418 
00419 
00420   /*
00421    * Disequality propagators
00422    *
00423    */
00424 
00431   template<class View>
00432   class Nq : public BinaryPropagator<View,PC_INT_VAL> {
00433   protected:
00434     using BinaryPropagator<View,PC_INT_VAL>::x0;
00435     using BinaryPropagator<View,PC_INT_VAL>::x1;
00436 
00438     Nq(Space& home, bool share, Nq<View>& p);
00440     Nq(Home home, View x0, View x1);
00441   public:
00443     virtual Actor* copy(Space& home, bool share);
00445     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00447     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00449     static  ExecStatus post(Home home, View x0, View x1);
00450   };
00451 
00452   /*
00453    * Order propagators
00454    *
00455    */
00456 
00464   template<class View>
00465   class Lq : public BinaryPropagator<View,PC_INT_BND> {
00466   protected:
00467     using BinaryPropagator<View,PC_INT_BND>::x0;
00468     using BinaryPropagator<View,PC_INT_BND>::x1;
00469 
00471     Lq(Space& home, bool share, Lq& p);
00473     Lq(Home home, View x0, View x1);
00474   public:
00476     virtual Actor*     copy(Space& home, bool share);
00478     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00480     static  ExecStatus post(Home home, View x0, View x1);
00481   };
00482 
00489   template<class View>
00490   class Le : public BinaryPropagator<View,PC_INT_BND> {
00491   protected:
00492     using BinaryPropagator<View,PC_INT_BND>::x0;
00493     using BinaryPropagator<View,PC_INT_BND>::x1;
00494 
00496     Le(Space& home, bool share, Le& p);
00498     Le(Home home, View x0, View x1);
00499   public:
00501     virtual Actor* copy(Space& home, bool share);
00503     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00505     static  ExecStatus post(Home home, View x0, View x1);
00506   };
00507 
00508 
00509   /*
00510    * Reified order propagators
00511    *
00512    */
00513 
00521   template<class View, class CtrlView>
00522   class ReLq : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
00523   protected:
00524     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00525     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
00526     using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
00527 
00529     ReLq(Space& home, bool share, ReLq& p);
00531     ReLq(Home home, View x0, View x1, CtrlView b);
00532   public:
00534     virtual Actor* copy(Space& home, bool share);
00536     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00538     static  ExecStatus post(Home home, View x0, View x1, CtrlView b);
00539   };
00540 
00548   template<class View, class CtrlView>
00549   class ReLqInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
00550   protected:
00551     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
00552     using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
00553 
00555     int c;
00557     ReLqInt(Space& home, bool share, ReLqInt& p);
00559     ReLqInt(Home home, View x, int c, CtrlView b);
00560   public:
00562     virtual Actor* copy(Space& home, bool share);
00564     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00566     static  ExecStatus post(Home home, View x, int c, CtrlView b);
00567    };
00568 
00569 
00570 
00571 
00572 
00596   template<class View>
00597   class LexLqLe : public Propagator {
00598   protected:
00600     ViewArray<View> x, y;
00602     bool strict;
00604     LexLqLe(Space& home, bool share, LexLqLe<View>& p);
00606     LexLqLe(Home home, ViewArray<View>& x, ViewArray<View>& y, bool strict);
00607   public:
00609     virtual Actor* copy(Space& home, bool share);
00611     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00613     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00615     static ExecStatus post(Home home, ViewArray<View>& x, ViewArray<View>& y,
00616                            bool strict);
00618     virtual size_t dispose(Space& home);
00619   };
00620 
00627   template<class View>
00628   class LexNq : public Propagator {
00629   protected:
00631     View x0, y0, x1, y1;
00633     ViewArray<View> x, y;
00635     ExecStatus resubscribe(Space& home, 
00636                            RelTest rt, View& x0, View& y0, View x1, View y1);
00638     LexNq(Home home, ViewArray<View>& x, ViewArray<View>& y);
00640     LexNq(Space& home, bool share, LexNq<View>& p);
00641   public:
00643     virtual Actor* copy(Space& home, bool share);
00645     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00647     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00649     static  ExecStatus post(Home home, ViewArray<View>& x, ViewArray<View>& y);
00651     virtual size_t dispose(Space& home);
00652   };
00653 
00654 }}}
00655 
00656 #include <gecode/int/rel/eq.hpp>
00657 #include <gecode/int/rel/nq.hpp>
00658 #include <gecode/int/rel/lq-le.hpp>
00659 #include <gecode/int/rel/lex.hpp>
00660 
00661 #endif
00662 
00663 
00664 // STATISTICS: int-prop
00665