Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
int-ter.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, 2003
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 Linear {
35 
36  /*
37  * Ternary linear propagators
38  *
39  */
40  template<class Val, class A, class B, class C, PropCond pc>
42  LinTer<Val,A,B,C,pc>::LinTer(Home home, A y0, B y1, C y2, Val c0)
43  : Propagator(home), x0(y0), x1(y1), x2(y2), c(c0) {
44  x0.subscribe(home,*this,pc);
45  x1.subscribe(home,*this,pc);
46  x2.subscribe(home,*this,pc);
47  }
48 
49  template<class Val, class A, class B, class C, PropCond pc>
52  : Propagator(home,p), c(p.c) {
53  x0.update(home,p.x0);
54  x1.update(home,p.x1);
55  x2.update(home,p.x2);
56  }
57 
58  template<class Val, class A, class B, class C, PropCond pc>
61  A y0, B y1, C y2, Val c0)
62  : Propagator(home,p), c(c0) {
63  x0.update(home,y0);
64  x1.update(home,y1);
65  x2.update(home,y2);
66  }
67 
68  template<class Val, class A, class B, class C, PropCond pc>
69  PropCost
71  return PropCost::ternary(PropCost::LO);
72  }
73 
74  template<class Val, class A, class B, class C, PropCond pc>
75  void
77  x0.reschedule(home,*this,pc);
78  x1.reschedule(home,*this,pc);
79  x2.reschedule(home,*this,pc);
80  }
81 
82  template<class Val, class A, class B, class C, PropCond pc>
83  forceinline size_t
85  x0.cancel(home,*this,pc);
86  x1.cancel(home,*this,pc);
87  x2.cancel(home,*this,pc);
88  (void) Propagator::dispose(home);
89  return sizeof(*this);
90  }
91 
92  /*
93  * Equality propagator
94  *
95  */
96 
97  template<class Val, class A, class B, class C>
99  EqTer<Val,A,B,C>::EqTer(Home home, A x0, B x1, C x2, Val c)
100  : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
101 
102  template<class Val, class A, class B, class C>
103  ExecStatus
104  EqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
105  (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
106  return ES_OK;
107  }
108 
109 
110  template<class Val, class A, class B, class C>
113  : LinTer<Val,A,B,C,PC_INT_BND>(home,p) {}
114 
115  template<class Val, class A, class B, class C>
118  A x0, B x1, C x2, Val c)
119  : LinTer<Val,A,B,C,PC_INT_BND>(home,p,x0,x1,x2,c) {}
120 
121  template<class Val, class A, class B, class C>
122  Actor*
124  return new (home) EqTer<Val,A,B,C>(home,*this);
125  }
126 
128  enum TerMod {
129  TM_X0_MIN = 1<<0,
130  TM_X0_MAX = 1<<1,
131  TM_X1_MIN = 1<<2,
132  TM_X1_MAX = 1<<3,
133  TM_X2_MIN = 1<<4,
134  TM_X2_MAX = 1<<5,
136  };
137 
138 #define GECODE_INT_PV(CASE,TELL,UPDATE) \
139  if (bm & (CASE)) { \
140  bm -= (CASE); ModEvent me = (TELL); \
141  if (me_failed(me)) return ES_FAILED; \
142  if (me_modified(me)) bm |= (UPDATE); \
143  }
144 
145  template<class Val, class A, class B, class C>
146  ExecStatus
148  int bm = TM_ALL;
149  do {
150  GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()),
151  TM_X1_MAX | TM_X2_MAX);
152  GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()),
153  TM_X0_MAX | TM_X2_MAX);
154  GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()),
155  TM_X0_MAX | TM_X1_MAX);
156  GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()),
157  TM_X1_MIN | TM_X2_MIN);
158  GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()),
159  TM_X0_MIN | TM_X2_MIN);
160  GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()),
161  TM_X0_MIN | TM_X1_MIN);
162  } while (bm);
163  return (x0.assigned() && x1.assigned()) ?
164  home.ES_SUBSUMED(*this) : ES_FIX;
165  }
166 
167 #undef GECODE_INT_PV
168 
169 
170 
171  /*
172  * Disequality propagator
173  *
174  */
175 
176  template<class Val, class A, class B, class C>
178  NqTer<Val,A,B,C>::NqTer(Home home, A x0, B x1, C x2, Val c)
179  : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
180 
181  template<class Val, class A, class B, class C>
182  ExecStatus
183  NqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
184  (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
185  return ES_OK;
186  }
187 
188 
189  template<class Val, class A, class B, class C>
192  : LinTer<Val,A,B,C,PC_INT_VAL>(home,p) {}
193 
194  template<class Val, class A, class B, class C>
195  Actor*
197  return new (home) NqTer<Val,A,B,C>(home,*this);
198  }
199 
200  template<class Val, class A, class B, class C>
203  A x0, B x1, C x2, Val c)
204  : LinTer<Val,A,B,C,PC_INT_VAL>(home,p,x0,x1,x2,c) {}
205 
206 
207  template<class Val, class A, class B, class C>
208  ExecStatus
210  if (x0.assigned() && x1.assigned()) {
211  GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
212  return home.ES_SUBSUMED(*this);
213  }
214  if (x0.assigned() && x2.assigned()) {
215  GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
216  return home.ES_SUBSUMED(*this);
217  }
218  if (x1.assigned() && x2.assigned()) {
219  GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
220  return home.ES_SUBSUMED(*this);
221  }
222  return ES_FIX;
223  }
224 
225 
226 
227  /*
228  * Inequality propagator
229  *
230  */
231 
232  template<class Val, class A, class B, class C>
234  LqTer<Val,A,B,C>::LqTer(Home home, A x0, B x1, C x2, Val c)
235  : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
236 
237  template<class Val, class A, class B, class C>
238  ExecStatus
239  LqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
240  (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
241  return ES_OK;
242  }
243 
244 
245  template<class Val, class A, class B, class C>
248  : LinTer<Val,A,B,C,PC_INT_BND>(home,p) {}
249 
250  template<class Val, class A, class B, class C>
251  Actor*
253  return new (home) LqTer<Val,A,B,C>(home,*this);
254  }
255 
256 
257  template<class Val, class A, class B, class C>
260  A x0, B x1, C x2, Val c)
261  : LinTer<Val,A,B,C,PC_INT_BND>(home,p,x0,x1,x2,c) {}
262 
263  template<class Val, class A, class B, class C>
264  ExecStatus
266  GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
267  GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
268  GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
269  return (x0.max()+x1.max()+x2.max() <= c) ?
270  home.ES_SUBSUMED(*this) : ES_FIX;
271  }
272 
273 }}}
274 
275 // STATISTICS: int-prop
276 
Definition: int-ter.hpp:134
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:386
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:398
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:239
Base-class for ternary linear propagators.
Definition: linear.hh:346
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: int-ter.hpp:123
Definition: int-ter.hpp:129
NqTer(Space &home, NqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:191
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:265
Computation spaces.
Definition: core.hpp:1742
Base-class for both propagators and branchers.
Definition: core.hpp:628
TerMod
Describe which view has been modified how.
Definition: int-ter.hpp:128
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:147
LqTer(Space &home, LqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:247
Definition: int-ter.hpp:132
Propagator for bounds consistent ternary linear disquality
Definition: linear.hh:419
LinTer(Space &home, LinTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:51
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:92
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: int-ter.hpp:252
Home class for posting propagators
Definition: core.hpp:856
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:104
Definition: int-ter.hpp:133
IntSet * A
Position of a piece in a square board.
#define GECODE_INT_PV(CASE, TELL, UPDATE)
Definition: int-ter.hpp:138
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Propagator for bounds consistent ternary linear equality
Definition: linear.hh:384
Definition: int-ter.hpp:135
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: int-ter.hpp:196
Propagation cost.
Definition: core.hpp:486
Definition: int-ter.hpp:131
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82
Propagation has computed fixpoint.
Definition: core.hpp:477
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:183
Propagator for bounds consistent ternary linear less or equal
Definition: linear.hh:454
#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
Definition: int-ter.hpp:130
Gecode::FloatVal c(-8, 8)
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Execution is okay.
Definition: core.hpp:476
EqTer(Space &home, EqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:112
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:209
ExecStatus
Definition: core.hpp:472