Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
int.cpp
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, 2002
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
34#include <gecode/int.hh>
35
36namespace Gecode { namespace Int {
37
38 forceinline bool
39 IntVarImp::closer_min(int n) const {
40 unsigned int l = static_cast<unsigned int>(n - dom.min());
41 unsigned int r = static_cast<unsigned int>(dom.max() - n);
42 return l < r;
43 }
44
45 int
46 IntVarImp::med(void) const {
47 // Computes the median
48 if (fst() == NULL)
49 return (dom.min()+dom.max())/2 - ((dom.min()+dom.max())%2 < 0 ? 1 : 0);
50 unsigned int i = size() / 2;
51 if (size() % 2 == 0)
52 i--;
53 const RangeList* p = NULL;
54 const RangeList* c = fst();
55 while (i >= c->width()) {
56 i -= c->width();
57 const RangeList* n=c->next(p); p=c; c=n;
58 }
59 return c->min() + static_cast<int>(i);
60 }
61
62 bool
63 IntVarImp::in_full(int m) const {
64 if (closer_min(m)) {
65 const RangeList* p = NULL;
66 const RangeList* c = fst();
67 while (m > c->max()) {
68 const RangeList* n=c->next(p); p=c; c=n;
69 }
70 return (m >= c->min());
71 } else {
72 const RangeList* n = NULL;
73 const RangeList* c = lst();
74 while (m < c->min()) {
75 const RangeList* p=c->prev(n); n=c; c=p;
76 }
77 return (m <= c->max());
78 }
79 }
80
81 /*
82 * "Standard" tell operations
83 *
84 */
85
87 IntVarImp::lq_full(Space& home, int m) {
88 assert((m >= dom.min()) && (m <= dom.max()));
89 int old_max = dom.max();
91 if (range()) { // Is already range...
92 dom.max(m);
93 if (assigned()) me = ME_INT_VAL;
94 } else if (m < fst()->next(NULL)->min()) { // Becomes range...
95 dom.max(std::min(m,fst()->max()));
96 fst()->dispose(home,NULL,lst());
97 fst(NULL); holes = 0;
98 if (assigned()) me = ME_INT_VAL;
99 } else { // Stays non-range...
100 RangeList* n = NULL;
101 RangeList* c = lst();
102 unsigned int h = 0;
103 while (m < c->min()) {
104 RangeList* p = c->prev(n); c->fix(n);
105 h += (c->min() - p->max() - 1);
106 n=c; c=p;
107 }
108 holes -= h;
109 int max_c = std::min(m,c->max());
110 dom.max(max_c); c->max(max_c);
111 if (c != lst()) {
112 n->dispose(home,lst());
113 c->next(n,NULL); lst(c);
114 }
115 }
116 IntDelta d(dom.max()+1,old_max);
117 return notify(home,me,d);
118 }
119
121 IntVarImp::gq_full(Space& home, int m) {
122 assert((m >= dom.min()) && (m <= dom.max()));
123 int old_min = dom.min();
125 if (range()) { // Is already range...
126 dom.min(m);
127 if (assigned()) me = ME_INT_VAL;
128 } else if (m > lst()->prev(NULL)->max()) { // Becomes range...
129 dom.min(std::max(m,lst()->min()));
130 fst()->dispose(home,NULL,lst());
131 fst(NULL); holes = 0;
132 if (assigned()) me = ME_INT_VAL;
133 } else { // Stays non-range...
134 RangeList* p = NULL;
135 RangeList* c = fst();
136 unsigned int h = 0;
137 while (m > c->max()) {
138 RangeList* n = c->next(p); c->fix(n);
139 h += (n->min() - c->max() - 1);
140 p=c; c=n;
141 }
142 holes -= h;
143 int min_c = std::max(m,c->min());
144 dom.min(min_c); c->min(min_c);
145 if (c != fst()) {
146 fst()->dispose(home,p);
147 c->prev(p,NULL); fst(c);
148 }
149 }
150 IntDelta d(old_min,dom.min()-1);
151 return notify(home,me,d);
152 }
153
155 IntVarImp::eq_full(Space& home, int m) {
156 dom.min(m); dom.max(m);
157 if (!range()) {
158 bool failed = false;
159 RangeList* p = NULL;
160 RangeList* c = fst();
161 while (m > c->max()) {
162 RangeList* n=c->next(p); c->fix(n); p=c; c=n;
163 }
164 if (m < c->min())
165 failed = true;
166 while (c != NULL) {
167 RangeList* n=c->next(p); c->fix(n); p=c; c=n;
168 }
169 assert(p == lst());
170 fst()->dispose(home,p);
171 fst(NULL); holes = 0;
172 if (failed)
173 return fail(home);
174 }
175 IntDelta d;
176 return notify(home,ME_INT_VAL,d);
177 }
178
180 IntVarImp::nq_full(Space& home, int m) {
181 assert(!((m < dom.min()) || (m > dom.max())));
183 if (range()) {
184 if ((m == dom.min()) && (m == dom.max()))
185 return fail(home);
186 if (m == dom.min()) {
187 dom.min(m+1);
189 } else if (m == dom.max()) {
190 dom.max(m-1);
192 } else {
193 RangeList* f = new (home) RangeList(dom.min(),m-1);
194 RangeList* l = new (home) RangeList(m+1,dom.max());
195 f->prevnext(NULL,l);
196 l->prevnext(f,NULL);
197 fst(f); lst(l); holes = 1;
198 }
199 } else if (m < fst()->next(NULL)->min()) { // Concerns the first range...
200 int f_max = fst()->max();
201 if (m > f_max)
202 return ME_INT_NONE;
203 int f_min = dom.min();
204 if ((m == f_min) && (m == f_max)) {
205 RangeList* f_next = fst()->next(NULL);
206 dom.min(f_next->min());
207 if (f_next == lst()) { // Turns into range
208 // Works as at the ends there are only NULL pointers
209 fst()->dispose(home,f_next);
210 fst(NULL); holes = 0;
212 } else { // Remains non-range
213 f_next->prev(fst(),NULL);
214 fst()->dispose(home); fst(f_next);
215 holes -= dom.min() - f_min - 1;
216 me = ME_INT_BND;
217 }
218 } else if (m == f_min) {
219 dom.min(m+1); fst()->min(m+1);
220 me = ME_INT_BND;
221 } else if (m == f_max) {
222 fst()->max(m-1); holes += 1;
223 } else {
224 // Create new hole
225 RangeList* f = new (home) RangeList(f_min,m-1);
226 f->prevnext(NULL,fst());
227 fst()->min(m+1); fst()->prev(NULL,f);
228 fst(f); holes += 1;
229 }
230 } else if (m > lst()->prev(NULL)->max()) { // Concerns the last range...
231 int l_min = lst()->min();
232 if (m < l_min)
233 return ME_INT_NONE;
234 int l_max = dom.max();
235 if ((m == l_min) && (m == l_max)) {
236 RangeList* l_prev = lst()->prev(NULL);
237 dom.max(l_prev->max());
238 if (l_prev == fst()) {
239 // Turns into range
240 l_prev->dispose(home,lst());
241 fst(NULL); holes = 0;
243 } else { // Remains non-range
244 l_prev->next(lst(),NULL);
245 lst()->dispose(home); lst(l_prev);
246 holes -= l_max - dom.max() - 1;
247 me = ME_INT_BND;
248 }
249 } else if (m == l_max) {
250 dom.max(m-1); lst()->max(m-1);
251 me = ME_INT_BND;
252 } else if (m == l_min) {
253 lst()->min(m+1); holes += 1;
254 } else { // Create new hole
255 RangeList* l = new (home) RangeList(m+1,l_max);
256 l->prevnext(lst(),NULL);
257 lst()->max(m-1); lst()->next(NULL,l);
258 lst(l); holes += 1;
259 }
260 } else { // Concerns element in the middle of the list of ranges
261 RangeList* p;
262 RangeList* c;
263 RangeList* n;
264 if (closer_min(m)) {
265 assert(m > fst()->max());
266 p = NULL;
267 c = fst();
268 do {
269 n=c->next(p); p=c; c=n;
270 } while (m > c->max());
271 if (m < c->min())
272 return ME_INT_NONE;
273 n=c->next(p);
274 } else {
275 assert(m < lst()->min());
276 n = NULL;
277 c = lst();
278 do {
279 p=c->prev(n); n=c; c=p;
280 } while (m < c->min());
281 if (m > c->max())
282 return ME_INT_NONE;
283 p=c->prev(n);
284 }
285 assert((fst() != c) && (lst() != c));
286 assert((m >= c->min()) && (m <= c->max()));
287 holes += 1;
288 int c_min = c->min();
289 int c_max = c->max();
290 if ((c_min == m) && (c_max == m)) {
291 c->dispose(home);
292 p->next(c,n); n->prev(c,p);
293 } else if (c_min == m) {
294 c->min(m+1);
295 } else {
296 c->max(m-1);
297 if (c_max != m) {
298 RangeList* l = new (home) RangeList(m+1,c_max);
299 l->prevnext(c,n);
300 c->next(n,l);
301 n->prev(c,l);
302 }
303 }
304 }
305 IntDelta d(m,m);
306 return notify(home,me,d);
307 }
308
309
310
311 /*
312 * Copying variables
313 *
314 */
315
318 : IntVarImpBase(home,x), dom(x.dom.min(),x.dom.max()) {
319 holes = x.holes;
320 if (holes) {
321 int m = 1;
322 // Compute length
323 {
324 RangeList* s_p = x.fst();
325 RangeList* s_c = s_p->next(NULL);
326 do {
327 m++;
328 RangeList* s_n = s_c->next(s_p); s_p=s_c; s_c=s_n;
329 } while (s_c != NULL);
330 }
331 RangeList* d_c = home.alloc<RangeList>(m);
332 fst(d_c); lst(d_c+m-1);
333 d_c->min(x.fst()->min());
334 d_c->max(x.fst()->max());
335 d_c->prevnext(NULL,NULL);
336 RangeList* s_p = x.fst();
337 RangeList* s_c = s_p->next(NULL);
338 do {
339 RangeList* d_n = d_c + 1;
340 d_c->next(NULL,d_n);
341 d_n->prevnext(d_c,NULL);
342 d_n->min(s_c->min()); d_n->max(s_c->max());
343 d_c = d_n;
344 RangeList* s_n=s_c->next(s_p); s_p=s_c; s_c=s_n;
345 } while (s_c != NULL);
346 d_c->next(NULL,NULL);
347 } else {
348 fst(NULL);
349 }
350 }
351
352 IntVarImp*
353 IntVarImp::perform_copy(Space& home) {
354 return new (home) IntVarImp(home,*this);
355 }
356
357 /*
358 * Dependencies
359 *
360 */
361 void
363 bool schedule) {
365 }
366
367 void
371
372 void
373 IntVarImp::subscribe(Space& home, Advisor& a, bool fail) {
375 }
376
377}}
378
379// STATISTICS: int-var
NNF * l
Left subtree.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for advisors.
Definition core.hpp:1292
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Base-class for Int-variable implementations.
Definition var-imp.hpp:47
void subscribe(Gecode::Space &home, Gecode::Propagator &p, Gecode::PropCond pc, bool assigned, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition var-imp.hpp:243
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition var-imp.hpp:252
void reschedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::PropCond pc, bool assigned)
Re-schedule propagator p.
Definition var-imp.hpp:256
Gecode::ModEvent notify(Gecode::Space &home, Gecode::ModEvent me, Gecode::Delta &d)
Notify that variable implementation has been modified with modification event me and delta informatio...
Definition var-imp.hpp:261
Lists of ranges (intervals)
Definition var-imp.hpp:102
int min(void) const
Return minimum.
Definition int.hpp:98
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition int.hpp:70
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition int.hpp:66
RangeList * next(const RangeList *p) const
Return next element (from previous p)
Definition int.hpp:62
int max(void) const
Return maximum.
Definition int.hpp:102
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition int.hpp:134
Integer variable implementation.
Definition var-imp.hpp:89
RangeList * lst(void) const
Return last element of rangelist.
Definition int.hpp:173
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition int.cpp:46
bool assigned(void) const
Test whether variable is assigned.
Definition int.hpp:242
int max(void) const
Return maximum of domain.
Definition int.hpp:228
RangeList * fst(void) const
Return first element of rangelist.
Definition int.hpp:163
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition int.cpp:362
unsigned int size(void) const
Return size (cardinality) of domain.
Definition int.hpp:253
int min(void) const
Return minimum of domain.
Definition int.hpp:224
RangeList dom
Domain information.
Definition var-imp.hpp:188
unsigned int holes
Size of holes in the domain.
Definition var-imp.hpp:200
bool range(void) const
Test whether domain is a range.
Definition int.hpp:238
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition int.cpp:317
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p.
Definition int.cpp:368
Base-class for propagators.
Definition core.hpp:1064
Lists of ranges (intervals)
Computation spaces.
Definition core.hpp:1742
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4270
VarImp< Gecode::Int::IntVarImpConf > * next
Definition core.hpp:275
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition var-type.hpp:65
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:54
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
Gecode::FloatVal c(-8, 8)
Gecode::IntSet d(v, 7)
#define forceinline
Definition config.hpp:187