← Back to branch summary

~ubuntu-branches/ubuntu/natty/gecode/natty

« back to all changes in this revision

Viewing changes to int/var/imp.icc

  • Committer: Bazaar Package Importer
  • Author(s): Kari Pahula
  • Date: 2005-12-24 07:51:25 UTC
  • Revision ID: james.westby@ubuntu.com-20051224075125-klkiqofvbfvusfvt
Tags: upstream-1.0.0.dfsg.1
Import upstream version 1.0.0.dfsg.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
int/var/imp.icc
 
1
/*
 
2
 *  Main authors:
 
3
 *     Christian Schulte <schulte@gecode.org>
 
4
 *
 
5
 *  Contributing authors:
 
6
 *     Guido Tack <tack@gecode.org>
 
7
 *
 
8
 *  Copyright:
 
9
 *     Christian Schulte, 2003
 
10
 *     Guido Tack, 2004
 
11
 *
 
12
 *  Last modified:
 
13
 *     $Date: 2005-10-31 11:02:00 +0100 (Mon, 31 Oct 2005) $ by $Author: schulte $
 
14
 *     $Revision: 2428 $
 
15
 *
 
16
 *  This file is part of Gecode, the generic constraint
 
17
 *  development environment:
 
18
 *     http://www.gecode.org
 
19
 *
 
20
 *  See the file "LICENSE" for information on usage and
 
21
 *  redistribution of this file, and for a
 
22
 *     DISCLAIMER OF ALL WARRANTIES.
 
23
 *
 
24
 */
 
25
 
 
26
namespace Gecode { namespace Int {
 
27
 
 
28
  /*
 
29
   * Range lists
 
30
   *
 
31
   */
 
32
 
 
33
#define RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
 
34
#define PD2RL(p) reinterpret_cast<RangeList*>(p)
 
35
 
 
36
  forceinline
 
37
  IntVarImp::RangeList::RangeList(void) {}
 
38
 
 
39
  forceinline
 
40
  IntVarImp::RangeList::RangeList(int min, int max)
 
41
    : _min(min), _max(max) {}
 
42
 
 
43
  forceinline
 
44
  IntVarImp::RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
 
45
    : _min(min), _max(max) {
 
46
    _next = PD2RL(RL2PD(p)^RL2PD(n)); 
 
47
  }
 
48
 
 
49
  forceinline IntVarImp::RangeList*
 
50
  IntVarImp::RangeList::next(const RangeList* p) const {
 
51
    return PD2RL(RL2PD(_next)^RL2PD(p));
 
52
  }
 
53
  forceinline IntVarImp::RangeList*
 
54
  IntVarImp::RangeList::prev(const RangeList* n) const {
 
55
    return PD2RL(RL2PD(_next)^RL2PD(n));
 
56
  }
 
57
  forceinline void
 
58
  IntVarImp::RangeList::prevnext(RangeList* p, RangeList* n) {
 
59
    _next = PD2RL(RL2PD(p)^RL2PD(n));
 
60
  }
 
61
  forceinline void
 
62
  IntVarImp::RangeList::next(RangeList* o, RangeList* n) {
 
63
    _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
 
64
  }
 
65
  forceinline void
 
66
  IntVarImp::RangeList::prev(RangeList* o, RangeList* n) {
 
67
    _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
 
68
  }
 
69
  forceinline void
 
70
  IntVarImp::RangeList::fix(RangeList* n) {
 
71
    _next = n;
 
72
  }
 
73
 
 
74
  forceinline void
 
75
  IntVarImp::RangeList::min(int n) {
 
76
    _min = n;
 
77
  }
 
78
  forceinline void
 
79
  IntVarImp::RangeList::max(int n) {
 
80
    _max = n;
 
81
  }
 
82
 
 
83
  forceinline int
 
84
  IntVarImp::RangeList::min(void) const {
 
85
    return _min;
 
86
  }
 
87
  forceinline int
 
88
  IntVarImp::RangeList::max(void) const {
 
89
    return _max;
 
90
  }
 
91
  forceinline unsigned int
 
92
  IntVarImp::RangeList::width(void) const {
 
93
    return _max - _min + 1;
 
94
  }
 
95
 
 
96
 
 
97
  forceinline void
 
98
  IntVarImp::RangeList::operator delete(void*) {}
 
99
 
 
100
  forceinline void
 
101
  IntVarImp::RangeList::operator delete(void*, Space*) {
 
102
    assert(false);
 
103
  }
 
104
 
 
105
  forceinline void*
 
106
  IntVarImp::RangeList::operator new(size_t s, Space* home) {
 
107
    assert(s == sizeof(RangeList));
 
108
    return home->fl_alloc<sizeof(RangeList)>();
 
109
  }
 
110
 
 
111
  forceinline void
 
112
  IntVarImp::RangeList::dispose(Space* home, RangeList* p, RangeList* l) {
 
113
    RangeList* c = this;
 
114
    while (c != l) {
 
115
      RangeList* n = c->next(p);
 
116
      c->fix(n);
 
117
      p=c; c=n;
 
118
    }
 
119
    home->fl_dispose<sizeof(RangeList)>(this,l);
 
120
  }
 
121
 
 
122
  forceinline void
 
123
  IntVarImp::RangeList::dispose(Space* home, RangeList* l) {
 
124
    home->fl_dispose<sizeof(RangeList)>(this,l);
 
125
  }
 
126
 
 
127
  forceinline void
 
128
  IntVarImp::RangeList::dispose(Space* home) {
 
129
    home->fl_dispose<sizeof(RangeList)>(this,this);
 
130
  }
 
131
 
 
132
#undef RL2PD
 
133
#undef PD2RL
 
134
 
 
135
  /*
 
136
   * Mainitaining range lists for variable domain
 
137
   *
 
138
   */
 
139
 
 
140
  forceinline IntVarImp::RangeList*
 
141
  IntVarImp::fst(void) const {
 
142
    return dom.next(NULL);
 
143
  }
 
144
 
 
145
  forceinline void
 
146
  IntVarImp::fst(IntVarImp::RangeList* f) {
 
147
    dom.prevnext(NULL,f);
 
148
  }
 
149
 
 
150
  forceinline IntVarImp::RangeList*
 
151
  IntVarImp::lst(void) const {
 
152
    return _lst;
 
153
  }
 
154
 
 
155
  forceinline void
 
156
  IntVarImp::lst(IntVarImp::RangeList* l) {
 
157
    _lst = l;
 
158
  }
 
159
 
 
160
  /*
 
161
   * Creation of new variable implementations
 
162
   *
 
163
   */
 
164
 
 
165
  forceinline
 
166
  IntVarImp::IntVarImp(Space* home, int min, int max)
 
167
    : Variable<VTI_INT,PC_INT_DOM>(home),
 
168
      dom(min,max,NULL,NULL), holes(0) {}
 
169
 
 
170
  forceinline
 
171
  IntVarImp::IntVarImp(Space* home, const IntSet& d)
 
172
    : Variable<VTI_INT,PC_INT_DOM>(home),
 
173
      dom(d.min(),d.max()) {
 
174
    if (d.size() > 1) {
 
175
      int n = d.size();
 
176
      RangeList* r = reinterpret_cast<RangeList*>
 
177
        (home->alloc(sizeof(RangeList)*n));
 
178
      fst(r); lst(r+n-1);
 
179
      unsigned int h = d.max()-d.min()+1;
 
180
      for (int i = n; i--; ) {
 
181
        h -= d.width(i);
 
182
        r[i].min(d.min(i)); r[i].max(d.max(i));
 
183
        r[i].prevnext(&r[i-1],&r[i+1]);
 
184
      }
 
185
      r[0].prev(&r[-1],NULL); 
 
186
      r[n-1].next(&r[n],NULL);
 
187
      holes = h;
 
188
    } else {
 
189
      fst(NULL); holes = 0;
 
190
    }
 
191
  }
 
192
 
 
193
 
 
194
  /*
 
195
   * Operations on integer variable implementations
 
196
   *
 
197
   */
 
198
 
 
199
  forceinline int
 
200
  IntVarImp::min(void) const {
 
201
    return dom.min();
 
202
  }
 
203
  forceinline int
 
204
  IntVarImp::max(void) const {
 
205
    return dom.max();
 
206
  }
 
207
  forceinline int
 
208
  IntVarImp::val(void) const {
 
209
    assert(dom.min() == dom.max());
 
210
    return dom.min();
 
211
  }
 
212
 
 
213
  forceinline bool
 
214
  IntVarImp::range(void) const {
 
215
    return fst() == NULL;
 
216
  }
 
217
  forceinline bool
 
218
  IntVarImp::assigned(void) const {
 
219
    return dom.min() == dom.max();
 
220
  }
 
221
 
 
222
 
 
223
  forceinline unsigned int
 
224
  IntVarImp::width(void) const {
 
225
    return dom.width();
 
226
  }
 
227
 
 
228
  forceinline unsigned int
 
229
  IntVarImp::size(void) const {
 
230
    return dom.width() - holes;
 
231
  }
 
232
 
 
233
  forceinline unsigned int
 
234
  IntVarImp::regret_min(void) const {
 
235
    if (fst() == NULL) {
 
236
      return (dom.min() == dom.max()) ? 0 : 1;
 
237
    } else if (dom.min() == fst()->max()) {
 
238
      return fst()->next(NULL)->min()-dom.min();
 
239
    } else {
 
240
      return 1;
 
241
    }
 
242
  }
 
243
  forceinline unsigned int
 
244
  IntVarImp::regret_max(void) const {
 
245
    if (lst() == NULL) {
 
246
      return (dom.min() == dom.max()) ? 0 : 1;
 
247
    } else if (dom.max() == lst()->min()) {
 
248
      return dom.max()-lst()->prev(NULL)->max();
 
249
    } else {
 
250
      return 1;
 
251
    }
 
252
  }
 
253
 
 
254
 
 
255
 
 
256
  /*
 
257
   * Tests
 
258
   *
 
259
   */
 
260
 
 
261
  forceinline bool
 
262
  IntVarImp::in(int n) const {
 
263
    if ((n < dom.min()) || (n > dom.max()))
 
264
      return false;
 
265
    return (fst() == NULL) || in_full(n);
 
266
  }
 
267
  forceinline bool
 
268
  IntVarImp::in(double n) const {
 
269
    if ((n < dom.min()) || (n > dom.max()))
 
270
      return false;
 
271
    return (fst() == NULL) || in_full(static_cast<int>(n));
 
272
  }
 
273
 
 
274
 
 
275
  /*
 
276
   * Accessing rangelists for iteration
 
277
   *
 
278
   */
 
279
 
 
280
  forceinline const IntVarImp::RangeList*
 
281
  IntVarImp::ranges_fwd(void) const {
 
282
    return (fst() == NULL) ? &dom : fst();
 
283
  }
 
284
 
 
285
  forceinline const IntVarImp::RangeList*
 
286
  IntVarImp::ranges_bwd(void) const {
 
287
    return (fst() == NULL) ? &dom : lst();
 
288
  }
 
289
 
 
290
 
 
291
 
 
292
  /*
 
293
   * Tell operations (to be inlined: performing bounds checks first)
 
294
   *
 
295
   */
 
296
 
 
297
  forceinline ModEvent
 
298
  IntVarImp::gq(Space* home, int n) {
 
299
    if (n <= dom.min()) return ME_INT_NONE;
 
300
    if (n > dom.max())  return ME_INT_FAILED;
 
301
    gq_full(home,n);
 
302
    if (assigned())
 
303
      return ME_INT_VAL;
 
304
    return ME_INT_BND;
 
305
  }
 
306
  forceinline ModEvent
 
307
  IntVarImp::gq(Space* home, double n) {
 
308
    if (n <= dom.min()) return ME_INT_NONE;
 
309
    if (n > dom.max())  return ME_INT_FAILED;
 
310
    gq_full(home,static_cast<int>(n));
 
311
    if (assigned())
 
312
      return ME_INT_VAL;
 
313
    return ME_INT_BND;
 
314
  }
 
315
 
 
316
 
 
317
  forceinline ModEvent
 
318
  IntVarImp::lq(Space* home, int n) {
 
319
    if (n >= dom.max()) return ME_INT_NONE;
 
320
    if (n < dom.min())  return ME_INT_FAILED;
 
321
    lq_full(home,n);
 
322
    if (dom.min() == n)
 
323
      return ME_INT_VAL;
 
324
    return ME_INT_BND;
 
325
  }
 
326
  forceinline ModEvent
 
327
  IntVarImp::lq(Space* home, double n) {
 
328
    if (n >= dom.max()) return ME_INT_NONE;
 
329
    if (n < dom.min())  return ME_INT_FAILED;
 
330
    lq_full(home,static_cast<int>(n));
 
331
    if (dom.max() == n)
 
332
      return ME_INT_VAL;
 
333
    return ME_INT_BND;
 
334
  }
 
335
 
 
336
 
 
337
  forceinline ModEvent
 
338
  IntVarImp::eq(Space* home, int n) {
 
339
    if ((n < dom.min()) || (n > dom.max())) 
 
340
      return ME_INT_FAILED;
 
341
    if ((n == dom.min()) && (n == dom.max()))
 
342
      return ME_INT_NONE;
 
343
    eq_full(home,n);
 
344
    if (dom.min() == Limits::Int::int_max+1)
 
345
      return ME_INT_FAILED;
 
346
    return ME_INT_VAL;
 
347
  }
 
348
  forceinline ModEvent
 
349
  IntVarImp::eq(Space* home, double n) {
 
350
    if ((n < dom.min()) || (n > dom.max())) 
 
351
      return ME_INT_FAILED;
 
352
    if ((n == dom.min()) && (n == dom.max()))
 
353
      return ME_INT_NONE;
 
354
    eq_full(home,static_cast<int>(n));
 
355
    if (dom.min() == Limits::Int::int_max+1)
 
356
      return ME_INT_FAILED;
 
357
    return ME_INT_VAL;
 
358
  }
 
359
 
 
360
 
 
361
  forceinline ModEvent
 
362
  IntVarImp::nq(Space* home, int n) {
 
363
    if ((n < dom.min()) || (n > dom.max())) return ME_INT_NONE;
 
364
    return nq_full(home,n);
 
365
  }
 
366
  forceinline ModEvent
 
367
  IntVarImp::nq(Space* home, double d) {
 
368
    if ((d < dom.min()) || (d > dom.max())) return ME_INT_NONE;
 
369
    return nq_full(home,static_cast<int>(d));
 
370
  }
 
371
 
 
372
 
 
373
  /*
 
374
   * Tell operations with respect to iterators
 
375
   *
 
376
   */
 
377
 
 
378
  template <class I>
 
379
  forceinline ModEvent
 
380
  IntVarImp::narrow(Space* home, I& ri) {
 
381
    // Is new domain empty?
 
382
    if (!ri())
 
383
      return ME_INT_FAILED;
 
384
    int min0 = ri.min();
 
385
    int max0 = ri.max();
 
386
    ++ri;
 
387
    // Is new domain range?
 
388
    if (!ri()) {
 
389
      // Remove possible rangelist (if it was not a range, the domain
 
390
      // must have been narrowed!)
 
391
      if (fst()) {
 
392
        fst()->dispose(home,NULL,lst());
 
393
        fst(NULL); holes = 0;
 
394
      }
 
395
      const int min1 = dom.min(); dom.min(min0);
 
396
      const int max1 = dom.max(); dom.max(max0);
 
397
      if ((min0 == min1) && (max0 == max1))
 
398
        return ME_INT_NONE;
 
399
      if (min0 == max0) {
 
400
        notify(home,ME_INT_VAL);
 
401
        return ME_INT_VAL;
 
402
      }
 
403
    } else {
 
404
      // Construct new rangelist
 
405
      RangeList*   f = new (home) RangeList(min0,max0,NULL,NULL);
 
406
      RangeList*   l = f;
 
407
      unsigned int s = max0-min0+1;
 
408
      do {
 
409
        RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
 
410
        l->next(NULL,n);
 
411
        l = n;
 
412
        s += ri.width();
 
413
        ++ri;
 
414
      } while (ri());
 
415
      if (fst() != NULL)
 
416
        fst()->dispose(home,NULL,lst());
 
417
      fst(f); lst(l);
 
418
      // Check for modification
 
419
      if (size() == s)
 
420
        return ME_INT_NONE;
 
421
      const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
 
422
      const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
 
423
      holes = width() - s;
 
424
      if ((min0 == min1) && (max0 == max1)) {
 
425
        notify(home,ME_INT_DOM);
 
426
        return ME_INT_DOM;
 
427
      }
 
428
    }
 
429
    notify(home,ME_INT_BND);
 
430
    return ME_INT_BND;
 
431
  }
 
432
 
 
433
  /*
 
434
   * Copying a variable
 
435
   *
 
436
   */
 
437
 
 
438
  forceinline IntVarImp*
 
439
  IntVarImp::copy(Space* home, bool share) {
 
440
    return copied() ? static_cast<IntVarImp*>(forward())
 
441
      : perform_copy(home,share);
 
442
  }
 
443
 
 
444
 
 
445
 
 
446
  /*
 
447
   * Boolean tell operations (assume not yet assigned 0/1 variable)
 
448
   *
 
449
   */
 
450
 
 
451
  forceinline void
 
452
  IntVarImp::t_zero_none(Space* home) {
 
453
    assert((dom.min() == 0) && (dom.max() == 1));
 
454
    dom.max(0);
 
455
    notify_unmodified(home,ME_INT_VAL);
 
456
  }
 
457
 
 
458
  forceinline void
 
459
  IntVarImp::t_one_none(Space* home) {
 
460
    assert((dom.min() == 0) && (dom.max() == 1));
 
461
    dom.min(1);
 
462
    notify_unmodified(home,ME_INT_VAL);
 
463
  }
 
464
 
 
465
 
 
466
  /*
 
467
   * Forward range iterator for rangelists
 
468
   *
 
469
   */
 
470
 
 
471
  forceinline
 
472
  IntVarImpFwd::IntVarImpFwd(void) {}
 
473
  forceinline
 
474
  IntVarImpFwd::IntVarImpFwd(const IntVarImp* x) 
 
475
    : p(NULL), c(x->ranges_fwd()) {}
 
476
  forceinline void
 
477
  IntVarImpFwd::init(const IntVarImp* x) {
 
478
    p=NULL; c=x->ranges_fwd();
 
479
  }
 
480
 
 
481
  forceinline bool
 
482
  IntVarImpFwd::operator()(void) const {
 
483
    return c != NULL;
 
484
  }
 
485
  forceinline void
 
486
  IntVarImpFwd::operator++(void) {
 
487
    const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
 
488
  }
 
489
 
 
490
  forceinline int
 
491
  IntVarImpFwd::min(void) const {
 
492
    return c->min();
 
493
  }
 
494
  forceinline int
 
495
  IntVarImpFwd::max(void) const {
 
496
    return c->max();
 
497
  }
 
498
  forceinline unsigned int
 
499
  IntVarImpFwd::width(void) const {
 
500
    return c->width();
 
501
  }
 
502
 
 
503
 
 
504
  /*
 
505
   * Backward range iterator for rangelists
 
506
   *
 
507
   */
 
508
 
 
509
  forceinline
 
510
  IntVarImpBwd::IntVarImpBwd(void) {}
 
511
  forceinline
 
512
  IntVarImpBwd::IntVarImpBwd(const IntVarImp* x) 
 
513
    : n(NULL), c(x->ranges_bwd()) {}
 
514
  forceinline void
 
515
  IntVarImpBwd::init(const IntVarImp* x) {
 
516
    n=NULL; c=x->ranges_bwd();
 
517
  }
 
518
 
 
519
  forceinline bool
 
520
  IntVarImpBwd::operator()(void) const {
 
521
    return c != NULL;
 
522
  }
 
523
  forceinline void
 
524
  IntVarImpBwd::operator++(void) {
 
525
    const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
 
526
  }
 
527
 
 
528
  forceinline int
 
529
  IntVarImpBwd::min(void) const {
 
530
    return c->min();
 
531
  }
 
532
  forceinline int
 
533
  IntVarImpBwd::max(void) const {
 
534
    return c->max();
 
535
  }
 
536
  forceinline unsigned int
 
537
  IntVarImpBwd::width(void) const {
 
538
    return c->width();
 
539
  }
 
540
 
 
541
 
 
542
  /*
 
543
   * More domain operations
 
544
   *
 
545
   */
 
546
  template <class I>
 
547
  forceinline ModEvent
 
548
  IntVarImp::inter(Space* home, I& i) {
 
549
    IntVarImpFwd j(this);
 
550
    Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
 
551
    return narrow(home,ij);
 
552
  }
 
553
 
 
554
  template <class I>
 
555
  forceinline ModEvent
 
556
  IntVarImp::minus(Space* home, I& i) {
 
557
    IntVarImpFwd j(this);
 
558
    Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
 
559
    return narrow(home,ij);
 
560
  }
 
561
 
 
562
}}
 
563
 
 
564
// STATISTICS: int-var
 
565