42 namespace Gecode {
namespace Int {
namespace Sequence {
84 template<
class View,
class Val,
bool iss>
96 bool violated(
int j,
int q,
int l,
int u)
const;
105 bool conlusion_scheduled(
void)
const;
109 int values(
int j,
int q)
const;
111 bool shaved(
const View& x, Val s,
int i)
const;
119 bool alternative_not_possible(
ViewArray<View>& a,Val s,
int i,
int idx)
const;
121 bool has_potential_violation(
void)
const;
123 int next_potential_violation(
void);
125 void potential_violation(
int i);
127 void set(
int idx,
int v,
int q,
int n);
129 void potential_violation(
int idx,
int q,
int n);
137 template<
class View,
class Val,
bool iss>
143 template<
class View,
class Val,
bool iss>
149 template<
class View,
class Val,
bool iss>
151 ViewValSupport<View,Val,iss>::next_potential_violation(
void) {
152 return static_cast<int>(
v.get());
155 template<
class View,
class Val,
bool iss>
157 ViewValSupport<View,Val,iss>::potential_violation(
int k) {
158 v.add(static_cast<unsigned int>(k));
162 template<
class View,
class Val,
bool iss>
168 template<
class View,
class Val,
bool iss>
174 template<
class View,
class Val,
bool iss>
176 ViewValSupport<View,Val,iss>::alternative_not_possible
179 return includes(a[idx-1],s) || (iss && (idx-1 ==
i));
182 template<
class View,
class Val,
bool iss>
184 ViewValSupport<View,Val,iss>::s_not_possible
187 return excludes(a[idx-1],s) || (!iss && (i == idx-1));
191 template<
class View,
class Val,
bool iss>
196 v.init(home,static_cast<unsigned int>(a.
size()));
198 for (
int l=0;
l<a.
size();
l++ ) {
199 if ( alternative_not_possible(a,s,i,
l+1) ) {
205 potential_violation(
l+1-q);
207 if (
l <= a.
size() - q ) {
208 potential_violation(
l);
214 template<
class View,
class Val,
bool iss>
221 y = home.
alloc<
int>(n0);
222 for (
int l=0;
l<n0;
l++ ) {
225 v.update(home,share,vvs.v);
230 template<
class View,
class Val,
bool iss>
239 template<
class View,
class Val,
bool iss>
241 ViewValSupport<View,Val,iss>::schedule_conclusion(
ViewArray<View>&
a, Val s,
247 potential_violation(0);
253 template<
class View,
class Val,
bool iss>
255 ViewValSupport<View,Val,iss>::conlusion_scheduled(
void)
const {
256 return !retired() && y[0] > 0;
259 template<
class View,
class Val,
bool iss>
265 template<
class View,
class Val,
bool iss>
271 template<
class View,
class Val,
bool iss>
286 template<
class View,
class Val,
bool iss>
288 ViewValSupport<View,Val,iss>::potential_violation(
int idx,
int q,
int n) {
290 potential_violation(idx-q);
292 if ( idx <= n - q - 1) {
293 potential_violation(idx);
297 template<
class View,
class Val,
bool iss>
299 ViewValSupport<View,Val,iss>::set(
int idx,
int v,
int q,
int n) {
303 potential_violation(idx,q,n);
307 template<
class View,
class Val,
bool iss>
309 ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,
int i,
int q,
int idx,
int v) {
311 int n = a.size() + 1;
313 set(idx,y[idx]+
v,q,
n);
315 if ( y[idx] > idx ) {
322 while ( idx > 0 && ((y[idx]-y[idx-1]>1) || ((y[idx]-y[idx-1]==1 && s_not_possible(a,s,i,idx)))) ) {
323 if ( s_not_possible(a,s,i,idx) ) {
324 set(idx-1,y[idx],q,
n);
326 set(idx-1,y[idx]-1,q,
n);
328 if ( y[idx-1]>idx-1 ) {
337 while ( idx < a.size() && ((y[idx]-y[idx+1]>0) || ((y[idx]-y[idx+1]==0) && alternative_not_possible(a,s,i,idx+1))) ) {
338 if ( alternative_not_possible(a,s,i,idx+1) ) {
339 set(idx+1,y[idx]+1,q,
n);
341 set(idx+1,y[idx],q,
n);
350 template<
class View,
class Val,
bool iss>
353 Val s,
int i,
int q,
int j,
357 if ((j == i) && shaved(a[j],s,j)) {
360 switch (
takes(a[j],s)) {
362 if (y[j+1]-y[j] == 0) {
363 if (!pushup(a,s,i,q,j+1,1)) {
369 if (y[j+1]-y[j] > 0) {
370 if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
381 if ( has_potential_violation() )
389 template<
class View,
class Val,
bool iss>
393 if ( conlusion_scheduled() ) {
394 return conclude(home,a,s,i);
397 while (has_potential_violation()) {
398 int j = next_potential_violation();
399 if (violated(j,q,l,u)) {
400 int forced_to_s =
values(j,q);
401 if (forced_to_s < l) {
402 if (!pushup(a,s,i,q,j+q,l-forced_to_s))
403 return conclude(home,a,s,i);
405 if (!pushup(a,s,i,q,j,forced_to_s-u))
406 return conclude(home,a,s,i);
408 if (violated(j,q,l,u))
409 return conclude(home,a,s,i);
416 template<
class View,
class Val,
bool iss>
420 template<
class View,
class Val,
bool iss>
425 template<
class View,
class Val,
bool iss>
430 for (
int i = n; i--; ) {
431 xs[
i].init(home,x,s,i,q);
436 template<
class View,
class Val,
bool iss>
444 template<
class View,
class Val,
bool iss>
450 template<
class View,
class Val,
bool iss>
453 assert((i >= 0) && (i <
size()));
457 template<
class View,
class Val,
bool iss>
460 assert((i >= 0) && (i <
size()));
464 template<
class View,
class Val,
bool iss>
470 for (
int i=n; i--; ) {
471 xs[
i].update(home,share,a[i],n+1);
476 template<
class View,
class Val,
bool iss>
479 for (
int i=n; i--; ) {
485 template<
class View,
class Val,
bool iss>
489 for (
int i=n; i--; ) {
490 if (
ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )