linear.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *     Tias Guns <tias.guns@cs.kuleuven.be>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2004
 *     Tias Guns, 2009
 *
 *  Last modified:
 *     $Date: 2009-02-18 12:54:16 +0100 (Wed, 18 Feb 2009) $ by $Author: schulte $
 *     $Revision: 8215 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#ifndef __GECODE_INT_LINEAR_HH__
#define __GECODE_INT_LINEAR_HH__

#include <gecode/int.hh>

namespace Gecode { namespace Int { namespace Linear {

  /*
   * Binary propagators
   *
   */

  template <class Val, class A, class B, PropCond pc>
  class LinBin : public Propagator {
  protected:
    A x0;
    B x1;
    Val c;
    LinBin(Space& home, bool share, LinBin& p);
    LinBin(Space& home, bool share, Propagator& p, A x0, B x1, Val c);
    LinBin(Space& home, A x0, B x1, Val c);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };

  template <class Val, class A, class B, PropCond pc, class Ctrl>
  class ReLinBin : public Propagator {
  protected:
    A x0;
    B x1;
    Val c;
    Ctrl b;
    ReLinBin(Space& home, bool share, ReLinBin& p);
    ReLinBin(Space& home, A x0, B x1, Val c, Ctrl b);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };

  template <class Val, class A, class B>
  class EqBin : public LinBin<Val,A,B,PC_INT_BND> {
  protected:
    using LinBin<Val,A,B,PC_INT_BND>::x0;
    using LinBin<Val,A,B,PC_INT_BND>::x1;
    using LinBin<Val,A,B,PC_INT_BND>::c;

    EqBin(Space& home, bool share, EqBin& p);
    EqBin(Space& home, A x0, B x1, Val c);
  public:
    EqBin(Space& home, bool share, Propagator& p, A x0, B x1, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, Val c);
  };

  template <class Val, class A, class B, class Ctrl>
  class ReEqBin : public ReLinBin<Val,A,B,PC_INT_BND,Ctrl> {
  protected:
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x0;
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x1;
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::c;
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::b;

    ReEqBin(Space& home, bool share, ReEqBin& p);
    ReEqBin(Space& home,A,B,Val,Ctrl);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, Val c, Ctrl b);
  };

  template <class Val, class A, class B>
  class NqBin : public LinBin<Val,A,B,PC_INT_VAL> {
  protected:
    using LinBin<Val,A,B,PC_INT_VAL>::x0;
    using LinBin<Val,A,B,PC_INT_VAL>::x1;
    using LinBin<Val,A,B,PC_INT_VAL>::c;

    NqBin(Space& home, bool share, NqBin& p);
    NqBin(Space& home, A x0, B x1, Val c);
  public:
    NqBin(Space& home, bool share, Propagator& p, A x0, B x1, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    static ExecStatus post(Space& home, A x0, B x1, Val c);
  };

  template <class Val, class A, class B>
  class LqBin : public LinBin<Val,A,B,PC_INT_BND> {
  protected:
    using LinBin<Val,A,B,PC_INT_BND>::x0;
    using LinBin<Val,A,B,PC_INT_BND>::x1;
    using LinBin<Val,A,B,PC_INT_BND>::c;

    LqBin(Space& home, bool share, LqBin& p);
    LqBin(Space& home, A x0, B x1, Val c);
  public:
    LqBin(Space& home, bool share, Propagator& p, A x0, B x1, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, Val c);
  };

  template <class Val, class A, class B>
  class GqBin : public LinBin<Val,A,B,PC_INT_BND> {
  protected:
    using LinBin<Val,A,B,PC_INT_BND>::x0;
    using LinBin<Val,A,B,PC_INT_BND>::x1;
    using LinBin<Val,A,B,PC_INT_BND>::c;

    GqBin(Space& home, bool share, GqBin& p);
    GqBin(Space& home, A x0, B x1, Val c);
  public:
    GqBin(Space& home, bool share, Propagator& p, A x0, B x1, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, Val c);
  };

  template <class Val, class A, class B>
  class ReLqBin : public ReLinBin<Val,A,B,PC_INT_BND,BoolView> {
  protected:
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x0;
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x1;
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::c;
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::b;

    ReLqBin(Space& home, bool share, ReLqBin& p);
    ReLqBin(Space& home, A x0, B x1, Val c, BoolView b);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, Val c, BoolView b);
  };

}}}

#include <gecode/int/linear/int-bin.hpp>

namespace Gecode { namespace Int { namespace Linear {

  /*
   * Ternary propagators
   *
   */

  template <class Val, class A, class B, class C, PropCond pc>
  class LinTer : public Propagator {
  protected:
    A x0;
    B x1;
    C x2;
    Val c;
    LinTer(Space& home, bool share, LinTer& p);
    LinTer(Space& home, A x0, B x1, C x2, Val c);
    LinTer(Space& home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };

  template <class Val, class A, class B, class C>
  class EqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
  protected:
    using LinTer<Val,A,B,C,PC_INT_BND>::x0;
    using LinTer<Val,A,B,C,PC_INT_BND>::x1;
    using LinTer<Val,A,B,C,PC_INT_BND>::x2;
    using LinTer<Val,A,B,C,PC_INT_BND>::c;

    EqTer(Space& home, bool share, EqTer& p);
    EqTer(Space& home, A x0, B x1, C x2, Val c);
  public:
    EqTer(Space& home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, C x2, Val c);
  };

  template <class Val, class A, class B, class C>
  class NqTer : public LinTer<Val,A,B,C,PC_INT_VAL> {
  protected:
    using LinTer<Val,A,B,C,PC_INT_VAL>::x0;
    using LinTer<Val,A,B,C,PC_INT_VAL>::x1;
    using LinTer<Val,A,B,C,PC_INT_VAL>::x2;
    using LinTer<Val,A,B,C,PC_INT_VAL>::c;

    NqTer(Space& home, bool share, NqTer& p);
    NqTer(Space& home, A x0, B x1, C x2, Val c);
  public:
    NqTer(Space& home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, C x2, Val c);
  };

  template <class Val, class A, class B, class C>
  class LqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
  protected:
    using LinTer<Val,A,B,C,PC_INT_BND>::x0;
    using LinTer<Val,A,B,C,PC_INT_BND>::x1;
    using LinTer<Val,A,B,C,PC_INT_BND>::x2;
    using LinTer<Val,A,B,C,PC_INT_BND>::c;

    LqTer(Space& home, bool share, LqTer& p);
    LqTer(Space& home, A x0, B x1, C x2, Val c);
  public:
    LqTer(Space& home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, A x0, B x1, C x2, Val c);
  };

}}}

#include <gecode/int/linear/int-ter.hpp>

namespace Gecode { namespace Int { namespace Linear {

  /*
   * n-ary propagators
   *
   */

  template <class Val, class P, class N, PropCond pc>
  class Lin : public Propagator {
  protected:
    ViewArray<P> x;
    ViewArray<N> y;
    Val c;

    Lin(Space& home, bool share, Lin& p);
    Lin(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };

  template <class Val, class P, class N, PropCond pc, class Ctrl>
  class ReLin : public Lin<Val,P,N,pc> {
  protected:
    Ctrl b;
    ReLin(Space& home, bool share, ReLin& p);
    ReLin(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
  public:
    virtual size_t dispose(Space& home);
  };

  template <class Val, class View>
  void bounds_p(ModEventDelta med, ViewArray<View>& x,
                Val& c, Val& sl, Val& su);

  template <class Val, class View>
  void bounds_n(ModEventDelta med, ViewArray<View>& y,
                Val& c, Val& sl, Val& su);

  template <class Val, class P, class N>
  class Eq : public Lin<Val,P,N,PC_INT_BND> {
  protected:
    using Lin<Val,P,N,PC_INT_BND>::x;
    using Lin<Val,P,N,PC_INT_BND>::y;
    using Lin<Val,P,N,PC_INT_BND>::c;

    Eq(Space& home, bool share, Eq& p);
  public:
    Eq(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus
    post(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c);
  };

  template <class Val, class View>
  class DomEq
    : public Lin<Val,View,View,PC_INT_DOM> {
  protected:
    using Lin<Val,View,View,PC_INT_DOM>::x;
    using Lin<Val,View,View,PC_INT_DOM>::y;
    using Lin<Val,View,View,PC_INT_DOM>::c;

    DomEq(Space& home, bool share, DomEq& p);
  public:
    DomEq(Space& home, ViewArray<View>& x, ViewArray<View>& y, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus
    post(Space& home, ViewArray<View>& x, ViewArray<View>& y, Val c);
  };

  template <class Val, class P, class N, class Ctrl>
  class ReEq : public ReLin<Val,P,N,PC_INT_BND,Ctrl> {
  protected:
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::x;
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::y;
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::c;
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::b;

    ReEq(Space& home, bool share, ReEq& p);
  public:
    ReEq(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus
    post(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
  };

  template <class Val, class P, class N>
  class Nq : public Lin<Val,P,N,PC_INT_VAL> {
  protected:
    using Lin<Val,P,N,PC_INT_VAL>::x;
    using Lin<Val,P,N,PC_INT_VAL>::y;
    using Lin<Val,P,N,PC_INT_VAL>::c;

    Nq(Space& home, bool share, Nq& p);
  public:
    Nq(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus
    post(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c);
  };

  template <class Val, class P, class N>
  class Lq : public Lin<Val,P,N,PC_INT_BND> {
  protected:
    using Lin<Val,P,N,PC_INT_BND>::x;
    using Lin<Val,P,N,PC_INT_BND>::y;
    using Lin<Val,P,N,PC_INT_BND>::c;

    Lq(Space& home, bool share, Lq& p);
  public:
    Lq(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus
    post(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c);
  };

  template <class Val, class P, class N>
  class ReLq : public ReLin<Val,P,N,PC_INT_BND,BoolView> {
  protected:
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::x;
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::y;
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::c;
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::b;

    ReLq(Space& home, bool share, ReLq& p);
  public:
    ReLq(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus
    post(Space& home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
  };

}}}

#include <gecode/int/linear/int-nary.hpp>
#include <gecode/int/linear/int-dom.hpp>

namespace Gecode { namespace Int { namespace Linear {

  /*
   * Boolean linear propagators
   *
   */

  template <class VX>
  class MemoryLinBoolInt : public Propagator {
  protected:
    ViewArray<VX> x;
    int n_s;
    int c;
    MemoryLinBoolInt(Space& home, bool share, MemoryLinBoolInt& p);
    MemoryLinBoolInt(Space& home, ViewArray<VX>& x, int n_s, int c);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };

  template <class VX>
  class SpeedLinBoolInt : public Propagator {
  protected:
    ViewArray<VX> x;
    int n_s;
    int c;
    Council<ViewAdvisor<VX> > co;
    SpeedLinBoolInt(Space& home, bool share, SpeedLinBoolInt& p);
    SpeedLinBoolInt(Space& home, ViewArray<VX>& x, int n_s, int c);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };

  template <class VX>
  class EqBoolInt {
  public:
    static const int threshold = 32;
    class Memory : public MemoryLinBoolInt<VX> {
    protected:
      using MemoryLinBoolInt<VX>::x;
      using MemoryLinBoolInt<VX>::n_s;
      using MemoryLinBoolInt<VX>::c;
    public:
      Memory(Space& home, bool share, Memory& p);
      Memory(Space& home, ViewArray<VX>& x, int c);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
      static ExecStatus post(Space& home, ViewArray<VX>& x, int c);
    };
    class Speed : public SpeedLinBoolInt<VX> {
    protected:
      using SpeedLinBoolInt<VX>::x;
      using SpeedLinBoolInt<VX>::n_s;
      using SpeedLinBoolInt<VX>::c;
      using SpeedLinBoolInt<VX>::co;
    public:
      Speed(Space& home, bool share, Speed& p);
      Speed(Space& home, ViewArray<VX>& x, int c);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    };
    static ExecStatus post(Space& home, ViewArray<VX>& x, int c);
  };

  template <class VX>
  class GqBoolInt {
  public:
    static const int threshold = 32;
    class Memory : public MemoryLinBoolInt<VX> {
    protected:
      using MemoryLinBoolInt<VX>::x;
      using MemoryLinBoolInt<VX>::n_s;
      using MemoryLinBoolInt<VX>::c;
    public:
      Memory(Space& home, bool share, Memory& p);
      Memory(Space& home, ViewArray<VX>& x, int c);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    };
    class Speed : public SpeedLinBoolInt<VX> {
    protected:
      using SpeedLinBoolInt<VX>::x;
      using SpeedLinBoolInt<VX>::n_s;
      using SpeedLinBoolInt<VX>::c;
      using SpeedLinBoolInt<VX>::co;
    public:
      Speed(Space& home, bool share, Speed& p);
      Speed(Space& home, ViewArray<VX>& x, int c);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    };
  public:
    static ExecStatus post(Space& home, ViewArray<VX>& x, int c);
  };

  template<class VX>
  class NqBoolInt : public BinaryPropagator<VX,PC_INT_VAL> {
  protected:
    using BinaryPropagator<VX,PC_INT_VAL>::x0;
    using BinaryPropagator<VX,PC_INT_VAL>::x1;
    ViewArray<VX> x;
    int c;
    bool resubscribe(Space& home, VX& y);
    NqBoolInt(Space& home,  ViewArray<VX>& b, int c);
    NqBoolInt(Space& home, bool share, NqBoolInt<VX>& p);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static  ExecStatus post(Space& home, ViewArray<VX>& b, int c);
  };


  /*
   * Reified boolean linear propagators
   *
   */

  template <class VX, class VB>
  class MemoryReLinBoolInt : public MemoryLinBoolInt<VX> {
  protected:
    using MemoryLinBoolInt<VX>::x;
    using MemoryLinBoolInt<VX>::n_s;
    using MemoryLinBoolInt<VX>::c;
    VB b;
    MemoryReLinBoolInt(Space& home, bool share, MemoryReLinBoolInt& p);
    MemoryReLinBoolInt(Space& home, ViewArray<VX>& x, int n_s, int c, VB b);
  public:
    virtual size_t dispose(Space& home);
  };

  template <class VX, class VB>
  class SpeedReLinBoolInt : public SpeedLinBoolInt<VX> {
  protected:
    using SpeedLinBoolInt<VX>::x;
    using SpeedLinBoolInt<VX>::n_s;
    using SpeedLinBoolInt<VX>::c;
    using SpeedLinBoolInt<VX>::co;
    VB b;
    SpeedReLinBoolInt(Space& home, bool share, SpeedReLinBoolInt& p);
    SpeedReLinBoolInt(Space& home, ViewArray<VX>& x, int n_s, int c, VB b);
  public:
    virtual size_t dispose(Space& home);
  };




  template <class VX, class VB>
  class ReGqBoolInt {
  public:
    static const int threshold = 32;
    class Memory : public MemoryReLinBoolInt<VX,VB> {
    protected:
      using MemoryReLinBoolInt<VX,VB>::x;
      using MemoryReLinBoolInt<VX,VB>::n_s;
      using MemoryReLinBoolInt<VX,VB>::c;
      using MemoryReLinBoolInt<VX,VB>::b;
    public:
      Memory(Space& home, bool share, Memory& p);
      Memory(Space& home, ViewArray<VX>& x, int c, VB b);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
      ExecStatus rewrite_inverse(Space& home, ViewArray<BoolView>& x, int c);
      ExecStatus rewrite_inverse(Space& home, ViewArray<NegBoolView>& x, int c);
    };
    class Speed : public SpeedReLinBoolInt<VX,VB> {
    protected:
      using SpeedReLinBoolInt<VX,VB>::x;
      using SpeedReLinBoolInt<VX,VB>::n_s;
      using SpeedReLinBoolInt<VX,VB>::c;
      using SpeedReLinBoolInt<VX,VB>::co;
      using SpeedReLinBoolInt<VX,VB>::b;
    public:
      Speed(Space& home, bool share, Speed& p);
      Speed(Space& home, ViewArray<VX>& x, int c, VB b);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
      ExecStatus rewrite_inverse(Space& home, ViewArray<BoolView>& x, int c);
      ExecStatus rewrite_inverse(Space& home, ViewArray<NegBoolView>& x, int c);
    };
  public:
    static ExecStatus post(Space& home, ViewArray<VX>& x, int c, VB b);
  };

  template <class VX, class VB>
  class ReEqBoolInt {
  public:
    static const int threshold = 32;
    class Memory : public MemoryReLinBoolInt<VX,VB> {
    protected:
      using MemoryReLinBoolInt<VX,VB>::x;
      using MemoryReLinBoolInt<VX,VB>::n_s;
      using MemoryReLinBoolInt<VX,VB>::c;
      using MemoryReLinBoolInt<VX,VB>::b;
    public:
      Memory(Space& home, bool share, Memory& p);
      Memory(Space& home, ViewArray<VX>& x, int c, VB b);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    };
    class Speed : public SpeedReLinBoolInt<VX,VB> {
    protected:
      using SpeedReLinBoolInt<VX,VB>::x;
      using SpeedReLinBoolInt<VX,VB>::n_s;
      using SpeedReLinBoolInt<VX,VB>::c;
      using SpeedReLinBoolInt<VX,VB>::co;
      using SpeedReLinBoolInt<VX,VB>::b;
    public:
      Speed(Space& home, bool share, Speed& p);
      Speed(Space& home, ViewArray<VX>& x, int c, VB b);
      virtual Actor* copy(Space& home, bool share);
      virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
      virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    };
    static ExecStatus post(Space& home, ViewArray<VX>& x, int c, VB b);
  };

}}}

#include <gecode/int/linear/bool-int.hpp>

namespace Gecode { namespace Int { namespace Linear {

  template <class XV, class YV>
  class LinBoolView : public Propagator {
  protected:
    ViewArray<XV> x;
    YV y;
    int c;
    LinBoolView(Space& home, bool share, LinBoolView& p);
    LinBoolView(Space& home, ViewArray<XV>& x, YV y, int c);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };


  template <class XV, class YV, class BV>
  class ReLinBoolView : public LinBoolView<XV,YV> {
  protected:
    using LinBoolView<XV,YV>::x;
    using LinBoolView<XV,YV>::y;
    using LinBoolView<XV,YV>::c;
    BV b;
    ReLinBoolView(Space& home, bool share, ReLinBoolView& p);
    ReLinBoolView(Space& home, ViewArray<XV>& x, YV y, int c, BV b);
  public:
    virtual size_t dispose(Space& home);
  };


  template <class XV, class YV>
  class EqBoolView : public LinBoolView<XV,YV> {
  protected:
    using LinBoolView<XV,YV>::x;
    using LinBoolView<XV,YV>::y;
    using LinBoolView<XV,YV>::c;

    EqBoolView(Space& home, bool share, EqBoolView& p);
    EqBoolView(Space& home, ViewArray<XV>& x, YV y, int c);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, ViewArray<XV>& x, YV y, int c);
  };

  template <class XV, class YV>
  class NqBoolView : public LinBoolView<XV,YV> {
  protected:
    using LinBoolView<XV,YV>::x;
    using LinBoolView<XV,YV>::y;
    using LinBoolView<XV,YV>::c;

    NqBoolView(Space& home, bool share, NqBoolView& p);
    NqBoolView(Space& home, ViewArray<XV>& x, YV y, int c);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, ViewArray<XV>& x, YV y, int c);
  };

  template <class XV, class YV>
  class GqBoolView : public LinBoolView<XV,YV> {
  protected:
    using LinBoolView<XV,YV>::x;
    using LinBoolView<XV,YV>::y;
    using LinBoolView<XV,YV>::c;

    GqBoolView(Space& home, bool share, GqBoolView& p);
    GqBoolView(Space& home, ViewArray<XV>& x, YV y, int c);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, ViewArray<XV>& x, YV y, int c);
  };

  template <class XV, class YV, class BV>
  class ReEqBoolView : public ReLinBoolView<XV,YV,BV> {
  protected:
    using ReLinBoolView<XV,YV,BV>::x;
    using ReLinBoolView<XV,YV,BV>::y;
    using ReLinBoolView<XV,YV,BV>::c;
    using ReLinBoolView<XV,YV,BV>::b;

    ReEqBoolView(Space& home, bool share, ReEqBoolView& p);
    ReEqBoolView(Space& home, ViewArray<XV>& x, YV y, int c, BV b);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, ViewArray<XV>& x, YV y, int c, BV b);
  };

  template <class XV, class YV, class BV>
  class ReGqBoolView : public ReLinBoolView<XV,YV,BV> {
  protected:
    using ReLinBoolView<XV,YV,BV>::x;
    using ReLinBoolView<XV,YV,BV>::y;
    using ReLinBoolView<XV,YV,BV>::c;
    using ReLinBoolView<XV,YV,BV>::b;

    ReGqBoolView(Space& home, bool share, ReGqBoolView& p);
    ReGqBoolView(Space& home, ViewArray<XV>& x, YV y, int c, BV b);
  public:
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, ViewArray<XV>& x, YV y, int c, BV b);
  };

}}}

#include <gecode/int/linear/bool-view.hpp>

namespace Gecode { namespace Int { namespace Linear {

  class ScaleBool {
  public:
    int      a;
    BoolView x;
  };

  class ScaleBoolArray {
  private:
    ScaleBool* _fst;
    ScaleBool* _lst;
  public:
    ScaleBoolArray(void);
    ScaleBoolArray(Space& home, int n);
    void subscribe(Space& home, Propagator& p);
    void cancel(Space& home, Propagator& p);
    void update(Space& home, bool share, ScaleBoolArray& sba);
    ScaleBool* fst(void) const;
    ScaleBool* lst(void) const;
    void fst(ScaleBool* f);
    void lst(ScaleBool* l);
    bool empty(void) const;
    int size(void) const;
  private:
    class ScaleDec {
    public:
      bool
      operator ()(const ScaleBool& x, const ScaleBool& y);
    };
  public:
    void sort(void);
  };


  class EmptyScaleBoolArray {
  public:
    EmptyScaleBoolArray(void);
    EmptyScaleBoolArray(Space& home, int n);
    void subscribe(Space& home, Propagator& p);
    void cancel(Space& home, Propagator& p);
    void update(Space& home, bool share, EmptyScaleBoolArray& esba);
    ScaleBool* fst(void) const;
    ScaleBool* lst(void) const;
    void fst(ScaleBool* f);
    void lst(ScaleBool* l);
    bool empty(void) const;
    int size(void) const;
    void sort(void);
  };


  template <class SBAP, class SBAN, class VX, PropCond pcx>
  class LinBoolScale : public Propagator {
  protected:
    SBAP p;
    SBAN n;
    VX   x;
    int  c;
  public:
    LinBoolScale(Space& home, SBAP& p, SBAN& n, VX x, int c);
    LinBoolScale(Space& home, bool share, Propagator& pr,
                 SBAP& p, SBAN& n, VX x, int c);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual size_t dispose(Space& home);
  };

  template <class SBAP, class SBAN, class VX>
  class EqBoolScale : public LinBoolScale<SBAP,SBAN,VX,PC_INT_BND> {
  protected:
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::p;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::n;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::x;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::c;
  public:
    EqBoolScale(Space& home, SBAP& p, SBAN& n, VX x, int c);
    EqBoolScale(Space& home, bool share, Propagator& pr,
                SBAP& p, SBAN& n, VX x, int c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, SBAP& p, SBAN& n, VX x, int c);
  };

  template <class SBAP, class SBAN, class VX>
  class LqBoolScale : public LinBoolScale<SBAP,SBAN,VX,PC_INT_BND> {
  protected:
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::p;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::n;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::x;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::c;
  public:
    LqBoolScale(Space& home, SBAP& p, SBAN& n, VX x, int c);
    LqBoolScale(Space& home, bool share, Propagator& pr,
                SBAP& p, SBAN& n, VX x, int c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, SBAP& p, SBAN& n, VX x, int c);
  };

  template <class SBAP, class SBAN, class VX>
  class NqBoolScale : public LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL> {
  protected:
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::p;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::n;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::x;
    using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::c;
  public:
    NqBoolScale(Space& home, SBAP& p, SBAN& n, VX x, int c);
    NqBoolScale(Space& home, bool share, Propagator& pr,
                SBAP& p, SBAN& n, VX x, int c);
    virtual Actor* copy(Space& home, bool share);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Space& home, SBAP& p, SBAN& n, VX x, int c);
  };

}}}

#include <gecode/int/linear/bool-scale.hpp>

namespace Gecode { namespace Int { namespace Linear {

  template<class View>
  class Term {
  public:
    int a;
    View x;
  };

  template<class View>
  void estimate(Term<View>* t, int n, int c,
                int& l, int& u);

  template<class View>
  bool normalize(Term<View>* t, int &n,
                 Term<View>* &t_p, int &n_p,
                 Term<View>* &t_n, int &n_n);


  GECODE_INT_EXPORT void
  post(Space& home, Term<IntView>* t, int n, IntRelType r, int c,
       IntConLevel=ICL_DEF);

  GECODE_INT_EXPORT void
  post(Space& home, Term<IntView>* t, int n, IntRelType r, int c, BoolView b,
       IntConLevel=ICL_DEF);

  GECODE_INT_EXPORT void
  post(Space& home, Term<BoolView>* t, int n, IntRelType r, int c,
       IntConLevel=ICL_DEF);

  GECODE_INT_EXPORT void
  post(Space& home, Term<BoolView>* t, int n, IntRelType r, int c, BoolView b,
       IntConLevel=ICL_DEF);

  GECODE_INT_EXPORT void
  post(Space& home, Term<BoolView>* t, int n, IntRelType r, IntView y, int c=0,
       IntConLevel=ICL_DEF);

  GECODE_INT_EXPORT void
  post(Space& home, Term<BoolView>* t, int n, IntRelType r, IntView y,
       BoolView b, IntConLevel=ICL_DEF);

}}}

#include <gecode/int/linear/post.hpp>

#endif

// STATISTICS: int-prop