this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * David Rijsman <David.Rijsman@quintiq.com>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 *
9 * Copyright:
10 * David Rijsman, 2009
11 * Christian Schulte, 2009
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
38namespace Gecode { namespace Int { namespace Sequence {
39
40 /**
41 * \brief Class for advising the propagator
42 */
43 template<class View>
44 class SupportAdvisor : public Advisor {
45 public:
46 /// Index position
47 int i;
48 /// Initialize
49 SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
50 int i0);
51 /// Copy during cloning
52 SupportAdvisor(Space& home, SupportAdvisor& a);
53 /// Dispose advisor
54 void dispose(Space& home, Council<SupportAdvisor>& c);
55 };
56
57 template<class View>
58 forceinline
59 SupportAdvisor<View>::SupportAdvisor(Space& home, Propagator& p,
60 Council<SupportAdvisor>& c,int i0)
61 : Advisor(home,p,c), i(i0) {
62 }
63
64 template<class View>
65 forceinline
66 SupportAdvisor<View>::SupportAdvisor(Space& home, SupportAdvisor& a)
67 : Advisor(home,a), i(a.i) {
68 }
69
70 template<class View>
71 forceinline void
72 SupportAdvisor<View>::dispose(Space& home, Council<SupportAdvisor>& c) {
73 Advisor::dispose(home,c);
74 }
75
76 /**
77 * \brief Class for view value support structure
78 */
79 template<class View, class Val, bool iss>
80 class ViewValSupport {
81 public:
82 /// Initialize
83 void init(Space& home, ViewArray<View>& x,Val s, int i, int q);
84 /// Update
85 void update(Space& home, ViewValSupport<View,Val,iss>& vvs, int n0);
86 /// Advise
87 ExecStatus advise(Space& home,ViewArray<View>& a,Val s,int i,int q, int j,const Delta& d);
88 /// Propagate
89 ExecStatus propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u);
90 /// Return true if sequence j has been violated
91 bool violated(int j, int q, int l, int u) const;
92 /// Check if retired
93 bool retired(void) const;
94 /// Allocate an instance
95 static ViewValSupport* allocate(Space&,int);
96 private:
97 /// Schedules the invoking support to be concluded (to be shaved)
98 ExecStatus schedule_conclusion(ViewArray<View>& a,Val s,int i);
99 /// Returns true if a conclusion to be made has been scheduled
100 bool conlusion_scheduled(void) const;
101 /// Retires invoking instance
102 void retire(void);
103 /// Return number of forced to s elements in sequence j
104 int values(int j, int q) const;
105 /// Checks if x[i] has been shaved
106 bool shaved(const View& x, Val s, int i) const;
107 /// Push up the cumulative array
108 bool pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v);
109 /// Make conclusion
110 ExecStatus conclude(Space& home,ViewArray<View>& a,Val s,int i);
111 /// Returns true if a[idx]=s not possible taking into account a[i]=s if iss or a[i]!=s if ! iss
112 bool s_not_possible(ViewArray<View>& a, Val s, int i, int idx) const;
113 /// Returns true if a[idx] can be not s taking into account a[i]=s if iss or a[i]!=s if ! iss
114 bool alternative_not_possible(ViewArray<View>& a,Val s,int i, int idx) const;
115 /// Returns true if there are potential violations marked
116 bool has_potential_violation(void) const;
117 /// Returns next potential violation and removes it
118 int next_potential_violation(void);
119 /// Adds potential violation i
120 void potential_violation(int i);
121 // Sets element idx of cumulative array to v
122 void set(int idx, int v, int q, int n);
123 /// Adds potential violations for location idx in cumulative array
124 void potential_violation(int idx, int q, int n);
125 /// Cumulative array
126 int* y;
127 /// Potential violation set
128 Violations v;
129 };
130
131
132 template<class View, class Val, bool iss>
133 forceinline ViewValSupport<View,Val,iss>*
134 ViewValSupport<View,Val,iss>::allocate(Space& home, int n) {
135 return home.alloc<ViewValSupport<View,Val,iss> >(n);
136 }
137
138 template<class View, class Val, bool iss>
139 forceinline bool
140 ViewValSupport<View,Val,iss>::has_potential_violation(void) const {
141 return !v.empty();
142 }
143
144 template<class View, class Val, bool iss>
145 forceinline int
146 ViewValSupport<View,Val,iss>::next_potential_violation(void) {
147 return static_cast<int>(v.get());
148 }
149
150 template<class View, class Val, bool iss>
151 forceinline void
152 ViewValSupport<View,Val,iss>::potential_violation(int k) {
153 v.add(static_cast<unsigned int>(k));
154 }
155
156
157 template<class View, class Val, bool iss>
158 forceinline bool
159 ViewValSupport<View,Val,iss>::retired(void) const {
160 return nullptr == y;
161 }
162
163 template<class View, class Val, bool iss>
164 forceinline void
165 ViewValSupport<View,Val,iss>::retire(void) {
166 y = nullptr;
167 }
168
169 template<class View,class Val, bool iss>
170 forceinline bool
171 ViewValSupport<View,Val,iss>::alternative_not_possible
172 (ViewArray<View>& a, Val s, int i, int idx) const {
173 (void) i;
174 return includes(a[idx-1],s) || (iss && (idx-1 == i));
175 }
176
177 template<class View, class Val, bool iss>
178 forceinline bool
179 ViewValSupport<View,Val,iss>::s_not_possible
180 (ViewArray<View>& a, Val s, int i, int idx) const {
181 (void) i;
182 return excludes(a[idx-1],s) || (!iss && (i == idx-1));
183 }
184
185
186 template<class View, class Val, bool iss>
187 forceinline void
188 ViewValSupport<View,Val,iss>::init(Space& home, ViewArray<View>& a, Val s,
189 int i, int q) {
190 y = home.alloc<int>(a.size()+1);
191 v.init(home,static_cast<unsigned int>(a.size()));
192 y[0] = 0;
193 for ( int l=0; l<a.size(); l++ ) {
194 if ( alternative_not_possible(a,s,i,l+1) ) {
195 y[l+1] = y[l] + 1;
196 } else {
197 y[l+1] = y[l];
198 }
199 if ( l+1 >= q ) {
200 potential_violation(l+1-q);
201 }
202 if ( l <= a.size() - q ) {
203 potential_violation(l);
204 }
205
206 }
207 }
208
209 template<class View, class Val, bool iss>
210 forceinline void
211 ViewValSupport<View,Val,iss>::update(Space& home,
212 ViewValSupport<View,Val,iss>& vvs,
213 int n0) {
214 y = nullptr;
215 if ( !vvs.retired() ) {
216 y = home.alloc<int>(n0);
217 for ( int l=0; l<n0; l++ ) {
218 y[l] = vvs.y[l];
219 }
220 v.update(home,vvs.v);
221 // = &home.construct<S>(S::key_compare(),S::allocator_type(home));
222 }
223 }
224
225 template<class View,class Val, bool iss>
226 forceinline bool
227 ViewValSupport<View,Val,iss>::shaved(const View& x, Val s, int) const {
228 if (iss)
229 return excludes(x,s);
230 else
231 return includes(x,s);
232 }
233
234 template<class View,class Val, bool iss>
235 forceinline ExecStatus
236 ViewValSupport<View,Val,iss>::schedule_conclusion(ViewArray<View>& a, Val s,
237 int i) {
238 if (!retired()) {
239 if ((iss && includes(a[i],s)) || (!iss && excludes(a[i],s)))
240 return ES_FAILED;
241 y[0] = 1;
242 potential_violation(0);
243 }
244
245 return ES_OK;
246 }
247
248 template<class View,class Val, bool iss>
249 forceinline bool
250 ViewValSupport<View,Val,iss>::conlusion_scheduled(void) const {
251 return !retired() && y[0] > 0;
252 }
253
254 template<class View,class Val, bool iss>
255 forceinline int
256 ViewValSupport<View,Val,iss>::values(int j, int q) const {
257 return y[j+q]-y[j];
258 }
259
260 template<class View,class Val,bool iss>
261 forceinline bool
262 ViewValSupport<View,Val,iss>::violated(int j, int q, int l, int u) const {
263 return values(j,q) < l || values(j,q) > u;
264 }
265
266 template<class View,class Val,bool iss>
267 forceinline ExecStatus
268 ViewValSupport<View,Val,iss>::conclude(Space& home,ViewArray<View>& a,
269 Val s, int i) {
270 if ( iss ) {
271 GECODE_ME_CHECK(exclude(home,a[i],s));
272 } else {
273 GECODE_ME_CHECK(include(home,a[i],s));
274 }
275
276 retire();
277
278 return ES_OK;
279 }
280
281 template<class View,class Val,bool iss>
282 forceinline void
283 ViewValSupport<View,Val,iss>::potential_violation(int idx, int q, int n) {
284 if ( idx >= q ) {
285 potential_violation(idx-q);
286 }
287 if ( idx <= n - q - 1) {
288 potential_violation(idx);
289 }
290 }
291
292 template<class View,class Val,bool iss>
293 forceinline void
294 ViewValSupport<View,Val,iss>::set(int idx, int v, int q, int n) {
295 assert(y[idx]<=v);
296 if ( y[idx] < v ) {
297 y[idx] = v;
298 potential_violation(idx,q,n);
299 }
300 }
301
302 template<class View,class Val,bool iss>
303 forceinline bool
304 ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v) {
305 if ( !retired() ) {
306 int n = a.size() + 1;
307
308 set(idx,y[idx]+v,q,n);
309
310 if ( y[idx] > idx ) {
311 return false;
312 }
313
314 int t = idx;
315
316 // repair y on the left
317 while ( idx > 0 && ((y[idx]-y[idx-1]>1) || ((y[idx]-y[idx-1]==1 && s_not_possible(a,s,i,idx)))) ) {
318 if ( s_not_possible(a,s,i,idx) ) {
319 set(idx-1,y[idx],q,n);
320 } else {
321 set(idx-1,y[idx]-1,q,n);
322 }
323 if ( y[idx-1]>idx-1 ) {
324 return false;
325 }
326 idx -= 1;
327 }
328
329 idx = t;
330
331 // repair y on the right
332 while ( idx < a.size() && ((y[idx]-y[idx+1]>0) || ((y[idx]-y[idx+1]==0) && alternative_not_possible(a,s,i,idx+1))) ) {
333 if ( alternative_not_possible(a,s,i,idx+1) ) {
334 set(idx+1,y[idx]+1,q,n);
335 } else {
336 set(idx+1,y[idx],q,n);
337 }
338 idx += 1;
339 }
340 }
341
342 return true;
343 }
344
345 template<class View,class Val,bool iss>
346 forceinline ExecStatus
347 ViewValSupport<View,Val,iss>::advise(Space&, ViewArray<View>& a,
348 Val s,int i,int q, int j,
349 const Delta&) {
350 ExecStatus status = ES_FIX;
351 if (!retired()) {
352 if ((j == i) && shaved(a[j],s,j)) {
353 retire();
354 } else {
355 switch (takes(a[j],s)) {
356 case TS_YES:
357 if (y[j+1]-y[j] == 0) {
358 if (!pushup(a,s,i,q,j+1,1)) {
359 GECODE_ES_CHECK(schedule_conclusion(a,s,i));
360 }
361 }
362 break;
363 case TS_NO:
364 if (y[j+1]-y[j] > 0) {
365 if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
366 GECODE_ES_CHECK(schedule_conclusion(a,s,i));
367 }
368 }
369 break;
370 case TS_MAYBE:
371 break;
372 default:
373 GECODE_NEVER;
374 }
375
376 if ( has_potential_violation() )
377 status = ES_NOFIX;
378 }
379 }
380
381 return status;
382 }
383
384 template<class View,class Val,bool iss>
385 forceinline ExecStatus
386 ViewValSupport<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u) {
387 if ( !retired() ) {
388 if ( conlusion_scheduled() ) {
389 return conclude(home,a,s,i);
390 }
391
392 while (has_potential_violation()) {
393 int j = next_potential_violation();
394 if (violated(j,q,l,u)) {
395 int forced_to_s = values(j,q);
396 if (forced_to_s < l) {
397 if (!pushup(a,s,i,q,j+q,l-forced_to_s))
398 return conclude(home,a,s,i);
399 } else {
400 if (!pushup(a,s,i,q,j,forced_to_s-u))
401 return conclude(home,a,s,i);
402 }
403 if (violated(j,q,l,u))
404 return conclude(home,a,s,i);
405 }
406 }
407 }
408 return ES_OK;
409 }
410
411 template<class View,class Val,bool iss>
412 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(void) : xs(nullptr), n(0) {
413 }
414
415 template<class View,class Val,bool iss>
416 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(const ViewValSupportArray<View,Val,iss>& a) {
417 n = a.n; xs = a.xs;
418 }
419
420 template<class View,class Val,bool iss>
421 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home,ViewArray<View>& x, Val s, int q) : xs(nullptr) {
422 n = x.size();
423 if ( n > 0 ) {
424 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
425 for (int i = n; i--; ) {
426 xs[i].init(home,x,s,i,q);
427 }
428 }
429 }
430
431 template<class View,class Val,bool iss>
432 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home, int n0) : xs(nullptr) {
433 n = n0;
434 if (n>0) {
435 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
436 }
437 }
438
439 template<class View,class Val,bool iss>
440 forceinline int
441 ViewValSupportArray<View,Val,iss>::size(void) const {
442 return n;
443 }
444
445 template<class View,class Val,bool iss>
446 forceinline ViewValSupport<View,Val,iss>&
447 ViewValSupportArray<View,Val,iss>::operator [](int i) {
448 assert((i >= 0) && (i < size()));
449 return xs[i];
450 }
451
452 template<class View,class Val,bool iss>
453 forceinline const ViewValSupport<View,Val,iss>&
454 ViewValSupportArray<View,Val,iss>::operator [](int i) const {
455 assert((i >= 0) && (i < size()));
456 return xs[i];
457 }
458
459 template<class View,class Val,bool iss>
460 void
461 ViewValSupportArray<View,Val,iss>::update(Space& home, ViewValSupportArray<View,Val,iss>& a) {
462 n = a.size();
463 if (n>0) {
464 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
465 for (int i=n; i--; ) {
466 xs[i].update(home,a[i],n+1);
467 }
468 }
469 }
470
471 template<class View,class Val,bool iss>
472 ExecStatus
473 ViewValSupportArray<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int q,int l,int u) {
474 for (int i=n; i--; ) {
475 GECODE_ES_CHECK(xs[i].propagate(home,a,s,i,q,l,u));
476 }
477 return ES_OK;
478 }
479
480 template<class View,class Val,bool iss>
481 ExecStatus
482 ViewValSupportArray<View,Val,iss>::advise(Space& home,ViewArray<View>& a,Val s,int q,int j,const Delta& d) {
483 ExecStatus status = ES_FIX;
484 for (int i=n; i--; ) {
485 if ( ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
486 status = ES_NOFIX;
487 }
488 return status;
489 }
490}}}
491
492
493// STATISTICS: int-prop
494