Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.9.1
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  * Last modified:
14  * $Date: 2011-08-19 16:47:28 +0200 (Fri, 19 Aug 2011) $ by $Author: tack $
15  * $Revision: 12318 $
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 namespace Gecode { namespace Set {
43 
46 
49  : DerivedView<Gecode::Int::IntView>(y) {}
50 
53  : DerivedView<Gecode::Int::IntView>(y) {}
54 
57  switch(pc) {
58  case PC_SET_VAL:
59  case PC_SET_CGLB:
60  case PC_SET_CARD:
62  default:
64  }
65  }
66 
69  switch(me) {
71  return ME_SET_FAILED;
73  return ME_SET_NONE;
75  return ME_SET_VAL;
77  return ME_SET_LUB;
78  default:
79  return ME_SET_LUB;
80  }
81  }
82 
85  switch(me) {
86  case ME_SET_FAILED:
88  case ME_SET_NONE:
90  case ME_SET_VAL:
92  default:
94  }
95  }
96 
97  forceinline unsigned int
98  SingletonView::glbSize(void) const {
99  return x.assigned() ? 1U : 0U;
100  }
101 
102  forceinline unsigned int
103  SingletonView::lubSize(void) const { return x.size(); }
104 
105  forceinline unsigned int
107  return lubSize() - glbSize();
108  }
109 
110  forceinline bool
111  SingletonView::contains(int n) const { return x.assigned() ?
112  (x.val()==n) : false; }
113 
114  forceinline bool
115  SingletonView::notContains(int n) const { return !x.in(n); }
116 
117  forceinline unsigned int
118  SingletonView::cardMin() const { return 1; }
119 
120  forceinline unsigned int
121  SingletonView::cardMax() const { return 1; }
122 
123  forceinline int
124  SingletonView::lubMin() const { return x.min(); }
125 
126  forceinline int
127  SingletonView::lubMax() const { return x.max(); }
128 
129  forceinline int
130  SingletonView::glbMin() const { return x.assigned() ?
131  x.val() : BndSet::MIN_OF_EMPTY; }
132 
133  forceinline int
134  SingletonView::glbMax() const { return x.assigned() ?
135  x.val() : BndSet::MAX_OF_EMPTY; }
136 
138  SingletonView::cardMin(Space&, unsigned int c) {
139  return c<=1 ? ME_SET_NONE : ME_SET_FAILED;
140  }
141 
143  SingletonView::cardMax(Space&, unsigned int c) {
144  return c<1 ? ME_SET_FAILED : ME_SET_NONE;
145  }
146 
149  return me_inttoset(x.eq(home,c));
150  }
151 
154  return me_inttoset(x.eq(home,c));
155  }
156 
158  SingletonView::intersect(Space& home,int i, int j) {
159  ModEvent me1 = me_inttoset(x.gq(home,i));
160  ModEvent me2 = me_inttoset(x.lq(home,j));
161  if (me_failed(me1) || me_failed(me2))
162  return ME_SET_FAILED;
163  switch (me1) {
164  case ME_SET_NONE:
165  case ME_SET_LUB:
166  return me2;
167  case ME_SET_VAL:
168  return ME_SET_VAL;
169  default:
170  GECODE_NEVER;
171  return ME_SET_VAL;
172  }
173  }
174 
177  return me_inttoset(x.nq(home,c));
178  }
179 
181  SingletonView::include(Space& home, int j, int k) {
182  return j==k ? me_inttoset(x.eq(home,j)) : ME_SET_FAILED ;
183  }
184 
186  SingletonView::exclude(Space& home, int j, int k) {
187  ModEvent me1 = me_inttoset(x.gr(home,j));
188  ModEvent me2 = me_inttoset(x.le(home,k));
189  if (me_failed(me1) || me_failed(me2))
190  return ME_SET_FAILED;
191  switch (me1) {
192  case ME_SET_NONE:
193  case ME_SET_LUB:
194  return me2;
195  case ME_SET_VAL:
196  return ME_SET_VAL;
197  default:
198  GECODE_NEVER;
199  return ME_SET_VAL;
200  }
201  }
202 
203  template<class I> ModEvent
204  SingletonView::excludeI(Space& home, I& iter) {
205  return me_inttoset(x.minus_r(home,iter));
206  }
207 
208  template<class I> ModEvent
209  SingletonView::includeI(Space& home, I& iter) {
210  if (!iter())
211  return ME_SET_NONE;
212 
213  if (iter.min()!=iter.max())
214  return ME_SET_FAILED;
215 
216  int val = iter.min();
217  ++iter;
218  if ( iter() )
219  return ME_SET_FAILED;
220 
221  return me_inttoset(x.eq(home, val));
222  }
223 
224  template<class I> ModEvent
226  return me_inttoset(x.inter_r(home,iter));
227  }
228 
229  forceinline void
231  bool schedule) {
232  x.subscribe(home,p,pc_settoint(pc),schedule);
233  }
234  forceinline void
236  x.cancel(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  /*
295  * Iterators
296  *
297  */
298 
303  template<>
305  public:
307 
308  LubRanges(void);
311  LubRanges(const SingletonView& x);
313  void init(const SingletonView& x);
315  };
316 
319 
322  Gecode::Int::IntVarImpFwd(s.base().varimp()) {}
323 
324  forceinline void
327  }
328 
333  template<>
335  private:
336  int val;
337  bool flag;
338  public:
340 
341  GlbRanges(void);
344  GlbRanges(const SingletonView& x);
346  void init(const SingletonView& x);
347 
349 
350  bool operator ()(void) const;
353  void operator ++(void);
355 
357 
358  int min(void) const;
361  int max(void) const;
363  unsigned int width(void) const;
365  };
366 
369 
370  forceinline void
372  if (s.base().assigned()) {
373  val = s.base().val();
374  flag = true;
375  } else {
376  val = 0;
377  flag = false;
378  }
379  }
380 
383  init(s);
384  }
385 
386  forceinline bool
387  GlbRanges<SingletonView>::operator ()(void) const { return flag; }
388 
389  forceinline void
391 
392  forceinline int
393  GlbRanges<SingletonView>::min(void) const { return val; }
394  forceinline int
395  GlbRanges<SingletonView>::max(void) const { return val; }
396  forceinline unsigned int
397  GlbRanges<SingletonView>::width(void) const { return 1; }
398 
399 }}
400 
401 // STATISTICS: set-var
402 
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:70
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:180
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:151
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: int.hpp:142
static ModEventDelta med(ModEvent me)
Translate modification event me to modification event delta for view.
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:459
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
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: singleton.hpp:115
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:138
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition: singleton.hpp:209
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
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: singleton.hpp:292
VarImpType * varimp(void) const
Return variable implementation of view.
Definition: view.hpp:433
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: singleton.hpp:225
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:160
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: singleton.hpp:283
SingletonView(void)
Default constructor.
Definition: singleton.hpp:45
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:181
int ModEvent
Type for modification events.
Definition: core.hpp:146
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: singleton.hpp:98
Base-class for propagators.
Definition: core.hpp:755
Base-class for advisors.
Definition: core.hpp:926
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:116
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: singleton.hpp:111
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:185
Computation spaces.
Definition: core.hpp:1362
static PropCond pc_settoint(PropCond pc)
Convert set variable PropCond pc to a PropCond for integer variables.
Definition: singleton.hpp:56
Base-class for derived views.
Definition: view.hpp:208
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
Gecode::IntSet d(v, 7)
int min(void) const
Return smallest value of range.
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:114
Gecode::FloatVal c(-8, 8)
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:453
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:124
int max(void) const
Return largest value of range.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:101
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: singleton.hpp:130
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: singleton.hpp:106
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: singleton.hpp:121
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:115
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:526
bool operator()(void) const
Test whether iterator is still at a range or done.
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:75
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
int lubMin(void) const
Return minimum of the least upper bound.
Definition: singleton.hpp:124
static ModEvent me_inttoset(ModEvent me)
Convert integer variable ModEvent me to a ModEvent for set variables.
Definition: singleton.hpp:68
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:387
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
void operator++(void)
Move iterator to next range (if possible)
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition: singleton.hpp:103
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition: int.hpp:220
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:235
Singleton set view.
Definition: view.hpp:589
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: singleton.hpp:204
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: singleton.hpp:134
Integer view for integer variables.
Definition: view.hpp:129
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: singleton.hpp:230
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: singleton.hpp:118
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
static ModEvent modevent(const Delta &d)
Return modification event.
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
Integer variables.
Definition: int.hh:350
GlbRanges(void)
Default constructor.
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
#define forceinline
Definition: config.hpp:132
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:448
int lubMax(void) const
Return maximum of the least upper bound.
Definition: singleton.hpp:127
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
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:158
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: singleton.hpp:250
Gecode::Int::IntView x
View from which this view is derived.
Definition: view.hpp:216
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:186
Gecode toplevel namespace
const Gecode::PropCond PC_SET_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:207
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
LubRanges(void)
Default constructor.
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
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:173
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
static ModEvent me_settoint(ModEvent me)
Convert set variable ModEvent me to a ModEvent for integer variables.
Definition: singleton.hpp:84
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82