Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.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  * 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
252  }
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 
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
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Base-class for advisors.
Definition: core.hpp:1292
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Base-class for derived views.
Definition: view.hpp:230
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:605
Gecode::Int::IntView x
View from which this view is derived.
Definition: view.hpp:238
Integer variables.
Definition: int.hh:371
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:392
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
Integer view for integer variables.
Definition: view.hpp:129
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:81
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:186
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: int.hpp:148
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:107
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:130
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:191
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:70
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition: int.hpp:230
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:157
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
Base-class for propagators.
Definition: core.hpp:1064
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:110
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:112
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
bool operator()(void) const
Test whether iterator is still at a range or done.
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
void operator++(void)
Move iterator to next range (if possible)
GlbRanges(void)
Default constructor.
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
LubRanges(void)
Default constructor.
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
Singleton set view.
Definition: view.hpp:594
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
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: singleton.hpp:292
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: singleton.hpp:107
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
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: singleton.hpp:114
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: singleton.hpp:235
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition: singleton.hpp:99
int lubMax(void) const
Return maximum of the least upper bound.
Definition: singleton.hpp:123
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: singleton.hpp:130
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: singleton.hpp:254
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: singleton.hpp:221
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: singleton.hpp:117
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: singleton.hpp:283
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: singleton.hpp:94
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition: singleton.hpp:205
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: singleton.hpp:126
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: singleton.hpp:231
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: singleton.hpp:102
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 notContains(int i) const
Test whether i is not in the least upper bound.
Definition: singleton.hpp:111
SingletonView(void)
Default constructor.
Definition: singleton.hpp:41
static PropCond pc_settoint(PropCond pc)
Convert set variable PropCond pc to a PropCond for integer variables.
Definition: singleton.hpp:52
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
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: singleton.hpp:200
static ModEvent me_inttoset(ModEvent me)
Convert integer variable ModEvent me to a ModEvent for set variables.
Definition: singleton.hpp:64
static ModEvent me_settoint(ModEvent me)
Convert set variable ModEvent me to a ModEvent for integer variables.
Definition: singleton.hpp:80
int lubMin(void) const
Return minimum of the least upper bound.
Definition: singleton.hpp:120
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: singleton.hpp:250
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
Computation spaces.
Definition: core.hpp:1742
static ModEventDelta med(ModEvent me)
Translate modification event me to modification event delta for view.
Definition: view.hpp:557
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: view.hpp:547
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:527
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: view.hpp:562
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: view.hpp:532
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:516
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:521
void varimp(VarImpType *y)
Set variable implementation to y.
Definition: view.hpp:484
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
int ModEvent
Type for modification events.
Definition: core.hpp:62
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
const double base
Base for geometric restart sequence.
Definition: search.hh:126
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:140
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:142
const Gecode::PropCond PC_SET_CARD
Propagate when the cardinality of a view changes.
Definition: var-type.hpp:216
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:381
const Gecode::PropCond PC_SET_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:207
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition: var-type.hpp:156
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:138
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 CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:387
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
#define forceinline
Definition: config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56