Generated on Thu Jul 25 2019 00:00:00 for Gecode by doxygen 1.8.15
bool-view.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, 2004
8  *
9  * Last modified:
10  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
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 
40  /*
41  * Base-class
42  *
43  */
44  template<class XV, class YV>
47  ViewArray<XV>& x0, YV y0, int c0)
48  : Propagator(home), x(x0), y(y0), c(c0) {
49  x.subscribe(home,*this,PC_INT_VAL);
50  y.subscribe(home,*this,PC_INT_BND);
51  }
52 
53  template<class XV, class YV>
54  forceinline size_t
56  x.cancel(home,*this,PC_INT_VAL);
57  y.cancel(home,*this,PC_INT_BND);
58  (void) Propagator::dispose(home);
59  return sizeof(*this);
60  }
61 
62  template<class XV, class YV>
65  : Propagator(home,share,p), c(p.c) {
66  x.update(home,share,p.x);
67  y.update(home,share,p.y);
68  }
69 
70  template<class XV, class YV>
71  PropCost
73  return PropCost::linear(PropCost::LO, x.size());
74  }
75 
76  template<class XV, class YV>
77  void
79  x.reschedule(home,*this,PC_INT_VAL);
80  y.reschedule(home,*this,PC_INT_BND);
81  }
82 
83 
84  /*
85  * Equality propagator
86  *
87  */
88  template<class XV, class YV>
91  : LinBoolView<XV,YV>(home,x,y,c) {}
92 
93  template<class XV, class YV>
96  if (y.assigned())
97  return EqBoolInt<XV>::post(home,x,y.val()+c);
98  int n = x.size();
99  for (int i = n; i--; )
100  if (x[i].one()) {
101  x[i]=x[--n]; c--;
102  } else if (x[i].zero()) {
103  x[i]=x[--n];
104  }
105  x.size(n);
106  GECODE_ME_CHECK(y.lq(home,n-c));
107  GECODE_ME_CHECK(y.gq(home,-c));
108  if (n == 0)
109  return ES_OK;
110  if (y.min()+c == n) {
111  assert(y.assigned());
112  for (int i = n; i--; )
113  GECODE_ME_CHECK(x[i].one_none(home));
114  return ES_OK;
115  }
116  if (y.max()+c == 0) {
117  assert(y.assigned());
118  for (int i = n; i--; )
119  GECODE_ME_CHECK(x[i].zero_none(home));
120  return ES_OK;
121  }
122  (void) new (home) EqBoolView<XV,YV>(home,x,y,c);
123  return ES_OK;
124  }
125 
126  template<class XV, class YV>
129  : LinBoolView<XV,YV>(home,share,p) {}
130 
131  template<class XV, class YV>
132  Actor*
133  EqBoolView<XV,YV>::copy(Space& home, bool share) {
134  return new (home) EqBoolView<XV,YV>(home,share,*this);
135  }
136 
137  template<class XV, class YV>
138  ExecStatus
140  int n = x.size();
141  for (int i = n; i--; )
142  if (x[i].one()) {
143  x[i]=x[--n]; c--;
144  } else if (x[i].zero()) {
145  x[i]=x[--n];
146  }
147  x.size(n);
148  GECODE_ME_CHECK(y.lq(home,n-c));
149  GECODE_ME_CHECK(y.gq(home,-c));
150  if (n == 0)
151  return home.ES_SUBSUMED(*this);
152  if (y.min()+c == n) {
153  assert(y.assigned());
154  for (int i = n; i--; )
155  GECODE_ME_CHECK(x[i].one_none(home));
156  return home.ES_SUBSUMED(*this);
157  }
158  if (y.max()+c == 0) {
159  assert(y.assigned());
160  for (int i = n; i--; )
161  GECODE_ME_CHECK(x[i].zero_none(home));
162  return home.ES_SUBSUMED(*this);
163  }
164  if (y.assigned())
165  GECODE_REWRITE(*this,EqBoolInt<XV>::post(home(*this),x,y.val()+c));
166  return ES_FIX;
167  }
168 
169 
170  /*
171  * Disequality propagator
172  *
173  */
174  template<class XV, class YV>
177  : LinBoolView<XV,YV>(home,x,y,c) {}
178 
179  template<class XV, class YV>
180  ExecStatus
182  if (y.assigned())
183  return NqBoolInt<XV>::post(home,x,y.val()+c);
184  int n = x.size();
185  for (int i = n; i--; )
186  if (x[i].one()) {
187  x[i]=x[--n]; c--;
188  } else if (x[i].zero()) {
189  x[i]=x[--n];
190  }
191  x.size(n);
192  if ((n-c < y.min() ) || (-c > y.max()))
193  return ES_OK;
194  if (n == 0) {
195  GECODE_ME_CHECK(y.nq(home,-c));
196  return ES_OK;
197  }
198  if ((n == 1) && y.assigned()) {
199  if (y.val()+c == 1) {
200  GECODE_ME_CHECK(x[0].zero_none(home));
201  } else {
202  assert(y.val()+c == 0);
203  GECODE_ME_CHECK(x[0].one_none(home));
204  }
205  return ES_OK;
206  }
207  (void) new (home) NqBoolView<XV,YV>(home,x,y,c);
208  return ES_OK;
209  }
210 
211 
212  template<class XV, class YV>
215  : LinBoolView<XV,YV>(home,share,p) {}
216 
217  template<class XV, class YV>
218  Actor*
219  NqBoolView<XV,YV>::copy(Space& home, bool share) {
220  return new (home) NqBoolView<XV,YV>(home,share,*this);
221  }
222 
223  template<class XV, class YV>
224  ExecStatus
226  int n = x.size();
227  for (int i = n; i--; )
228  if (x[i].one()) {
229  x[i]=x[--n]; c--;
230  } else if (x[i].zero()) {
231  x[i]=x[--n];
232  }
233  x.size(n);
234  if ((n-c < y.min() ) || (-c > y.max()))
235  return home.ES_SUBSUMED(*this);
236  if (n == 0) {
237  GECODE_ME_CHECK(y.nq(home,-c));
238  return home.ES_SUBSUMED(*this);
239  }
240  if ((n == 1) && y.assigned()) {
241  if (y.val()+c == 1) {
242  GECODE_ME_CHECK(x[0].zero_none(home));
243  } else {
244  assert(y.val()+c == 0);
245  GECODE_ME_CHECK(x[0].one_none(home));
246  }
247  return home.ES_SUBSUMED(*this);
248  }
249  return ES_FIX;
250  }
251 
252 
253  /*
254  * Greater or equal propagator
255  *
256  */
257  template<class XV, class YV>
260  : LinBoolView<XV,YV>(home,x,y,c) {}
261 
262  template<class XV, class YV>
263  ExecStatus
265  if (y.assigned())
266  return GqBoolInt<XV>::post(home,x,y.val()+c);
267  // Eliminate assigned views
268  int n = x.size();
269  for (int i = n; i--; )
270  if (x[i].one()) {
271  x[i]=x[--n]; c--;
272  } else if (x[i].zero()) {
273  x[i]=x[--n];
274  }
275  x.size(n);
276  GECODE_ME_CHECK(y.lq(home,n-c));
277  if (-c >= y.max())
278  return ES_OK;
279  if (y.min()+c == n) {
280  for (int i = n; i--; )
281  GECODE_ME_CHECK(x[i].one_none(home));
282  return ES_OK;
283  }
284  (void) new (home) GqBoolView<XV,YV>(home,x,y,c);
285  return ES_OK;
286  }
287 
288 
289  template<class XV, class YV>
292  : LinBoolView<XV,YV>(home,share,p) {}
293 
294  template<class XV, class YV>
295  Actor*
296  GqBoolView<XV,YV>::copy(Space& home, bool share) {
297  return new (home) GqBoolView<XV,YV>(home,share,*this);
298  }
299 
300  template<class XV, class YV>
301  ExecStatus
303  int n = x.size();
304  for (int i = n; i--; )
305  if (x[i].one()) {
306  x[i]=x[--n]; c--;
307  } else if (x[i].zero()) {
308  x[i]=x[--n];
309  }
310  x.size(n);
311  GECODE_ME_CHECK(y.lq(home,n-c));
312  if (-c >= y.max())
313  return home.ES_SUBSUMED(*this);
314  if (y.min()+c == n) {
315  for (int i = n; i--; )
316  GECODE_ME_CHECK(x[i].one_none(home));
317  return home.ES_SUBSUMED(*this);
318  }
319  if (y.assigned())
320  GECODE_REWRITE(*this,GqBoolInt<XV>::post(home(*this),x,y.val()+c));
321  return ES_FIX;
322  }
323 
324 }}}
325 
326 // STATISTICS: int-prop
327 
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-view.hpp:139
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
ViewArray< XV > x
Boolean views.
Definition: linear.hh:1030
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4841
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:50
Base-class for Boolean linear propagators.
Definition: linear.hh:1027
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
Propagator for integer disequal to Boolean sum (cardinality)
Definition: linear.hh:887
EqBoolView(Space &home, bool share, EqBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:128
Base-class for propagators.
Definition: core.hpp:1092
YV y
View to compare number of assigned Boolean views to.
Definition: linear.hh:1032
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
GqBoolView(Space &home, bool share, GqBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:291
virtual void reschedule(Space &home)
Schedule function.
Definition: bool-view.hpp:78
Propagation has computed fixpoint.
Definition: core.hpp:545
static ExecStatus post(Home home, ViewArray< XV > &x, YV y, int c)
Post propagator for .
Definition: bool-view.hpp:95
Computation spaces.
Definition: core.hpp:1748
Propagator for equality to Boolean sum (cardinality)
Definition: linear.hh:1056
Base-class for both propagators and branchers.
Definition: core.hpp:696
static ExecStatus post(Home home, ViewArray< XV > &x, YV y, int c)
Post propagator for .
Definition: bool-view.hpp:264
static ExecStatus post(Home home, ViewArray< XV > &x, YV y, int c)
Post propagator for .
Definition: bool-view.hpp:181
Gecode::FloatVal c(-8, 8)
Propagator for greater or equal to Boolean sum (cardinality)
Definition: linear.hh:1108
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
Propagator for integer less or equal to Boolean sum (cardinality)
Definition: linear.hh:855
Propagator for integer equal to Boolean sum (cardinality)
Definition: linear.hh:823
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: bool-view.hpp:133
NqBoolView(Space &home, bool share, NqBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:214
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: bool-view.hpp:72
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-view.hpp:225
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
#define forceinline
Definition: config.hpp:173
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: bool-view.hpp:296
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-view.hpp:302
LinBoolView(Space &home, bool share, LinBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:64
Gecode toplevel namespace
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: bool-view.hpp:55
Propagator for disequality to Boolean sum (cardinality)
Definition: linear.hh:1082
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: bool-view.hpp:219
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82