Generated on Thu Jul 25 2019 00:00:00 for Gecode by doxygen 1.8.15
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: 2016-09-02 15:36:56 +0200 (Fri, 02 Sep 2016) $ by $Author: schulte $
15  * $Revision: 15162 $
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  forceinline void
240  x.reschedule(home,p,pc_settoint(pc));
241  }
242 
243  forceinline void
245  x.subscribe(home,a);
246  }
247  forceinline void
249  x.cancel(home,a);
250  }
251 
252 
253  forceinline void
256  }
260  }
263  return SetView::med(me_settoint(me));
264  }
265 
266 
267  /*
268  * Delta information for advisors
269  *
270  * For SingletonViews, a glb change means that the view is assigned.
271  * Thus, the delta for the glb is always equal to the delta for the lub.
272  *
273  */
274 
278  }
279 
280  forceinline int
281  SingletonView::glbMin(const Delta& d) const { return x.min(d); }
282 
283  forceinline int
284  SingletonView::glbMax(const Delta& d) const { return x.max(d); }
285 
286  forceinline bool
287  SingletonView::glbAny(const Delta& d) const { return x.any(d); }
288 
289  forceinline int
290  SingletonView::lubMin(const Delta& d) const { return x.min(d); }
291 
292  forceinline int
293  SingletonView::lubMax(const Delta& d) const { return x.max(d); }
294 
295  forceinline bool
296  SingletonView::lubAny(const Delta& d) const { return x.any(d); }
297 
298  /*
299  * Iterators
300  *
301  */
302 
307  template<>
309  public:
311 
312  LubRanges(void);
315  LubRanges(const SingletonView& x);
317  void init(const SingletonView& x);
319  };
320 
323 
326  Gecode::Int::IntVarImpFwd(s.base().varimp()) {}
327 
328  forceinline void
331  }
332 
337  template<>
339  private:
340  int val;
341  bool flag;
342  public:
344 
345  GlbRanges(void);
348  GlbRanges(const SingletonView& x);
350  void init(const SingletonView& x);
351 
353 
354  bool operator ()(void) const;
357  void operator ++(void);
359 
361 
362  int min(void) const;
365  int max(void) const;
367  unsigned int width(void) const;
369  };
370 
373 
374  forceinline void
376  if (s.base().assigned()) {
377  val = s.base().val();
378  flag = true;
379  } else {
380  val = 0;
381  flag = false;
382  }
383  }
384 
387  init(s);
388  }
389 
390  forceinline bool
391  GlbRanges<SingletonView>::operator ()(void) const { return flag; }
392 
393  forceinline void
395 
396  forceinline int
397  GlbRanges<SingletonView>::min(void) const { return val; }
398  forceinline int
399  GlbRanges<SingletonView>::max(void) const { return val; }
400  forceinline unsigned int
401  GlbRanges<SingletonView>::width(void) const { return 1; }
402 
403 }}
404 
405 // STATISTICS: set-var
406 
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.
Definition: view.hpp:519
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:489
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:561
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: singleton.hpp:276
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Definition: singleton.hpp:262
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: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
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: singleton.hpp:225
int lubMin(void) const
Return minimum of the least upper bound.
Definition: singleton.hpp:124
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:160
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: singleton.hpp:130
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:121
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:142
void varimp(VarImpType *y)
Set variable implementation to y.
Definition: view.hpp:453
Base-class for propagators.
Definition: core.hpp:1092
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:75
Base-class for advisors.
Definition: core.hpp:1294
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
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: view.hpp:494
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:1748
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: singleton.hpp:98
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:222
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: singleton.hpp:287
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:103
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:114
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::FloatVal c(-8, 8)
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:101
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:483
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:124
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: singleton.hpp:258
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
int lubMax(void) const
Return maximum of the least upper bound.
Definition: singleton.hpp:127
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: singleton.hpp:118
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
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:68
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: singleton.hpp:134
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: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
Integer view for integer variables.
Definition: view.hpp:129
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition: int.hpp:220
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: singleton.hpp:230
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:478
const double base
Base for geometric restart sequence.
Definition: search.hh:122
Generic domain change information to be supplied to advisors.
Definition: core.hpp:281
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: view.hpp:524
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:353
GlbRanges(void)
Default constructor.
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:514
#define forceinline
Definition: config.hpp:173
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
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:254
Post propagator for SetVar x
Definition: set.hh:784
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: singleton.hpp:115
Gecode::Int::IntView x
View from which this view is derived.
Definition: view.hpp:230
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
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: singleton.hpp:106
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:509
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: singleton.hpp:239
LubRanges(void)
Default constructor.
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:169
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: singleton.hpp:296
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: singleton.hpp:111
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
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