Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
extensional.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Linnea Ingmar <linnea.ingmar@hotmail.com>
5  * Mikael Lagerkvist <lagerkvist@gecode.org>
6  * Christian Schulte <schulte@gecode.org>
7  *
8  * Copyright:
9  * Linnea Ingmar, 2017
10  * Mikael Lagerkvist, 2007
11  * Christian Schulte, 2004
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_INT_EXTENSIONAL_HH__
39 #define __GECODE_INT_EXTENSIONAL_HH__
40 
41 #include <gecode/int.hh>
42 
43 #include <gecode/int/rel.hh>
44 
50 namespace Gecode { namespace Int { namespace Extensional {
51 
66  template<class View, class Val, class Degree, class StateIdx>
67  class LayeredGraph : public Propagator {
68  protected:
70  class State {
71  public:
72  Degree i_deg;
73  Degree o_deg;
74  void init(void);
76  };
78  class Edge {
79  public:
80  StateIdx i_state;
81  StateIdx o_state;
82  };
84  class Support {
85  public:
86  Val val;
87  Degree n_edges;
89  };
93  class Layer {
94  public:
95  View x;
96  StateIdx n_states;
97  ValSize size;
100  };
102  class LayerValues {
103  private:
104  const Support* s1;
105  const Support* s2;
106  public:
108  LayerValues(void);
110  LayerValues(const Layer& l);
112  void init(const Layer& l);
114  bool operator ()(void) const;
116  void operator ++(void);
118  int val(void) const;
119  };
121  class Index : public Advisor {
122  public:
124  int i;
126  Index(Space& home, Propagator& p, Council<Index>& c, int i);
128  Index(Space& home, Index& a);
129  };
131  class IndexRange {
132  private:
133  int _fst;
134  int _lst;
135  public:
137  IndexRange(void);
139  void reset(void);
141  void add(int i);
143  void add(const IndexRange& ir);
145  void lshift(int n);
147  bool empty(void) const;
149  int fst(void) const;
151  int lst(void) const;
152  };
156  int n;
160  StateIdx max_states;
162  unsigned int n_states;
164  unsigned int n_edges;
172  State& i_state(int i, StateIdx is);
174  State& i_state(int i, const Edge& e);
176  bool i_dec(int i, const Edge& e);
178  State& o_state(int i, StateIdx os);
180  State& o_state(int i, const Edge& e);
182  bool o_dec(int i, const Edge& e);
184  void audit(void);
186  template<class Var>
188  const VarArgArray<Var>& x, const DFA& dfa);
191  public:
193  template<class Var>
194  LayeredGraph(Home home,
195  const VarArgArray<Var>& x, const DFA& dfa);
197  virtual Actor* copy(Space& home);
199  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
201  virtual void reschedule(Space& home);
203  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
205  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
207  virtual size_t dispose(Space& home);
209  template<class Var>
210  static ExecStatus post(Home home,
211  const VarArgArray<Var>& x, const DFA& dfa);
212  };
213 
215  template<class Var>
216  ExecStatus post_lgp(Home home,
217  const VarArgArray<Var>& x, const DFA& dfa);
218 
219 }}}
220 
222 
223 
224 namespace Gecode { namespace Int { namespace Extensional {
225 
228 
229  /*
230  * Forward declarations
231  */
232  template<unsigned int size> class TinyBitSet;
233 
235  template<class IndexType>
236  class BitSet {
237  template<class> friend class BitSet;
238  template<unsigned int> friend class TinyBitSet;
239  protected:
241  IndexType _limit;
243  IndexType* index;
245  BitSetData* bits;
247  void replace_and_decrease(IndexType i, BitSetData w);
248  public:
250  BitSet(Space& home, unsigned int n);
252  template<class OldIndexType>
253  BitSet(Space& home, const BitSet<OldIndexType>& bs);
255  BitSet(Space& home, const TinyBitSet<1U>& tbs);
257  BitSet(Space& home, const TinyBitSet<2U>& tbs);
259  BitSet(Space& home, const TinyBitSet<3U>& tbs);
261  BitSet(Space& home, const TinyBitSet<4U>& tbs);
263  unsigned int limit(void) const;
265  bool empty(void) const;
267  unsigned int width(void) const;
269  void clear_mask(BitSetData* mask) const;
271  void add_to_mask(const BitSetData* b, BitSetData* mask) const;
273  template<bool sparse>
274  void intersect_with_mask(const BitSetData* mask);
276  void intersect_with_masks(const BitSetData* a, const BitSetData* b);
278  bool intersects(const BitSetData* b) const;
280  void nand_with_mask(const BitSetData* b);
282  unsigned int words(void) const;
284  unsigned int size(void) const;
285  };
286 
287 }}}
288 
290 
291 namespace Gecode { namespace Int { namespace Extensional {
292 
294  template<unsigned int _size>
295  class TinyBitSet {
296  template<unsigned int> friend class TinyBitSet;
297  protected:
299  BitSetData bits[_size];
300  public:
302  TinyBitSet(Space& home, unsigned int n);
304  template<unsigned int largersize>
305  TinyBitSet(Space& home, const TinyBitSet<largersize>& tbs);
307  template<class IndexType>
308  TinyBitSet(Space& home, const BitSet<IndexType>& bs);
310  int limit(void) const;
312  bool empty(void) const;
314  unsigned int width(void) const;
316  void clear_mask(BitSetData* mask);
318  void add_to_mask(const BitSetData* b, BitSetData* mask) const;
320  template<bool sparse>
321  void intersect_with_mask(const BitSetData* mask);
323  void intersect_with_masks(const BitSetData* a, const BitSetData* b);
325  bool intersects(const BitSetData* b);
327  void nand_with_mask(const BitSetData* b);
329  void nand_with_masks(const BitSetData* a, const BitSetData* b);
331  unsigned int words(void) const;
333  unsigned int size(void) const;
334  };
335 
336 }}}
337 
339 
340 namespace Gecode { namespace Int { namespace Extensional {
341 
343  typedef TupleSet::Tuple Tuple;
344 
346  template<class View>
347  class Compact : public Propagator {
348  protected:
352  class CTAdvisor : public ViewAdvisor<View> {
353  public:
355  protected:
357  const Range* _fst;
359  const Range* _lst;
360  public:
362 
365  const TupleSet& ts, View x0, int i);
367  CTAdvisor(Space& home, CTAdvisor& a);
369  void adjust(void);
372  const Range* fst(void) const;
374  const Range* lst(void) const;
376  void dispose(Space& home, Council<CTAdvisor>& c);
377  };
379 
380  enum StatusType {
382  SINGLE = 0,
383  MULTIPLE = 1,
384  NONE = 2,
385  PROPAGATING = 3
386  };
388  class Status {
389  protected:
391  ptrdiff_t s;
392  public:
396  Status(const Status& s);
398  StatusType type(void) const;
400  bool single(CTAdvisor& a) const;
402  void touched(CTAdvisor& a);
404  void none(void);
406  void propagating(void);
407  };
409 
411  class ValidSupports {
413  protected:
415  const unsigned int n_words;
417  int max;
421  const Range* sr;
423  int n;
425  const BitSetData* s;
426  public:
430  ValidSupports(const TupleSet& ts, int i, View x);
432  void operator ++(void);
434  bool operator ()(void) const;
436  const BitSetData* supports(void) const;
438  int val(void) const;
439  };
441  class LostSupports {
442  protected:
444  const unsigned int n_words;
446  const Range* r;
448  int l;
450  int h;
452  const BitSetData* s;
453  public:
456  int l, int h);
458  void operator ++(void);
460  bool operator ()(void) const;
462  const BitSetData* supports(void) const;
463  };
465  protected:
469  const unsigned int n_words;
477  Compact(Space& home, Compact& p);
479  Compact(Home home, ViewArray<View>& x, const TupleSet& ts);
481  const Range* range(CTAdvisor& a, int n);
483  const BitSetData* supports(CTAdvisor& a, int n);
484  public:
486  size_t dispose(Space& home);
487  };
488 
502  template<class View, class Table>
503  class CompactTable : public Compact<View> {
504  public:
506  typedef typename Compact<View>::Range Range;
509  typedef typename Compact<View>::Status Status;
511 
514  using Compact<View>::status;
515  using Compact<View>::c;
516  using Compact<View>::ts;
517 
519  Table table;
521  template<class TableProp>
522  CompactTable(Space& home, TableProp& p);
524  CompactTable(Home home, ViewArray<View>& x, const TupleSet& ts);
525  public:
527  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
529  virtual void reschedule(Space& home);
531  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
533  virtual Actor* copy(Space& home);
535  static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts);
537  size_t dispose(Space& home);
539  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
540  };
541 
543  template<class View>
545 
546 }}}
547 
549 
550 #endif
551 
552 // STATISTICS: int-prop
IndexRange i_ch
Index range with in-degree modifications.
Definition: extensional.hh:166
Council of advisors
Definition: core.hpp:154
NodeType t
Type of node.
Definition: bool-expr.cpp:230
TupleSet ts
The tuple set.
Definition: extensional.hh:473
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void audit(void)
Perform consistency check on data structures.
Edge defined by in-state and out-state
Definition: extensional.hh:78
Council< Index > c
The advisor council.
Definition: extensional.hh:154
int n
Number of layers (and views)
Definition: extensional.hh:156
Iterator for telling variable domains by scanning support.
Definition: extensional.hh:102
IndexRange a_ch
Index range for any change (for compression)
Definition: extensional.hh:170
StateIdx n_states
Number of states used by outgoing edges.
Definition: extensional.hh:96
const unsigned int n_words
Number of words in supports.
Definition: extensional.hh:469
unsigned int n_states
Total number of states.
Definition: extensional.hh:162
const Range * r
Range information.
Definition: extensional.hh:446
int * Tuple
Type of a tuple.
Definition: int.hh:2146
StateIdx i_state
Number of in-state.
Definition: extensional.hh:80
Base-class for propagators.
Definition: core.hpp:1023
Compact< View >::CTAdvisor CTAdvisor
Definition: extensional.hh:507
Base-class for advisors.
Definition: core.hpp:1251
Gecode::Support::BitSetData BitSetData
Import type.
Definition: extensional.hh:227
Computation spaces.
Definition: core.hpp:1701
ViewRanges< View > xr
Range iterator.
Definition: extensional.hh:419
Advisor storing a single view
Definition: advisor.hpp:43
Support information for a value
Definition: extensional.hh:84
const BitSetData * s
The lost value&#39;s support.
Definition: extensional.hh:452
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
LayeredGraph(Space &home, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
IndexRange o_ch
Index range with out-degree modifications.
Definition: extensional.hh:168
Base-class for both propagators and branchers.
Definition: core.hpp:627
Status status
Propagator status.
Definition: extensional.hh:471
Range iterator for integer views.
Definition: view.hpp:54
Gecode::IntSet d(v, 7)
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
ValSize size
Number of supported values.
Definition: extensional.hh:97
StateIdx o_state
Number of out-state.
Definition: extensional.hh:81
Deterministic finite automaton (DFA)
Definition: int.hh:2023
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Gecode::IntArgs i(4, 1, 2, 3, 4)
Domain consistent extensional propagator.
Definition: extensional.hh:503
::Gecode::TupleSet::Tuple Tuple
Import tuple type.
Definition: tuple-set.cpp:44
ExecStatus postcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for compact table propagator.
Definition: compact.hpp:581
Range approximation of which positions have changed.
Definition: extensional.hh:131
const unsigned int n_words
Number of words.
Definition: extensional.hh:444
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
Layer for a view in the layered graph
Definition: extensional.hh:93
Degree n_edges
Number of supporting edges.
Definition: extensional.hh:87
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: minimodel.hh:2026
Compact< View >::StatusType StatusType
Definition: extensional.hh:508
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1036
Layer * layers
The layers of the graph.
Definition: extensional.hh:158
StateIdx max_states
Maximal number of states per layer.
Definition: extensional.hh:160
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
View arrays.
Definition: array.hpp:224
const Range * _lst
Last range of support data structure.
Definition: extensional.hh:359
Council< CTAdvisor > c
The advisor council.
Definition: extensional.hh:475
Traits to for information about integer types.
Definition: int-type.hpp:52
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Definition: extensional.hh:73
State * states
States used by outgoing edges.
Definition: extensional.hh:98
const BitSetData * s
The value&#39;s support.
Definition: extensional.hh:425
Domain consistent layered graph (regular) propagator.
Definition: extensional.hh:67
IndexType * index
Indices.
Definition: extensional.hh:243
Class represeting a set of tuples.
Definition: int.hh:2140
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
Compact< View >::ValidSupports ValidSupports
Definition: extensional.hh:505
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Advisors for views (by position in array)
Definition: extensional.hh:121
Propagation cost.
Definition: core.hpp:485
const Range * _fst
First range of support data structure.
Definition: extensional.hh:357
ExecStatus
Definition: core.hpp:471
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Date item for bitsets.
Definition: bitset-base.hpp:65
Advisor for updating current table.
Definition: extensional.hh:352
Post propagator for SetVar x
Definition: set.hh:765
virtual Actor * copy(Space &home)
Copy propagator during cloning.
ptrdiff_t s
A tagged pointer for storing the status.
Definition: extensional.hh:391
Edge * edges
Supporting edges in layered graph.
Definition: extensional.hh:88
Compact< View >::LostSupports LostSupports
Definition: extensional.hh:510
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Gecode toplevel namespace
Argument array for variables.
Definition: array.hpp:49
const unsigned int n_words
Number of words.
Definition: extensional.hh:415
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
Base class for compact table propagator.
Definition: extensional.hh:347
States are described by number of incoming and outgoing edges.
Definition: extensional.hh:70
Degree i_deg
The in-degree (number of incoming edges)
Definition: extensional.hh:72
int unassigned
Number of unassigned views.
Definition: extensional.hh:467
virtual void reschedule(Space &home)
Schedule function.
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
unsigned int n_edges
Total number of edges.
Definition: extensional.hh:164
Range information.
Definition: int.hh:2150
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Definition: extensional.hh:91
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
int i
The position of the view in the view array.
Definition: extensional.hh:124
TupleSet::Range Range
Range type for supports.
Definition: extensional.hh:350