Generated on for Gecode by doxygen 1.17.0
open.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
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#ifndef GECODE_INT_SEQUENCE_OPEN_HPP
35#define GECODE_INT_SEQUENCE_OPEN_HPP
36
39#include <gecode/int/linear.hh>
40#include <gecode/int/rel.hh>
41
42#include <algorithm>
43
44namespace Gecode { namespace Int { namespace Sequence {
45
47 class OpenWindowAdvisor : public Advisor {
48 public:
49 int index;
50
52 Council<OpenWindowAdvisor>& council, int index0)
53 : Advisor(home,p,council), index(index0) {}
54
57
58 void
60 Advisor::dispose(home,council);
61 }
62 };
63
65 template<class View>
67 protected:
70
71 int width;
73 int first;
74 int last;
76
78 : OpenListPropagator<View>(home,list), width(width0),
79 first(Int::Limits::max), last(-1), council(home) {}
80
82 : OpenListPropagator<View>(home,p), width(p.width),
83 first(p.first), last(p.last), council(home) {
84 council.update(home,p.council);
85 }
86
87 void
88 changed(int index) {
89 first = std::min(first,std::max(0,index-width+1));
90 last = std::max(last,std::min(index,list.known_length()-width));
91 }
92
93 void
95 if ((size > processed) && (size >= width)) {
96 first = std::min(first,std::max(0,processed-width+1));
97 last = size-width;
98 }
100 }
101
102 void
103 subscribe(Space& home, int index) {
104 View x(list[index]);
105 x.subscribe(home,*new (home)
106 OpenWindowAdvisor(home,*this,council,index));
107 }
108
109 void
111 if (!home.failed())
112 for (Advisors<OpenWindowAdvisor> a(council); a(); ++a) {
113 View x(list[a.advisor().index]);
114 if (!x.assigned())
115 x.cancel(home,a.advisor());
116 }
117 council.dispose(home);
119 }
120
121 public:
122 virtual PropCost
123 cost(const Space&, const ModEventDelta&) const {
124 return PropCost::linear(PropCost::HI,list.known_length());
125 }
126
127 virtual void
130 first = 0;
131 last = list.known_length()-width;
132 View::schedule(home,*this,ME_INT_DOM);
133 }
134 };
135
136
138 template<class View>
139 class Open : public OpenWindowPropagator<View> {
140 protected:
152
154 int lower;
155 int upper;
156
158 const IntSet& values0, int width0,
159 int lower0, int upper0)
160 : OpenWindowPropagator<View>(home,list,width0), values(values0),
161 lower(lower0), upper(upper0) {
162 home.notice(*this,AP_DISPOSE);
163 }
164
165 Open(Space& home, Open& p)
166 : OpenWindowPropagator<View>(home,p), values(p.values),
167 lower(p.lower), upper(p.upper) {}
168
169 public:
170 virtual Actor*
171 copy(Space& home) {
172 return new (home) Open(home,*this);
173 }
174
175 virtual ExecStatus
176 advise(Space& home, Advisor& advisor, const Delta&) {
177 OpenWindowAdvisor& a = static_cast<OpenWindowAdvisor&>(advisor);
178 View x(list[a.index]);
179 if (undecided(x,values))
180 return ES_FIX;
181 changed(a.index);
182 if (!x.assigned())
183 x.cancel(home,a);
184 return home.ES_NOFIX_DISPOSE(council,a);
185 }
186
187 virtual ExecStatus
189 const int size = list.known_length();
190 for (int i=processed; i<size; i++)
191 if (undecided(list[i],values))
192 subscribe(home,i);
193 appended(size);
194
195 if (first <= last) {
196 const int begin = first;
197 const int end = last;
199 last = -1;
200 Region region;
201 const int n = end-begin+width;
202 TakesStatus* status = region.alloc<TakesStatus>(n);
203 for (int i=0; i<n; i++)
204 status[i] = takes(list[begin+i],values);
205 int must = 0;
206 int may = 0;
207 for (int i=0; i<width; i++) {
208 must += status[i] == TS_YES;
209 may += status[i] != TS_NO;
210 }
211 // Track the furthest end of each kind of forcing window so overlapping
212 // windows apply each membership update once.
213 int include_end = 0;
214 int exclude_end = 0;
215 for (int i=0; i<n; i++) {
216 if (i <= end-begin) {
217 if ((must > upper) || (may < lower))
218 return ES_FAILED;
219 if (must == upper)
220 exclude_end = i+width;
221 if (may == lower)
222 include_end = i+width;
223 if (i < end-begin) {
224 must -= status[i] == TS_YES;
225 may -= status[i] != TS_NO;
226 must += status[i+width] == TS_YES;
227 may += status[i+width] != TS_NO;
228 }
229 }
230 if (status[i] == TS_MAYBE) {
231 if ((i < include_end) && (i < exclude_end))
232 return ES_FAILED;
233 View x(list[begin+i]);
234 if (i < exclude_end)
236 else if (i < include_end)
238 }
239 }
240 }
241 if (first <= last)
242 return ES_NOFIX;
243 return closed() && ((size < width) || council.empty()) ?
244 home.ES_SUBSUMED(*this) : ES_FIX;
245 }
246
247 virtual size_t
248 dispose(Space& home) {
249 home.ignore(*this,AP_DISPOSE);
250 values.~IntSet();
251 dispose_windows(home);
252 return sizeof(*this);
253 }
254
255 static void
257 int width, int lower, int upper, IntPropLevel) {
258 (void) new (home)
260 }
261 };
262
263
265 template<class View>
267 protected:
271
272 int width;
273 int sum;
275
277 int width0, int sum0, IntPropLevel ipl0)
279 width(width0), sum(sum0), ipl(ipl0) {
280 // Choose the default from the full window, before linear posting
281 // eliminates assigned terms. Delayed posting then has the same
282 // propagation strength as posting before those assignments.
283 if (vbd(ipl) == IPL_DEF)
284 ipl = static_cast<IntPropLevel>
285 (ipl | ((width <= 2) ? IPL_DOM : IPL_BND));
286 }
287
289 : OpenListPropagator<View>(home,p),
290 width(p.width), sum(p.sum), ipl(p.ipl) {}
291
292 static void
294 term.a = 1;
295 term.x = x;
296 }
297
298 static void
300 term.a = -1;
301 term.x = x.base();
302 }
303
304 static ExecStatus
305 binary_sum(Home home, IntView x, IntView y, int sum) {
307 (home,MinusView(x),OffsetView(y,-sum));
308 }
309
310 static ExecStatus
312 return binary_sum(home,x.base(),y.base(),-sum);
313 }
314
315 public:
316 virtual Actor*
317 copy(Space& home) {
318 return new (home) OpenSlidingSumEq(home,*this);
319 }
320
321 virtual ExecStatus
323 const int size = list.known_length();
324 if ((processed < width) && (size >= width)) {
325 if (width == 1) {
326 GECODE_ME_CHECK(list[0].eq(home,sum));
327 } else if ((width == 2) && (vbd(ipl) == IPL_DOM)) {
328 View x(list[0]);
329 View y(list[1]);
330 // Clip with wide residuals before constructing y-sum: its
331 // range must fit integer limits. Binary domain filtering then
332 // uses range intersections, even for very large domains.
333 const long long int target = sum;
334 GECODE_ME_CHECK(x.gq(home,target-y.max()));
335 GECODE_ME_CHECK(x.lq(home,target-y.min()));
336 GECODE_ME_CHECK(y.gq(home,target-x.max()));
337 GECODE_ME_CHECK(y.lq(home,target-x.min()));
338 GECODE_ES_CHECK(binary_sum(home(*this),x,y,sum));
339 } else {
340 Region region;
341 Linear::Term<IntView>* terms =
343 for (int i=0; i<width; i++)
344 linear_term(terms[i],list[i]);
345 Linear::post(home(*this),terms,width,IRT_EQ,sum,ipl);
346 if (home.failed())
347 return ES_FAILED;
348 }
349 }
350 // Equal consecutive window sums imply periodic values. One window sum
351 // and these equalities provide the selected propagation level.
352 for (int i=std::max(width,processed); i<size; i++) {
353 View x(list[i]);
354 View representative(list[i%width]);
355 if (vbd(ipl) == IPL_DOM) {
357 (home(*this),x,representative)));
358 } else {
360 (home(*this),x,representative)));
361 }
362 }
363 processed = size;
364 return closed() ? home.ES_SUBSUMED(*this) : ES_FIX;
365 }
366
367 virtual size_t
368 dispose(Space& home) {
370 return sizeof(*this);
371 }
372
373 static void
375 int width, int sum, IntPropLevel ipl) {
376 (void) new (home) OpenSlidingSumEq(home,list,width,sum,ipl);
377 }
378 };
379
380
382 template<class View>
384 protected:
396
397 int lower;
398 int upper;
399
401 int width0, int lower0, int upper0)
402 : OpenWindowPropagator<View>(home,list,width0),
403 lower(lower0), upper(upper0) {}
404
408
409 public:
410 virtual Actor*
411 copy(Space& home) {
412 return new (home) OpenSlidingSumBnd(home,*this);
413 }
414
415 virtual ExecStatus
416 advise(Space& home, Advisor& advisor, const Delta& delta) {
417 if (View::modevent(delta) == ME_INT_DOM)
418 return ES_FIX;
419 OpenWindowAdvisor& a = static_cast<OpenWindowAdvisor&>(advisor);
420 changed(a.index);
421 if (list[a.index].assigned())
422 return home.ES_NOFIX_DISPOSE(council,a);
423 return ES_NOFIX;
424 }
425
426 virtual ExecStatus
428 const int size = list.known_length();
429 for (int i=processed; i<size; i++)
430 if (!list[i].assigned())
431 subscribe(home,i);
432 appended(size);
433
434 if (first <= last) {
435 const int begin = first;
436 const int end = last;
438 last = -1;
439 Region region;
440 const int n = end-begin+width;
441 int* minimum = region.alloc<int>(n);
442 int* maximum = region.alloc<int>(n);
443 for (int i=0; i<n; i++) {
444 minimum[i] = list[begin+i].min();
445 maximum[i] = list[begin+i].max();
446 }
447 // Both width and variable bounds are limited to Int::Limits, so
448 // sums and the residual bounds below fit in long long int.
449 long long int min_sum = 0;
450 long long int max_sum = 0;
451 for (int i=0; i<width; i++) {
452 min_sum += minimum[i];
453 max_sum += maximum[i];
454 }
455 struct Residual {
456 long long int lower;
457 long long int upper;
458 };
459 const int windows = end-begin+1;
460 Residual* residual = region.alloc<Residual>(windows);
461 for (int start=0; start<windows; start++) {
462 if ((min_sum > upper) || (max_sum < lower))
463 return ES_FAILED;
464 residual[start].lower = static_cast<long long int>(lower)-max_sum;
465 residual[start].upper = static_cast<long long int>(upper)-min_sum;
466 if (start+1 < windows) {
467 min_sum -= minimum[start];
468 max_sum -= maximum[start];
469 min_sum += minimum[start+width];
470 max_sum += maximum[start+width];
471 }
472 }
473 // Monotone queues track the strongest residuals among windows
474 // covering each position. Every window enters and leaves once.
475 int* lower_queue = region.alloc<int>(windows);
476 int* upper_queue = region.alloc<int>(windows);
477 int lower_head = 0;
478 int lower_tail = 0;
479 int upper_head = 0;
480 int upper_tail = 0;
481 for (int i=0; i<n; i++) {
482 if ((lower_head < lower_tail) &&
483 (lower_queue[lower_head] <= i-width))
484 lower_head++;
485 if ((upper_head < upper_tail) &&
486 (upper_queue[upper_head] <= i-width))
487 upper_head++;
488 if (i < windows) {
489 while ((lower_head < lower_tail) &&
490 (residual[lower_queue[lower_tail-1]].lower <=
491 residual[i].lower))
492 lower_tail--;
493 lower_queue[lower_tail++] = i;
494 while ((upper_head < upper_tail) &&
495 (residual[upper_queue[upper_tail-1]].upper >=
496 residual[i].upper))
497 upper_tail--;
498 upper_queue[upper_tail++] = i;
499 }
500 View x(list[begin+i]);
501 GECODE_ME_CHECK(x.gq(home,
502 residual[lower_queue[lower_head]].lower+maximum[i]));
503 GECODE_ME_CHECK(x.lq(home,
504 residual[upper_queue[upper_head]].upper+minimum[i]));
505 }
506 }
507 if (first <= last)
508 return ES_NOFIX;
509 return closed() && ((size < width) || council.empty()) ?
510 home.ES_SUBSUMED(*this) : ES_FIX;
511 }
512
513 virtual size_t
514 dispose(Space& home) {
515 dispose_windows(home);
516 return sizeof(*this);
517 }
518
519 static void
521 int width, int lower, int upper) {
522 (void) new (home)
524 }
525 };
526
527
528}}}
529
530#endif
531
532// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:4060
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition core.hpp:4098
friend class Council
Definition core.hpp:1310
Class to iterate over advisors of a council.
Definition core.hpp:1282
Generic domain change information to be supplied to advisors.
Definition core.hpp:209
View base(void) const
Return view from which this view is derived.
Definition view.hpp:605
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
Integer sets.
Definition int.hh:179
Integer view for integer variables.
Definition view.hpp:129
Class for describing linear term .
Definition linear.hh:1336
int a
Coefficient.
Definition linear.hh:1339
Minus integer view.
Definition view.hpp:282
Offset integer view.
Definition view.hpp:443
virtual void reschedule(Space &home)
Schedule function.
OpenListPropagator(Home home, OpenViewList< View > list0)
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition eq.hpp:108
static ExecStatus post(Home home, View0 x0, View1 x1)
Post domain consistent propagator .
Definition eq.hpp:176
OpenSlidingSumBnd(Space &home, OpenSlidingSumBnd &p)
Definition open.hpp:405
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:514
virtual ExecStatus advise(Space &home, Advisor &advisor, const Delta &delta)
Advise function.
Definition open.hpp:416
static void post(Home home, OpenViewList< View > list, int width, int lower, int upper)
Definition open.hpp:520
OpenSlidingSumBnd(Home home, OpenViewList< View > list, int width0, int lower0, int upper0)
Definition open.hpp:400
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:427
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:411
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:322
static ExecStatus binary_sum(Home home, IntView x, IntView y, int sum)
Definition open.hpp:305
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:317
static ExecStatus binary_sum(Home home, MinusView x, MinusView y, int sum)
Definition open.hpp:311
OpenSlidingSumEq(Space &home, OpenSlidingSumEq &p)
Definition open.hpp:288
OpenSlidingSumEq(Home home, OpenViewList< View > list, int width0, int sum0, IntPropLevel ipl0)
Definition open.hpp:276
static void post(Home home, OpenViewList< View > list, int width, int sum, IntPropLevel ipl)
Definition open.hpp:374
static void linear_term(Linear::Term< IntView > &term, IntView x)
Definition open.hpp:293
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:368
static void linear_term(Linear::Term< IntView > &term, MinusView x)
Definition open.hpp:299
Identify the windows affected by a position's domain change.
Definition open.hpp:47
OpenWindowAdvisor(Space &home, OpenWindowAdvisor &a)
Definition open.hpp:55
OpenWindowAdvisor(Space &home, Propagator &p, Council< OpenWindowAdvisor > &council, int index0)
Definition open.hpp:51
void dispose(Space &home, Council< OpenWindowAdvisor > &council)
Definition open.hpp:59
Council< OpenWindowAdvisor > council
Definition open.hpp:75
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition open.hpp:123
int first
Inclusive range of window starts needing propagation.
Definition open.hpp:73
void subscribe(Space &home, int index)
Definition open.hpp:103
virtual void reschedule(Space &home)
Schedule function.
Definition open.hpp:128
OpenWindowPropagator(Home home, OpenViewList< View > list, int width0)
Definition open.hpp:77
OpenWindowPropagator(Space &home, OpenWindowPropagator &p)
Definition open.hpp:81
static void post(Home home, OpenViewList< View > list, const IntSet &values, int width, int lower, int upper, IntPropLevel)
Definition open.hpp:256
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:171
Open(Space &home, Open &p)
Definition open.hpp:165
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:188
Open(Home home, OpenViewList< View > list, const IntSet &values0, int width0, int lower0, int upper0)
Definition open.hpp:157
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:248
virtual ExecStatus advise(Space &home, Advisor &advisor, const Delta &)
Advise function.
Definition open.hpp:176
View interface to a space-local list with an open length.
Definition int.hh:1044
Propagation cost.
Definition core.hpp:493
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
@ HI
Expensive.
Definition core.hpp:521
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1086
friend class Space
Definition core.hpp:1075
friend class Advisor
Definition core.hpp:1077
friend class Council
Definition core.hpp:1078
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
void post(Home home, Term< IntView > *t, int n, IntRelType irt, int c, IntPropLevel ipl=IPL_DEF)
Post propagator for linear constraint over integers.
Definition int-post.cpp:219
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:4121
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
#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
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
@ IPL_DEF
Simple propagation levels.
Definition int.hh:1276
@ IPL_BND
Bounds propagation.
Definition int.hh:1278
Numerical limits for integer variables.
Definition int.hh:119
const int max
Largest allowed integer value.
Definition int.hh:121
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
TakesStatus
Status of whether a view takes a value from a set.
Definition set-op.hpp:37
@ 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
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
Definition set-op.hpp:123
bool undecided(const View &x, int s)
Test whether no decision on inclusion or exclusion of values of view x in s can be made.
Definition set-op.hpp:106
TakesStatus takes(const View &x, int s)
Return whether view x takes value s.
Definition set-op.hpp:46
Finite domain integers.
Definition lastval.hh:52
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:80
Gecode toplevel namespace
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition ipl.hpp:37
ExecStatus
Definition core.hpp:479
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .