Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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 
36 namespace 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 
86  ModEvent
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 
120  ModEvent
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 
154  ModEvent
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 
179  ModEvent
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
369  IntVarImpBase::reschedule(home,p,pc,dom.min()==dom.max());
370  }
371 
372  void
373  IntVarImp::subscribe(Space& home, Advisor& a, bool fail) {
375  }
376 
377 }}
378 
379 // STATISTICS: int-var
int max(void) const
Return maximum.
Definition: int.hpp:102
Post propagator for SetVar x
Definition: set.hh:767
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
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:386
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:173
int min(void) const
Return minimum of domain.
Definition: int.hpp:224
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: int.hpp:134
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition: int.hpp:70
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:398
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4570
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:238
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
Computation spaces.
Definition: core.hpp:1742
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:242
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: int.cpp:362
Integer variable implementation.
Definition: var-imp.hpp:89
RangeList * next(const RangeList *p) const
Return next element (from previous p)
Definition: int.hpp:62
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:46
Gecode toplevel namespace
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:163
Base-class for propagators.
Definition: core.hpp:1064
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:66
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition: var-type.hpp:65
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
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
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:200
void min(Home home, SetVar s, IntVar x, Reify r)
Definition: int.cpp:241
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition: var-imp.hpp:252
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p.
Definition: int.cpp:368
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int ModEvent
Type for modification events.
Definition: core.hpp:62
RangeList dom
Domain information.
Definition: var-imp.hpp:188
VarImp< Gecode::Int::IntVarImpConf > * next
During cloning, points to the next copied variable.
Definition: core.hpp:275
void max(Home home, SetVar s, IntVar x, Reify r)
Definition: int.cpp:273
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:253
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Gecode::IntSet d(v, 7)
Base-class for advisors.
Definition: core.hpp:1292
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4270
#define forceinline
Definition: config.hpp:192
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Lists of ranges (intervals)
Definition: range-list.hpp:49
void reschedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::PropCond pc, bool assigned)
Re-schedule propagator p.
Definition: var-imp.hpp:256
Gecode::IntArgs i({1, 2, 3, 4})
int min(void) const
Return minimum.
Definition: int.hpp:98
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
Lists of ranges (intervals)
Definition: var-imp.hpp:102
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:317
int max(void) const
Return maximum of domain.
Definition: int.hpp:228