Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
view.hpp
Go to the documentation of this file.
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
43 template<class View>
44 class SupportAdvisor : public Advisor {
45 public:
47 int i;
50 int i0);
55 };
56
57 template<class View>
61 : Advisor(home,p,c), i(i0) {
62 }
63
64 template<class View>
69
70 template<class View>
71 forceinline void
74 }
75
79 template<class View, class Val, bool iss>
81 public:
83 void init(Space& home, ViewArray<View>& x,Val s, int i, int q);
85 void update(Space& home, ViewValSupport<View,Val,iss>& vvs, int n0);
87 ExecStatus advise(Space& home,ViewArray<View>& a,Val s,int i,int q, int j,const Delta& d);
89 ExecStatus propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u);
91 bool violated(int j, int q, int l, int u) const;
93 bool retired(void) const;
96 private:
98 ExecStatus schedule_conclusion(ViewArray<View>& a,Val s,int i);
100 bool conlusion_scheduled(void) const;
102 void retire(void);
104 int values(int j, int q) const;
106 bool shaved(const View& x, Val s, int i) const;
108 bool pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v);
110 ExecStatus conclude(Space& home,ViewArray<View>& a,Val s,int i);
112 bool s_not_possible(ViewArray<View>& a, Val s, int i, int idx) const;
114 bool alternative_not_possible(ViewArray<View>& a,Val s,int i, int idx) const;
116 bool has_potential_violation(void) const;
118 int next_potential_violation(void);
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);
124 void potential_violation(int idx, int q, int n);
126 int* y;
128 Violations v;
129 };
130
131
132 template<class View, class Val, bool iss>
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
160 return NULL == y;
161 }
162
163 template<class View, class Val, bool iss>
164 forceinline void
165 ViewValSupport<View,Val,iss>::retire(void) {
166 y = NULL;
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
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
213 int n0) {
214 y = NULL;
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>
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>
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>
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:
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>
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>
414
415 template<class View,class Val,bool iss>
419
420 template<class View,class Val,bool iss>
422 n = x.size();
423 if ( n > 0 ) {
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>
433 n = n0;
434 if (n>0) {
436 }
437 }
438
439 template<class View,class Val,bool iss>
440 forceinline int
442 return n;
443 }
444
445 template<class View,class Val,bool iss>
448 assert((i >= 0) && (i < size()));
449 return xs[i];
450 }
451
452 template<class View,class Val,bool iss>
455 assert((i >= 0) && (i < size()));
456 return xs[i];
457 }
458
459 template<class View,class Val,bool iss>
460 void
462 n = a.size();
463 if (n>0) {
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>
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>
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
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:3838
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition core.hpp:3871
friend class Council
Definition core.hpp:1296
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
SupportAdvisor(Space &home, Propagator &p, Council< SupportAdvisor > &c, int i0)
Initialize.
Definition view.hpp:59
void dispose(Space &home, Council< SupportAdvisor > &c)
Dispose advisor.
Definition view.hpp:72
ViewValSupportArray(void)
Default constructor.
Definition view.hpp:412
void update(Space &home, ViewValSupportArray< View, Val, iss > &x)
Cloning.
Definition view.hpp:461
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int q, int j, const Delta &d)
Advise.
Definition view.hpp:482
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int q, int l, int u)
Propagate.
Definition view.hpp:473
int size(void) const
Return the current size.
Definition view.hpp:441
ViewValSupport< View, Val, iss > & operator[](int n)
Access element n.
Definition view.hpp:447
Class for view value support structure.
Definition view.hpp:80
static ViewValSupport * allocate(Space &, int)
Allocate an instance.
Definition view.hpp:134
void update(Space &home, ViewValSupport< View, Val, iss > &vvs, int n0)
Update.
Definition view.hpp:211
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int i, int q, int l, int u)
Propagate.
Definition view.hpp:386
bool violated(int j, int q, int l, int u) const
Return true if sequence j has been violated.
Definition view.hpp:262
void init(Space &home, ViewArray< View > &x, Val s, int i, int q)
Initialize.
Definition view.hpp:188
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int i, int q, int j, const Delta &d)
Advise.
Definition view.hpp:347
bool retired(void) const
Check if retired.
Definition view.hpp:159
Simple bitsets for recording violations.
Computation spaces.
Definition core.hpp:1744
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
View arrays.
Definition array.hpp:253
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Sequence propagators
Definition sequence.hh:40
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition set-op.hpp:137
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
Definition set-op.hpp:89
@ TS_MAYBE
Maybe or maybe not.
Definition set-op.hpp:40
@ TS_NO
Definitely not.
Definition set-op.hpp:38
@ TS_YES
Definitely yes.
Definition set-op.hpp:39
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
Definition set-op.hpp:72
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
Definition set-op.hpp:123
TakesStatus takes(const View &x, int s)
Return whether view x takes value s.
Definition set-op.hpp:46
Finite domain integers.
Gecode toplevel namespace
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Post propagator for SetVar x
Definition set.hh:773
Gecode::FloatVal a(-8, 5)
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56