Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
bool.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  * Copyright:
7  * Guido Tack, 2004
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 #include <gecode/int.hh>
35 
36 namespace Gecode { namespace Set { namespace Channel {
37 
38  template<class View>
39  template<class A>
43  Council<A>& c, int index)
44  : Advisor(home,p,c), idx(index) {
45  if (idx == -1)
46  p.y.subscribe(home,*this);
47  else {
48  p.x[idx].subscribe(home,*this);
49  }
50  }
51 
52  template<class View>
55  : Advisor(home,a), idx(a.idx) {}
56 
57  template<class View>
58  forceinline int
60  return idx;
61  }
62 
63  template<class View>
64  template<class A>
65  forceinline void
67  ChannelBool<View>& p = static_cast<ChannelBool<View>&>(propagator());
68  if (idx == -1)
69  p.y.cancel(home,*this);
70  else {
71  p.x[idx].cancel(home,*this);
72  }
73  Advisor::dispose(home,c);
74  }
75 
76  template<class View>
80  View y0)
81  : Super(home,x0,y0), co(home), running(false) {
82  bool assigned = false;
83  for (int i=x.size(); i--;) {
84  if (x[i].zero()) {
85  assigned = true;
86  SetDelta d;
87  zeros.include(home, i, i, d);
88  } else if (x[i].one()) {
89  assigned = true;
90  SetDelta d;
91  ones.include(home, i, i, d);
92  } else {
93  (void) new (home) IndexAdvisor(home,*this,co,i);
94  }
95  }
96  if (assigned)
98  View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
99  if (y.assigned()) {
100  if (y.glbSize()==static_cast<unsigned int>(y.glbMax()-y.glbMin()+1)) {
101  new (&delta) SetDelta(y.glbMin(),y.glbMax(),1,0);
102  } else {
103  new (&delta) SetDelta(2,0,1,0);
104  }
105  }
106  (void) new (home) IndexAdvisor(home,*this,co,-1);
107  }
108 
109  template<class View>
112  : Super(home,p), running(false) {
113  co.update(home, p.co);
114  }
115 
116  template<class View>
119  View y) {
120  GECODE_ME_CHECK(y.intersect(home, 0, x.size()-1));
121  (void) new (home) ChannelBool(home,x,y);
122  return ES_OK;
123  }
124 
125  template<class View>
126  PropCost
128  return PropCost::quadratic(PropCost::LO, x.size()+1);
129  }
130 
131  template<class View>
132  void
134  x.reschedule(home,*this,Gecode::Int::PC_BOOL_VAL);
135  View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
136  }
137 
138  template<class View>
139  forceinline size_t
141  co.dispose(home);
142  (void) Super::dispose(home);
143  return sizeof(*this);
144  }
145 
146  template<class View>
147  Actor*
149  return new (home) ChannelBool(home,*this);
150  }
151 
152  template<class View>
153  ExecStatus
155  running = true;
156  if (zeros.size() > 0) {
157  BndSetRanges zi(zeros);
158  GECODE_ME_CHECK(y.excludeI(home, zi));
159  zeros.init(home);
160  }
161  if (ones.size() > 0) {
162  BndSetRanges oi(ones);
163  GECODE_ME_CHECK(y.includeI(home, oi));
164  ones.init(home);
165  }
166  running = false;
167 
168  if (delta.glbMin() != 1 || delta.glbMax() != 0) {
169  if (!delta.glbAny()) {
170  for (int i=delta.glbMin(); i<=delta.glbMax(); i++)
171  GECODE_ME_CHECK(x[i].one(home));
172  } else {
173  GlbRanges<View> glb(y);
174  for (Iter::Ranges::ToValues<GlbRanges<View> > gv(glb); gv(); ++gv) {
175  GECODE_ME_CHECK(x[gv.val()].one(home));
176  }
177  }
178  }
179  if (delta.lubMin() != 1 || delta.lubMax() != 0) {
180  if (!delta.lubAny()) {
181  for (int i=delta.lubMin(); i<=delta.lubMax(); i++)
182  GECODE_ME_CHECK(x[i].zero(home));
183  } else {
184  int cur = 0;
185  for (LubRanges<View> lub(y); lub(); ++lub) {
186  for (; cur < lub.min(); cur++) {
187  GECODE_ME_CHECK(x[cur].zero(home));
188  }
189  cur = lub.max() + 1;
190  }
191  for (; cur < x.size(); cur++) {
192  GECODE_ME_CHECK(x[cur].zero(home));
193  }
194  }
195  }
196 
197  new (&delta) SetDelta();
198 
199  return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
200  }
201 
202  template<class View>
203  ExecStatus
205  IndexAdvisor& a = static_cast<IndexAdvisor&>(_a);
206  const SetDelta& d = static_cast<const SetDelta&>(_d);
207 
208  ModEvent me = View::modevent(d);
209  int index = a.index();
210  if ( (running && index == -1 && me != ME_SET_VAL)
211  || (index == -1 && me == ME_SET_CARD) ) {
212  return ES_OK;
213  }
214 
215  if (index >= 0) {
216  if (x[index].zero()) {
217  SetDelta dummy;
218  zeros.include(home, index, index, dummy);
219  } else {
220  assert(x[index].one());
221  SetDelta dummy;
222  ones.include(home, index, index, dummy);
223  }
224  return home.ES_NOFIX_DISPOSE( co, a);
225  }
226 
227  if ((a.index() == -1) && Rel::testSetEventLB(me)) {
228  if (d.glbAny()) {
229  new (&delta)
230  SetDelta(2,0, delta.lubMin(), delta.lubMax());
231  } else {
232  if (delta.glbMin() == 1 && delta.glbMax() == 0) {
233  new (&delta)
234  SetDelta(d.glbMin(), d.glbMax(),
235  delta.lubMin(), delta.lubMax());
236  } else {
237  if (delta.glbMin() != 2 || delta.glbMax() != 0) {
238  if ((delta.glbMin() <= d.glbMin() && delta.glbMax() >= d.glbMin())
239  ||
240  (delta.glbMin() <= d.glbMax() && delta.glbMax() >= d.glbMax())
241  ) {
242  new (&delta)
243  SetDelta(std::min(delta.glbMin(), d.glbMin()),
244  std::max(delta.glbMax(), d.glbMax()),
245  delta.lubMin(), delta.lubMax());
246  } else {
247  new (&delta)
248  SetDelta(2, 0, delta.lubMin(), delta.lubMax());
249  }
250  }
251  }
252  }
253  }
254  if ((a.index() == -1) && Rel::testSetEventUB(me)) {
255  if (d.lubAny()) {
256  new (&delta)
257  SetDelta(delta.glbMin(), delta.glbMax(), 2,0);
258  } else {
259  if (delta.lubMin() == 1 && delta.lubMax() == 0) {
260  new (&delta)
261  SetDelta(delta.glbMin(), delta.glbMax(),
262  d.lubMin(), d.lubMax());
263  } else {
264  if (delta.lubMin() != 2 || delta.lubMax() != 0) {
265  if ((delta.lubMin() <= d.lubMin() && delta.lubMax() >= d.lubMin())
266  ||
267  (delta.lubMin() <= d.lubMax() && delta.lubMax() >= d.lubMax())
268  ) {
269  new (&delta)
270  SetDelta(delta.lubMin(), delta.lubMax(),
271  std::min(delta.lubMin(), d.lubMin()),
272  std::max(delta.lubMax(), d.lubMax())
273  );
274  } else {
275  new (&delta)
276  SetDelta(delta.glbMin(), delta.glbMax(), 2, 0);
277  }
278  }
279  }
280  }
281  }
282  if (y.assigned())
283  return home.ES_NOFIX_DISPOSE( co, a);
284  else
285  return ES_NOFIX;
286  }
287 
288 }}}
289 
290 // STATISTICS: set-prop
View y
Single view.
Definition: pattern.hpp:277
Post propagator for SetVar x
Definition: set.hh:767
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:279
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:126
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3887
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
Council< IndexAdvisor > co
Council for managing advisors.
Definition: channel.hh:185
Single _a(2, 3)
void dummy(Space &)
A dummy function for branching.
Definition: nogoods.cpp:51
ViewArray< Gecode::Int::BoolView > x
Array of views.
Definition: pattern.hpp:275
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Cheap.
Definition: core.hpp:513
Advisor storing a single index
Definition: channel.hh:166
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: bool.hpp:140
IndexAdvisor(Space &home, ChannelBool< View > &p, Council< A > &c, int index)
Constructor for creation.
Definition: bool.hpp:41
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Multi _d(Gecode::IntArgs({3, 2, 1}))
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:142
GLBndSet zeros
Accumulated zero Booleans.
Definition: channel.hh:189
Computation spaces.
Definition: core.hpp:1742
void dispose(Space &home, Council< A > &c)
Delete advisor.
Definition: bool.hpp:66
Base-class for both propagators and branchers.
Definition: core.hpp:628
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4787
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:116
virtual void reschedule(Space &home)
Schedule function.
Definition: bool.hpp:133
Gecode toplevel namespace
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:87
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
GLBndSet ones
Accumulated one Booleans.
Definition: channel.hh:191
Home class for posting propagators
Definition: core.hpp:856
Value iterator from range iterator.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: bool.hpp:148
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: view.hpp:547
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:46
const Gecode::ModEvent ME_SET_BB
Domain operation has changed both greatest lower and least upper bound.
Definition: var-type.hpp:172
Propagator for channelling between set variable and its characteristic function
Definition: channel.hh:148
int ModEvent
Type for modification events.
Definition: core.hpp:62
Propagation cost.
Definition: core.hpp:486
bool running
Flag whether propagation is currently running.
Definition: channel.hh:193
ChannelBool(Space &home, ChannelBool &p)
Constructor for cloning p.
Definition: bool.hpp:111
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_QUADRATIC_LO)
Definition: bool.hpp:127
int index(void) const
Access index.
Definition: bool.hpp:59
Council of advisors
Definition: core.hpp:155
Finite set delta information for advisors.
Definition: var-imp.hpp:52
Gecode::IntSet d(v, 7)
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: bool.hpp:204
Base-class for advisors.
Definition: core.hpp:1292
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3864
Propagation has computed fixpoint.
Definition: core.hpp:477
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1156
Range iterator for integer sets.
Definition: var-imp.hpp:185
#define forceinline
Definition: config.hpp:185
static ExecStatus post(Home home, ViewArray< Gecode::Int::BoolView > &x, View y)
Post propagator for .
Definition: bool.hpp:118
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
bool testSetEventLB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:83
Gecode::FloatVal c(-8, 8)
int idx
The single index.
Definition: channel.hh:169
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool.hpp:154
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})
const Gecode::ModEvent ME_SET_CARD
Domain operation has changed the variable cardinality.
Definition: var-type.hpp:148
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
Definition: filter.cpp:131
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
SetDelta delta
Accumulated delta information.
Definition: channel.hh:187
ExecStatus
Definition: core.hpp:472