Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
int.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
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 { namespace Int { namespace Element {
35
36
37 // Index value pairs
38 template<class V0, class V1, class Idx, class Val>
39 forceinline void
43 template<class V0, class V1, class Idx, class Val>
44 forceinline bool
46 return idx<0;
47 }
48
49
50 // Index iterator
51 template<class V0, class V1, class Idx, class Val>
54 : iv(iv0) {
55 Idx p=0;
56 i = iv[p].idx_next;
57 while ((i != 0) && iv[i].marked())
58 i=iv[i].idx_next;
59 iv[p].idx_next=i;
60 }
61 template<class V0, class V1, class Idx, class Val>
62 forceinline bool
64 return i != 0;
65 }
66 template<class V0, class V1, class Idx, class Val>
67 forceinline void
69 int p=i;
70 i = iv[p].idx_next;
71 while ((i != 0) && iv[i].marked())
72 i=iv[i].idx_next;
73 iv[p].idx_next=i;
74 }
75 template<class V0, class V1, class Idx, class Val>
76 forceinline Idx
78 assert(!iv[i].marked());
79 return iv[i].idx;
80 }
81
82
83
84 template<class V0, class V1, class Idx, class Val>
87 : iv(iv0), i(iv[0].val_next) {}
88 template<class V0, class V1, class Idx, class Val>
89 forceinline bool
91 return i != 0;
92 }
93 template<class V0, class V1, class Idx, class Val>
94 forceinline void
96 i=iv[i].val_next;
97 }
98 template<class V0, class V1, class Idx, class Val>
101 assert(!iv[i].marked());
102 return iv[i].val;
103 }
104
105
106
107 template<class V0, class V1, class Idx, class Val>
110 : iv(iv0) {
111 Idx p=0;
112 i = iv[p].val_next;
113 while ((i != 0) && iv[i].marked())
114 i=iv[i].val_next;
115 iv[p].val_next=i;
116 }
117 template<class V0, class V1, class Idx, class Val>
118 forceinline bool
120 return i != 0;
121 }
122 template<class V0, class V1, class Idx, class Val>
123 forceinline void
125 int p=i;
126 i = iv[p].val_next;
127 while ((i != 0) && iv[i].marked())
128 i=iv[i].val_next;
129 iv[p].val_next=i;
130 }
131 template<class V0, class V1, class Idx, class Val>
134 assert(!iv[i].marked());
135 return iv[i].val;
136 }
137
138
139
140 // Sort function
141 template<class V0, class V1, class Idx, class Val>
144 : iv(iv0) {}
145 template<class V0, class V1, class Idx, class Val>
146 forceinline bool
148 return iv[i].val < iv[j].val;
149 }
150
151
152 /*
153 * Element propagator proper
154 *
155 */
156 template<class V0, class V1, class Idx, class Val>
159 : Propagator(home), x0(y0), s0(0), x1(y1), s1(0), c(c0), iv(NULL) {
160 home.notice(*this,AP_DISPOSE);
161 x0.subscribe(home,*this,PC_INT_DOM);
162 x1.subscribe(home,*this,PC_INT_DOM);
163 }
164
165 template<class V0, class V1, class Idx, class Val>
166 forceinline size_t
168 home.ignore(*this,AP_DISPOSE);
169 x0.cancel(home,*this,PC_INT_DOM);
170 x1.cancel(home,*this,PC_INT_DOM);
171 c.~IntSharedArray();
172 (void) Propagator::dispose(home);
173 return sizeof(*this);
174 }
175
176 template<class V0, class V1, class Idx, class Val>
179 if (x0.assigned()) {
180 GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
181 } else if (x1.assigned()) {
183 } else {
184 (void) new (home) Int<V0,V1,Idx,Val>(home,c,x0,x1);
185 }
186 return ES_OK;
187 }
188
189 template<class V0, class V1, class Idx, class Val>
192 : Propagator(home,p), s0(0), s1(0), c(p.c), iv(NULL) {
193 x0.update(home,p.x0);
194 x1.update(home,p.x1);
195 }
196
197 template<class V0, class V1, class Idx, class Val>
198 Actor*
200 return new (home) Int<V0,V1,Idx,Val>(home,*this);
201 }
202
203 template<class V0, class V1, class Idx, class Val>
206 if ((V0::me(med) == ME_INT_VAL) ||
207 (V1::me(med) == ME_INT_VAL))
209 else
211 }
212
213 template<class V0, class V1, class Idx, class Val>
214 void
216 x0.reschedule(home,*this,PC_INT_DOM);
217 x1.reschedule(home,*this,PC_INT_DOM);
218 }
219
220 template<class V0, class V1, class Idx, class Val>
221 void
223 Idx p = 0;
224 Idx i = iv[p].idx_next;
226 while (v() && (i != 0)) {
227 assert(!iv[i].marked());
228 if (iv[i].idx < v.min()) {
229 iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
230 } else if (iv[i].idx > v.max()) {
231 ++v;
232 } else {
233 p=i; i=iv[i].idx_next;
234 }
235 }
236 iv[p].idx_next = 0;
237 while (i != 0) {
238 iv[i].mark(); i=iv[i].idx_next;
239 }
240 }
241
242 template<class V0, class V1, class Idx, class Val>
243 void
245 Idx p = 0;
246 Idx i = iv[p].val_next;
248 while (v() && (i != 0)) {
249 if (iv[i].marked()) {
250 i=iv[i].val_next; iv[p].val_next=i;
251 } else if (iv[i].val < v.min()) {
252 iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
253 } else if (iv[i].val > v.max()) {
254 ++v;
255 } else {
256 p=i; i=iv[i].val_next;
257 }
258 }
259 iv[p].val_next = 0;
260 while (i != 0) {
261 iv[i].mark(); i=iv[i].val_next;
262 }
263 }
264
265 template<class V0, class V1, class Idx, class Val>
268 V0 x0, V1 x1) {
269 Region r;
270 int* v = r.alloc<int>(x0.size());
271 int n = 0;
272 for (ViewValues<V0> i(x0); i(); ++i)
273 if (c[i.val()] != x1.val())
274 v[n++]=i.val();
276 GECODE_ME_CHECK(x0.minus_v(home,iv,false));
277 return ES_OK;
278 }
279
280 template<class V0, class V1, class Idx, class Val>
283 if (x0.assigned()) {
284 GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
285 return home.ES_SUBSUMED(*this);
286 }
287
288 if (x1.assigned() && (iv == NULL)) {
290 return home.ES_SUBSUMED(*this);
291 }
292
293 if ((static_cast<ValSize>(x1.size()) == s1) &&
294 (static_cast<IdxSize>(x0.size()) != s0)) {
295 assert(iv != NULL);
296 assert(!shared(x0,x1));
297
298 prune_idx();
299
300 IterValUnmark v(iv);
301 GECODE_ME_CHECK(x1.narrow_v(home,v,false));
302
303 s1=static_cast<ValSize>(x1.size());
304
305 assert(!x0.assigned());
306 return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
307 }
308
309 if ((static_cast<IdxSize>(x0.size()) == s0) &&
310 (static_cast<ValSize>(x1.size()) != s1)) {
311 assert(iv != NULL);
312 assert(!shared(x0,x1));
313
314 prune_val();
315
316 IterIdxUnmark i(iv);
317 GECODE_ME_CHECK(x0.narrow_v(home,i,false));
318
319 s0=static_cast<IdxSize>(x0.size());
320
321 return (x0.assigned() || x1.assigned()) ?
322 home.ES_SUBSUMED(*this) : ES_FIX;
323 }
324
325 bool assigned = x0.assigned() && x1.assigned();
326 if (iv == NULL) {
327 // Initialize data structure
328 iv = home.alloc<IdxVal>(x0.size() + 1);
329
330 // The first element in iv[0] is used as sentinel
331 // Enter information sorted by idx
332 IdxVal* by_idx = &iv[1];
333 Idx size = 0;
334 for (ViewValues<V0> v(x0); v(); ++v)
335 if ((x1.min() <= c[v.val()]) && (x1.max() >= c[v.val()])) {
336 by_idx[size].idx = static_cast<Idx>(v.val());
337 by_idx[size].val = static_cast<Val>(c[v.val()]);
338 size++;
339 }
340 if (size == 0)
341 return ES_FAILED;
342 // Create val links sorted by val
343 Region r;
344 Idx* by_val = r.alloc<Idx>(size);
345 if (x1.width() <= 128) {
346 int n_buckets = static_cast<int>(x1.width());
347 int* pos = r.alloc<int>(n_buckets);
348 int* buckets = pos - x1.min();
349 for (int i=0; i<n_buckets; i++)
350 pos[i]=0;
351 for (Idx i=0; i<size; i++)
352 buckets[by_idx[i].val]++;
353 int p=0;
354 for (int i=0; i<n_buckets; i++) {
355 int n=pos[i]; pos[i]=p; p+=n;
356 }
357 assert(p == size);
358 for (Idx i=0; i<size; i++)
359 by_val[buckets[by_idx[i].val]++] = i+1;
360 } else {
361 for (Idx i=0; i<size; i++)
362 by_val[i] = i+1;
363 ByVal less(iv);
364 Support::quicksort<Idx>(by_val,size,less);
365 }
366 // Create val links
367 for (Idx i=0; i<size-1; i++) {
368 by_idx[i].idx_next = i+2;
369 iv[by_val[i]].val_next = by_val[i+1];
370 }
371 by_idx[size-1].idx_next = 0;
372 iv[by_val[size-1]].val_next = 0;
373 // Set up sentinel element: iv[0]
374 iv[0].idx_next = 1;
375 iv[0].val_next = by_val[0];
376 } else {
377 prune_idx();
378 }
379
380 // Prune values
381 prune_val();
382
383 // Peform tell
384 {
385 IterIdxUnmark i(iv);
386 GECODE_ME_CHECK(x0.narrow_v(home,i,false));
387 IterVal v(iv);
388 if (shared(x0,x1)) {
389 GECODE_ME_CHECK(x1.inter_v(home,v,false));
390 s0=static_cast<IdxSize>(x0.size());
391 s1=static_cast<ValSize>(x1.size());
392 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
393 } else {
394 GECODE_ME_CHECK(x1.narrow_v(home,v,false));
395 s0=static_cast<IdxSize>(x0.size());
396 s1=static_cast<ValSize>(x1.size());
397 return (x0.assigned() || x1.assigned()) ?
398 home.ES_SUBSUMED(*this) : ES_FIX;
399 }
400 }
401 }
402
403 template<class V0, class V1>
405 post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
406 assert(c.size() > 0);
407 GECODE_ME_CHECK(x0.gq(home,0));
408 GECODE_ME_CHECK(x0.le(home,c.size()));
409 Support::IntType idx_type = Support::s_type(c.size());
410 int min = c[0];
411 int max = c[0];
412 for (int i=1; i<c.size(); i++) {
413 min = std::min(c[i],min); max = std::max(c[i],max);
414 }
415 GECODE_ME_CHECK(x1.gq(home,min));
416 GECODE_ME_CHECK(x1.lq(home,max));
417 Support::IntType val_type =
419 switch (idx_type) {
420 case Support::IT_CHAR:
421 switch (val_type) {
422 case Support::IT_CHAR:
423 return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
424 case Support::IT_SHRT:
426 default: break;
427 }
428 break;
429 case Support::IT_SHRT:
430 switch (val_type) {
431 case Support::IT_CHAR:
432 case Support::IT_SHRT:
434 default: break;
435 }
436 break;
437 default: break;
438 }
439 return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
440 }
441
442}}}
443
444// STATISTICS: int-prop
445
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3256
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
Home class for posting propagators
Definition core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3223
Sorting pointers to (index,value) pairs in value order.
Definition element.hh:141
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition int.hpp:147
const IdxVal * iv
Index-value pairs.
Definition element.hh:143
ByVal(const IdxVal *iv)
Initialize with index value pairs.
Definition int.hpp:143
Linked index-value pairs.
Definition element.hh:67
Val val
The value Mark that this pair should be removed.
Definition element.hh:72
bool marked(void) const
Return whether this pair is marked for removal.
Definition int.hpp:45
Idx idx_next
The position of the next pair in index order.
Definition element.hh:69
Value iterator for indices in index-value map.
Definition element.hh:84
Idx val(void) const
Return index of current index value pair.
Definition int.hpp:77
void operator++(void)
Move to next index value pair (next index)
Definition int.hpp:68
IterIdxUnmark(IdxVal *iv)
Initialize with start.
Definition int.hpp:53
bool operator()(void) const
Test whether more pairs to be iterated.
Definition int.hpp:63
Value iterator for values in index-value map.
Definition element.hh:126
void operator++(void)
Move to next index value pair (next value)
Definition int.hpp:124
bool operator()(void) const
Test whether more pairs to be iterated.
Definition int.hpp:119
Val val(void) const
Return value of current index value pair.
Definition int.hpp:133
IterValUnmark(IdxVal *iv)
Initialize with start.
Definition int.hpp:109
Value iterator for values in index-value map.
Definition element.hh:104
bool operator()(void) const
Test whether more pairs to be iterated.
Definition int.hpp:90
IterVal(IdxVal *iv)
Initialize with start.
Definition int.hpp:86
Val val(void) const
Return value of current index value pair.
Definition int.hpp:100
void operator++(void)
Move to next index value pair (next value)
Definition int.hpp:95
Int(Space &home, Int &p)
Constructor for cloning p.
Definition int.hpp:191
ValSize s1
Size of x1 at last execution.
Definition element.hh:162
void prune_val(void)
Prune values according to x1.
Definition int.hpp:244
IntSharedArray c
Shared array of integer values.
Definition element.hh:164
V1 x1
View for result.
Definition element.hh:158
static ExecStatus post(Home home, IntSharedArray &i, V0 x0, V1 x1)
Post propagator for .
Definition int.hpp:178
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition int.hpp:199
virtual void reschedule(Space &home)
Schedule function.
Definition int.hpp:215
static ExecStatus assigned_val(Space &home, IntSharedArray &c, V0 x0, V1 x1)
Prune when x1 is assigned.
Definition int.hpp:267
IdxSize s0
Size of x0 at last execution.
Definition element.hh:156
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int.hpp:282
IdxVal * iv
The index-value data structure.
Definition element.hh:166
Gecode::Support::IntTypeTraits< Idx >::utype IdxSize
Type for index size.
Definition element.hh:154
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for value size.
Definition element.hh:160
V0 x0
View for index.
Definition element.hh:152
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high binary)
Definition int.hpp:205
void prune_idx(void)
Prune index according to x0.
Definition int.hpp:222
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int.hpp:167
Range iterator for integer views.
Definition view.hpp:54
Value iterator for integer views.
Definition view.hpp:94
Value iterator for array of integers
Propagation cost.
Definition core.hpp:486
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4820
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition core.hpp:4816
@ HI
Expensive.
Definition core.hpp:514
size_t size
The size of the propagator (used during subsumption)
Definition core.hpp:1079
friend class Space
Definition core.hpp:1068
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1077
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4081
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#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:562
Element propagators
ExecStatus post_int(Home home, IntSharedArray &c, V0 x0, V1 x1)
Post propagator with apropriate index and value types.
Definition int.hpp:405
Finite domain integers.
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
IntType s_type(signed int n)
Return type required to represent n.
IntType
Description of integer types.
Definition int-type.hpp:39
@ IT_CHAR
char integer type
Definition int-type.hpp:40
@ IT_SHRT
short integer type
Definition int-type.hpp:41
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1492
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
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
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition array.hpp:1472
#define forceinline
Definition config.hpp:194