Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
singleton.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Guido Tack, 2004
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 namespace Gecode { namespace Set {
39 
42 
45  : DerivedView<Gecode::Int::IntView>(y) {}
46 
49  : DerivedView<Gecode::Int::IntView>(y) {}
50 
53  switch(pc) {
54  case PC_SET_VAL:
55  case PC_SET_CGLB:
56  case PC_SET_CARD:
58  default:
60  }
61  }
62 
65  switch(me) {
67  return ME_SET_FAILED;
69  return ME_SET_NONE;
71  return ME_SET_VAL;
73  return ME_SET_LUB;
74  default:
75  return ME_SET_LUB;
76  }
77  }
78 
81  switch(me) {
82  case ME_SET_FAILED:
84  case ME_SET_NONE:
86  case ME_SET_VAL:
88  default:
90  }
91  }
92 
93  forceinline unsigned int
94  SingletonView::glbSize(void) const {
95  return x.assigned() ? 1U : 0U;
96  }
97 
98  forceinline unsigned int
99  SingletonView::lubSize(void) const { return x.size(); }
100 
101  forceinline unsigned int
103  return lubSize() - glbSize();
104  }
105 
106  forceinline bool
107  SingletonView::contains(int n) const { return x.assigned() ?
108  (x.val()==n) : false; }
109 
110  forceinline bool
111  SingletonView::notContains(int n) const { return !x.in(n); }
112 
113  forceinline unsigned int
114  SingletonView::cardMin() const { return 1; }
115 
116  forceinline unsigned int
117  SingletonView::cardMax() const { return 1; }
118 
119  forceinline int
120  SingletonView::lubMin() const { return x.min(); }
121 
122  forceinline int
123  SingletonView::lubMax() const { return x.max(); }
124 
125  forceinline int
126  SingletonView::glbMin() const { return x.assigned() ?
127  x.val() : BndSet::MIN_OF_EMPTY; }
128 
129  forceinline int
130  SingletonView::glbMax() const { return x.assigned() ?
131  x.val() : BndSet::MAX_OF_EMPTY; }
132 
134  SingletonView::cardMin(Space&, unsigned int c) {
135  return c<=1 ? ME_SET_NONE : ME_SET_FAILED;
136  }
137 
139  SingletonView::cardMax(Space&, unsigned int c) {
140  return c<1 ? ME_SET_FAILED : ME_SET_NONE;
141  }
142 
145  return me_inttoset(x.eq(home,c));
146  }
147 
150  return me_inttoset(x.eq(home,c));
151  }
152 
154  SingletonView::intersect(Space& home,int i, int j) {
155  ModEvent me1 = me_inttoset(x.gq(home,i));
156  ModEvent me2 = me_inttoset(x.lq(home,j));
157  if (me_failed(me1) || me_failed(me2))
158  return ME_SET_FAILED;
159  switch (me1) {
160  case ME_SET_NONE:
161  case ME_SET_LUB:
162  return me2;
163  case ME_SET_VAL:
164  return ME_SET_VAL;
165  default:
166  GECODE_NEVER;
167  return ME_SET_VAL;
168  }
169  }
170 
173  return me_inttoset(x.nq(home,c));
174  }
175 
177  SingletonView::include(Space& home, int j, int k) {
178  return j==k ? me_inttoset(x.eq(home,j)) : ME_SET_FAILED ;
179  }
180 
182  SingletonView::exclude(Space& home, int j, int k) {
183  ModEvent me1 = me_inttoset(x.gr(home,j));
184  ModEvent me2 = me_inttoset(x.le(home,k));
185  if (me_failed(me1) || me_failed(me2))
186  return ME_SET_FAILED;
187  switch (me1) {
188  case ME_SET_NONE:
189  case ME_SET_LUB:
190  return me2;
191  case ME_SET_VAL:
192  return ME_SET_VAL;
193  default:
194  GECODE_NEVER;
195  return ME_SET_VAL;
196  }
197  }
198 
199  template<class I> ModEvent
200  SingletonView::excludeI(Space& home, I& iter) {
201  return me_inttoset(x.minus_r(home,iter));
202  }
203 
204  template<class I> ModEvent
205  SingletonView::includeI(Space& home, I& iter) {
206  if (!iter())
207  return ME_SET_NONE;
208 
209  if (iter.min()!=iter.max())
210  return ME_SET_FAILED;
211 
212  int val = iter.min();
213  ++iter;
214  if ( iter() )
215  return ME_SET_FAILED;
216 
217  return me_inttoset(x.eq(home, val));
218  }
219 
220  template<class I> ModEvent
222  return me_inttoset(x.inter_r(home,iter));
223  }
224 
225  forceinline void
227  bool schedule) {
228  x.subscribe(home,p,pc_settoint(pc),schedule);
229  }
230  forceinline void
232  x.cancel(home,p,pc_settoint(pc));
233  }
234  forceinline void
236  x.reschedule(home,p,pc_settoint(pc));
237  }
238 
239  forceinline void
241  x.subscribe(home,a);
242  }
243  forceinline void
245  x.cancel(home,a);
246  }
247 
248 
249  forceinline void
251  return Gecode::Int::IntView::schedule(home,p,me_settoint(me));
252  }
255  return me_inttoset(Int::IntView::me(med));
256  }
259  return SetView::med(me_settoint(me));
260  }
261 
262 
263  /*
264  * Delta information for advisors
265  *
266  * For SingletonViews, a glb change means that the view is assigned.
267  * Thus, the delta for the glb is always equal to the delta for the lub.
268  *
269  */
270 
274  }
275 
276  forceinline int
277  SingletonView::glbMin(const Delta& d) const { return x.min(d); }
278 
279  forceinline int
280  SingletonView::glbMax(const Delta& d) const { return x.max(d); }
281 
282  forceinline bool
283  SingletonView::glbAny(const Delta& d) const { return x.any(d); }
284 
285  forceinline int
286  SingletonView::lubMin(const Delta& d) const { return x.min(d); }
287 
288  forceinline int
289  SingletonView::lubMax(const Delta& d) const { return x.max(d); }
290 
291  forceinline bool
292  SingletonView::lubAny(const Delta& d) const { return x.any(d); }
293 
294  forceinline bool
296  return x.base() == y.base();
297  }
298 
299  forceinline bool
301  return x.base() != y.base();
302  }
303 
304 
305  /*
306  * Iterators
307  *
308  */
309 
314  template<>
316  public:
318 
319  LubRanges(void);
322  LubRanges(const SingletonView& x);
324  void init(const SingletonView& x);
326  };
327 
330 
333  Gecode::Int::IntVarImpFwd(s.base().varimp()) {}
334 
335  forceinline void
338  }
339 
344  template<>
346  private:
347  int val;
348  bool flag;
349  public:
351 
352  GlbRanges(void);
355  GlbRanges(const SingletonView& x);
357  void init(const SingletonView& x);
358 
360 
361  bool operator ()(void) const;
364  void operator ++(void);
366 
368 
369  int min(void) const;
372  int max(void) const;
374  unsigned int width(void) const;
376  };
377 
380 
381  forceinline void
383  if (s.base().assigned()) {
384  val = s.base().val();
385  flag = true;
386  } else {
387  val = 0;
388  flag = false;
389  }
390  }
391 
394  init(s);
395  }
396 
397  forceinline bool
398  GlbRanges<SingletonView>::operator ()(void) const { return flag; }
399 
400  forceinline void
402 
403  forceinline int
404  GlbRanges<SingletonView>::min(void) const { return val; }
405  forceinline int
406  GlbRanges<SingletonView>::max(void) const { return val; }
407  forceinline unsigned int
408  GlbRanges<SingletonView>::width(void) const { return 1; }
409 
410 }}
411 
412 // STATISTICS: set-var
413 
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:186
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:157
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: int.hpp:148
static ModEventDelta med(ModEvent me)
Translate modification event me to modification event delta for view.
Definition: view.hpp:557
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:527
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:70
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:605
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: singleton.hpp:272
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Definition: singleton.hpp:258
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:138
int min(void) const
Return smallest value of range.
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition: singleton.hpp:205
const Gecode::PropCond PC_SET_CARD
Propagate when the cardinality of a view changes.
Definition: var-type.hpp:216
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition: var-type.hpp:156
int max(void) const
Return largest value of range.
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: singleton.hpp:221
bool operator!=(const SingletonView &x, const SingletonView &y)
Test whether views x and y are the not same.
Definition: singleton.hpp:300
int lubMin(void) const
Return minimum of the least upper bound.
Definition: singleton.hpp:120
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: singleton.hpp:126
bool operator()(void) const
Test whether iterator is still at a range or done.
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: singleton.hpp:117
SingletonView(void)
Default constructor.
Definition: singleton.hpp:41
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
Definition: singleton.hpp:177
int ModEvent
Type for modification events.
Definition: core.hpp:62
void varimp(VarImpType *y)
Set variable implementation to y.
Definition: view.hpp:484
Base-class for propagators.
Definition: core.hpp:1023
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:81
Base-class for advisors.
Definition: core.hpp:1251
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:112
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: view.hpp:532
#define forceinline
Definition: config.hpp:185
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:191
Computation spaces.
Definition: core.hpp:1701
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: singleton.hpp:94
static PropCond pc_settoint(PropCond pc)
Convert set variable PropCond pc to a PropCond for integer variables.
Definition: singleton.hpp:52
Base-class for derived views.
Definition: view.hpp:230
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: singleton.hpp:283
Gecode::IntSet d(v, 7)
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition: singleton.hpp:99
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:110
Gecode::FloatVal c(-8, 8)
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:107
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:521
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:130
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: singleton.hpp:254
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
int lubMax(void) const
Return maximum of the least upper bound.
Definition: singleton.hpp:123
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: singleton.hpp:114
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
static ModEvent me_inttoset(ModEvent me)
Convert integer variable ModEvent me to a ModEvent for set variables.
Definition: singleton.hpp:64
int min(void) const
Return smallest value of range.
void operator++(void)
Move iterator to next range (if possible)
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: singleton.hpp:130
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:392
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
void operator++(void)
Move iterator to next range (if possible)
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:140
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: singleton.hpp:231
Singleton set view.
Definition: view.hpp:594
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: singleton.hpp:200
Integer view for integer variables.
Definition: view.hpp:129
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition: int.hpp:230
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: singleton.hpp:226
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:516
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: view.hpp:562
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
const Gecode::PropCond PC_SET_CGLB
Propagate when the cardinality or the greatest lower bound of a view changes.
Definition: var-type.hpp:238
bool operator==(const SingletonView &x, const SingletonView &y)
Test whether views x and y are the same.
Definition: singleton.hpp:295
Integer variables.
Definition: int.hh:371
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
GlbRanges(void)
Default constructor.
Definition: set.hpp:492
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
Definition: set.hpp:465
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j...
Definition: singleton.hpp:154
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: singleton.hpp:250
Post propagator for SetVar x
Definition: set.hh:767
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: singleton.hpp:111
Gecode::Int::IntView x
View from which this view is derived.
Definition: view.hpp:238
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j...
Definition: singleton.hpp:182
VarImpType * varimp(void) const
Return variable implementation of view.
Definition: view.hpp:599
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: singleton.hpp:102
int max(void) const
Return largest value of range.
Gecode toplevel namespace
const Gecode::PropCond PC_SET_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:207
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: view.hpp:547
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: singleton.hpp:235
LubRanges(void)
Default constructor.
Definition: set.hpp:458
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:142
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: singleton.hpp:292
bool operator()(void) const
Test whether iterator is still at a range or done.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: singleton.hpp:107
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
Definition: set.hpp:499
static ModEvent me_settoint(ModEvent me)
Convert set variable ModEvent me to a ModEvent for integer variables.
Definition: singleton.hpp:80
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82