this repo has no description
dekker.one
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, 2004, 2016
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
34namespace Gecode { namespace Search { namespace Seq {
35
36 /*
37 * Nodes for the probing engine (just remember next alternative
38 * to try)
39 *
40 */
41
42 template<class Tracer>
43 forceinline
44 Probe<Tracer>::Node::Node(void) {}
45
46 template<class Tracer>
47 forceinline
48 Probe<Tracer>::Node::Node(Space* s, const Choice* c, unsigned int a,
49 unsigned int nid)
50 : _space(s), _choice(c), _alt(a), _nid(nid) {}
51
52 template<class Tracer>
53 forceinline Space*
54 Probe<Tracer>::Node::space(void) const {
55 return _space;
56 }
57
58 template<class Tracer>
59 forceinline const Choice*
60 Probe<Tracer>::Node::choice(void) const {
61 return _choice;
62 }
63
64 template<class Tracer>
65 forceinline unsigned int
66 Probe<Tracer>::Node::alt(void) const {
67 return _alt;
68 }
69
70 template<class Tracer>
71 forceinline unsigned int
72 Probe<Tracer>::Node::nid(void) const {
73 return _nid;
74 }
75
76 template<class Tracer>
77 forceinline void
78 Probe<Tracer>::Node::next(void) {
79 _alt--;
80 }
81
82
83 /*
84 * The probing engine: computes all solutions with
85 * exact number of discrepancies (solutions with
86 * fewer discrepancies are discarded)
87 *
88 */
89
90 template<class Tracer>
91 forceinline
92 Probe<Tracer>::Probe(const Options& opt)
93 : tracer(opt.tracer), ds(heap) {
94 tracer.engine(SearchTracer::EngineType::LDS, 1U);
95 tracer.worker();
96 }
97
98 template<class Tracer>
99 forceinline void
100 Probe<Tracer>::init(Space* s) {
101 cur = s; d = 0U; exhausted = true;
102 if (tracer)
103 tracer.ei()->invalidate();
104 }
105
106 template<class Tracer>
107 forceinline void
108 Probe<Tracer>::reset(Space* s, unsigned int d0) {
109 tracer.round();
110 delete cur;
111 while (!ds.empty())
112 delete ds.pop().space();
113 cur = s; d = d0; exhausted = true;
114 if (tracer)
115 tracer.ei()->invalidate();
116 Worker::reset(0);
117 }
118
119 template<class Tracer>
120 forceinline Statistics
121 Probe<Tracer>::statistics(void) const {
122 return *this;
123 }
124
125 template<class Tracer>
126 forceinline bool
127 Probe<Tracer>::done(void) const {
128 return exhausted;
129 }
130
131 template<class Tracer>
132 forceinline
133 Probe<Tracer>::~Probe(void) {
134 tracer.done();
135 delete cur;
136 while (!ds.empty())
137 delete ds.pop().space();
138 }
139
140 template<class Tracer>
141 forceinline Space*
142 Probe<Tracer>::next(const Options& opt) {
143 start();
144 while (true) {
145 if (cur == nullptr) {
146 backtrack:
147 if (ds.empty())
148 return nullptr;
149 if (stop(opt))
150 return nullptr;
151 unsigned int a = ds.top().alt();
152 const Choice* ch = ds.top().choice();
153 unsigned int nid = ds.top().nid();
154 if (a == 0) {
155 cur = ds.pop().space();
156 if (tracer)
157 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
158 cur->commit(*ch,0);
159 delete ch;
160 } else {
161 ds.top().next();
162 cur = ds.top().space()->clone();
163 if (tracer)
164 tracer.ei()->init(tracer.wid(), nid, a, *cur, *ch);
165 cur->commit(*ch,a);
166 }
167 node++;
168 d++;
169 }
170 check_discrepancy:
171 if (d == 0) {
172 Space* s = cur;
173 while (s->status(*this) == SS_BRANCH) {
174 if (stop(opt)) {
175 cur = s;
176 return nullptr;
177 }
178 const Choice* ch = s->choice();
179 if (ch->alternatives() > 1)
180 exhausted = false;
181 if (tracer) {
182 unsigned int nid = tracer.nid();
183 SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
184 tracer.wid(), nid, *s, ch);
185 tracer.node(*tracer.ei(),ni);
186 if (tracer)
187 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
188 }
189 s->commit(*ch,0);
190 node++;
191 delete ch;
192 }
193 cur = nullptr;
194 if (s->failed()) {
195 if (tracer) {
196 SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
197 tracer.wid(), tracer.nid(), *s);
198 tracer.node(*tracer.ei(),ni);
199 }
200 fail++;
201 delete s;
202 goto backtrack;
203 } else {
204 if (tracer) {
205 SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
206 tracer.wid(), tracer.nid(), *s);
207 tracer.node(*tracer.ei(),ni);
208 }
209 // Deletes all pending branchings
210 (void) s->choice();
211 return s;
212 }
213 } else {
214 node++;
215 switch (cur->status(*this)) {
216 case SS_FAILED:
217 if (tracer) {
218 SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
219 tracer.wid(), tracer.nid(), *cur);
220 tracer.node(*tracer.ei(),ni);
221 }
222 fail++;
223 delete cur;
224 cur = nullptr;
225 goto backtrack;
226 case SS_SOLVED:
227 if (tracer) {
228 tracer.skip(*tracer.ei());
229 }
230 delete cur;
231 cur = nullptr;
232 goto backtrack;
233 case SS_BRANCH:
234 {
235 const Choice* ch = cur->choice();
236 unsigned int alt = ch->alternatives();
237 unsigned int nid = tracer.nid();
238 if (tracer) {
239 SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
240 tracer.wid(), nid, *cur, ch);
241 tracer.node(*tracer.ei(),ni);
242 }
243 if (alt > 1) {
244 if (d < alt-1)
245 exhausted = false;
246 unsigned int d_a = (d >= alt-1) ? alt-1 : d;
247 Space* cc = cur->clone();
248 Node sn(cc,ch,d_a-1,nid);
249 ds.push(sn);
250 stack_depth(static_cast<unsigned long int>(ds.entries()));
251 if (tracer)
252 tracer.ei()->init(tracer.wid(), nid, d_a, *cur, *ch);
253 cur->commit(*ch,d_a);
254 d -= d_a;
255 } else {
256 if (tracer)
257 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
258 cur->commit(*ch,0);
259 node++;
260 delete ch;
261 }
262 goto check_discrepancy;
263 }
264 default: GECODE_NEVER;
265 }
266 }
267 }
268 }
269
270 template<class Tracer>
271 forceinline
272 LDS<Tracer>::LDS(Space* s, const Options& o)
273 : opt(o), e(opt), root(nullptr), d(0) {
274 e.node = 1;
275 if (s->status(e) == SS_FAILED) {
276 e.fail++;
277 e.init(nullptr);
278 } else {
279 Space* c = snapshot(s,opt);
280 if (opt.d_l > 0) {
281 root = c->clone();
282 }
283 e.init(c);
284 }
285 }
286
287 template<class Tracer>
288 Space*
289 LDS<Tracer>::next(void) {
290 while (true) {
291 Space* s = e.next(opt);
292 if (s != nullptr)
293 return s;
294 if (((s == nullptr) && e.stopped()) || (++d > opt.d_l) || e.done())
295 break;
296 if (d == opt.d_l) {
297 if (root != nullptr)
298 e.reset(root,d);
299 root = nullptr;
300 } else if (root != nullptr) {
301 e.reset(root->clone(),d);
302 }
303 }
304 return nullptr;
305 }
306
307 template<class Tracer>
308 bool
309 LDS<Tracer>::stopped(void) const {
310 return e.stopped();
311 }
312
313 template<class Tracer>
314 Statistics
315 LDS<Tracer>::statistics(void) const {
316 return e.statistics();
317 }
318
319
320 template<class Tracer>
321 forceinline void
322 LDS<Tracer>::reset(Space* s) {
323 delete root; root=nullptr; d=0;
324 e.node = 1;
325 if ((s == nullptr) || (s->status(e) == SS_FAILED)) {
326 delete s;
327 e.fail++;
328 e.reset(nullptr,0);
329 } else {
330 if (opt.d_l > 0) {
331 root = s->clone();
332 }
333 e.reset(s,0);
334 }
335 }
336
337 template<class Tracer>
338 forceinline void
339 LDS<Tracer>::constrain(const Space& b) {
340 (void) b;
341 assert(false);
342 }
343
344 template<class Tracer>
345 LDS<Tracer>::~LDS(void) {
346 delete root;
347 }
348
349}}}
350
351// STATISTICS: search-seq