Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/int.hh>
39 
40 namespace Gecode { namespace Int {
41 
42  forceinline bool
43  IntVarImp::closer_min(int n) const {
44  unsigned int l = static_cast<unsigned int>(n - dom.min());
45  unsigned int r = static_cast<unsigned int>(dom.max() - n);
46  return l < r;
47  }
48 
49  int
50  IntVarImp::med(void) const {
51  // Computes the median
52  if (fst() == NULL)
53  return (dom.min()+dom.max())/2 - ((dom.min()+dom.max())%2 < 0 ? 1 : 0);
54  unsigned int i = size() / 2;
55  if (size() % 2 == 0)
56  i--;
57  const RangeList* p = NULL;
58  const RangeList* c = fst();
59  while (i >= c->width()) {
60  i -= c->width();
61  const RangeList* n=c->next(p); p=c; c=n;
62  }
63  return c->min() + static_cast<int>(i);
64  }
65 
66  bool
67  IntVarImp::in_full(int m) const {
68  if (closer_min(m)) {
69  const RangeList* p = NULL;
70  const RangeList* c = fst();
71  while (m > c->max()) {
72  const RangeList* n=c->next(p); p=c; c=n;
73  }
74  return (m >= c->min());
75  } else {
76  const RangeList* n = NULL;
77  const RangeList* c = lst();
78  while (m < c->min()) {
79  const RangeList* p=c->prev(n); n=c; c=p;
80  }
81  return (m <= c->max());
82  }
83  }
84 
85  /*
86  * "Standard" tell operations
87  *
88  */
89 
90  ModEvent
91  IntVarImp::lq_full(Space& home, int m) {
92  assert((m >= dom.min()) && (m <= dom.max()));
93  int old_max = dom.max();
95  if (range()) { // Is already range...
96  dom.max(m);
97  if (assigned()) me = ME_INT_VAL;
98  } else if (m < fst()->next(NULL)->min()) { // Becomes range...
99  dom.max(std::min(m,fst()->max()));
100  fst()->dispose(home,NULL,lst());
101  fst(NULL); holes = 0;
102  if (assigned()) me = ME_INT_VAL;
103  } else { // Stays non-range...
104  RangeList* n = NULL;
105  RangeList* c = lst();
106  unsigned int h = 0;
107  while (m < c->min()) {
108  RangeList* p = c->prev(n); c->fix(n);
109  h += (c->min() - p->max() - 1);
110  n=c; c=p;
111  }
112  holes -= h;
113  int max_c = std::min(m,c->max());
114  dom.max(max_c); c->max(max_c);
115  if (c != lst()) {
116  n->dispose(home,lst());
117  c->next(n,NULL); lst(c);
118  }
119  }
120  IntDelta d(dom.max()+1,old_max);
121  return notify(home,me,d);
122  }
123 
124  ModEvent
125  IntVarImp::gq_full(Space& home, int m) {
126  assert((m >= dom.min()) && (m <= dom.max()));
127  int old_min = dom.min();
129  if (range()) { // Is already range...
130  dom.min(m);
131  if (assigned()) me = ME_INT_VAL;
132  } else if (m > lst()->prev(NULL)->max()) { // Becomes range...
133  dom.min(std::max(m,lst()->min()));
134  fst()->dispose(home,NULL,lst());
135  fst(NULL); holes = 0;
136  if (assigned()) me = ME_INT_VAL;
137  } else { // Stays non-range...
138  RangeList* p = NULL;
139  RangeList* c = fst();
140  unsigned int h = 0;
141  while (m > c->max()) {
142  RangeList* n = c->next(p); c->fix(n);
143  h += (n->min() - c->max() - 1);
144  p=c; c=n;
145  }
146  holes -= h;
147  int min_c = std::max(m,c->min());
148  dom.min(min_c); c->min(min_c);
149  if (c != fst()) {
150  fst()->dispose(home,p);
151  c->prev(p,NULL); fst(c);
152  }
153  }
154  IntDelta d(old_min,dom.min()-1);
155  return notify(home,me,d);
156  }
157 
158  ModEvent
159  IntVarImp::eq_full(Space& home, int m) {
160  dom.min(m); dom.max(m);
161  if (!range()) {
162  bool failed = false;
163  RangeList* p = NULL;
164  RangeList* c = fst();
165  while (m > c->max()) {
166  RangeList* n=c->next(p); c->fix(n); p=c; c=n;
167  }
168  if (m < c->min())
169  failed = true;
170  while (c != NULL) {
171  RangeList* n=c->next(p); c->fix(n); p=c; c=n;
172  }
173  assert(p == lst());
174  fst()->dispose(home,p);
175  fst(NULL); holes = 0;
176  if (failed)
177  return fail(home);
178  }
179  IntDelta d;
180  return notify(home,ME_INT_VAL,d);
181  }
182 
183  ModEvent
184  IntVarImp::nq_full(Space& home, int m) {
185  assert(!((m < dom.min()) || (m > dom.max())));
187  if (range()) {
188  if ((m == dom.min()) && (m == dom.max()))
189  return fail(home);
190  if (m == dom.min()) {
191  dom.min(m+1);
192  me = assigned() ? ME_INT_VAL : ME_INT_BND;
193  } else if (m == dom.max()) {
194  dom.max(m-1);
195  me = assigned() ? ME_INT_VAL : ME_INT_BND;
196  } else {
197  RangeList* f = new (home) RangeList(dom.min(),m-1);
198  RangeList* l = new (home) RangeList(m+1,dom.max());
199  f->prevnext(NULL,l);
200  l->prevnext(f,NULL);
201  fst(f); lst(l); holes = 1;
202  }
203  } else if (m < fst()->next(NULL)->min()) { // Concerns the first range...
204  int f_max = fst()->max();
205  if (m > f_max)
206  return ME_INT_NONE;
207  int f_min = dom.min();
208  if ((m == f_min) && (m == f_max)) {
209  RangeList* f_next = fst()->next(NULL);
210  dom.min(f_next->min());
211  if (f_next == lst()) { // Turns into range
212  // Works as at the ends there are only NULL pointers
213  fst()->dispose(home,f_next);
214  fst(NULL); holes = 0;
215  me = assigned() ? ME_INT_VAL : ME_INT_BND;
216  } else { // Remains non-range
217  f_next->prev(fst(),NULL);
218  fst()->dispose(home); fst(f_next);
219  holes -= dom.min() - f_min - 1;
220  me = ME_INT_BND;
221  }
222  } else if (m == f_min) {
223  dom.min(m+1); fst()->min(m+1);
224  me = ME_INT_BND;
225  } else if (m == f_max) {
226  fst()->max(m-1); holes += 1;
227  } else {
228  // Create new hole
229  RangeList* f = new (home) RangeList(f_min,m-1);
230  f->prevnext(NULL,fst());
231  fst()->min(m+1); fst()->prev(NULL,f);
232  fst(f); holes += 1;
233  }
234  } else if (m > lst()->prev(NULL)->max()) { // Concerns the last range...
235  int l_min = lst()->min();
236  if (m < l_min)
237  return ME_INT_NONE;
238  int l_max = dom.max();
239  if ((m == l_min) && (m == l_max)) {
240  RangeList* l_prev = lst()->prev(NULL);
241  dom.max(l_prev->max());
242  if (l_prev == fst()) {
243  // Turns into range
244  l_prev->dispose(home,lst());
245  fst(NULL); holes = 0;
246  me = assigned() ? ME_INT_VAL : ME_INT_BND;
247  } else { // Remains non-range
248  l_prev->next(lst(),NULL);
249  lst()->dispose(home); lst(l_prev);
250  holes -= l_max - dom.max() - 1;
251  me = ME_INT_BND;
252  }
253  } else if (m == l_max) {
254  dom.max(m-1); lst()->max(m-1);
255  me = ME_INT_BND;
256  } else if (m == l_min) {
257  lst()->min(m+1); holes += 1;
258  } else { // Create new hole
259  RangeList* l = new (home) RangeList(m+1,l_max);
260  l->prevnext(lst(),NULL);
261  lst()->max(m-1); lst()->next(NULL,l);
262  lst(l); holes += 1;
263  }
264  } else { // Concerns element in the middle of the list of ranges
265  RangeList* p;
266  RangeList* c;
267  RangeList* n;
268  if (closer_min(m)) {
269  assert(m > fst()->max());
270  p = NULL;
271  c = fst();
272  do {
273  n=c->next(p); p=c; c=n;
274  } while (m > c->max());
275  if (m < c->min())
276  return ME_INT_NONE;
277  n=c->next(p);
278  } else {
279  assert(m < lst()->min());
280  n = NULL;
281  c = lst();
282  do {
283  p=c->prev(n); n=c; c=p;
284  } while (m < c->min());
285  if (m > c->max())
286  return ME_INT_NONE;
287  p=c->prev(n);
288  }
289  assert((fst() != c) && (lst() != c));
290  assert((m >= c->min()) && (m <= c->max()));
291  holes += 1;
292  int c_min = c->min();
293  int c_max = c->max();
294  if ((c_min == m) && (c_max == m)) {
295  c->dispose(home);
296  p->next(c,n); n->prev(c,p);
297  } else if (c_min == m) {
298  c->min(m+1);
299  } else {
300  c->max(m-1);
301  if (c_max != m) {
302  RangeList* l = new (home) RangeList(m+1,c_max);
303  l->prevnext(c,n);
304  c->next(n,l);
305  n->prev(c,l);
306  }
307  }
308  }
309  IntDelta d(m,m);
310  return notify(home,me,d);
311  }
312 
313 
314 
315  /*
316  * Copying variables
317  *
318  */
319 
322  : IntVarImpBase(home,x), dom(x.dom.min(),x.dom.max()) {
323  holes = x.holes;
324  if (holes) {
325  int m = 1;
326  // Compute length
327  {
328  RangeList* s_p = x.fst();
329  RangeList* s_c = s_p->next(NULL);
330  do {
331  m++;
332  RangeList* s_n = s_c->next(s_p); s_p=s_c; s_c=s_n;
333  } while (s_c != NULL);
334  }
335  RangeList* d_c = home.alloc<RangeList>(m);
336  fst(d_c); lst(d_c+m-1);
337  d_c->min(x.fst()->min());
338  d_c->max(x.fst()->max());
339  d_c->prevnext(NULL,NULL);
340  RangeList* s_p = x.fst();
341  RangeList* s_c = s_p->next(NULL);
342  do {
343  RangeList* d_n = d_c + 1;
344  d_c->next(NULL,d_n);
345  d_n->prevnext(d_c,NULL);
346  d_n->min(s_c->min()); d_n->max(s_c->max());
347  d_c = d_n;
348  RangeList* s_n=s_c->next(s_p); s_p=s_c; s_c=s_n;
349  } while (s_c != NULL);
350  d_c->next(NULL,NULL);
351  } else {
352  fst(NULL);
353  }
354  }
355 
356  IntVarImp*
357  IntVarImp::perform_copy(Space& home) {
358  return new (home) IntVarImp(home,*this);
359  }
360 
361  /*
362  * Dependencies
363  *
364  */
365  void
367  bool schedule) {
369  }
370 
371  void
373  IntVarImpBase::reschedule(home,p,pc,dom.min()==dom.max());
374  }
375 
376  void
379  }
380 
381 }}
382 
383 // STATISTICS: int-var
RangeList * next(const RangeList *p) const
Return next element (from previous p)
Definition: int.hpp:66
int min(void) const
Return minimum.
Definition: int.hpp:102
int min(void) const
Return minimum of domain.
Definition: int.hpp:228
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:321
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: int.hpp:138
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:242
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition: int.hpp:88
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:70
void reschedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::PropCond pc, bool assigned)
Re-schedule propagator p.
Definition: var-imp.hpp:256
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: int.cpp:366
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:177
void max(Home home, SetVar s, IntVar x, Reify r)
Definition: int.cpp:277
int ModEvent
Type for modification events.
Definition: core.hpp:64
Base-class for propagators.
Definition: core.hpp:1016
Base-class for advisors.
Definition: core.hpp:1218
void min(Home home, SetVar s, IntVar x, Reify r)
Definition: int.cpp:245
#define forceinline
Definition: config.hpp:182
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Computation spaces.
Definition: core.hpp:1668
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:50
Gecode::IntSet d(v, 7)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2757
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:246
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition: var-imp.hpp:252
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4117
int max(void) const
Return maximum.
Definition: int.hpp:106
int PropCond
Type for propagation conditions.
Definition: core.hpp:74
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:167
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition: var-type.hpp:65
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
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: int.hpp:110
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:204
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p.
Definition: int.cpp:372
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
Integer delta information for advisors.
Definition: var-imp.hpp:55
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Integer variable implementation.
Definition: var-imp.hpp:93
RangeList dom
Domain information.
Definition: var-imp.hpp:192
Lists of ranges (intervals)
Definition: var-imp.hpp:106
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition: int.hpp:74
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4417
Post propagator for SetVar x
Definition: set.hh:769
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:257
Gecode toplevel namespace
VarImp * next(void) const
Return next copied variable.
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
int max(void) const
Return maximum of domain.
Definition: int.hpp:232
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