Generated on for Gecode by doxygen 1.17.0
open-var-list.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
34namespace Gecode {
35
36 template<class Var>
37 class OpenVarList<Var>::Object : public LocalObject {
38 public:
39 class Functions {
40 public:
43
44 Functions(Factory create0, Transition transition0)
45 : create(create0), transition(transition0) {}
46 };
47
49 // A separate event source reports appended positions even when length.min()
50 // already requires them and therefore does not change during construction.
53 int n;
55 typedef std::unordered_set<const void*> VarImpSet;
57 // Only committed positions are indexed. Assigned variables need no alias
58 // check, so their entries need not be removed.
61
62 static int
64 Int::Limits::check(max,"OpenVarList");
65 if (max < 0)
66 throw Int::VariableEmptyDomain("OpenVarList");
67 return max;
68 }
69
70 static Factory
71 checked(Factory create) {
72 if (!create)
73 throw InvalidFunction("OpenVarList");
74 return create;
75 }
76
77 static Transition
79 if (!t)
80 throw InvalidFunction("OpenVarList");
81 return t;
82 }
83
84 Object(Home home, Factory create, int max)
85 : LocalObject(home),
86 length(home,0,checked_maximum(max)),
87 materialized(home,0,max),
88 x(nullptr), n(0), capacity(0), indexed(0),
89 functions(Functions(checked(create),Transition())) {
90 home.notice(*this,AP_DISPOSE);
91 }
92
93 Object(Home home, Factory create, Transition t, int max)
94 : LocalObject(home),
95 length(home,0,checked_maximum(max)),
96 materialized(home,0,max),
97 x(nullptr), n(0), capacity(0), indexed(0),
98 functions(Functions(checked(create),checked(t))) {
99 home.notice(*this,AP_DISPOSE);
100 }
101
102 Object(Space& home, Object& s)
103 : LocalObject(home,s), x(nullptr), n(s.n), capacity(s.n), indexed(0),
104 functions(s.functions) {
105 length.update(home,s.length);
106 materialized.update(home,s.materialized);
107 if (capacity > 0) {
108 x = heap.alloc<Var>(capacity);
109 try {
110 for (int i=0; i<n; i++)
111 x[i].update(home,s.x[i]);
112 } catch (...) {
113 heap.free<Var>(x,capacity);
114 throw;
115 }
116 }
117 }
118
119 virtual Actor*
120 copy(Space& home) {
121 return new (home) Object(home,*this);
122 }
123
124 virtual size_t
125 dispose(Space& home) {
126 home.ignore(*this,AP_DISPOSE);
127 if (capacity > 0)
128 heap.free<Var>(x,capacity);
129 identities.~VarImpSet();
130 functions.~SharedData<Functions>();
131 return sizeof(*this);
132 }
133
134 void
136 if (y.assigned())
137 return;
138 // Each clone builds its own index on the first alias check. Indexing a
139 // position on the next append puts allocation failures before changes
140 // to length or materialized.
141 for (; indexed<n; indexed++)
142 if (!x[indexed].assigned())
143 identities.insert(x[indexed].varimp());
144 if (identities.find(y.varimp()) != identities.end())
145 throw Int::ArgumentSame("OpenVarList::append");
146 }
147
148 void
149 reserve(void) {
150 if (n == capacity) {
151 int next = (capacity < 4) ? 4 :
153 x = heap.realloc<Var>(x,capacity,next);
154 capacity = next;
155 }
156 }
157
158 void
159 append(Space& home, Var y) {
160 if (home.failed())
161 return;
162 if (n == Int::Limits::max) {
163 home.fail();
164 return;
165 }
166 check_alias(y);
167 reserve();
168 const int next = n + 1;
170 Int::IntView m(materialized);
171 if (me_failed(l.gq(home,next)) || me_failed(m.gq(home,next))) {
172 home.fail();
173 return;
174 }
175 x[n++] = y;
176 const Transition& transition = functions().transition;
177 if (transition) {
178 Space::NoGPI no_gpi(home);
179 transition(home,OpenVarList<Var>(this),next-1);
180 }
181 }
182
183 void
184 materialize(Space& home, int size) {
185 Space::NoGPI no_gpi(home);
186 Int::Limits::nonnegative(size,"OpenVarList::materialize");
188 if (me_failed(l.gq(home,size))) {
189 home.fail();
190 return;
191 }
192 while (n < l.min()) {
193 const int i = n;
194 GECODE_VALID_FUNCTION(functions().create);
195 Var y = functions().create(home,i);
196 append(home,y);
197 if (home.failed())
198 return;
199 }
200 }
201
202 void
204 Int::IntView(materialized).subscribe(home,p,Int::PC_INT_BND);
205 }
206
207 void
209 Int::IntView(materialized).cancel(home,p,Int::PC_INT_BND);
210 }
211
212 void
214 Int::IntView(materialized).reschedule(home,p,Int::PC_INT_BND);
215 }
216 };
217
218}
219
220namespace Gecode { namespace Int {
221
223 template<class Var>
224 class OpenMaterialize : public Propagator, private LocalHandle {
225 protected:
228
230 : Propagator(home), LocalHandle(source), length(source->length) {
231 length.subscribe(home,*this,PC_INT_BND);
232 }
233
235 : Propagator(home,p) {
236 LocalHandle::update(home,p);
237 length.update(home,p.length);
238 }
239
240 public:
241 virtual Actor*
242 copy(Space& home) {
243 return new (home) OpenMaterialize(home,*this);
244 }
245
246 virtual PropCost
247 cost(const Space&, const ModEventDelta&) const {
248 const int n = length.min()-static_cast<Object*>(object())->n;
249 return (n <= 1) ? PropCost::unary(PropCost::LO) :
251 }
252
253 virtual void
255 length.reschedule(home,*this,PC_INT_BND);
256 }
257
258 virtual ExecStatus
260 static_cast<Object*>(object())->materialize(home,length.min());
261 if (home.failed())
262 return ES_FAILED;
263 if (length.assigned())
264 return home.ES_SUBSUMED(*this);
265 return ES_FIX;
266 }
267
268 virtual size_t
269 dispose(Space& home) {
270 length.cancel(home,*this,PC_INT_BND);
272 (void) Propagator::dispose(home);
273 return sizeof(*this);
274 }
275
276 static void
277 post(Home home, Object* source) {
278 if (!source->length.assigned())
279 (void) new (home) OpenMaterialize(home,source);
280 }
281 };
282
283}}
284
285namespace Gecode {
286
287 template<class Var>
289
290 template<class Var>
292 : LocalHandle(source) {}
293
294 template<class Var>
296 : LocalHandle(new (home) Object(home,create,max)) {
297 Int::OpenMaterialize<Var>::post(home,static_cast<Object*>(object()));
298 }
299
300 template<class Var>
302 Transition t, int max)
303 : LocalHandle(new (home) Object(home,create,t,max)) {
304 Int::OpenMaterialize<Var>::post(home,static_cast<Object*>(object()));
305 }
306
308 OpenIntVarList::OpenIntVarList(const OpenVarList<IntVar>& x)
309 : OpenVarList<IntVar>(x) {}
310
312 OpenBoolVarList::OpenBoolVarList(const OpenVarList<BoolVar>& x)
313 : OpenVarList<BoolVar>(x) {}
314
315 template<class Var>
316 void
317 OpenVarList<Var>::update(Space& home, OpenVarList<Var>& s) {
318 LocalHandle::update(home,s);
319 }
320
321 template<class Var>
322 int
324 return static_cast<Object*>(object())->n;
325 }
326
327 template<class Var>
328 Var
330 Object* s = static_cast<Object*>(object());
331 assert((i >= 0) && (i < s->n));
332 return s->x[i];
333 }
334
335 template<class Var>
336 IntVar
338 return static_cast<Object*>(object())->length;
339 }
340
341 template<class Var>
342 void
344 if (!home.failed())
345 static_cast<Object*>(object())->append(home,y);
346 }
347
348 template<class Var>
349 void
351 if (!home.failed())
352 static_cast<Object*>(object())->materialize(home,n);
353 }
354
355 template<class Var>
356 Var
358 Int::Limits::nonnegative(i,"OpenVarList::get");
359 if (home.failed())
360 return Var();
361 Object* s = static_cast<Object*>(object());
362 if (i >= s->length.max())
363 throw Int::OutOfLimits("OpenVarList::get");
364 materialize(home,i+1);
365 if (home.failed())
366 return Var();
367 return static_cast<Object*>(object())->x[i];
368 }
369
370 template<class Var>
371 void
373 if (home.failed())
374 return;
375 materialize(home,length().min());
376 if (home.failed())
377 return;
378 Object* s = static_cast<Object*>(object());
379 if (me_failed(Int::IntView(s->length).eq(home,s->n)))
380 home.fail();
381 }
382
383 template<class Var>
384 void
386 static_cast<Object*>(object())->subscribe(home,p);
387 }
388
389 template<class Var>
390 void
392 static_cast<Object*>(object())->cancel(home,p);
393 }
394
395 template<class Var>
396 void
398 static_cast<Object*>(object())->reschedule(home,p);
399 }
400
401}
402
403namespace Gecode { namespace Int {
404
406 template<class View>
407 forceinline View
408 open_list_view(typename View::VarType x) {
409 return View(x);
410 }
411
412 template<>
417
418}}
419
420namespace Gecode {
421
422 template<class View>
424
425 template<class View>
428
429 template<class View>
430 void
434
435 template<class View>
436 int
438 return static_cast<Object*>(object())->n;
439 }
440
441 template<class View>
442 View
444 Object* s = static_cast<Object*>(object());
445 assert((i >= 0) && (i < s->n));
446 return Int::open_list_view<View>(s->x[i]);
447 }
448
449 template<class View>
452 return Int::IntView(static_cast<Object*>(object())->length);
453 }
454
455 template<class View>
456 void
458 if (!home.failed())
459 static_cast<Object*>(object())->materialize(home,n);
460 }
461
462 template<class View>
463 void
465 static_cast<Object*>(object())->subscribe(home,p);
466 }
467
468 template<class View>
469 void
471 static_cast<Object*>(object())->cancel(home,p);
472 }
473
474 template<class View>
475 void
477 static_cast<Object*>(object())->reschedule(home,p);
478 }
479
480}
481
482// STATISTICS: int-var
Base-class for both propagators and branchers.
Definition core.hpp:635
friend class Propagator
Definition core.hpp:638
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Boolean integer variables.
Definition int.hh:534
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 variables.
Definition int.hh:390
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Integer view for integer variables.
Definition view.hpp:129
int min(void) const
Return minimum of domain.
Definition int.hpp:58
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
Minus integer view.
Definition view.hpp:282
OpenMaterialize(Space &home, OpenMaterialize &p)
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
virtual size_t dispose(Space &home)
Delete actor and return its size.
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
OpenVarList< Var >::Object Object
virtual void reschedule(Space &home)
Schedule function.
OpenMaterialize(Home home, Object *source)
virtual Actor * copy(Space &home)
Create copy.
static void post(Home home, Object *source)
Exception: Value out of limits
Definition exception.hpp:44
Exception: Variable created with empty domain
Definition exception.hpp:59
Exception: invalid function
Handles for local (space-shared) objects.
Definition core.hpp:1576
LocalHandle(void)
Create local handle pointing to nullptr object.
Definition core.hpp:3968
~LocalHandle(void)
Destructor.
Definition core.hpp:3979
void update(Space &home, LocalHandle &lh)
Updating during cloning.
Definition core.hpp:3985
LocalObject * object(void) const
Access to the local object.
Definition core.hpp:3981
friend class Space
Definition core.hpp:1553
LocalObject(Home home)
Constructor for creation.
Definition core.hpp:3950
OpenBoolVarList(void)
Construct an uninitialized list.
OpenIntVarList(void)
Construct an uninitialized list.
Functions(Factory create0, Transition transition0)
Object(Home home, Factory create, Transition t, int max)
static int checked_maximum(int max)
void reschedule(Space &home, Propagator &p)
static Factory checked(Factory create)
virtual Actor * copy(Space &home)
Create copy.
void cancel(Space &home, Propagator &p)
Object(Space &home, Object &s)
void subscribe(Space &home, Propagator &p)
void materialize(Space &home, int size)
Object(Home home, Factory create, int max)
void append(Space &home, Var y)
static Transition checked(Transition t)
virtual size_t dispose(Space &home)
Delete actor and return its size.
void materialize(Space &home, int n)
Materialize the first n variables.
void close(Space &home)
Close the list at its materialized length.
void update(Space &home, OpenVarList< Var > &s)
Update during cloning.
int known_length(void) const
Return the number of constructed positions (their values may be unassigned).
IntVar length(void) const
Return the eventual-length variable.
SharedData< Functions > functions
std::function< Var(Space &home, int i)> Factory
Function creating the variable at position i in home.
Definition int.hh:948
OpenVarList(void)
Construct an uninitialized list.
void cancel(Space &home, Propagator &p)
Cancel the subscription of p to the addition of positions.
void reschedule(Space &home, Propagator &p)
Reschedule p for the addition of positions.
void subscribe(Space &home, Propagator &p)
Subscribe p to the addition of positions.
std::function< void(Space &home, OpenVarList< Var > x, int i)> Transition
Function called after materializing position i.
Definition int.hh:959
Var get(Space &home, int i)
Require and return the variable at position i.
Var operator[](int i) const
Return variable at position i, where 0 <= i < known_length().
std::unordered_set< const void * > VarImpSet
VarImpSet identities
void append(Space &home, Var x)
Append variable x.
void materialize(Space &home, int n)
Require and construct at least the first n positions.
View operator[](int i) const
Return the view at constructed position i.
Int::IntView length(void) const
Return the eventual-length view.
void reschedule(Space &home, Propagator &p)
Reschedule p for construction of positions.
int known_length(void) const
Return the number of constructed positions.
void update(Space &home, OpenViewList< View > &s)
Update during cloning.
void cancel(Space &home, Propagator &p)
Cancel the subscription of p to construction of positions.
OpenViewList(void)
Construct an uninitialized list.
void subscribe(Space &home, Propagator &p)
Subscribe p to construction of positions.
Propagation cost.
Definition core.hpp:493
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:5097
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
Base-class for propagators.
Definition core.hpp:1073
friend class Space
Definition core.hpp:1075
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Class for sharing data between spaces.
~SharedData(void)
Destructors.
Suppress global propagator information during scoped posting.
Definition core.hpp:2070
Computation spaces.
Definition core.hpp:1787
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition view.hpp:527
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition view.hpp:532
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition view.hpp:521
Base class for variables.
Definition var.hpp:40
const int capacity[n_warehouses]
Capacity of a single warehouse.
Heap heap
The single global heap.
Definition heap.cpp:44
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
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
void fail(void)
Fail space.
Definition core.hpp:4275
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
void nonnegative(int n, const char *l)
Check whether n is in range and nonnegative, otherwise throw out of limits with information l.
Definition limits.hpp:68
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition limits.hpp:46
const int max
Largest allowed integer value.
Definition int.hh:121
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
MinusView open_list_view< MinusView >(IntVar x)
View open_list_view(typename View::VarType x)
Construct an element view without changing the shared source list.
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
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
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
#define forceinline
Definition config.hpp:144
#define GECODE_VALID_FUNCTION(f)
Assert that a function is valid.
Definition macros.hpp:94