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