Generated on for Gecode by doxygen 1.18.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_REL_OPEN_HPP
35#define GECODE_INT_REL_OPEN_HPP
36
37#include <gecode/int/rel.hh>
39
40namespace Gecode { namespace Int { namespace Rel {
41
43 template<class View, IntRelType irt>
44 class Open : public OpenListPropagator<View> {
45 protected:
49
51 class Position : public Advisor {
52 public:
53 int index;
54
56 int index0)
57 : Advisor(home,p,council), index(index0) {}
58
60 : Advisor(home,a), index(a.index) {}
61
62 void
66 };
67
70 int first;
71 int last;
73 bool domain;
74
76 : OpenListPropagator<View>(home,list), council(home),
77 first(Int::Limits::max), last(-1),
78 domain((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {}
79
80 Open(Space& home, Open& p)
81 : OpenListPropagator<View>(home,p), council(home),
82 first(p.first), last(p.last), domain(p.domain) {
83 council.update(home,p.council);
84 }
85
86 void
87 changed(int index) {
88 first = std::min(first,index);
89 last = std::max(last,index);
90 }
91
93 View
94 ordered(int index, int size) const {
95 return list[((irt == IRT_GQ) || (irt == IRT_GR))
96 ? size-1-index : index];
97 }
98
101 propagate_equal(Space& home, int begin, int end, int size) {
102 View common(list[0]);
103 const unsigned int old_size = common.size();
104 for (int i=begin; i<=end; i++) {
105 View x(list[i]);
106 if (x == common)
107 continue;
108 if (domain) {
109 ViewRanges<View> ranges(x);
110 GECODE_ME_CHECK(common.inter_r(home,ranges,false));
111 } else {
112 GECODE_ME_CHECK(common.gq(home,x.min()));
113 GECODE_ME_CHECK(common.lq(home,x.max()));
114 }
115 }
116 // If the common domain is unchanged, update only the changed positions.
117 if ((begin == 0) || (common.size() != old_size)) {
118 begin = 1;
119 end = size-1;
120 }
121 for (int i=begin; i<=end; i++) {
122 View x(list[i]);
123 if (x == common)
124 continue;
125 if (domain) {
126 ViewRanges<View> ranges(common);
127 GECODE_ME_CHECK(x.inter_r(home,ranges,false));
128 } else {
129 GECODE_ME_CHECK(x.gq(home,common.min()));
130 GECODE_ME_CHECK(x.lq(home,common.max()));
131 }
132 }
133 return ES_OK;
134 }
135
138 propagate_different(Space& home, int begin, int end, int size) {
139 for (int i=begin; i<=end; i++) {
140 View x(list[i]);
141 if (!x.assigned())
142 continue;
143 if (i > 0)
144 GECODE_ME_CHECK(list[i-1].nq(home,x.val()));
145 if (i+1 < size)
146 GECODE_ME_CHECK(list[i+1].nq(home,x.val()));
147 }
148 return ES_OK;
149 }
150
153 propagate_order(Space& home, int begin, int end, int size) {
154 const int offset = ((irt == IRT_LE) || (irt == IRT_GR)) ? 1 : 0;
155 if constexpr ((irt == IRT_GQ) || (irt == IRT_GR)) {
156 const int old_begin = begin;
157 begin = size-1-end;
158 end = size-1-old_begin;
159 }
160 for (int i=std::max(1,begin); i<size; i++) {
161 ModEvent me = ordered(i,size).gq(home,ordered(i-1,size).min()+offset);
162 if (me_failed(me))
163 return ES_FAILED;
164 if ((i > end) && !me_modified(me))
165 break;
166 }
167 for (int i=std::min(size-2,end); i>=0; i--) {
168 ModEvent me = ordered(i,size).lq(home,ordered(i+1,size).max()-offset);
169 if (me_failed(me))
170 return ES_FAILED;
171 if ((i < begin) && !me_modified(me))
172 break;
173 }
174 return ES_OK;
175 }
176
177 public:
178 virtual Actor*
179 copy(Space& home) {
180 return new (home) Open(home,*this);
181 }
182
183 virtual PropCost
184 cost(const Space&, const ModEventDelta&) const {
185 return PropCost::linear(PropCost::LO,list.known_length());
186 }
187
188 virtual ExecStatus
189 advise(Space& home, Advisor& advisor, const Delta& delta) {
190 Position& a = static_cast<Position&>(advisor);
191 View x(list[a.index]);
192 if constexpr (irt == IRT_NQ) {
193 if (!x.assigned())
194 return ES_FIX;
195 } else if (((irt != IRT_EQ) || !domain) &&
196 (View::modevent(delta) == ME_INT_DOM)) {
197 return ES_FIX;
198 }
199 changed(a.index);
200 if (x.assigned())
201 return home.ES_NOFIX_DISPOSE(council,a);
202 return ES_NOFIX;
203 }
204
205 virtual ExecStatus
207 const int size = list.known_length();
208 if (processed < size) {
209 changed(std::max(0,processed-1));
210 changed(size-1);
211 }
212 for (int i=processed; i<size; i++) {
213 View x(list[i]);
214 if (((irt == IRT_NQ) || (irt == IRT_LE) || (irt == IRT_GR)) &&
215 (i > 0) && (x == list[i-1]))
216 return ES_FAILED;
217 if (!x.assigned())
218 x.subscribe(home,*new (home) Position(home,*this,council,i));
219 }
220 processed = size;
221
222 // Advisors record further changes caused by sparse bounds or aliases.
223 while (first <= last) {
224 const int begin = first;
225 const int end = last;
227 last = -1;
228 if constexpr (irt == IRT_EQ) {
229 GECODE_ES_CHECK(propagate_equal(home,begin,end,size));
230 } else if constexpr (irt == IRT_NQ) {
231 GECODE_ES_CHECK(propagate_different(home,begin,end,size));
232 } else {
233 GECODE_ES_CHECK(propagate_order(home,begin,end,size));
234 }
235 }
236 return (closed() && ((size < 2) || council.empty()))
237 ? home.ES_SUBSUMED(*this) : ES_FIX;
238 }
239
240 virtual void
243 first = 0;
244 last = list.known_length()-1;
245 View::schedule(home,*this,ME_INT_DOM);
246 }
247
248 virtual size_t
249 dispose(Space& home) {
250 if (!home.failed())
251 for (Advisors<Position> a(council); a(); ++a)
252 list[a.advisor().index].cancel(home,a.advisor());
253 council.dispose(home);
255 return sizeof(*this);
256 }
257
258 static void
260 (void) new (home) Open(home,list,ipl);
261 }
262 };
263
264}}}
265
266#endif
267
268// 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
bool empty(void) const
Test whether council has advisor left.
Definition core.hpp:4150
void update(Space &home, Council< A > &c)
Update during cloning (copies all advisors).
Definition core.hpp:4160
void dispose(Space &home)
Dispose council.
Definition core.hpp:4216
Generic domain change information to be supplied to advisors.
Definition core.hpp:209
Home class for posting propagators
Definition core.hpp:863
virtual void reschedule(Space &home)
Schedule function.
OpenListPropagator(Home home, OpenViewList< View > list0)
Identify the position whose domain changed.
Definition open.hpp:51
Position(Space &home, Propagator &p, Council< Position > &council, int index0)
Definition open.hpp:55
void dispose(Space &home, Council< Position > &council)
Definition open.hpp:63
Position(Space &home, Position &a)
Definition open.hpp:59
View ordered(int index, int size) const
Read decreasing relations in increasing order.
Definition open.hpp:94
Council< Position > council
Definition open.hpp:68
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:206
ExecStatus propagate_order(Space &home, int begin, int end, int size)
Sweep lower bounds forward and upper bounds backward from changed positions.
Definition open.hpp:153
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:249
ExecStatus propagate_equal(Space &home, int begin, int end, int size)
Accumulate the domain intersection in the first position.
Definition open.hpp:101
Open(Space &home, Open &p)
Definition open.hpp:80
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:179
virtual ExecStatus advise(Space &home, Advisor &advisor, const Delta &delta)
Advise function.
Definition open.hpp:189
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition open.hpp:184
virtual void reschedule(Space &home)
Schedule function.
Definition open.hpp:241
Open(Home home, OpenViewList< View > list, IntPropLevel ipl)
Definition open.hpp:75
void changed(int index)
Definition open.hpp:87
ExecStatus propagate_different(Space &home, int begin, int end, int size)
Propagate assignments to their immediate neighbors.
Definition open.hpp:138
int first
Inclusive range of positions needing propagation.
Definition open.hpp:70
bool domain
Whether equality propagates holes as well as bounds.
Definition open.hpp:73
static void post(Home home, OpenViewList< View > list, IntPropLevel ipl)
Definition open.hpp:259
Range iterator for integer views.
Definition view.hpp:54
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
friend class Space
Definition core.hpp:1075
friend class Advisor
Definition core.hpp:1077
friend class Council
Definition core.hpp:1078
virtual Val val(const Space &home, View x, int i)=0
Return value of view x at position i.
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
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
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IRT_NQ
Disequality ( ).
Definition int.hh:1227
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:1230
@ IRT_LE
Less ( ).
Definition int.hh:1229
@ IRT_GR
Greater ( ).
Definition int.hh:1231
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
@ IPL_DEF
Simple propagation levels.
Definition int.hh:1276
Numerical limits for integer variables.
Definition int.hh:119
const int max
Largest allowed integer value.
Definition int.hh:121
Simple relation propagators.
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
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition ipl.hpp:37
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ 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 .
int ModEvent
Type for modification events.
Definition core.hpp:67