Generated on for Gecode by doxygen 1.17.0
afc.cpp
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.dev>
5 *
6 * Copyright:
7 * Christian Schulte, 2009
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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/kernel.hh>
35#include <gecode/int.hh>
36
37#include "test/test.hh"
38
39#include <memory>
40
41namespace Test {
42
44 class AFC : public Test::Base {
45 protected:
47 class TestSpace : public Gecode::Space {
48 protected:
51 public:
53 TestSpace(void) : x(*this,0,10), y(*this,0,10) {}
56 x.update(*this,s.x);
57 y.update(*this,s.y);
58 }
59
60 void post(void) {
61 Gecode::rel(*this, x, Gecode::IRT_LE, y);
62 }
63
64 virtual Space* copy(void) {
65 return new TestSpace(*this);
66 }
67 };
68
69 static const int n_ops = 8 * 1024;
71 static const int n = 16;
73 int space(TestSpace* s[]) {
74 int i = _rand(n);
75 while (s[i] == nullptr)
76 i = (i+1) % n;
77 return i;
78 }
79
80 int index(void) {
81 return _rand(n);
82 }
83 public:
85 AFC(void) : Test::Base("AFC") {}
87 bool run(void) {
88 // Array of spaces for tests
89 TestSpace* s[n];
90 // How many spaces exist in s
91 int n_s = 1;
92
93 for (int i=n; i--; )
94 s[i] = nullptr;
95 s[0] = new TestSpace;
96
97 for (int o=n_ops; o--; )
98 switch (_rand(3)) {
99 case 0:
100 // clone space
101 {
102 int i = index();
103 if ((s[i] != nullptr)) {
104 if (n_s > 1) {
105 delete s[i]; s[i]=nullptr; n_s--;
106 } else {
107 break;
108 }
109 }
110 int j = space(s);
111 (void) s[j]->status();
112 s[i] = static_cast<TestSpace*>(s[j]->clone());
113 n_s++;
114 }
115 break;
116 case 1:
117 // delete space
118 if (n_s > 1) {
119 int i = space(s);
120 delete s[i]; s[i]=nullptr; n_s--;
121 }
122 break;
123 case 2:
124 // post propagator
125 s[space(s)]->post();
126 break;
127 default:
129 }
130 // Delete all remaining spaces
131 for (int i=n; i--; )
132 delete s[i];
133 return true;
134 }
135 };
136
138 class NoGPI : public Test::Base {
140 class TestSpace : public Gecode::Space {
141 public:
142 Gecode::IntVar x, y;
144 TestSpace(void) : x(*this,0,10), y(*this,0,10), b(*this,0,1) {}
145 TestSpace(TestSpace& s) : Space(s) {
146 x.update(*this,s.x); y.update(*this,s.y); b.update(*this,s.b);
147 }
148 virtual Space* copy(void) { return new TestSpace(*this); }
150 Gecode::Propagator* find(unsigned int id) {
151 for (Propagators ps(*this); ps(); ++ps)
152 if (ps.propagator().id() == id)
153 return &ps.propagator();
154 return nullptr;
155 }
159 Gecode::rel((*this)(g), x, Gecode::IRT_LE, y);
160 Gecode::Propagator* p = nullptr;
161 for (Propagators ps(*this); ps(); ++ps)
162 if ((p == nullptr) || (ps.propagator().id() > p->id()))
163 p = &ps.propagator();
164 return *p;
165 }
166 };
167
169 bool scopes(void) {
170 using namespace Gecode;
171 TestSpace s, other;
172 if (s.post().afc() != 1.0)
173 return false;
174 {
175 Space::NoGPI outer(s);
176 if ((s.post().afc() != 0.0) || (other.post().afc() != 1.0))
177 return false;
178 try {
179 Space::NoGPI inner(s);
180 if (s.post().afc() != 0.0)
181 return false;
182 throw 1;
183 } catch (int) {}
184 if (s.post().afc() != 0.0)
185 return false;
186 {
187 Space::UseGPI use(s);
188 if (s.post().afc() != 1.0)
189 return false;
190 {
191 Space::NoGPI suppress(s);
192 if (s.post().afc() != 0.0)
193 return false;
194 }
195 if (s.post().afc() != 1.0)
196 return false;
197 }
198 if (s.post().afc() != 0.0)
199 return false;
200 try {
201 Space::UseGPI use(s);
202 if (s.post().afc() != 1.0)
203 return false;
204 throw 1;
205 } catch (int) {}
206 if (s.post().afc() != 0.0)
207 return false;
208 (void) s.status();
209 std::unique_ptr<TestSpace> c(static_cast<TestSpace*>(s.clone()));
210 if (c->post().afc() != 1.0)
211 return false;
212 }
213 try {
214 Space::NoGPI context(s);
215 throw 1;
216 } catch (int) {}
217 return s.post().afc() == 1.0;
218 }
219
221 bool lifetime(void) {
222 using namespace Gecode;
223 std::unique_ptr<TestSpace> s(new TestSpace);
224 PropagatorGroup a, b;
225 unsigned int id;
226 {
227 Space::NoGPI context(*s);
228 Propagator& p = s->post(a);
229 id = p.id();
230 if ((p.group() != a) || (s->post().id() == id))
231 return false;
232 }
233 a.disable(*s);
234 (void) s->status();
235 std::unique_ptr<TestSpace> c(static_cast<TestSpace*>(s->clone()));
236 // The first call marks the shared pool; the second really unshares.
237 s->afc_unshare();
238 c->afc_unshare();
239 Propagator* p = c->find(id);
240 if (!p || !p->disabled() || (p->afc() != 0.0))
241 return false;
242 b.move(*c,id);
243 if ((p->group() != b) || (s->find(id)->group() != a))
244 return false;
245 s.reset();
246 b.enable(*c);
247 if (p->disabled() || (c->status() == SS_FAILED))
248 return false;
249 b.kill(*c);
250 return (c->find(id) == nullptr) && (b.size(*c) == 0);
251 }
252
254 bool failure(bool local) {
255 using namespace Gecode;
256 TestSpace s;
257 Propagator* p;
258 if (local) {
259 Space::NoGPI context(s);
260 p = &s.post();
261 } else {
262 p = &s.post();
263 }
264 (void) s.status();
265 std::unique_ptr<TestSpace> c(static_cast<TestSpace*>(s.clone()));
266 // Force rescaling on failure for the ordinary propagator.
267 IntAFC afc(*c,IntVarArgs() << c->x << c->y,1.0e-300,false);
268 c->afc_unshare();
269 Propagator* q = c->find(p->id());
270 if (!q || (q->afc() != (local ? 0.0 : 1.0)))
271 return false;
272 rel(*c,c->x,IRT_EQ,5);
273 rel(*c,c->y,IRT_EQ,4);
274 if (c->status() != SS_FAILED)
275 return false;
276 return local ? ((q->afc() == 0.0) && (p->afc() == 0.0)) :
277 ((q->afc() > 1.0) && (p->afc() < 1.0));
278 }
279
281 bool rewrite(bool local) {
282 using namespace Gecode;
283 TestSpace s;
285 if (local) {
286 Space::NoGPI context(s);
287 rel(s(g),s.x,IRT_EQ,s.y,Reify(s.b));
288 } else {
289 rel(s(g),s.x,IRT_EQ,s.y,Reify(s.b));
290 }
291 (void) s.status();
293 unsigned int id = ps.propagator().id();
294 rel(s,s.b,IRT_EQ,1);
295 if (local) {
296 Space::UseGPI context(s);
297 (void) s.status();
298 } else {
299 Space::NoGPI context(s);
300 (void) s.status();
301 }
302 Propagator* p = s.find(id);
303 if (!p || (p->group() != g) ||
304 (p->afc() != (local ? 0.0 : 1.0)))
305 return false;
306 rel(s,s.x,IRT_EQ,3);
307 return (s.status() == SS_SOLVED) && s.y.assigned() && (s.y.val() == 3);
308 }
309
310 public:
311 NoGPI(void) : Test::Base("AFC::NoGPI") {}
312 virtual bool run(void) {
313 return scopes() && lifetime() && failure(false) && failure(true) &&
314 rewrite(false) && rewrite(true);
315 }
316 };
317
319
321
322}
323
324// STATISTICS: test-core
Boolean integer variables.
Definition int.hh:534
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Recording AFC information for integer variables.
Definition int.hh:5379
Passing integer variables.
Definition int.hh:681
Integer variables.
Definition int.hh:390
int val(void) const
Return assigned value.
Definition int.hpp:56
Group of propagators.
Definition core.hpp:734
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition core.hpp:799
static PropagatorGroup all
Group of all propagators.
Definition core.hpp:796
Base-class for propagators.
Definition core.hpp:1073
double afc(void) const
Return the accumulated failure count.
Definition core.hpp:3742
unsigned int id(void) const
Return propagator id.
Definition core.hpp:3759
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition core.hpp:3764
bool disabled(void) const
Whether propagator is currently disabled.
Definition core.hpp:3685
Class to iterate over propagators in a group.
Definition core.hpp:2890
const Propagator & propagator(void) const
Return propagator.
Definition core.hpp:5360
Reification specification.
Definition int.hh:1176
Suppress global propagator information during scoped posting.
Definition core.hpp:2070
Enable global propagator information during scoped posting.
Definition core.hpp:2092
Computation spaces.
Definition core.hpp:1787
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@275070317317120154232063063134255170030071110047 p
Data only available during propagation or branching.
friend class Propagators
Definition core.hpp:1791
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
Test space.
Definition afc.cpp:47
Gecode::IntVar y
Definition afc.cpp:50
void post(void)
Post arbitrary propagator.
Definition afc.cpp:60
TestSpace(TestSpace &s)
Constructor for cloning s.
Definition afc.cpp:55
TestSpace(void)
Constructor for creation.
Definition afc.cpp:53
virtual Space * copy(void)
Copy during cloning.
Definition afc.cpp:64
Gecode::IntVar x
Two integer variables.
Definition afc.cpp:50
Test for AFC infrastructure
Definition afc.cpp:44
AFC(void)
Initialize test.
Definition afc.cpp:85
static const int n
How many spaces to maintain.
Definition afc.cpp:71
bool run(void)
Perform actual tests.
Definition afc.cpp:87
static const int n_ops
How many test operations to be performed.
Definition afc.cpp:69
int index(void)
Return random index.
Definition afc.cpp:80
int space(TestSpace *s[])
Return random index of non-null space.
Definition afc.cpp:73
Base class for all tests to be run
Definition test.hh:186
Gecode::Support::RandomGenerator _rand
Random number generator.
Definition test.hh:238
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
Scoped suppression of global propagator information.
Definition afc.cpp:138
virtual bool run(void)
Run test.
Definition afc.cpp:312
NoGPI(void)
Definition afc.cpp:311
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IRT_LE
Less ( ).
Definition int.hh:1229
Space(void)
Default constructor.
Definition core.cpp:121
virtual Space * copy(void)=0
Copying member function.
Space * clone(void) const
Clone space.
Definition core.hpp:3384
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1728
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Gecode toplevel namespace
General test support.
Definition afc.cpp:41
AFC afc
Definition afc.cpp:320
NoGPI no_gpi
Definition afc.cpp:318
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56