extensional.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Linnea Ingmar <linnea.ingmar@hotmail.com>
 *     Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
 *     Christian Schulte <schulte@gecode.dev>
 *
 *  Copyright:
 *     Linnea Ingmar, 2017
 *     Mikael Zayenz Lagerkvist, 2007
 *     Christian Schulte, 2004
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.dev
 *
 *  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_EXTENSIONAL_HH
#define GECODE_INT_EXTENSIONAL_HH
 
#include <gecode/int.hh>
 
#include <gecode/int/rel.hh>

 
namespace Gecode { namespace Int { namespace Extensional {

  class CompressedSupport {
  protected:
    const TupleSet::CSupportWord* b;
    const TupleSet::CSupportWord* e;
  public:
    CompressedSupport(void);
    CompressedSupport(const TupleSet::CSupportWord* b0,
                      const TupleSet::CSupportWord* e0);
    const TupleSet::CSupportWord* begin(void) const;
    const TupleSet::CSupportWord* end(void) const;
    bool empty(void) const;
  };

  template<class View, class Val, class Degree, class StateIdx>
  class LayeredGraph : public Propagator {
  protected:
    class State {
    public:
      Degree i_deg; 
      Degree o_deg; 
      void init(void);
    };

    class Edge {
    public:
      StateIdx i_state; 
      StateIdx o_state; 
    };

    class Support {
    public:
      Val val; 
      Degree n_edges; 
      Edge* edges; 
    };

    typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize;
    class Layer {
    public:
      View x; 
      StateIdx n_states; 
      ValSize size; 
      State* states; 
      Support* support; 
    };

    class LayerValues {
    private:
      const Support* s1; 
      const Support* s2; 
    public:
      LayerValues(void);
      LayerValues(const Layer& l);
      void init(const Layer& l);
      bool operator ()(void) const;
      void operator ++(void);
      int val(void) const;
    };

    class Index : public Advisor {
    public:
      int i;
      Index(Space& home, Propagator& p, Council<Index>& c, int i);
      Index(Space& home, Index& a);
    };

    class IndexRange {
    private:
      int _fst; 
      int _lst; 
    public:
      IndexRange(void);
      void reset(void);
      void add(int i);
      void add(const IndexRange& ir);
      void lshift(int n);
      bool empty(void) const;
      int fst(void) const;
      int lst(void) const;
    };

    Council<Index> c;
    int n;
    Layer* layers;
    StateIdx max_states;
    unsigned int n_states;
    unsigned int n_edges;
    IndexRange i_ch;
    IndexRange o_ch;
    IndexRange a_ch;
    State& i_state(int i, StateIdx is);
    State& i_state(int i, const Edge& e);
    bool i_dec(int i, const Edge& e);
    State& o_state(int i, StateIdx os);
    State& o_state(int i, const Edge& e);
    bool o_dec(int i, const Edge& e);
    void audit(void);
    template<class Var>
    ExecStatus initialize(Space& home,
                          const VarArgArray<Var>& x, const DFA& dfa);
    LayeredGraph(Space& home, LayeredGraph<View,Val,Degree,StateIdx>& p);
  public:
    template<class Var>
    LayeredGraph(Home home,
                 const VarArgArray<Var>& x, const DFA& dfa);
    virtual Actor* copy(Space& home);
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    virtual void reschedule(Space& home);
    virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual size_t dispose(Space& home);
    template<class Var>
    static ExecStatus post(Home home,
                           const VarArgArray<Var>& x, const DFA& dfa);
  };

  template<class Var>
  ExecStatus post_lgp(Home home,
                      const VarArgArray<Var>& x, const DFA& dfa);
 
}}}
 
#include <gecode/int/extensional/layered-graph.hpp>
 
namespace Gecode { namespace Int { namespace Extensional {

  typedef Gecode::Support::BitSetData BitSetData;
 
  /*
   * Forward declarations
   */
  template<unsigned int size> class TinyBitSet;

  template<class IndexType>
  class BitSet {
    template<class> friend class BitSet;
    template<unsigned int> friend class TinyBitSet;
  protected:
    IndexType _active_words;
    IndexType _word_capacity;
    IndexType* _word_index;
    BitSetData* _word_bits;
    IndexType* _active_position;
    void replace_and_decrease(IndexType active_pos, BitSetData word);
  public:
    BitSet(Space& home, unsigned int n, bool indexed=false);
    template<class OldIndexType>
    BitSet(Space& home, const BitSet<OldIndexType>& bs);
    BitSet(Space& home, const TinyBitSet<1U>& tbs);
    BitSet(Space& home, const TinyBitSet<2U>& tbs);
    BitSet(Space& home, const TinyBitSet<3U>& tbs);
    BitSet(Space& home, const TinyBitSet<4U>& tbs);
    unsigned int limit(void) const;
    bool empty(void) const;
    void flush(void);
    unsigned int width(void) const;
    void clear_mask(BitSetData* mask) const;
    void add_to_mask(const BitSetData* support, BitSetData* mask) const;
    void add_to_mask(const CompressedSupport& support, BitSetData* mask) const;
    template<bool sparse>
    void intersect_with_mask(const BitSetData* mask);
    void intersect_with_mask(const CompressedSupport& support);
    void intersect_with_masks(const BitSetData* a, const BitSetData* b);
    void intersect_with_masks(const CompressedSupport& a,
                              const CompressedSupport& b);
    bool intersects(const BitSetData* mask) const;
    bool intersects(const CompressedSupport& support) const;
    void nand_with_mask(const BitSetData* mask);
    void nand_with_mask(const CompressedSupport& support);
    unsigned long long int ones(void) const;
    unsigned long long int ones(const BitSetData* mask) const;
    unsigned long long int ones(const CompressedSupport& support) const;
    unsigned long long int bits(void) const;
    unsigned int words(void) const;
    unsigned int size(void) const;
  };
 
}}}
 
#include <gecode/int/extensional/bit-set.hpp>
 
namespace Gecode { namespace Int { namespace Extensional {

  template<unsigned int _size>
  class TinyBitSet {
    template<unsigned int> friend class TinyBitSet;
  protected:
    BitSetData _bits[_size];
  public:
    TinyBitSet(Space& home, unsigned int n, bool indexed=false);
    template<unsigned int largersize>
    TinyBitSet(Space& home, const TinyBitSet<largersize>& tbs);
    template<class IndexType>
    TinyBitSet(Space& home, const BitSet<IndexType>& bs);
    int limit(void) const;
    bool empty(void) const;
    void flush(void);
    unsigned int width(void) const;
    void clear_mask(BitSetData* mask);
    void add_to_mask(const BitSetData* b, BitSetData* mask) const;
    void add_to_mask(const CompressedSupport& s, BitSetData* mask) const;
    template<bool sparse>
    void intersect_with_mask(const BitSetData* mask);
    void intersect_with_mask(const CompressedSupport& s);
    void intersect_with_masks(const BitSetData* a, const BitSetData* b);
    void intersect_with_masks(const CompressedSupport& a,
                              const CompressedSupport& b);
    bool intersects(const BitSetData* b);
    bool intersects(const CompressedSupport& s);
    void nand_with_mask(const BitSetData* b);
    void nand_with_mask(const CompressedSupport& s);
    void nand_with_masks(const BitSetData* a, const BitSetData* b);
    unsigned long long int ones(void) const;
    unsigned long long int ones(const BitSetData* b) const;
    unsigned long long int ones(const CompressedSupport& s) const;
    unsigned long long int bits(void) const;
    unsigned int words(void) const;
    unsigned int size(void) const;
  };
      
}}}
 
#include <gecode/int/extensional/tiny-bit-set.hpp>
 
namespace Gecode { namespace Int { namespace Extensional {

  typedef TupleSet::Tuple Tuple;

  template<bool indexed>
  class CompactAdvisorIndex;

  template<>
  class CompactAdvisorIndex<false> {
  protected:
    CompactAdvisorIndex(int i);
    int index(void) const;
  };

  template<>
  class CompactAdvisorIndex<true> {
  protected:
    int _index;
    CompactAdvisorIndex(int i);
    int index(void) const;
  };

  template<class View, bool pos, bool indexed>
  class CompactAdvisor : public ViewAdvisor<View>,
                         private CompactAdvisorIndex<indexed> {
  protected:
    typedef TupleSet::Range Range;
    const Range* _fst;
    const Range* _lst;
  public:
    using ViewAdvisor<View>::view;
    CompactAdvisor(Space& home, Propagator& p,
                   Council<CompactAdvisor>& c, const TupleSet& ts,
                   View x, int i);
    CompactAdvisor(Space& home, CompactAdvisor& a);
    void adjust(void);
    int index(void) const;
    const Range* fst(void) const;
    const Range* lst(void) const;
    void dispose(Space& home, Council<CompactAdvisor>& c);
  };

  template<class Advisor>
  class CompactStatus {
  protected:
    ptrdiff_t s;
  public:
    enum StatusType {
      SINGLE      = 0, 
      MULTIPLE    = 1, 
      NONE        = 2, 
      PROPAGATING = 3  
    };

    CompactStatus(StatusType t);
    CompactStatus(const CompactStatus& status);
    StatusType type(void) const;
    bool single(Advisor& a) const;
    void touched(Advisor& a);
    void none(void);
    void propagating(void);
  };

  template<class Actor>
  class PosCompactAlgorithm;
  template<class Actor>
  class NegCompactAlgorithm;
  template<class Actor>
  class ReCompactAlgorithm;

  template<class View, bool pos>
  class Compact : public Propagator {
  protected:
    typedef TupleSet::Range Range;
    typedef CompactAdvisor<View,pos,false> CTAdvisor;


    class ValidSupports {
    protected:
      const unsigned int n_words;
      int max_value;
      ViewRanges<View> view_ranges;
      const Range* support_range;
      const Range* last_support_range;
      int value;
      const BitSetData* support_words;
      void find(void);
    public:
      ValidSupports(const Compact<View,pos>& p, CTAdvisor& a);
      ValidSupports(const TupleSet& ts, int i, View x);
      void operator ++(void);
      bool operator ()(void) const;
      const BitSetData* support(void) const;
      int val(void) const;
    };

    class LostSupports {
    protected:
      const unsigned int n_words;
      const Range* support_range;
      const Range* last_support_range;
      int value;
      int last_value;
      const BitSetData* support_words;
    public:
      LostSupports(const Compact<View,pos>& p, CTAdvisor& a,
                   int first_value, int last_value);
      void operator ++(void);
      bool operator ()(void) const;
      const BitSetData* support(void) const;
    };



    bool all(void) const;
    bool atmostone(void) const;
  protected:
    const unsigned int n_words;
    TupleSet ts;
    Council<CTAdvisor> c;
    Compact(Space& home, Compact& p);
    Compact(Home home, const TupleSet& ts);
    template<class Table>
    void setup(Space& home, Table& table, ViewArray<View>& x);
    template<class Table>
    bool full(const Table& table) const;
    const Range* range(CTAdvisor& a, int n);
    const BitSetData* supports(CTAdvisor& a, int n);
  public:
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    size_t dispose(Space& home);
  };

  template<class View, class Table>
  class PosCompact : public Compact<View,true> {
    template<class Actor> friend class PosCompactAlgorithm;
  public:
    typedef View ViewType;
    typedef typename Compact<View,true>::ValidSupports ValidSupports;
    typedef typename Compact<View,true>::Range Range;
    typedef typename Compact<View,true>::CTAdvisor CTAdvisor;
    typedef typename Compact<View,true>::LostSupports LostSupports;
 
    using Compact<View,true>::setup;
    using Compact<View,true>::supports;
    using Compact<View,true>::all;
    using Compact<View,true>::atmostone;
    using Compact<View,true>::c;
    using Compact<View,true>::ts;

    typedef CompactStatus<CTAdvisor> Status;
    typedef typename Status::StatusType StatusType;
    Status status;
    Table table;
    bool empty(void) const;
    template<class TableProp>
    PosCompact(Space& home, TableProp& p);
    PosCompact(Home home, ViewArray<View>& x, const TupleSet& ts);
  public:
    virtual void reschedule(Space& home);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual Actor* copy(Space& home);
    static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts);
    size_t dispose(Space& home);
    virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
  };

  template<class View>
  ExecStatus postposcompact(Home home, ViewArray<View>& x, const TupleSet& ts);
  template<class View>
  ExecStatus postposcompact_compressed(Home home, ViewArray<View>& x,
                                       const TupleSet& ts);

  template<class View, class Table>
  class NegCompact : public Compact<View,false> {
    template<class Actor> friend class NegCompactAlgorithm;
  public:
    typedef View ViewType;
    typedef typename Compact<View,false>::ValidSupports ValidSupports;
    typedef typename Compact<View,false>::Range Range;
    typedef typename Compact<View,false>::CTAdvisor CTAdvisor;
 
    using Compact<View,false>::setup;
    using Compact<View,false>::full;
    using Compact<View,false>::supports;
    using Compact<View,false>::atmostone;
    using Compact<View,false>::c;
    using Compact<View,false>::ts;

    Table table;
    template<class TableProp>
    NegCompact(Space& home, TableProp& p);
    NegCompact(Home home, ViewArray<View>& x, const TupleSet& ts);
  public:
    virtual void reschedule(Space& home);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual Actor* copy(Space& home);
    static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts);
    size_t dispose(Space& home);
    virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
  };

  template<class View>
  ExecStatus postnegcompact(Home home, ViewArray<View>& x, const TupleSet& ts);
  template<class View>
  ExecStatus postnegcompact_compressed(Home home, ViewArray<View>& x,
                                       const TupleSet& ts);
 

  template<class View, class Table, class CtrlView, ReifyMode rm>
  class ReCompact : public Compact<View,false> {
    template<class Actor> friend class ReCompactAlgorithm;
  public:
    typedef View ViewType;
    static constexpr ReifyMode mode = rm;
    typedef typename Compact<View,false>::ValidSupports ValidSupports;
    typedef typename Compact<View,false>::Range Range;
    typedef typename Compact<View,false>::CTAdvisor CTAdvisor;
 
    using Compact<View,false>::setup;
    using Compact<View,false>::full;
    using Compact<View,false>::supports;
    using Compact<View,false>::c;
    using Compact<View,false>::ts;

    Table table;
    CtrlView b;
    ViewArray<View> y;
    template<class TableProp>
    ReCompact(Space& home, TableProp& p);
    ReCompact(Home home, ViewArray<View>& x, const TupleSet& ts, CtrlView b);
    static ExecStatus post_pos(Home home, ViewArray<View>& x,
                               const TupleSet& ts);
    static ExecStatus post_neg(Home home, ViewArray<View>& x,
                               const TupleSet& ts);
  public:
    virtual void reschedule(Space& home);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    virtual Actor* copy(Space& home);
    static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts,
                           CtrlView b);
    size_t dispose(Space& home);
    virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
  };

  template<class View, class CtrlView, ReifyMode rm>
  ExecStatus postrecompact(Home home, ViewArray<View>& x, const TupleSet& ts,
                           CtrlView b);
  template<class View, class CtrlView, ReifyMode rm>
  ExecStatus postrecompact_compressed(Home home, ViewArray<View>& x,
                                      const TupleSet& ts, CtrlView b);
 
}}}
 
#include <gecode/int/extensional/compact.hpp>
 
#endif
 
// STATISTICS: int-prop