Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.1
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  * 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  * Ternary linear propagators
42  *
43  */
44  template<class Val, class A, class B, class C, PropCond pc>
46  LinTer<Val,A,B,C,pc>::LinTer(Home home, A y0, B y1, C y2, Val c0)
47  : Propagator(home), x0(y0), x1(y1), x2(y2), c(c0) {
48  x0.subscribe(home,*this,pc);
49  x1.subscribe(home,*this,pc);
50  x2.subscribe(home,*this,pc);
51  }
52 
53  template<class Val, class A, class B, class C, PropCond pc>
57  : Propagator(home,share,p), c(p.c) {
58  x0.update(home,share,p.x0);
59  x1.update(home,share,p.x1);
60  x2.update(home,share,p.x2);
61  }
62 
63  template<class Val, class A, class B, class C, PropCond pc>
66  A y0, B y1, C y2, Val c0)
67  : Propagator(home,share,p), c(c0) {
68  x0.update(home,share,y0);
69  x1.update(home,share,y1);
70  x2.update(home,share,y2);
71  }
72 
73  template<class Val, class A, class B, class C, PropCond pc>
74  PropCost
77  }
78 
79  template<class Val, class A, class B, class C, PropCond pc>
80  forceinline size_t
82  x0.cancel(home,*this,pc);
83  x1.cancel(home,*this,pc);
84  x2.cancel(home,*this,pc);
85  (void) Propagator::dispose(home);
86  return sizeof(*this);
87  }
88 
89  /*
90  * Equality propagator
91  *
92  */
93 
94  template<class Val, class A, class B, class C>
96  EqTer<Val,A,B,C>::EqTer(Home home, A x0, B x1, C x2, Val c)
97  : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
98 
99  template<class Val, class A, class B, class C>
100  ExecStatus
101  EqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
102  (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
103  return ES_OK;
104  }
105 
106 
107  template<class Val, class A, class B, class C>
110  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
111 
112  template<class Val, class A, class B, class C>
115  A x0, B x1, C x2, Val c)
116  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
117 
118  template<class Val, class A, class B, class C>
119  Actor*
120  EqTer<Val,A,B,C>::copy(Space& home, bool share) {
121  return new (home) EqTer<Val,A,B,C>(home,share,*this);
122  }
123 
125  enum TerMod {
126  TM_X0_MIN = 1<<0,
127  TM_X0_MAX = 1<<1,
128  TM_X1_MIN = 1<<2,
129  TM_X1_MAX = 1<<3,
130  TM_X2_MIN = 1<<4,
131  TM_X2_MAX = 1<<5,
133  };
134 
135 #define GECODE_INT_PV(CASE,TELL,UPDATE) \
136  if (bm & (CASE)) { \
137  bm -= (CASE); ModEvent me = (TELL); \
138  if (me_failed(me)) return ES_FAILED; \
139  if (me_modified(me)) bm |= (UPDATE); \
140  }
141 
142  template<class Val, class A, class B, class C>
143  ExecStatus
145  int bm = TM_ALL;
146  do {
147  GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()),
148  TM_X1_MAX | TM_X2_MAX);
149  GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()),
150  TM_X0_MAX | TM_X2_MAX);
151  GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()),
152  TM_X0_MAX | TM_X1_MAX);
153  GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()),
154  TM_X1_MIN | TM_X2_MIN);
155  GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()),
156  TM_X0_MIN | TM_X2_MIN);
157  GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()),
158  TM_X0_MIN | TM_X1_MIN);
159  } while (bm);
160  return (x0.assigned() && x1.assigned()) ?
161  home.ES_SUBSUMED(*this) : ES_FIX;
162  }
163 
164 #undef GECODE_INT_PV
165 
166 
167 
168  /*
169  * Disequality propagator
170  *
171  */
172 
173  template<class Val, class A, class B, class C>
175  NqTer<Val,A,B,C>::NqTer(Home home, A x0, B x1, C x2, Val c)
176  : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
177 
178  template<class Val, class A, class B, class C>
179  ExecStatus
180  NqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
181  (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
182  return ES_OK;
183  }
184 
185 
186  template<class Val, class A, class B, class C>
189  : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p) {}
190 
191  template<class Val, class A, class B, class C>
192  Actor*
193  NqTer<Val,A,B,C>::copy(Space& home, bool share) {
194  return new (home) NqTer<Val,A,B,C>(home,share,*this);
195  }
196 
197  template<class Val, class A, class B, class C>
200  A x0, B x1, C x2, Val c)
201  : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p,x0,x1,x2,c) {}
202 
203 
204  template<class Val, class A, class B, class C>
205  ExecStatus
207  if (x0.assigned() && x1.assigned()) {
208  GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
209  return home.ES_SUBSUMED(*this);
210  }
211  if (x0.assigned() && x2.assigned()) {
212  GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
213  return home.ES_SUBSUMED(*this);
214  }
215  if (x1.assigned() && x2.assigned()) {
216  GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
217  return home.ES_SUBSUMED(*this);
218  }
219  return ES_FIX;
220  }
221 
222 
223 
224  /*
225  * Inequality propagator
226  *
227  */
228 
229  template<class Val, class A, class B, class C>
231  LqTer<Val,A,B,C>::LqTer(Home home, A x0, B x1, C x2, Val c)
232  : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
233 
234  template<class Val, class A, class B, class C>
235  ExecStatus
236  LqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
237  (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
238  return ES_OK;
239  }
240 
241 
242  template<class Val, class A, class B, class C>
245  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
246 
247  template<class Val, class A, class B, class C>
248  Actor*
249  LqTer<Val,A,B,C>::copy(Space& home, bool share) {
250  return new (home) LqTer<Val,A,B,C>(home,share,*this);
251  }
252 
253 
254  template<class Val, class A, class B, class C>
257  A x0, B x1, C x2, Val c)
258  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
259 
260  template<class Val, class A, class B, class C>
261  ExecStatus
263  GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
264  GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
265  GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
266  return (x0.max()+x1.max()+x2.max() <= c) ?
267  home.ES_SUBSUMED(*this) : ES_FIX;
268  }
269 
270 }}}
271 
272 // STATISTICS: int-prop
273 
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:180
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-ter.hpp:249
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-ter.hpp:193
Propagator for bounds consistent ternary linear equality
Definition: linear.hh:382
Base-class for propagators.
Definition: core.hpp:755
Base-class for ternary linear propagators.
Definition: linear.hh:346
Propagation has computed fixpoint.
Definition: core.hpp:528
EqTer(Space &home, bool share, EqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:109
Computation spaces.
Definition: core.hpp:1362
LinTer(Space &home, bool share, LinTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:55
Base-class for both propagators and branchers.
Definition: core.hpp:666
Propagator for bounds consistent ternary linear less or equal
Definition: linear.hh:452
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-ter.hpp:81
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:236
A x0
View of type A.
Definition: linear.hh:349
NqTer(Space &home, bool share, NqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:188
B x1
View of type B.
Definition: linear.hh:351
TerMod
Describe which view has been modified how.
Definition: int-ter.hpp:125
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-ter.hpp:120
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:262
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:101
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:144
Execution is okay.
Definition: core.hpp:527
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4050
Gecode toplevel namespace
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
Propagator for bounds consistent ternary linear disquality
Definition: linear.hh:417
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:206
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
Home class for posting propagators
Definition: core.hpp:717
C x2
View of type C.
Definition: linear.hh:353
#define GECODE_INT_PV(CASE, TELL, UPDATE)
Definition: int-ter.hpp:135
LqTer(Space &home, bool share, LqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:244
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low ternary)
Definition: int-ter.hpp:75