Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.9.1
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  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Mikael Lagerkvist, 2007
9  * Christian Schulte, 2004
10  *
11  * Last modified:
12  * $Date: 2012-07-19 08:53:57 +0200 (Thu, 19 Jul 2012) $ by $Author: tack $
13  * $Revision: 12963 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_INT_EXTENSIONAL_HH__
41 #define __GECODE_INT_EXTENSIONAL_HH__
42 
43 #include <gecode/int.hh>
44 
45 #include <gecode/int/rel.hh>
46 
52 namespace Gecode { namespace Int { namespace Extensional {
53 
68  template<class View, class Val, class Degree, class StateIdx>
69  class LayeredGraph : public Propagator {
70  protected:
72  class State {
73  public:
74  Degree i_deg;
75  Degree o_deg;
76  void init(void);
78  };
80  class Edge {
81  public:
82  StateIdx i_state;
83  StateIdx o_state;
84  };
86  class Support {
87  public:
88  Val val;
89  Degree n_edges;
91  };
95  class Layer {
96  public:
97  View x;
98  StateIdx n_states;
99  ValSize size;
102  };
104  class LayerValues {
105  private:
106  const Support* s1;
107  const Support* s2;
108  public:
110  LayerValues(void);
112  LayerValues(const Layer& l);
114  void init(const Layer& l);
116  bool operator ()(void) const;
118  void operator ++(void);
120  int val(void) const;
121  };
123  class Index : public Advisor {
124  public:
126  int i;
128  Index(Space& home, Propagator& p, Council<Index>& c, int i);
130  Index(Space& home, bool share, Index& a);
131  };
133  class IndexRange {
134  private:
135  int _fst;
136  int _lst;
137  public:
139  IndexRange(void);
141  void reset(void);
143  void add(int i);
145  void add(const IndexRange& ir);
147  void lshift(int n);
149  bool empty(void) const;
151  int fst(void) const;
153  int lst(void) const;
154  };
158  int n;
162  StateIdx max_states;
164  unsigned int n_states;
166  unsigned int n_edges;
174  State& i_state(int i, StateIdx is);
176  State& i_state(int i, const Edge& e);
178  bool i_dec(int i, const Edge& e);
180  State& o_state(int i, StateIdx os);
182  State& o_state(int i, const Edge& e);
184  bool o_dec(int i, const Edge& e);
186  void audit(void);
188  template<class Var>
189  ExecStatus initialize(Space& home,
190  const VarArgArray<Var>& x, const DFA& dfa);
192  LayeredGraph(Space& home, bool share,
194  public:
196  template<class Var>
197  LayeredGraph(Home home,
198  const VarArgArray<Var>& x, const DFA& dfa);
200  virtual Actor* copy(Space& home, bool share);
202  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
204  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
206  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
208  virtual size_t dispose(Space& home);
210  template<class Var>
211  static ExecStatus post(Home home,
212  const VarArgArray<Var>& x, const DFA& dfa);
213  };
214 
216  template<class Var>
217  ExecStatus post_lgp(Home home,
218  const VarArgArray<Var>& x, const DFA& dfa);
219 
220 }}}
221 
223 
224 
225 namespace Gecode { namespace Int { namespace Extensional {
226 
230 
241  template<class View, bool subscribe = true>
242  class Base : public Propagator {
243  protected:
246  Tuple** last_data;
247  TupleSet::TupleSetI* ts(void);
249 
251  Base(Space& home, bool share, Base<View,subscribe>& p);
253  Base(Home home, ViewArray<View>& x, const TupleSet& t);
255  void init_last(Space& home, Tuple** source, Tuple* base);
257  Tuple last(int i, int n);
259  Tuple last_next(int i, int n);
261  void init_dom(Space& home, Domain dom);
263  bool valid(Tuple t, Domain dom);
265  Tuple find_support(Domain dom, int i, int n);
266  public:
268  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
270  virtual size_t dispose(Space& home);
271  protected:
273  virtual ~Base(void) {}
274  };
275 }}}
276 
278 
279 
280 namespace Gecode { namespace Int { namespace Extensional {
281 
294  template<class View, bool shared>
295  class Basic : public Base<View> {
296  protected:
297  using Base<View>::x;
298  using Base<View>::tupleSet;
299  using Base<View>::ts;
300  using Base<View>::last;
301  using Base<View>::last_next;
302  using Base<View>::init_last;
303  using Base<View>::init_dom;
305 
307  Basic(Space& home, bool share, Basic<View,shared>& p);
309  Basic(Home home, ViewArray<View>& x, const TupleSet& t);
310 
311  public:
313  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
320  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
322  virtual Actor* copy(Space& home, bool share);
324  static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
325  };
326 
327 }}}
328 
330 
331 
332 namespace Gecode { namespace Int { namespace Extensional {
342  template<class View>
343  class Incremental : public Base<View, false> {
344  protected:
345  using Base<View, false>::x;
347  using Base<View, false>::ts;
353  class SupportEntry : public FreeList {
354  public:
357 
359 
360  SupportEntry* next(void) const;
363  SupportEntry** nextRef(void);
365 
367 
368  SupportEntry(Tuple t);
373 
375 
376  void dispose(Space& home, SupportEntry* l);
379  void dispose(Space& home);
380 
382  static void* operator new(size_t s, Space& home);
384  static void operator delete(void* p);
386  static void operator delete(void* p, Space& home);
388  };
390  class WorkEntry : public FreeList {
391  public:
393  int i;
395  int n;
396 
398 
399  WorkEntry(int i, int n, WorkEntry* ne);
402 
404 
405  WorkEntry* next(void) const;
408  void next(WorkEntry* n);
410 
412 
413  void dispose(Space& home);
415 
417  static void* operator new(size_t s, Space& home);
419  static void operator delete(void* p);
421  static void operator delete(void* p, Space& home);
423  };
425  class Work {
426  private:
428  WorkEntry* we;
429  public:
431  Work(void);
433  bool empty(void) const;
435  void push(Space& home, int i, int n);
437  void pop(Space& home, int& i, int& n);
438  };
443 
448 
450  Incremental(Space& home, bool share, Incremental<View>& p);
452  Incremental(Home home, ViewArray<View>& x, const TupleSet& t);
454  void init_support(Space& home);
456  void find_support(Space& home, Domain dom, int i, int n);
458  void add_support(Space& home, Tuple l);
460  void remove_support(Space& home, Tuple l, int i, int n);
462  SupportEntry* support(int i, int n);
463  public:
465  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
472  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
474  virtual Actor* copy(Space& home, bool share);
476  static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
478  size_t dispose(Space& home);
479  private:
481  class SupportAdvisor : public Advisor {
482  public:
484  int i;
486  SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
487  int i);
489  SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
491  void dispose(Space& home, Council<SupportAdvisor>& c);
492  };
495  public:
497  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
498  };
499 
500 }}}
501 
503 
504 
505 #endif
506 
507 // STATISTICS: int-prop
508 
IndexRange i_ch
Index range with in-degree modifications.
Definition: extensional.hh:168
int lst(void) const
Return last position.
Council of advisors
Definition: core.hpp:226
TupleSet tupleSet
Definition of constraint.
Definition: extensional.hh:245
NodeType t
Type of node.
Definition: bool-expr.cpp:234
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Work w_remove
Work for removing values.
Definition: extensional.hh:442
void init_dom(Space &home, Domain dom)
Initialize domain information.
Definition: base.hpp:118
Description of work to be done.
Definition: extensional.hh:390
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:80
Council< Index > c
The advisor council.
Definition: extensional.hh:156
Tuple find_support(Domain dom, int i, int n)
Find support for view at position i and value n.
Definition: base.hpp:138
int val(void) const
Return supported value.
int n
Number of layers (and views)
Definition: extensional.hh:158
Iterator for telling variable domains by scanning support.
Definition: extensional.hh:104
IndexRange a_ch
Index range for any change (for compression)
Definition: extensional.hh:172
StateIdx n_states
Number of states used by outgoing edges.
Definition: extensional.hh:98
void dispose(Space &home)
Free memory for this element.
virtual ~Base(void)
Unused destructor (to avoid warnings)
Definition: extensional.hh:273
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
unsigned int n_states
Total number of states.
Definition: extensional.hh:164
void init_last(Space &home, Tuple **source, Tuple *base)
Initialize last support.
Definition: base.hpp:74
WorkEntry(int i, int n, WorkEntry *ne)
Initialize with position i, value n, and next entry ne.
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
size_t dispose(Space &home)
Delete propagator and return its size.
void init(const Layer &l)
Initialize for support of layer l.
Basic bitset support.
int * Tuple
Type of a tuple.
Definition: int.hh:2028
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
StateIdx i_state
Number of in-state.
Definition: extensional.hh:82
Base-class for propagators.
Definition: core.hpp:755
Base-class for advisors.
Definition: core.hpp:926
Tuple last_next(int i, int n)
Find last support for view at position i and value n.
Definition: base.hpp:105
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
Tuple last(int i, int n)
Find last support for view at position i and value n.
Definition: base.hpp:99
void dispose(Space &home, SupportEntry *l)
Free memory for all elements between this and l (inclusive)
void lshift(int n)
Shift index range by n elements to the left.
void add_support(Space &home, Tuple l)
Add support.
Computation spaces.
Definition: core.hpp:1362
void init_support(Space &home)
Initialize support.
Support information for a value
Definition: extensional.hh:86
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: basic.hpp:86
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
IndexRange o_ch
Index range with out-degree modifications.
Definition: extensional.hh:170
Base-class for both propagators and branchers.
Definition: core.hpp:666
Gecode::IntSet d(v, 7)
SupportEntry ** support_data
Support information.
Definition: extensional.hh:445
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:99
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: basic.hpp:92
Gecode::FloatVal c(-8, 8)
StateIdx o_state
Number of out-state.
Definition: extensional.hh:83
Deterministic finite automaton (DFA)
Definition: int.hh:1881
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
TupleSet::Tuple Tuple
Definition: extensional.hh:227
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Domain consistent extensional propagator.
Definition: extensional.hh:295
void operator++(void)
Move to next supported value.
void remove_support(Space &home, Tuple l, int i, int n)
Remove support for view at position i and value n.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: base.hpp:148
Range approximation of which positions have changed.
Definition: extensional.hh:133
SupportEntry(Tuple t)
Initialize with Tuple t.
Definition: incremental.hpp:76
ViewArray< View > x
Variables.
Definition: extensional.hh:244
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Tuple ** last_data
Last tuple looked at Access real tuple-set.
Definition: extensional.hh:246
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
Layer for a view in the layered graph
Definition: extensional.hh:95
Support::BitSetBase * Domain
Definition: extensional.hh:229
Degree n_edges
Number of supporting edges.
Definition: extensional.hh:89
void find_support(Space &home, Domain dom, int i, int n)
Find a next support for view at position i and value n.
LayeredGraph(Space &home, bool share, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
bool operator()(void) const
Test whether more values supported.
Layer * layers
The layers of the graph.
Definition: extensional.hh:160
int fst(void) const
Return first position.
int i
Position of view in view array.
Definition: extensional.hh:393
StateIdx max_states
Maximal number of states per layer.
Definition: extensional.hh:162
bool valid(Tuple t, Domain dom)
Check wether tuple is valid for domain.
Definition: base.hpp:129
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: basic.hpp:77
bool empty(void) const
Check whether work stack is empty.
Data stored for a Table.
Definition: int.hh:2034
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high quadratic)
Definition: base.hpp:91
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
void reset(void)
Reset range to be empty.
View arrays.
Definition: array.hpp:234
Traits to for information about integer types.
Definition: int-type.hpp:56
int unassigned
Number of unassigned views.
Definition: extensional.hh:447
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Definition: extensional.hh:75
State * states
States used by outgoing edges.
Definition: extensional.hh:100
Domain consistent layered graph (regular) propagator.
Definition: extensional.hh:69
Class represeting a set of tuples.
Definition: int.hh:2022
SupportEntry ** nextRef(void)
Return reference to field for next support entry.
Definition: incremental.hpp:92
void push(Space &home, int i, int n)
Push new work entry for position i and value n.
Work w_support
Work for finding support.
Definition: extensional.hh:440
Domain consistent extensional propagator.
Definition: extensional.hh:343
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &t)
Post propagator for views x.
Definition: basic.hpp:58
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base(Space &home, bool share, Base< View, subscribe > &p)
Constructor for cloning p.
Definition: base.hpp:64
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
Basic(Space &home, bool share, Basic< View, shared > &p)
Constructor for cloning p.
Definition: basic.hpp:71
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Advisors for views (by position in array)
Definition: extensional.hh:123
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &t)
Post propagator for views x.
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
Incremental(Space &home, bool share, Incremental< View > &p)
Constructor for cloning p.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
SupportEntry * support(int i, int n)
Creat support entry for view at position i and value n.
Support::BitSetBase BitSet
Definition: extensional.hh:228
Base-class for freelist-managed objects.
TupleSet::TupleSetI * ts(void)
Definition: base.hpp:85
Base for domain consistent extensional propagation
Definition: extensional.hh:242
Edge * edges
Supporting edges in layered graph.
Definition: extensional.hh:90
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
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
void pop(Space &home, int &i, int &n)
Pop current top entry and set position i and value n.
States are described by number of incoming and outgoing edges.
Definition: extensional.hh:72
Degree i_deg
The in-degree (number of incoming edges)
Definition: extensional.hh:74
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:173
Home class for posting propagators
Definition: core.hpp:717
bool empty(void) const
Test whether range is empty.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
unsigned int n_edges
Total number of edges.
Definition: extensional.hh:166
SupportEntry * next(void) const
Return next support entry.
Definition: incremental.hpp:86
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Definition: extensional.hh:93
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
WorkEntry * next(void) const
Return next work entry.
int i
The position of the view in the view array.
Definition: extensional.hh:126