view.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Contributing authors:
 *     Samuel Gagnon <samuel.gagnon92@gmail.com>
 *
 *  Copyright:
 *     Christian Schulte, 2005
 *     Samuel Gagnon, 2018
 *
 *  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.
 *
 */

#include <iostream>

namespace Gecode { namespace Int {

  template<class View>
  class ViewRanges {
  public:


    ViewRanges(void);
    ViewRanges(const View& x);
    void init(const View& x);



    bool operator ()(void) const;
    void operator ++(void);



    int min(void) const;
    int max(void) const;
    unsigned int width(void) const;
  };

  template<class View>
  class ViewValues : public Iter::Ranges::ToValues<ViewRanges<View> > {
  public:


    ViewValues(void);
    ViewValues(const View& x);
    void init(const View& x);
  };

}}

#include <gecode/int/view/iter.hpp>

namespace Gecode { namespace Int {

  class IntView : public VarImpView<IntVar> {
  protected:
    using VarImpView<IntVar>::x;
  public:


    IntView(void);
    IntView(const IntVar& y);
    IntView(IntVarImp* y);



    int min(void) const;
    int max(void) const;
    int med(void) const;
    int val(void) const;
#ifdef GECODE_HAS_CBS

    int baseval(int val) const;
#endif

    unsigned int size(void) const;
    unsigned int width(void) const;
    unsigned int regret_min(void) const;
    unsigned int regret_max(void) const;



    bool range(void) const;

    bool in(int n) const;
    bool in(long long int n) const;



    ModEvent lq(Space& home, int n);
    ModEvent lq(Space& home, long long int n);

    ModEvent le(Space& home, int n);
    ModEvent le(Space& home, long long int n);

    ModEvent gq(Space& home, int n);
    ModEvent gq(Space& home, long long int n);

    ModEvent gr(Space& home, int n);
    ModEvent gr(Space& home, long long int n);

    ModEvent nq(Space& home, int n);
    ModEvent nq(Space& home, long long int n);

    ModEvent eq(Space& home, int n);
    ModEvent eq(Space& home, long long int n);


    template<class I>
    ModEvent narrow_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent narrow_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_v(Space& home, I& i, bool depends=true);



    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;



    static ModEventDelta med(ModEvent me);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const IntView& x);


  class MinusView : public DerivedView<IntView> {
  protected:
    using DerivedView<IntView>::x;
  public:


    MinusView(void);
    explicit MinusView(const IntView& y);



    int min(void) const;
    int max(void) const;
    int med(void) const;
    int val(void) const;
#ifdef GECODE_HAS_CBS

    int baseval(int val) const;
#endif

    unsigned int size(void) const;
    unsigned int width(void) const;
    unsigned int regret_min(void) const;
    unsigned int regret_max(void) const;



    bool range(void) const;

    bool in(int n) const;
    bool in(long long int n) const;



    ModEvent lq(Space& home, int n);
    ModEvent lq(Space& home, long long int n);

    ModEvent le(Space& home, int n);
    ModEvent le(Space& home, long long int n);

    ModEvent gq(Space& home, int n);
    ModEvent gq(Space& home, long long int n);

    ModEvent gr(Space& home, int n);
    ModEvent gr(Space& home, long long int n);

    ModEvent nq(Space& home, int n);
    ModEvent nq(Space& home, long long int n);

    ModEvent eq(Space& home, int n);
    ModEvent eq(Space& home, long long int n);


    template<class I>
    ModEvent narrow_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent narrow_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_v(Space& home, I& i, bool depends=true);



    static ModEventDelta med(ModEvent me);



    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const MinusView& x);


  class OffsetView : public DerivedView<IntView> {
  protected:
    int c;
    using DerivedView<IntView>::x;
  public:


    OffsetView(void);
    OffsetView(const IntView& y, int c);



    int offset(void) const;
    void offset(int n);
    int min(void) const;
    int max(void) const;
    int med(void) const;
    int val(void) const;
#ifdef GECODE_HAS_CBS

    int baseval(int val) const;
#endif

    unsigned int size(void) const;
    unsigned int width(void) const;
    unsigned int regret_min(void) const;
    unsigned int regret_max(void) const;



    bool range(void) const;

    bool in(int n) const;
    bool in(long long int n) const;



    ModEvent lq(Space& home, int n);
    ModEvent lq(Space& home, long long int n);

    ModEvent le(Space& home, int n);
    ModEvent le(Space& home, long long int n);

    ModEvent gq(Space& home, int n);
    ModEvent gq(Space& home, long long int n);

    ModEvent gr(Space& home, int n);
    ModEvent gr(Space& home, long long int n);

    ModEvent nq(Space& home, int n);
    ModEvent nq(Space& home, long long int n);

    ModEvent eq(Space& home, int n);
    ModEvent eq(Space& home, long long int n);


    template<class I>
    ModEvent narrow_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent narrow_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_v(Space& home, I& i, bool depends=true);



    static ModEventDelta med(ModEvent me);



    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;



    void update(Space& home, OffsetView& y);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const OffsetView& x);


  bool same(const OffsetView& x, const OffsetView& y);
  bool before(const OffsetView& x, const OffsetView& y);

  template<class View>
  class NoOffset {
  public:
    typedef View ViewType;
    View& operator ()(View& x);
    void update(const NoOffset&);
    int offset(void) const;
  };

  template<class View>
  forceinline View&
  NoOffset<View>::operator ()(View& x) {
    return x;
  }

  template<class View>
  forceinline void
  NoOffset<View>::update(const NoOffset&) {}

  template<class View>
  forceinline int
  NoOffset<View>::offset(void) const {
    return 0;
  }


  class Offset {
  public:
    typedef OffsetView ViewType;
    int c;
    Offset(int off = 0);
    OffsetView operator()(IntView& x);
    void update(const Offset& o);
    int offset(void) const;
  };

  forceinline
  Offset::Offset(int off) : c(off) {}

  forceinline void
  Offset::update(const Offset& o) { c = o.c; }

  forceinline int
  Offset::offset(void) const { return c; }

  forceinline OffsetView
  Offset::operator ()(IntView& x) {
      return OffsetView(x,c);
  }

  template<class Val, class UnsVal>
  class ScaleView : public DerivedView<IntView> {
  protected:
    using DerivedView<IntView>::x;
    int a;
  public:


    ScaleView(void);
    ScaleView(int b, const IntView& y);



    int scale(void) const;
    Val min(void) const;
    Val max(void) const;
    Val med(void) const;
    Val val(void) const;
#ifdef GECODE_HAS_CBS

    Val baseval(Val val) const;
#endif

    UnsVal size(void) const;
    UnsVal width(void) const;
    UnsVal regret_min(void) const;
    UnsVal regret_max(void) const;



    bool range(void) const;
    bool in(Val n) const;



    ModEvent lq(Space& home, Val n);
    ModEvent le(Space& home, Val n);
    ModEvent gq(Space& home, Val n);
    ModEvent gr(Space& home, Val n);
    ModEvent nq(Space& home, Val n);
    ModEvent eq(Space& home, Val n);



    static ModEventDelta med(ModEvent me);



    Val min(const Delta& d) const;
    Val max(const Delta& d) const;
    UnsVal width(const Delta& d) const;
    bool any(const Delta& d) const;



    void update(Space& home, ScaleView<Val,UnsVal>& y);
  };

  typedef ScaleView<int,unsigned int> IntScaleView;

  typedef ScaleView<long long int,unsigned long long int> LLongScaleView;

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const IntScaleView& x);

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const LLongScaleView& x);


  template<class Val, class UnsVal>
  bool same(const ScaleView<Val,UnsVal>& x, const ScaleView<Val,UnsVal>& y);
  template<class Val, class UnsVal>
  bool before(const ScaleView<Val,UnsVal>& x, const ScaleView<Val,UnsVal>& y);



  class ConstIntView : public ConstView<IntView> {
  protected:
    int x;
  public:


    ConstIntView(void);
    ConstIntView(int n);



    int min(void) const;
    int max(void) const;
    int med(void) const;
    int val(void) const;

    unsigned int size(void) const;
    unsigned int width(void) const;
    unsigned int regret_min(void) const;
    unsigned int regret_max(void) const;



    bool range(void) const;
    bool in(int n) const;
    bool in(long long int n) const;



    ModEvent lq(Space& home, int n);
    ModEvent lq(Space& home, long long int n);

    ModEvent le(Space& home, int n);
    ModEvent le(Space& home, long long int n);

    ModEvent gq(Space& home, int n);
    ModEvent gq(Space& home, long long int n);

    ModEvent gr(Space& home, int n);
    ModEvent gr(Space& home, long long int n);

    ModEvent nq(Space& home, int n);
    ModEvent nq(Space& home, long long int n);

    ModEvent eq(Space& home, int n);
    ModEvent eq(Space& home, long long int n);


    template<class I>
    ModEvent narrow_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent narrow_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_v(Space& home, I& i, bool depends=true);



    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;



    void update(Space& home, ConstIntView& y);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const ConstIntView& x);


  bool same(const ConstIntView& x, const ConstIntView& y);
  bool before(const ConstIntView& x, const ConstIntView& y);


  class ZeroIntView : public ConstView<IntView> {
  public:


    ZeroIntView(void);



    int min(void) const;
    int max(void) const;
    int med(void) const;
    int val(void) const;

    unsigned int size(void) const;
    unsigned int width(void) const;
    unsigned int regret_min(void) const;
    unsigned int regret_max(void) const;



    bool range(void) const;
    bool in(int n) const;
    bool in(long long int n) const;



    ModEvent lq(Space& home, int n);
    ModEvent lq(Space& home, long long int n);

    ModEvent le(Space& home, int n);
    ModEvent le(Space& home, long long int n);

    ModEvent gq(Space& home, int n);
    ModEvent gq(Space& home, long long int n);

    ModEvent gr(Space& home, int n);
    ModEvent gr(Space& home, long long int n);

    ModEvent nq(Space& home, int n);
    ModEvent nq(Space& home, long long int n);

    ModEvent eq(Space& home, int n);
    ModEvent eq(Space& home, long long int n);


    template<class I>
    ModEvent narrow_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent narrow_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_v(Space& home, I& i, bool depends=true);



    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const ZeroIntView& x);


  bool same(const ZeroIntView& x, const ZeroIntView& y);

  template<class View> class ViewDiffRanges;

  template<class View>
  class CachedView : public DerivedView<View> {
    friend class ViewDiffRanges<View>;
  protected:
    using DerivedView<View>::x;
    RangeList* _firstRange;
    RangeList* _lastRange;
    unsigned int _size;
  public:


    CachedView(void);
    explicit CachedView(const View& y);



    int min(void) const;
    int max(void) const;
    int med(void) const;
    int val(void) const;
#ifdef GECODE_HAS_CBS

    int baseval(int val) const;
#endif

    unsigned int size(void) const;
    unsigned int width(void) const;
    unsigned int regret_min(void) const;
    unsigned int regret_max(void) const;



    bool range(void) const;

    bool in(int n) const;
    bool in(long long int n) const;



    ModEvent lq(Space& home, int n);
    ModEvent lq(Space& home, long long int n);

    ModEvent le(Space& home, int n);
    ModEvent le(Space& home, long long int n);

    ModEvent gq(Space& home, int n);
    ModEvent gq(Space& home, long long int n);

    ModEvent gr(Space& home, int n);
    ModEvent gr(Space& home, long long int n);

    ModEvent nq(Space& home, int n);
    ModEvent nq(Space& home, long long int n);

    ModEvent eq(Space& home, int n);
    ModEvent eq(Space& home, long long int n);


    template<class I>
    ModEvent narrow_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent narrow_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_v(Space& home, I& i, bool depends=true);



    static ModEventDelta med(ModEvent me);



    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;



    void initCache(Space& home, const IntSet& s);
    void cache(Space& home);
    bool modified(void) const;



    void update(Space& home, CachedView<View>& y);
  };

  template<class Char, class Traits, class View>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const CachedView<View>& x);


  template<class View>
  bool same(const CachedView<View>& x, const CachedView<View>& y);
  template<class View>
  bool before(const CachedView<View>& x, const CachedView<View>& y);

  template<class View>
  class ViewDiffRanges
    : public Iter::Ranges::Diff<Iter::Ranges::RangeList,ViewRanges<View> > {
    typedef Iter::Ranges::Diff<Iter::Ranges::RangeList,ViewRanges<View> >
      Super;
  protected:
    Iter::Ranges::RangeList cr;
    ViewRanges<View> dr;
  public:


    ViewDiffRanges(void);
    ViewDiffRanges(const CachedView<View>& x);
    void init(const CachedView<View>& x);
  };

  class BoolView : public VarImpView<BoolVar> {
  protected:
    using VarImpView<BoolVar>::x;
  public:


    BoolView(void);
    BoolView(const BoolVar& y);
    BoolView(BoolVarImp* y);



    static const int BITS = BoolVarImp::BITS;
    static const BoolStatus ZERO = BoolVarImp::ZERO;
    static const BoolStatus ONE  = BoolVarImp::ONE;
    static const BoolStatus NONE = BoolVarImp::NONE;
    BoolStatus status(void) const;



    int min(void) const;
    int max(void) const;
    int med(void) const;
    int val(void) const;
#ifdef GECODE_HAS_CBS

    int baseval(int val) const;
#endif

    unsigned int size(void) const;
    unsigned int width(void) const;
    unsigned int regret_min(void) const;
    unsigned int regret_max(void) const;



    bool range(void) const;
    bool in(int n) const;
    bool in(long long int n) const;



    bool zero(void) const;
    bool one(void) const;
    bool none(void) const;



    ModEvent one(Space& home);
    ModEvent zero(Space& home);
    ModEvent one_none(Space& home);
    ModEvent zero_none(Space& home);



    ModEvent lq(Space& home, int n);
    ModEvent lq(Space& home, long long int n);

    ModEvent le(Space& home, int n);
    ModEvent le(Space& home, long long int n);

    ModEvent gq(Space& home, int n);
    ModEvent gq(Space& home, long long int n);

    ModEvent gr(Space& home, int n);
    ModEvent gr(Space& home, long long int n);

    ModEvent nq(Space& home, int n);
    ModEvent nq(Space& home, long long int n);

    ModEvent eq(Space& home, int n);
    ModEvent eq(Space& home, long long int n);


    template<class I>
    ModEvent narrow_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_r(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent narrow_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent inter_v(Space& home, I& i, bool depends=true);
    template<class I>
    ModEvent minus_v(Space& home, I& i, bool depends=true);



    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;
    static bool zero(const Delta& d);
    static bool one(const Delta& d);



    static ModEventDelta med(ModEvent me);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const BoolView& x);



  class NegBoolView : public DerivedView<BoolView> {
  protected:
    using DerivedView<BoolView>::x;
  public:


    NegBoolView(void);
    explicit NegBoolView(const BoolView& y);



    static const int BITS = BoolView::BITS;
    static const BoolStatus ZERO = BoolView::ONE;
    static const BoolStatus ONE  = BoolView::ZERO;
    static const BoolStatus NONE = BoolView::NONE;
    BoolStatus status(void) const;



    bool zero(void) const;
    bool one(void) const;
    bool none(void) const;



    ModEvent one(Space& home);
    ModEvent zero(Space& home);
    ModEvent one_none(Space& home);
    ModEvent zero_none(Space& home);



    int min(void) const;
    int max(void) const;
    int val(void) const;
#ifdef GECODE_HAS_CBS

    int baseval(int val) const;
#endif




    int min(const Delta& d) const;
    int max(const Delta& d) const;
    unsigned int width(const Delta& d) const;
    bool any(const Delta& d) const;
    static bool zero(const Delta& d);
    static bool one(const Delta& d);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const NegBoolView& x);

}}

#include <gecode/int/var/int.hpp>
#include <gecode/int/var/bool.hpp>

#include <gecode/int/view/int.hpp>

#include <gecode/int/view/constint.hpp>
#include <gecode/int/view/zero.hpp>
#include <gecode/int/view/minus.hpp>
#include <gecode/int/view/offset.hpp>
#include <gecode/int/view/scale.hpp>
#include <gecode/int/view/cached.hpp>

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

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

#include <gecode/int/view/print.hpp>
#include <gecode/int/var/print.hpp>

namespace Gecode { namespace Int {


  enum RelTest {
    RT_FALSE = 0, 
    RT_MAYBE = 1, 
    RT_TRUE  = 2  
  };

  template<class VX, class VY> RelTest rtest_eq_bnd(VX x, VY y);
  template<class VX, class VY> RelTest rtest_eq_dom(VX x, VY y);
  template<class VX> RelTest rtest_eq_bnd(VX x, int n);
  template<class VX> RelTest rtest_eq_dom(VX x, int n);

  template<class VX, class VY> RelTest rtest_nq_bnd(VX x, VY y);
  template<class VX, class VY> RelTest rtest_nq_dom(VX x, VY y);
  template<class VX> RelTest rtest_nq_bnd(VX x, int n);
  template<class VX> RelTest rtest_nq_dom(VX x, int n);

  template<class VX, class VY> RelTest rtest_lq(VX x, VY y);
  template<class VX> RelTest rtest_lq(VX x, int n);

  template<class VX, class VY> RelTest rtest_le(VX x, VY y);
  template<class VX> RelTest rtest_le(VX x, int n);

  template<class VX, class VY> RelTest rtest_gq(VX x, VY y);
  template<class VX> RelTest rtest_gq(VX x, int n);

  template<class VX, class VY> RelTest rtest_gr(VX x, VY y);
  template<class VX> RelTest rtest_gr(VX x, int n);


  enum BoolTest {
    BT_NONE, 
    BT_SAME, 
    BT_COMP  
  };


  BoolTest bool_test(const BoolView& b0, const BoolView& b1);
  BoolTest bool_test(const BoolView& b0, const NegBoolView& b1);
  BoolTest bool_test(const NegBoolView& b0, const BoolView& b1);
  BoolTest bool_test(const NegBoolView& b0, const NegBoolView& b1);

}}

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

// STATISTICS: int-var