Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.1
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: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
11  * $Revision: 10364 $
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>
46  ViewArray<XV>& x0, YV y0, int c0)
47  : Propagator(home), x(x0), y(y0), c(c0) {
48  x.subscribe(home,*this,PC_INT_VAL);
49  y.subscribe(home,*this,PC_INT_BND);
50  }
51 
52  template<class XV, class YV>
53  forceinline size_t
55  x.cancel(home,*this,PC_INT_VAL);
56  y.cancel(home,*this,PC_INT_BND);
57  (void) Propagator::dispose(home);
58  return sizeof(*this);
59  }
60 
61  template<class XV, class YV>
64  : Propagator(home,share,p), c(p.c) {
65  x.update(home,share,p.x);
66  y.update(home,share,p.y);
67  }
68 
69  template<class XV, class YV>
70  PropCost
72  return PropCost::linear(PropCost::LO, x.size());
73  }
74 
75 
76  /*
77  * Equality propagator
78  *
79  */
80  template<class XV, class YV>
83  : LinBoolView<XV,YV>(home,x,y,c) {}
84 
85  template<class XV, class YV>
88  if (y.assigned())
89  return EqBoolInt<XV>::post(home,x,y.val()+c);
90  int n = x.size();
91  for (int i = n; i--; )
92  if (x[i].one()) {
93  x[i]=x[--n]; c--;
94  } else if (x[i].zero()) {
95  x[i]=x[--n];
96  }
97  x.size(n);
98  GECODE_ME_CHECK(y.lq(home,n-c));
99  GECODE_ME_CHECK(y.gq(home,-c));
100  if (n == 0)
101  return ES_OK;
102  if (y.min()+c == n) {
103  assert(y.assigned());
104  for (int i = n; i--; )
105  GECODE_ME_CHECK(x[i].one_none(home));
106  return ES_OK;
107  }
108  if (y.max()+c == 0) {
109  assert(y.assigned());
110  for (int i = n; i--; )
111  GECODE_ME_CHECK(x[i].zero_none(home));
112  return ES_OK;
113  }
114  (void) new (home) EqBoolView<XV,YV>(home,x,y,c);
115  return ES_OK;
116  }
117 
118  template<class XV, class YV>
121  : LinBoolView<XV,YV>(home,share,p) {}
122 
123  template<class XV, class YV>
124  Actor*
125  EqBoolView<XV,YV>::copy(Space& home, bool share) {
126  return new (home) EqBoolView<XV,YV>(home,share,*this);
127  }
128 
129  template<class XV, class YV>
130  ExecStatus
132  int n = x.size();
133  for (int i = n; i--; )
134  if (x[i].one()) {
135  x[i]=x[--n]; c--;
136  } else if (x[i].zero()) {
137  x[i]=x[--n];
138  }
139  x.size(n);
140  GECODE_ME_CHECK(y.lq(home,n-c));
141  GECODE_ME_CHECK(y.gq(home,-c));
142  if (n == 0)
143  return home.ES_SUBSUMED(*this);
144  if (y.min()+c == n) {
145  assert(y.assigned());
146  for (int i = n; i--; )
147  GECODE_ME_CHECK(x[i].one_none(home));
148  return home.ES_SUBSUMED(*this);
149  }
150  if (y.max()+c == 0) {
151  assert(y.assigned());
152  for (int i = n; i--; )
153  GECODE_ME_CHECK(x[i].zero_none(home));
154  return home.ES_SUBSUMED(*this);
155  }
156  if (y.assigned())
157  GECODE_REWRITE(*this,EqBoolInt<XV>::post(home(*this),x,y.val()+c));
158  return ES_FIX;
159  }
160 
161 
162  /*
163  * Disequality propagator
164  *
165  */
166  template<class XV, class YV>
169  : LinBoolView<XV,YV>(home,x,y,c) {}
170 
171  template<class XV, class YV>
172  ExecStatus
174  if (y.assigned())
175  return NqBoolInt<XV>::post(home,x,y.val()+c);
176  int n = x.size();
177  for (int i = n; i--; )
178  if (x[i].one()) {
179  x[i]=x[--n]; c--;
180  } else if (x[i].zero()) {
181  x[i]=x[--n];
182  }
183  x.size(n);
184  if ((n-c < y.min() ) || (-c > y.max()))
185  return ES_OK;
186  if (n == 0) {
187  GECODE_ME_CHECK(y.nq(home,-c));
188  return ES_OK;
189  }
190  if ((n == 1) && y.assigned()) {
191  if (y.val()+c == 1) {
192  GECODE_ME_CHECK(x[0].zero_none(home));
193  } else {
194  assert(y.val()+c == 0);
195  GECODE_ME_CHECK(x[0].one_none(home));
196  }
197  return ES_OK;
198  }
199  (void) new (home) NqBoolView<XV,YV>(home,x,y,c);
200  return ES_OK;
201  }
202 
203 
204  template<class XV, class YV>
207  : LinBoolView<XV,YV>(home,share,p) {}
208 
209  template<class XV, class YV>
210  Actor*
211  NqBoolView<XV,YV>::copy(Space& home, bool share) {
212  return new (home) NqBoolView<XV,YV>(home,share,*this);
213  }
214 
215  template<class XV, class YV>
216  ExecStatus
218  int n = x.size();
219  for (int i = n; i--; )
220  if (x[i].one()) {
221  x[i]=x[--n]; c--;
222  } else if (x[i].zero()) {
223  x[i]=x[--n];
224  }
225  x.size(n);
226  if ((n-c < y.min() ) || (-c > y.max()))
227  return home.ES_SUBSUMED(*this);
228  if (n == 0) {
229  GECODE_ME_CHECK(y.nq(home,-c));
230  return home.ES_SUBSUMED(*this);
231  }
232  if ((n == 1) && y.assigned()) {
233  if (y.val()+c == 1) {
234  GECODE_ME_CHECK(x[0].zero_none(home));
235  } else {
236  assert(y.val()+c == 0);
237  GECODE_ME_CHECK(x[0].one_none(home));
238  }
239  return home.ES_SUBSUMED(*this);
240  }
241  return ES_FIX;
242  }
243 
244 
245  /*
246  * Greater or equal propagator
247  *
248  */
249  template<class XV, class YV>
252  : LinBoolView<XV,YV>(home,x,y,c) {}
253 
254  template<class XV, class YV>
255  ExecStatus
257  if (y.assigned())
258  return GqBoolInt<XV>::post(home,x,y.val()+c);
259  // Eliminate assigned views
260  int n = x.size();
261  for (int i = n; i--; )
262  if (x[i].one()) {
263  x[i]=x[--n]; c--;
264  } else if (x[i].zero()) {
265  x[i]=x[--n];
266  }
267  x.size(n);
268  GECODE_ME_CHECK(y.lq(home,n-c));
269  if (-c >= y.max())
270  return ES_OK;
271  if (y.min()+c == n) {
272  for (int i = n; i--; )
273  GECODE_ME_CHECK(x[i].one_none(home));
274  return ES_OK;
275  }
276  (void) new (home) GqBoolView<XV,YV>(home,x,y,c);
277  return ES_OK;
278  }
279 
280 
281  template<class XV, class YV>
284  : LinBoolView<XV,YV>(home,share,p) {}
285 
286  template<class XV, class YV>
287  Actor*
288  GqBoolView<XV,YV>::copy(Space& home, bool share) {
289  return new (home) GqBoolView<XV,YV>(home,share,*this);
290  }
291 
292  template<class XV, class YV>
293  ExecStatus
295  int n = x.size();
296  for (int i = n; i--; )
297  if (x[i].one()) {
298  x[i]=x[--n]; c--;
299  } else if (x[i].zero()) {
300  x[i]=x[--n];
301  }
302  x.size(n);
303  GECODE_ME_CHECK(y.lq(home,n-c));
304  if (-c >= y.max())
305  return home.ES_SUBSUMED(*this);
306  if (y.min()+c == n) {
307  for (int i = n; i--; )
308  GECODE_ME_CHECK(x[i].one_none(home));
309  return home.ES_SUBSUMED(*this);
310  }
311  if (y.assigned())
312  GECODE_REWRITE(*this,GqBoolInt<XV>::post(home(*this),x,y.val()+c));
313  return ES_FIX;
314  }
315 
316 }}}
317 
318 // STATISTICS: int-prop
319 
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-view.hpp:131
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
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:1008
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
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:1005
Propagator for integer disequal to Boolean sum (cardinality)
Definition: linear.hh:869
EqBoolView(Space &home, bool share, EqBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:120
Base-class for propagators.
Definition: core.hpp:755
YV y
View to compare number of assigned Boolean views to.
Definition: linear.hh:1010
GqBoolView(Space &home, bool share, GqBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:283
Propagation has computed fixpoint.
Definition: core.hpp:528
static ExecStatus post(Home home, ViewArray< XV > &x, YV y, int c)
Post propagator for .
Definition: bool-view.hpp:87
Computation spaces.
Definition: core.hpp:1362
Propagator for equality to Boolean sum (cardinality)
Definition: linear.hh:1032
Base-class for both propagators and branchers.
Definition: core.hpp:666
static ExecStatus post(Home home, ViewArray< XV > &x, YV y, int c)
Post propagator for .
Definition: bool-view.hpp:256
static ExecStatus post(Home home, ViewArray< XV > &x, YV y, int c)
Post propagator for .
Definition: bool-view.hpp:173
Gecode::FloatVal c(-8, 8)
Propagator for greater or equal to Boolean sum (cardinality)
Definition: linear.hh:1084
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
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: bool-view.hpp:71
Propagator for integer less or equal to Boolean sum (cardinality)
Definition: linear.hh:840
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
Propagator for integer equal to Boolean sum (cardinality)
Definition: linear.hh:811
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:125
NqBoolView(Space &home, bool share, NqBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:206
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-view.hpp:217
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
Execution is okay.
Definition: core.hpp:527
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: bool-view.hpp:288
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-view.hpp:294
LinBoolView(Space &home, bool share, LinBoolView &p)
Constructor for cloning p.
Definition: bool-view.hpp:63
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: bool-view.hpp:54
Propagator for disequality to Boolean sum (cardinality)
Definition: linear.hh:1058
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
Home class for posting propagators
Definition: core.hpp:717
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: bool-view.hpp:211
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82