Generated on Thu Apr 5 2018 19:44:19 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  * Last modified:
14  * $Date$ by $Author$
15  * $Revision$
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #ifndef __GECODE_INT_EXTENSIONAL_HH__
43 #define __GECODE_INT_EXTENSIONAL_HH__
44 
45 #include <gecode/int.hh>
46 
47 #include <gecode/int/rel.hh>
48 
54 namespace Gecode { namespace Int { namespace Extensional {
55 
70  template<class View, class Val, class Degree, class StateIdx>
71  class LayeredGraph : public Propagator {
72  protected:
74  class State {
75  public:
76  Degree i_deg;
77  Degree o_deg;
78  void init(void);
80  };
82  class Edge {
83  public:
84  StateIdx i_state;
85  StateIdx o_state;
86  };
88  class Support {
89  public:
90  Val val;
91  Degree n_edges;
93  };
97  class Layer {
98  public:
99  View x;
100  StateIdx n_states;
101  ValSize size;
104  };
106  class LayerValues {
107  private:
108  const Support* s1;
109  const Support* s2;
110  public:
112  LayerValues(void);
114  LayerValues(const Layer& l);
116  void init(const Layer& l);
118  bool operator ()(void) const;
120  void operator ++(void);
122  int val(void) const;
123  };
125  class Index : public Advisor {
126  public:
128  int i;
130  Index(Space& home, Propagator& p, Council<Index>& c, int i);
132  Index(Space& home, Index& a);
133  };
135  class IndexRange {
136  private:
137  int _fst;
138  int _lst;
139  public:
141  IndexRange(void);
143  void reset(void);
145  void add(int i);
147  void add(const IndexRange& ir);
149  void lshift(int n);
151  bool empty(void) const;
153  int fst(void) const;
155  int lst(void) const;
156  };
160  int n;
164  StateIdx max_states;
166  unsigned int n_states;
168  unsigned int n_edges;
176  State& i_state(int i, StateIdx is);
178  State& i_state(int i, const Edge& e);
180  bool i_dec(int i, const Edge& e);
182  State& o_state(int i, StateIdx os);
184  State& o_state(int i, const Edge& e);
186  bool o_dec(int i, const Edge& e);
188  void audit(void);
190  template<class Var>
192  const VarArgArray<Var>& x, const DFA& dfa);
195  public:
197  template<class Var>
198  LayeredGraph(Home home,
199  const VarArgArray<Var>& x, const DFA& dfa);
201  virtual Actor* copy(Space& home);
203  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
205  virtual void reschedule(Space& home);
207  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
209  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
211  virtual size_t dispose(Space& home);
213  template<class Var>
214  static ExecStatus post(Home home,
215  const VarArgArray<Var>& x, const DFA& dfa);
216  };
217 
219  template<class Var>
220  ExecStatus post_lgp(Home home,
221  const VarArgArray<Var>& x, const DFA& dfa);
222 
223 }}}
224 
226 
227 
228 namespace Gecode { namespace Int { namespace Extensional {
229 
232 
233  /*
234  * Forward declarations
235  */
236  template<unsigned int size> class TinyBitSet;
237 
239  template<class IndexType>
240  class BitSet {
241  template<class> friend class BitSet;
242  template<unsigned int> friend class TinyBitSet;
243  protected:
245  IndexType _limit;
247  IndexType* index;
249  BitSetData* bits;
251  void replace_and_decrease(IndexType i, BitSetData w);
252  public:
254  BitSet(Space& home, unsigned int n);
256  template<class OldIndexType>
257  BitSet(Space& home, const BitSet<OldIndexType>& bs);
259  BitSet(Space& home, const TinyBitSet<1U>& tbs);
261  BitSet(Space& home, const TinyBitSet<2U>& tbs);
263  BitSet(Space& home, const TinyBitSet<3U>& tbs);
265  BitSet(Space& home, const TinyBitSet<4U>& tbs);
267  unsigned int limit(void) const;
269  bool empty(void) const;
271  unsigned int width(void) const;
273  void clear_mask(BitSetData* mask) const;
275  void add_to_mask(const BitSetData* b, BitSetData* mask) const;
277  template<bool sparse>
278  void intersect_with_mask(const BitSetData* mask);
280  void intersect_with_masks(const BitSetData* a, const BitSetData* b);
282  bool intersects(const BitSetData* b) const;
284  void nand_with_mask(const BitSetData* b);
286  unsigned int words(void) const;
288  unsigned int size(void) const;
289  };
290 
291 }}}
292 
294 
295 namespace Gecode { namespace Int { namespace Extensional {
296 
298  template<unsigned int _size>
299  class TinyBitSet {
300  template<unsigned int> friend class TinyBitSet;
301  protected:
303  BitSetData bits[_size];
304  public:
306  TinyBitSet(Space& home, unsigned int n);
308  template<unsigned int largersize>
309  TinyBitSet(Space& home, const TinyBitSet<largersize>& tbs);
311  template<class IndexType>
312  TinyBitSet(Space& home, const BitSet<IndexType>& bs);
314  int limit(void) const;
316  bool empty(void) const;
318  unsigned int width(void) const;
320  void clear_mask(BitSetData* mask);
322  void add_to_mask(const BitSetData* b, BitSetData* mask) const;
324  template<bool sparse>
325  void intersect_with_mask(const BitSetData* mask);
327  void intersect_with_masks(const BitSetData* a, const BitSetData* b);
329  bool intersects(const BitSetData* b);
331  void nand_with_mask(const BitSetData* b);
333  void nand_with_masks(const BitSetData* a, const BitSetData* b);
335  unsigned int words(void) const;
337  unsigned int size(void) const;
338  };
339 
340 }}}
341 
343 
344 namespace Gecode { namespace Int { namespace Extensional {
345 
347  typedef TupleSet::Tuple Tuple;
348 
350  template<class View>
351  class Compact : public Propagator {
352  protected:
356  class CTAdvisor : public ViewAdvisor<View> {
357  public:
359  protected:
361  const Range* _fst;
363  const Range* _lst;
364  public:
366 
369  const TupleSet& ts, View x0, int i);
371  CTAdvisor(Space& home, CTAdvisor& a);
373  void adjust(void);
376  const Range* fst(void) const;
378  const Range* lst(void) const;
380  void dispose(Space& home, Council<CTAdvisor>& c);
381  };
383 
384  enum StatusType {
386  SINGLE = 0,
387  MULTIPLE = 1,
388  NONE = 2,
389  PROPAGATING = 3
390  };
392  class Status {
393  protected:
395  ptrdiff_t s;
396  public:
400  Status(const Status& s);
402  StatusType type(void) const;
404  bool single(CTAdvisor& a) const;
406  void touched(CTAdvisor& a);
408  void none(void);
410  void propagating(void);
411  };
413 
415  class ValidSupports {
417  protected:
419  const unsigned int n_words;
421  int max;
425  const Range* sr;
427  int n;
429  const BitSetData* s;
430  public:
434  ValidSupports(const TupleSet& ts, int i, View x);
436  void operator ++(void);
438  bool operator ()(void) const;
440  const BitSetData* supports(void) const;
442  int val(void) const;
443  };
445  class LostSupports {
446  protected:
448  const unsigned int n_words;
450  const Range* r;
452  int l;
454  int h;
456  const BitSetData* s;
457  public:
460  int l, int h);
462  void operator ++(void);
464  bool operator ()(void) const;
466  const BitSetData* supports(void) const;
467  };
469  protected:
473  const unsigned int n_words;
481  Compact(Space& home, Compact& p);
483  Compact(Home home, ViewArray<View>& x, const TupleSet& ts);
485  const Range* range(CTAdvisor& a, int n);
487  const BitSetData* supports(CTAdvisor& a, int n);
488  public:
490  size_t dispose(Space& home);
491  };
492 
506  template<class View, class Table>
507  class CompactTable : public Compact<View> {
508  public:
510  typedef typename Compact<View>::Range Range;
513  typedef typename Compact<View>::Status Status;
515 
518  using Compact<View>::status;
519  using Compact<View>::c;
520  using Compact<View>::ts;
521 
523  Table table;
525  template<class TableProp>
526  CompactTable(Space& home, TableProp& p);
528  CompactTable(Home home, ViewArray<View>& x, const TupleSet& ts);
529  public:
531  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
533  virtual void reschedule(Space& home);
535  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
537  virtual Actor* copy(Space& home);
539  static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts);
541  size_t dispose(Space& home);
543  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
544  };
545 
547  template<class View>
549 
550 }}}
551 
553 
554 #endif
555 
556 // STATISTICS: int-prop
IndexRange i_ch
Index range with in-degree modifications.
Definition: extensional.hh:170
Council of advisors
Definition: core.hpp:156
NodeType t
Type of node.
Definition: bool-expr.cpp:234
TupleSet ts
The tuple set.
Definition: extensional.hh:477
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void audit(void)
Perform consistency check on data structures.
Edge defined by in-state and out-state
Definition: extensional.hh:82
Council< Index > c
The advisor council.
Definition: extensional.hh:158
int n
Number of layers (and views)
Definition: extensional.hh:160
Iterator for telling variable domains by scanning support.
Definition: extensional.hh:106
IndexRange a_ch
Index range for any change (for compression)
Definition: extensional.hh:174
StateIdx n_states
Number of states used by outgoing edges.
Definition: extensional.hh:100
const unsigned int n_words
Number of words in supports.
Definition: extensional.hh:473
unsigned int n_states
Total number of states.
Definition: extensional.hh:166
const Range * r
Range information.
Definition: extensional.hh:450
int * Tuple
Type of a tuple.
Definition: int.hh:2150
StateIdx i_state
Number of in-state.
Definition: extensional.hh:84
Base-class for propagators.
Definition: core.hpp:1016
Compact< View >::CTAdvisor CTAdvisor
Definition: extensional.hh:511
Base-class for advisors.
Definition: core.hpp:1218
Gecode::Support::BitSetData BitSetData
Import type.
Definition: extensional.hh:231
Computation spaces.
Definition: core.hpp:1668
ViewRanges< View > xr
Range iterator.
Definition: extensional.hh:423
Advisor storing a single view
Definition: advisor.hpp:47
Support information for a value
Definition: extensional.hh:88
const BitSetData * s
The lost value&#39;s support.
Definition: extensional.hh:456
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:172
Base-class for both propagators and branchers.
Definition: core.hpp:620
Status status
Propagator status.
Definition: extensional.hh:475
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:101
StateIdx o_state
Number of out-state.
Definition: extensional.hh:85
Deterministic finite automaton (DFA)
Definition: int.hh:2027
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Domain consistent extensional propagator.
Definition: extensional.hh:507
::Gecode::TupleSet::Tuple Tuple
Import tuple type.
Definition: tuple-set.cpp:48
ExecStatus postcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for compact table propagator.
Definition: compact.hpp:585
Range approximation of which positions have changed.
Definition: extensional.hh:135
const unsigned int n_words
Number of words.
Definition: extensional.hh:448
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1027
Layer for a view in the layered graph
Definition: extensional.hh:97
Degree n_edges
Number of supporting edges.
Definition: extensional.hh:91
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: minimodel.hh:2030
Compact< View >::StatusType StatusType
Definition: extensional.hh:512
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1029
Layer * layers
The layers of the graph.
Definition: extensional.hh:162
StateIdx max_states
Maximal number of states per layer.
Definition: extensional.hh:164
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:228
const Range * _lst
Last range of support data structure.
Definition: extensional.hh:363
Council< CTAdvisor > c
The advisor council.
Definition: extensional.hh:479
Traits to for information about integer types.
Definition: int-type.hpp:56
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Definition: extensional.hh:77
State * states
States used by outgoing edges.
Definition: extensional.hh:102
const BitSetData * s
The value&#39;s support.
Definition: extensional.hh:429
Domain consistent layered graph (regular) propagator.
Definition: extensional.hh:71
IndexType * index
Indices.
Definition: extensional.hh:247
Class represeting a set of tuples.
Definition: int.hh:2144
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:509
Generic domain change information to be supplied to advisors.
Definition: core.hpp:205
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Advisors for views (by position in array)
Definition: extensional.hh:125
Propagation cost.
Definition: core.hpp:478
const Range * _fst
First range of support data structure.
Definition: extensional.hh:361
ExecStatus
Definition: core.hpp:464
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Date item for bitsets.
Definition: bitset-base.hpp:69
Advisor for updating current table.
Definition: extensional.hh:356
Post propagator for SetVar x
Definition: set.hh:769
virtual Actor * copy(Space &home)
Copy propagator during cloning.
ptrdiff_t s
A tagged pointer for storing the status.
Definition: extensional.hh:395
Edge * edges
Supporting edges in layered graph.
Definition: extensional.hh:92
Compact< View >::LostSupports LostSupports
Definition: extensional.hh:514
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:53
const unsigned int n_words
Number of words.
Definition: extensional.hh:419
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
Base class for compact table propagator.
Definition: extensional.hh:351
States are described by number of incoming and outgoing edges.
Definition: extensional.hh:74
Degree i_deg
The in-degree (number of incoming edges)
Definition: extensional.hh:76
int unassigned
Number of unassigned views.
Definition: extensional.hh:471
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:91
Home class for posting propagators
Definition: core.hpp:846
unsigned int n_edges
Total number of edges.
Definition: extensional.hh:168
Range information.
Definition: int.hh:2154
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Definition: extensional.hh:95
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:128
TupleSet::Range Range
Range type for supports.
Definition: extensional.hh:354