Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
lq.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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Int { namespace Bool {
35 
36  /*
37  * Less or equal propagator
38  *
39  */
40 
41  template<class BV>
43  Lq<BV>::Lq(Home home, BV b0, BV b1)
44  : BoolBinary<BV,BV>(home,b0,b1) {}
45 
46  template<class BV>
49  : BoolBinary<BV,BV>(home,p) {}
50 
51  template<class BV>
52  Actor*
54  return new (home) Lq<BV>(home,*this);
55  }
56 
57  template<class BV>
58  inline ExecStatus
59  Lq<BV>::post(Home home, BV b0, BV b1) {
60  if (b0.zero()) {
61  return ES_OK;
62  } else if (b0.one()) {
63  GECODE_ME_CHECK(b1.one(home));
64  } else if (b1.zero()) {
65  GECODE_ME_CHECK(b0.zero(home));
66  } else if (b1.one()) {
67  return ES_OK;
68  } else {
69  (void) new (home) Lq<BV>(home,b0,b1);
70  }
71  return ES_OK;
72  }
73 
74  template<class BV>
77 #define GECODE_INT_STATUS(S0,S1) \
78  ((BV::S0<<(1*BV::BITS))|(BV::S1<<(0*BV::BITS)))
79  switch ((x0.status()<<(1*BV::BITS)) | (x1.status()<<(0*BV::BITS))) {
80  case GECODE_INT_STATUS(NONE,NONE):
82  case GECODE_INT_STATUS(NONE,ZERO):
83  GECODE_ME_CHECK(x0.zero_none(home)); break;
84  case GECODE_INT_STATUS(NONE,ONE):
85  case GECODE_INT_STATUS(ZERO,NONE):
86  case GECODE_INT_STATUS(ZERO,ZERO):
87  case GECODE_INT_STATUS(ZERO,ONE):
88  break;
89  case GECODE_INT_STATUS(ONE,NONE):
90  GECODE_ME_CHECK(x1.one_none(home)); break;
91  case GECODE_INT_STATUS(ONE,ZERO):
92  return ES_FAILED;
93  case GECODE_INT_STATUS(ONE,ONE):
94  break;
95  default:
97  }
98  return home.ES_SUBSUMED(*this);
99 #undef GECODE_INT_STATUS
100  }
101 
102 
103  /*
104  * N-ary Boolean less or equal propagator
105  *
106  */
107 
108  template<class VX>
111  : NaryPropagator<VX,PC_BOOL_NONE>(home,x),
112  run(false), n_zero(0), n_one(0), c(home) {
113  x.subscribe(home,*new (home) Advisor(home,*this,c));
114  }
115 
116  template<class VX>
119  : NaryPropagator<VX,PC_BOOL_NONE>(home,p),
120  run(false), n_zero(0), n_one(0) {
121  c.update(home,p.c);
122  }
123 
124  template<class VX>
125  Actor*
127  return new (home) NaryLq<VX>(home,*this);
128  }
129 
130  template<class VX>
131  inline ExecStatus
133  int i = 0;
134  while (i < x.size())
135  if (x[i].zero()) {
136  // All x[j] left of i must be zero as well
137  for (int j=0; j<i; j++)
138  GECODE_ME_CHECK(x[j].zero_none(home));
139  x.drop_fst(i+1); i=0;
140  } else if (x[i].one()) {
141  // All x[j] right of i must be one as well
142  for (int j=i+1; j<x.size(); j++)
143  GECODE_ME_CHECK(x[j].one(home));
144  x.drop_lst(i-1); break;
145  } else {
146  i++;
147  }
148 
149  if (x.size() == 2)
150  return Lq<VX>::post(home,x[0],x[1]);
151  if (x.size() > 2)
152  (void) new (home) NaryLq(home,x);
153  return ES_OK;
154  }
155 
156  template<class VX>
157  PropCost
158  NaryLq<VX>::cost(const Space&, const ModEventDelta&) const {
160  }
161 
162  template<class VX>
163  ExecStatus
165  if (VX::zero(d))
166  n_zero++;
167  else
168  n_one++;
169  return run ? ES_FIX : ES_NOFIX;
170  }
171 
172  template<class VX>
173  forceinline size_t
175  Advisors<Advisor> as(c);
176  x.cancel(home,as.advisor());
177  c.dispose(home);
179  return sizeof(*this);
180  }
181 
182  template<class VX>
183  ExecStatus
185  run = true;
186  while (n_zero > 0) {
187  int i = 0;
188  while (x[i].none())
189  i++;
190  if (x[i].one())
191  return ES_FAILED;
192  // As the x[j] might be shared, only zero() but not zero_none()
193  for (int j=0; j<i; j++)
194  GECODE_ME_CHECK(x[j].zero(home));
195  n_zero -= i + 1;
196  assert(n_zero >= 0);
197  x.drop_fst(i+1);
198  }
199 
200  while (n_one > 0) {
201  int i = x.size() - 1;
202  while (x[i].none())
203  i--;
204  assert(x[i].one());
205  // As the x[j] might be shared, only one() but not one_none()
206  for (int j=i+1; j<x.size(); j++)
207  GECODE_ME_CHECK(x[j].one(home));
208  n_one -= x.size() - i;
209  assert(n_one >= 0);
210  x.drop_lst(i-1);
211  }
212 
213  if (x.size() < 2)
214  return home.ES_SUBSUMED(*this);
215 
216  run = false;
217  return ES_FIX;
218  }
219 
220 
221  /*
222  * Less posting
223  *
224  */
225 
226  template<class BV>
228  Le<BV>::post(Home home, BV b0, BV b1) {
229  GECODE_ME_CHECK(b0.zero(home));
230  GECODE_ME_CHECK(b1.one(home));
231  return ES_OK;
232  }
233 
234 }}}
235 
236 // STATISTICS: int-prop
237 
const Gecode::PropCond PC_BOOL_NONE
Propagation condition to be ignored (convenience)
Definition: var-type.hpp:118
Post propagator for SetVar x
Definition: set.hh:767
NaryLq(Home home, ViewArray< VX > &x)
Constructor for posting.
Definition: lq.hpp:110
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1341
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: lq.hpp:53
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4809
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: lq.hpp:174
Class to iterate over advisors of a council.
Definition: core.hpp:156
Cheap.
Definition: core.hpp:513
Computation spaces.
Definition: core.hpp:1742
Base-class for both propagators and branchers.
Definition: core.hpp:628
Council< Advisor > c
The advisor council.
Definition: bool.hh:193
ViewArray< VX > x
Array of views.
Definition: pattern.hpp:145
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: lq.hpp:126
#define GECODE_INT_STATUS(S0, S1)
static ExecStatus post(Home home, BV b0, BV b1)
Post propagator .
Definition: lq.hpp:59
Gecode toplevel namespace
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: lq.hpp:76
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: lq.hpp:184
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Basic b1(3)
Home class for posting propagators
Definition: core.hpp:856
n-ary propagator
Definition: pattern.hpp:142
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:46
Boolean less or equal propagator.
Definition: bool.hh:159
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: lq.hpp:164
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
Nary Boolean less or equal propagator.
Definition: bool.hh:183
Base-class for binary Boolean propagators.
Definition: bool.hh:55
Propagation cost.
Definition: core.hpp:486
Lq(Home home, BV b0, BV b1)
Constructor for posting.
Definition: lq.hpp:43
Gecode::IntSet d(v, 7)
Base-class for advisors.
Definition: core.hpp:1292
Propagation has computed fixpoint.
Definition: core.hpp:477
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary)
Definition: lq.hpp:158
static ExecStatus post(Home home, ViewArray< VX > &x)
Post propagator .
Definition: lq.hpp:132
static ExecStatus post(Home home, BV b0, BV b1)
Post propagator .
Definition: lq.hpp:228
#define forceinline
Definition: config.hpp:185
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
Gecode::FloatVal c(-8, 8)
A & advisor(void) const
Return advisor.
Definition: core.hpp:4010
Execution has resulted in failure.
Definition: core.hpp:474
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Propagation has not computed fixpoint.
Definition: core.hpp:475
Gecode::IntArgs i({1, 2, 3, 4})
Execution is okay.
Definition: core.hpp:476
friend class Advisor
Definition: core.hpp:1068
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ExecStatus
Definition: core.hpp:472