Generated on Thu Feb 21 2013 23:11:44 for Gecode by doxygen 1.8.3.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: 2010-07-15 01:46:18 +1000 (Thu, 15 Jul 2010) $ by $Author: schulte $
13  * $Revision: 11192 $
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 
77  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;
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:
247 
248  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);
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 
361  SupportEntry* next(void) const;
363  SupportEntry** nextRef(void);
365 
367 
368 
373 
375 
376 
377  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 
400  WorkEntry(int i, int n, WorkEntry* ne);
402 
404 
405 
406  WorkEntry* next(void) const;
408  void next(WorkEntry* n);
410 
412 
413 
414  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