Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.1
int-dom.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2006
8  *
9  * Last modified:
10  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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 Int { namespace Linear {
39 
47  class SupportSet {
48  private:
51  public:
53  SupportSet(void);
55  void init(Region& r, unsigned int n);
57  void support(unsigned int i);
59  bool supported(unsigned int i) const;
60 
61  private:
63  class ResultIter : public ViewValues<IntView> {
64  protected:
66  const SupportSet& s;
68  unsigned int p;
69  public:
71  ResultIter(const SupportSet& s0, const IntView& x);
73  void operator ++(void);
74  };
75 
76  public:
78  ModEvent tell(Space& home, IntView& x) const;
79  };
80 
85  template<class Val>
86  class SupportIter {
87  protected:
89  int a;
95  int c;
97  unsigned int p;
99  Val l;
101  Val u;
102  public:
104  void init(Region& r, int a, const IntView& x, Val l, Val u);
106  void support(void);
108  ModEvent tell(Space& home);
109  };
110 
111 
116  template<class Val>
117  class PosSupportIter : public SupportIter<Val> {
118  private:
120  IntVarImpFwd i;
121  // Using-declarations for dependant names
122  using SupportIter<Val>::a;
123  using SupportIter<Val>::x;
124  using SupportIter<Val>::s;
125  using SupportIter<Val>::c;
126  using SupportIter<Val>::p;
127  using SupportIter<Val>::l;
128  using SupportIter<Val>::u;
129  public:
131  bool reset(Val& d);
133  bool adjust(Val& d);
134  };
135 
136 
141  template<class Val>
142  class NegSupportIter : public SupportIter<Val> {
143  private:
145  IntVarImpBwd i;
146  // Using-declarations for dependant names
147  using SupportIter<Val>::a;
148  using SupportIter<Val>::x;
149  using SupportIter<Val>::s;
150  using SupportIter<Val>::c;
151  using SupportIter<Val>::p;
152  using SupportIter<Val>::l;
153  using SupportIter<Val>::u;
154  public:
156  bool reset(Val& d);
158  bool adjust(Val& d);
159  };
160 
161 
162  /*
163  * Support set
164  *
165  */
168  forceinline void
169  SupportSet::init(Region& r, unsigned int n) {
170  bs.init(r,n);
171  }
172  forceinline void
173  SupportSet::support(unsigned int i) {
174  bs.set(i);
175  }
176  forceinline bool
177  SupportSet::supported(unsigned int i) const {
178  return bs.get(i);
179  }
180 
182  SupportSet::ResultIter::ResultIter(const SupportSet& s0, const IntView& x)
183  : ViewValues<IntView>(x), s(s0), p(0) {
184  while (ViewValues<IntView>::operator ()() && s.supported(p)) {
186  }
187  }
188  forceinline void
189  SupportSet::ResultIter::operator ++(void) {
190  do {
192  } while (ViewValues<IntView>::operator ()() && s.supported(p));
193  }
194 
195 
197  SupportSet::tell(Space& home, IntView& x) const {
198  switch (bs.status()) {
199  case Support::BSS_NONE:
200  return ME_INT_FAILED;
201  case Support::BSS_ALL:
202  return ME_INT_NONE;
203  case Support::BSS_SOME:
204  {
205  ResultIter i(*this,x);
206  return x.minus_v(home,i);
207  }
208  default:
209  GECODE_NEVER;
210  }
211  return ME_INT_NONE;
212  }
213 
214 
215  /*
216  * Base-class for support-based iterator
217  *
218  */
219  template<class Val>
220  forceinline void
222  int a0, const IntView& x0, Val l0, Val u0) {
223  a=a0; x=x0; l=l0; u=u0;
224  s.init(r,x.size());
225  }
226  template<class Val>
227  forceinline void
229  s.support(p);
230  }
231  template<class Val>
234  return s.tell(home,x);
235  }
236 
237 
238  /*
239  * Support-based iterator for positive view
240  *
241  */
242  template<class Val>
243  forceinline bool
245  // Way too small, no value can make it big enough
246  if (d + static_cast<Val>(a)*x.max() < u)
247  return false;
248  // Restart iterator and position of values
249  i.init(x.varimp()); p = 0;
250  // Skip all ranges which are too small
251  while (d + static_cast<Val>(a)*i.max() < u) {
252  p += i.width(); ++i;
253  }
254  // There is at least one range left (check of max)
255  assert(i());
256  // Initialize current range and adjust value
257  c = i.min();
258  // Skip all values which are too small
259  while (d + static_cast<Val>(a)*c < u) {
260  p++; c++;
261  }
262  // Adjust to new value
263  d += static_cast<Val>(a) * c;
264  return true;
265  }
266  template<class Val>
267  forceinline bool
269  // Current value
270  Val v = static_cast<Val>(a) * c;
271  // Subtract current value from d
272  d -= v;
273  // Move to next position (number of value)
274  p++;
275  // Still in the same range
276  if (c < i.max()) {
277  // Decrement current values
278  c += 1; v += a;
279  } else {
280  // Go to next range
281  ++i;
282  if (!i())
283  return false;
284  c = i.min(); v = static_cast<Val>(a) * c;
285  }
286  // Is d with the current value too large?
287  if (d + v > l)
288  return false;
289  // Update d
290  d += v;
291  return true;
292  }
293 
294 
295  /*
296  * Support-based iterator for negative view
297  *
298  */
299  template<class Val>
300  forceinline bool
302  // Way too small, no value can make it big enough
303  if (d + static_cast<Val>(a)*x.min() < u)
304  return false;
305  // Restart iterator and position of values
306  i.init(x.varimp()); p = x.size()-1;
307  // Skip all ranges which are too small
308  while (d + static_cast<Val>(a)*i.min() < u) {
309  p -= i.width(); ++i;
310  }
311  // There is at least one range left (check of max)
312  assert(i());
313  // Initialize current range
314  c = i.max();
315  // Skip all values which are too small
316  while (d + static_cast<Val>(a)*c < u) {
317  p--; c--;
318  }
319  // Adjust to new value
320  d += static_cast<Val>(a) * c;
321  return true;
322  }
323  template<class Val>
324  forceinline bool
326  // Current value
327  Val v = static_cast<Val>(a) * c;
328  // Subtract current value from d
329  d -= v;
330  // Move to next position (number of value)
331  p--;
332  // Still in the same range
333  if (c > i.min()) {
334  // Decrement current values
335  c -= 1; v -= a;
336  } else {
337  // Go to next range
338  ++i;
339  if (!i())
340  return false;
341  c = i.max(); v = static_cast<Val>(a) * c;
342  }
343  // Is d with the current value too large?
344  if (d + v > l)
345  return false;
346  // Update d
347  d += v;
348  return true;
349  }
350 
351 
352 
353  /*
354  * The domain consisten equality propagator
355  *
356  */
357  template<class Val, class View>
361  Val c)
362  : Lin<Val,View,View,PC_INT_DOM>(home,x,y,c) {}
363 
364  template<class Val, class View>
365  ExecStatus
368  Val c) {
369  (void) new (home) DomEq<Val,View>(home,x,y,c);
370  return ES_OK;
371  }
372 
373  template<class Val, class View>
376  : Lin<Val,View,View,PC_INT_DOM>(home,share,p) {}
377 
378  template<class Val, class View>
379  Actor*
380  DomEq<Val,View>::copy(Space& home, bool share) {
381  return new (home) DomEq<Val,View>(home,share,*this);
382  }
383 
384  template<class Val, class View>
385  PropCost
386  DomEq<Val,View>::cost(const Space&, const ModEventDelta& med) const {
387  if (View::me(med) != ME_INT_DOM)
388  return PropCost::linear(PropCost::LO, x.size()+y.size());
389  else
390  return PropCost::crazy(PropCost::HI, x.size()+y.size());
391  }
392 
393  template<class Val, class View>
394  ExecStatus
396  if (View::me(med) != ME_INT_DOM) {
397  ExecStatus es = prop_bnd<Val,View,View>(home,med,*this,x,y,c);
398  GECODE_ES_CHECK(es);
399  return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
400  }
401 
402  // Value of equation for partial assignment
403  Val d = -c;
404 
405  int n = x.size();
406  int m = y.size();
407 
408  Region r(home);
409  // Create support-base iterators
412 
413  // Initialize views for assignments
414  {
415  Val l = 0;
416  Val u = 0;
417  for (int j=m; j--; ) {
418  yp[j].init(r,-y[j].scale(),y[j].base(),l,u);
419  l += y[j].max(); u += y[j].min();
420  }
421  for (int i=n; i--; ) {
422  xp[i].init(r,x[i].scale(),x[i].base(),l,u);
423  l -= x[i].min(); u -= x[i].max();
424  }
425  }
426 
427  // Collect support information by iterating assignments
428  {
429  // Force reset of all iterators in first round
430  int i = 0;
431  int j = 0;
432 
433  next_i:
434  // Reset all iterators for positive views and update d
435  while (i<n) {
436  if (!xp[i].reset(d)) goto prev_i;
437  i++;
438  }
439  next_j:
440  // Reset all iterators for negative views and update d
441  while (j<m) {
442  if (!yp[j].reset(d)) goto prev_j;
443  j++;
444  }
445  // Check whether current assignment is solution
446  if (d == 0) {
447  // Record support
448  for (int is=n; is--; ) xp[is].support();
449  for (int js=m; js--; ) yp[js].support();
450  }
451  prev_j:
452  // Try iterating to next assignment: negative views
453  while (j>0) {
454  if (yp[j-1].adjust(d)) goto next_j;
455  j--;
456  }
457  prev_i:
458  // Try iterating to next assignment: positive views
459  while (i>0) {
460  if (xp[i-1].adjust(d)) goto next_i;
461  i--;
462  }
463  }
464 
465  // Tell back new variable domains
466  bool assigned = true;
467  for (int i=n; i--; ) {
468  GECODE_ME_CHECK(xp[i].tell(home));
469  if (!x[i].assigned())
470  assigned = false;
471  }
472  for (int j=m; j--; ) {
473  GECODE_ME_CHECK(yp[j].tell(home));
474  if (!y[j].assigned())
475  assigned = false;
476  }
477  if (assigned)
478  return home.ES_SUBSUMED(*this);
479  return ES_FIX;
480  }
481 
482 }}}
483 
484 // STATISTICS: int-prop
bool get(unsigned int i) const
Access value at bit i.
bool reset(Val &d)
Reset iterator to beginning and adjust.
Definition: int-dom.hpp:244
Val u
Upper bound information for value.
Definition: int-dom.hpp:101
unsigned int p
Position of current value.
Definition: int-dom.hpp:97
SupportSet(void)
Default constructor.
Definition: int-dom.hpp:167
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Some but not all bits set.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
VarImpType * varimp(void) const
Return variable implementation of view.
Definition: view.hpp:433
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
Propagator for domain consistent n-ary linear equality
Definition: linear.hh:600
bool adjust(Val &d)
Adjust.
Definition: int-dom.hpp:325
bool supported(unsigned int i) const
Check whether position.
Definition: int-dom.hpp:177
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-dom.hpp:380
Basic bitset support.
int ModEvent
Type for modification events.
Definition: core.hpp:146
Expensive.
Definition: core.hpp:564
Val l
Lower bound information for value.
Definition: int-dom.hpp:99
Set for support information
Definition: int-dom.hpp:47
Handle to region.
Definition: region.hpp:61
Value iterator for integer views.
Definition: view.hpp:94
Base-class for n-ary linear propagators.
Definition: linear.hh:495
Propagation has computed fixpoint.
Definition: core.hpp:528
SupportSet s
Set of support for values in x.
Definition: int-dom.hpp:93
Computation spaces.
Definition: core.hpp:1362
bool reset(Val &d)
Reset iterator to beginning and adjust.
Definition: int-dom.hpp:301
Base-class for both propagators and branchers.
Definition: core.hpp:666
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:200
void operator++(void)
Move iterator to next value (if possible)
Gecode::IntSet d(v, 7)
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
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
Gecode::FloatVal c(-8, 8)
Base-class for support-based iterator.
Definition: int-dom.hpp:86
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
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:75
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:387
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-dom.hpp:395
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
Backward iterator for ranges of integer variable implementations.
Definition: var-imp.hpp:430
ModEvent tell(Space &home)
Tell back new variable domain according to support found.
Definition: int-dom.hpp:233
Support-based iterator for negative view.
Definition: int-dom.hpp:142
void init(A &a, unsigned int s, bool setbits=false)
Initialize for s bits and allocator a (only after default constructor)
void set(unsigned int i)
Set bit i.
View arrays.
Definition: array.hpp:234
BitSetStatus status(void) const
Return status of bitset.
DomEq(Space &home, bool share, DomEq &p)
Constructor for cloning p.
Definition: int-dom.hpp:375
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: int-dom.hpp:386
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
void support(unsigned int i)
Record that there is support at position i.
Definition: int-dom.hpp:173
static ExecStatus post(Home home, ViewArray< View > &x, ViewArray< View > &y, Val c)
Post propagator for .
Definition: int-dom.hpp:366
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
const int v[7]
Definition: distinct.cpp:207
Integer view for integer variables.
Definition: view.hpp:129
void init(Region &r, unsigned int n)
Initialize support set with cardinality n.
Definition: int-dom.hpp:169
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Propagation cost.
Definition: core.hpp:537
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
int a
Integer coefficient for view.
Definition: int-dom.hpp:89
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:4014
void init(Region &r, int a, const IntView &x, Val l, Val u)
Initialize view.
Definition: int-dom.hpp:221
Execution is okay.
Definition: core.hpp:527
Support-based iterator for positive view.
Definition: int-dom.hpp:117
void support(void)
Record value at current position as supported.
Definition: int-dom.hpp:228
Gecode toplevel namespace
ModEvent tell(Space &home, IntView &x) const
Perform tell according to recorded support information on.
Definition: int-dom.hpp:197
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
#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.
IntView x
Integer view.
Definition: int-dom.hpp:91
bool adjust(Val &d)
Adjust.
Definition: int-dom.hpp:268