this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Copyright:
7 * Guido Tack, 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 Set {
35
36 /**
37 * \brief %Range iterator for a two-dimensional array
38 * \ingroup TaskActorSetView
39 */
40 class ArrayRanges {
41 private:
42 int *_ranges;
43 int _size;
44 int _pos;
45 public:
46 /// \name Constructors and initialization
47 //@{
48 /// Default constructor
49 ArrayRanges(void) : _ranges(nullptr), _size(0), _pos(0) {}
50 /// Initialize with ranges for array \a ranges which is of size \a size
51 ArrayRanges(int *ranges, int size)
52 : _ranges(ranges), _size(size), _pos(0) {}
53 /// Initialize with ranges for array \a ranges which is of size \a size
54 void init(int* ranges, int size) {
55 _ranges = ranges; _size = size; _pos = 0;
56 }
57 //@}
58
59 /// \name Iteration control
60 //@{
61 /// Test whether iterator is still at a range or done
62 bool operator ()(void) const { return _pos<_size; }
63 /// Move iterator to next range (if possible)
64 void operator ++(void) { _pos++; }
65 //@}
66
67 /// \name Range access
68 //@{
69 /// Return smallest value of range
70 int min(void) const { return _ranges[_pos*2]; }
71 /// Return largest value of range
72 int max(void) const { return _ranges[_pos*2+1]; }
73 /// Return width of range (distance between minimum and maximum)
74 unsigned int width(void) const {
75 return static_cast<unsigned int>(_ranges[_pos*2+1]-_ranges[_pos*2]+1);
76 }
77 //@}
78 };
79
80 forceinline
81 ConstSetView::ConstSetView(void) : ranges(nullptr), size(0), domSize(0) {}
82
83 forceinline
84 ConstSetView::ConstSetView(Space& home, const IntSet& dom) {
85 size = dom.ranges();
86 domSize = 0;
87 if (size > 0) {
88 ranges = home.alloc<int>(2*size);
89 IntSetRanges dr(dom);
90 for (int i=0; dr(); ++dr, i+=2) {
91 int min = dr.min(); int max = dr.max();
92 ranges[i] = min;
93 ranges[i+1] = max;
94 domSize += static_cast<unsigned int>(max-min+1);
95 }
96 } else {
97 ranges = nullptr;
98 }
99 }
100
101 forceinline unsigned int
102 ConstSetView::glbSize(void) const { return domSize; }
103
104 forceinline unsigned int
105 ConstSetView::lubSize(void) const { return domSize; }
106
107 forceinline unsigned int
108 ConstSetView::unknownSize(void) const { return 0; }
109
110 forceinline bool
111 ConstSetView::contains(int i) const {
112 for (int j=size; j--; ) {
113 if (ranges[2*j+1] < i)
114 return false;
115 if (ranges[2*j] >= i)
116 return true;
117 }
118 return false;
119 }
120
121 forceinline bool
122 ConstSetView::notContains(int i) const {
123 return !contains(i);
124 }
125
126 forceinline unsigned int
127 ConstSetView::cardMin(void) const { return domSize; }
128
129 forceinline unsigned int
130 ConstSetView::cardMax(void) const { return domSize; }
131
132 forceinline int
133 ConstSetView::lubMin(void) const {
134 return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0];
135 }
136
137 forceinline int
138 ConstSetView::lubMax(void) const {
139 return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1];
140 }
141
142 forceinline int
143 ConstSetView::glbMin(void) const { return lubMin(); }
144
145 forceinline int
146 ConstSetView::glbMax(void) const { return lubMax(); }
147
148 forceinline ModEvent
149 ConstSetView::cardMin(Space&,unsigned int c) {
150 return c<=domSize ? ME_SET_NONE : ME_SET_FAILED;
151 }
152
153 forceinline ModEvent
154 ConstSetView::cardMax(Space&,unsigned int c) {
155 return c>=domSize ? ME_SET_NONE : ME_SET_FAILED;
156 }
157
158 forceinline ModEvent
159 ConstSetView::include(Space&,int c) {
160 return contains(c) ? ME_SET_NONE : ME_SET_FAILED;
161 }
162
163 forceinline ModEvent
164 ConstSetView::exclude(Space&,int c) {
165 return contains(c) ? ME_SET_FAILED : ME_SET_NONE;
166 }
167
168 forceinline ModEvent
169 ConstSetView::intersect(Space&,int c) {
170 return (size==0 ||
171 (size==1 &&
172 ranges[0]==ranges[1] && ranges[0]==c)) ?
173 ME_SET_NONE : ME_SET_FAILED;
174 }
175
176 forceinline ModEvent
177 ConstSetView::intersect(Space&,int i,int j) {
178 return (glbMin()>=i && glbMax()<=j) ?
179 ME_SET_NONE : ME_SET_FAILED;
180 }
181
182 forceinline ModEvent
183 ConstSetView::include(Space&,int i,int j) {
184 Iter::Ranges::Singleton single(i,j);
185 ArrayRanges ar(ranges, size);
186 return (single() && Iter::Ranges::subset(single, ar)) ?
187 ME_SET_NONE : ME_SET_FAILED;
188 }
189
190 forceinline ModEvent
191 ConstSetView::exclude(Space&,int i,int j) {
192 Iter::Ranges::Singleton single(i,j);
193 ArrayRanges ar(ranges, size);
194 return (single() && Iter::Ranges::subset(single, ar)) ?
195 ME_SET_FAILED : ME_SET_NONE;
196 }
197
198 template<class I> ModEvent
199 ConstSetView::excludeI(Space&,I& i) {
200 ArrayRanges ar(ranges, size);
201 return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE;
202 }
203
204 template<class I> ModEvent
205 ConstSetView::includeI(Space&,I& i) {
206 ArrayRanges ar(ranges, size);
207 return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED;
208 }
209
210 template<class I> ModEvent
211 ConstSetView::intersectI(Space&,I& i) {
212 ArrayRanges ar(ranges, size);
213 return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED;
214 }
215
216 forceinline void
217 ConstSetView::update(Space& home, ConstSetView& p) {
218 ConstView<SetView>::update(home,p);
219 // dispose old ranges
220 if (size > 0)
221 home.free<int>(ranges, 2);
222
223 domSize = p.domSize;
224 size = p.size;
225 if (size == 0) {
226 ranges = nullptr;
227 } else {
228 // copy ranges from p
229 ranges = home.alloc<int>(2*size);
230 for (int i=size; i--; ) {
231 ranges[2*i] = p.ranges[2*i];
232 ranges[2*i+1] = p.ranges[2*i+1];
233 }
234 }
235 }
236
237
238 /*
239 * Delta information for advisors
240 *
241 */
242 forceinline int
243 ConstSetView::glbMin(const Delta&) const {
244 GECODE_NEVER;
245 return 0;
246 }
247 forceinline int
248 ConstSetView::glbMax(const Delta&) const {
249 GECODE_NEVER;
250 return 0;
251 }
252 forceinline bool
253 ConstSetView::glbAny(const Delta&) const {
254 GECODE_NEVER;
255 return false;
256 }
257 forceinline int
258 ConstSetView::lubMin(const Delta&) const {
259 GECODE_NEVER;
260 return 0;
261 }
262 forceinline int
263 ConstSetView::lubMax(const Delta&) const {
264 GECODE_NEVER;
265 return 0;
266 }
267 forceinline bool
268 ConstSetView::lubAny(const Delta&) const {
269 GECODE_NEVER;
270 return false;
271 }
272
273 forceinline
274 EmptyView::EmptyView(void) {}
275
276
277
278 forceinline unsigned int
279 EmptyView::glbSize(void) const { return 0; }
280
281 forceinline unsigned int
282 EmptyView::lubSize(void) const { return 0; }
283
284 forceinline unsigned int
285 EmptyView::unknownSize(void) const { return 0; }
286
287 forceinline bool
288 EmptyView::contains(int) const { return false; }
289
290 forceinline bool
291 EmptyView::notContains(int) const { return true; }
292
293 forceinline unsigned int
294 EmptyView::cardMin(void) const { return 0; }
295
296 forceinline unsigned int
297 EmptyView::cardMax(void) const { return 0; }
298
299 forceinline int
300 EmptyView::lubMin(void) const { return 0; }
301
302 forceinline int
303 EmptyView::lubMax(void) const { return 0; }
304
305 forceinline int
306 EmptyView::glbMin(void) const { return 0; }
307
308 forceinline int
309 EmptyView::glbMax(void) const { return 0; }
310
311 forceinline ModEvent
312 EmptyView::cardMin(Space&,unsigned int c) {
313 return c==0 ? ME_SET_NONE : ME_SET_FAILED;
314 }
315
316 forceinline ModEvent
317 EmptyView::cardMax(Space&,unsigned int) {
318 return ME_SET_NONE;
319 }
320
321
322 forceinline ModEvent
323 EmptyView::include(Space&,int) {
324 return ME_SET_FAILED;
325 }
326
327 forceinline ModEvent
328 EmptyView::exclude(Space&,int) { return ME_SET_NONE; }
329
330 forceinline ModEvent
331 EmptyView::intersect(Space&,int) { return ME_SET_NONE; }
332
333 forceinline ModEvent
334 EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; }
335
336 forceinline ModEvent
337 EmptyView::include(Space&,int,int) {
338 return ME_SET_FAILED; }
339
340 forceinline ModEvent
341 EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; }
342
343 template<class I> ModEvent
344 EmptyView::excludeI(Space&,I&) {
345 return ME_SET_NONE;
346 }
347
348 template<class I> ModEvent
349 EmptyView::includeI(Space&,I& i) {
350 return i() ? ME_SET_FAILED : ME_SET_NONE;
351 }
352
353 template<class I> ModEvent
354 EmptyView::intersectI(Space&,I&) {
355 return ME_SET_NONE;
356 }
357
358 /*
359 * Delta information for advisors
360 *
361 */
362 forceinline int
363 EmptyView::glbMin(const Delta&) const {
364 GECODE_NEVER;
365 return 0;
366 }
367
368 forceinline int
369 EmptyView::glbMax(const Delta&) const {
370 GECODE_NEVER;
371 return 0;
372 }
373
374 forceinline bool
375 EmptyView::glbAny(const Delta&) const {
376 GECODE_NEVER;
377 return false;
378 }
379
380 forceinline int
381 EmptyView::lubMin(const Delta&) const {
382 GECODE_NEVER;
383 return 0;
384 }
385
386 forceinline int
387 EmptyView::lubMax(const Delta&) const {
388 GECODE_NEVER;
389 return 0;
390 }
391
392 forceinline bool
393 EmptyView::lubAny(const Delta&) const {
394 GECODE_NEVER;
395 return false;
396 }
397
398 // Constant universe variable
399
400 forceinline
401 UniverseView::UniverseView(void) {}
402
403 forceinline unsigned int
404 UniverseView::glbSize(void) const { return Set::Limits::card; }
405
406 forceinline unsigned int
407 UniverseView::lubSize(void) const { return Set::Limits::card; }
408
409 forceinline unsigned int
410 UniverseView::unknownSize(void) const { return 0; }
411
412 forceinline bool
413 UniverseView::contains(int) const { return true; }
414
415 forceinline bool
416 UniverseView::notContains(int) const { return false; }
417
418 forceinline unsigned int
419 UniverseView::cardMin(void) const { return Set::Limits::card; }
420
421 forceinline unsigned int
422 UniverseView::cardMax(void) const { return Limits::card; }
423
424 forceinline int
425 UniverseView::lubMin(void) const { return Limits::card; }
426
427 forceinline int
428 UniverseView::lubMax(void) const { return Limits::card; }
429
430 forceinline int
431 UniverseView::glbMin(void) const { return Limits::card; }
432
433 forceinline int
434 UniverseView::glbMax(void) const { return Limits::card; }
435
436 forceinline ModEvent
437 UniverseView::cardMin(Space&,unsigned int c) {
438 return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE;
439 }
440
441 forceinline ModEvent
442 UniverseView::cardMax(Space&,unsigned int c) {
443 return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED;
444 }
445
446
447 forceinline ModEvent
448 UniverseView::include(Space&,int) {
449 return ME_SET_NONE;
450 }
451
452 forceinline ModEvent
453 UniverseView::exclude(Space&,int) { return ME_SET_FAILED; }
454
455 forceinline ModEvent
456 UniverseView::intersect(Space&,int) { return ME_SET_FAILED; }
457
458 forceinline ModEvent
459 UniverseView::include(Space&,int,int) { return ME_SET_NONE; }
460
461 forceinline ModEvent
462 UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; }
463
464 template<class I> ModEvent
465 UniverseView::excludeI(Space&,I& i) {
466 return i() ? ME_SET_FAILED : ME_SET_NONE;
467 }
468
469 template<class I> forceinline ModEvent
470 UniverseView::includeI(Space&,I&) {
471 return ME_SET_NONE;
472 }
473
474 forceinline ModEvent
475 UniverseView::intersect(Space&,int i,int j) {
476 return (i>Limits::min ||
477 j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE;
478 }
479
480 template<class I> forceinline ModEvent
481 UniverseView::intersectI(Space&,I& i) {
482 return (i() &&
483 (i.min()>Limits::min ||
484 i.max()<Limits::max) ) ?
485 ME_SET_FAILED : ME_SET_NONE;
486 }
487
488
489 /*
490 * Delta information for advisors
491 *
492 */
493 forceinline int
494 UniverseView::glbMin(const Delta&) const {
495 GECODE_NEVER;
496 return 0;
497 }
498
499 forceinline int
500 UniverseView::glbMax(const Delta&) const {
501 GECODE_NEVER;
502 return 0;
503 }
504
505 forceinline bool
506 UniverseView::glbAny(const Delta&) const {
507 GECODE_NEVER;
508 return false;
509 }
510
511 forceinline int
512 UniverseView::lubMin(const Delta&) const {
513 GECODE_NEVER;
514 return 0;
515 }
516
517 forceinline int
518 UniverseView::lubMax(const Delta&) const {
519 GECODE_NEVER;
520 return 0;
521 }
522
523 forceinline bool
524 UniverseView::lubAny(const Delta&) const {
525 GECODE_NEVER;
526 return false;
527 }
528
529 /*
530 * Iterators
531 *
532 */
533
534 /**
535 * \brief %Range iterator for least upper bound of constantly empty set view
536 * \ingroup TaskActorSetView
537 */
538 template<>
539 class LubRanges<EmptyView> : public Iter::Ranges::Empty {
540 public:
541 /// \name Constructors and initialization
542 //@{
543 /// Default constructor
544 LubRanges(void) {}
545 /// Initialize with ranges for view \a x
546 LubRanges(const EmptyView& x) { (void)x; }
547 /// Initialize with ranges for view \a x
548 void init(const EmptyView& x) { (void)x; }
549 //@}
550 };
551
552 /**
553 * \brief %Range iterator for greatest lower bound of constantly empty set view
554 * \ingroup TaskActorSetView
555 */
556 template<>
557 class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
558 public:
559 /// \name Constructors and initialization
560 //@{
561 /// Default constructor
562 GlbRanges(void) {}
563 /// Initialize with ranges for view \a x
564 GlbRanges(const EmptyView& x) { (void)x; }
565 /// Initialize with ranges for view \a x
566 void init(const EmptyView& x) { (void)x; }
567 //@}
568 };
569
570 /**
571 * \brief %Range iterator for least upper bound of constant universe set view
572 * \ingroup TaskActorSetView
573 */
574 template<>
575 class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
576 public:
577 /// \name Constructors and initialization
578 //@{
579 /// Default constructor
580 LubRanges(void)
581 : Iter::Ranges::Singleton(Limits::min,
582 Limits::max) {}
583 /// Initialize with ranges for view \a x
584 LubRanges(const UniverseView& x)
585 : Iter::Ranges::Singleton(Limits::min,
586 Limits::max) {
587 (void)x;
588 }
589 /// Initialize with ranges for view \a x
590 void init(const UniverseView& x) { (void)x; }
591 //@}
592 };
593
594 /**
595 * \brief %Range iterator for greatest lower bound of constant universe set view
596 * \ingroup TaskActorSetView
597 */
598 template<>
599 class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
600 public:
601 /// \name Constructors and initialization
602 //@{
603 /// Default constructor
604 GlbRanges(void)
605 : Iter::Ranges::Singleton(Limits::min,
606 Limits::max) {}
607 /// Initialize with ranges for view \a x
608 GlbRanges(const UniverseView& x)
609 : Iter::Ranges::Singleton(Limits::min,
610 Limits::max) {
611 (void)x;
612 }
613 /// Initialize with ranges for view \a x
614 void init(const UniverseView& x) { (void)x; }
615 //@}
616 };
617
618
619 /**
620 * \brief %Range iterator for least upper bound of constant set view
621 * \ingroup TaskActorSetView
622 */
623 template<>
624 class LubRanges<ConstSetView> {
625 private:
626 ArrayRanges ar;
627 public:
628 /// \name Constructors and initialization
629 //@{
630 /// Default constructor
631 LubRanges(void) {}
632 /// Initialize with ranges for view \a x
633 LubRanges(const ConstSetView& x) : ar(x.ranges,x.size) {}
634 /// Initialize with ranges for view \a x
635 void init(const ConstSetView& x) {
636 ar.init(x.ranges,x.size);
637 }
638 //@}
639
640 /// \name Iteration control
641 //@{
642 /// Test whether iterator is still at a value or done
643 bool operator ()(void) const { return ar(); }
644 /// Move iterator to next value (if possible)
645 void operator ++(void) { ++ar; }
646 //@}
647
648 /// \name Range access
649 //@{
650 /// Return smallest value of range
651 int min(void) const { return ar.min(); }
652 /// Return largest value of range
653 int max(void) const { return ar.max(); }
654 /// Return width of range (distance between minimum and maximum)
655 unsigned int width(void) const { return ar.width(); }
656 //@}
657 };
658
659 /**
660 * \brief %Range iterator for greatest lower bound of constant set view
661 * \ingroup TaskActorSetView
662 */
663 template<>
664 class GlbRanges<ConstSetView> : public LubRanges<ConstSetView> {
665 public:
666 /// \name Constructors and initialization
667 //@{
668 /// Default constructor
669 GlbRanges(void) {}
670 /// Initialize with ranges for view \a x
671 GlbRanges(const ConstSetView& x) : LubRanges<ConstSetView>(x) {}
672 /// Initialize with ranges for view \a x
673 void init(const ConstSetView& x) {
674 LubRanges<ConstSetView>::init(x);
675 }
676 //@}
677 };
678
679 forceinline bool
680 ConstSetView::operator <(const ConstSetView& y) const {
681 if (size < y.size)
682 return true;
683 if (size > y.size)
684 return false;
685 if (domSize < y.domSize)
686 return true;
687 if (domSize > y.domSize)
688 return false;
689 for (int i=size; i--; ) {
690 if (ranges[2*i] < y.ranges[2*i])
691 return true;
692 if (ranges[2*i] > y.ranges[2*i])
693 return false;
694 if (ranges[2*i+1] < y.ranges[2*i+1])
695 return true;
696 if (ranges[2*i+1] > y.ranges[2*i+1])
697 return false;
698 }
699 return false;
700 }
701
702 /*
703 * Testing
704 *
705 */
706 forceinline bool
707 operator ==(const ConstSetView& x, const ConstSetView& y) {
708 if ((x.size != y.size) || (x.domSize != y.domSize))
709 return false;
710 for (int i=x.size; i--; )
711 if ((x.ranges[2*i] != y.ranges[2*i]) ||
712 (x.ranges[2*i+1] != y.ranges[2*i+1]))
713 return false;
714 return true;
715 }
716 forceinline bool
717 operator !=(const ConstSetView& x, const ConstSetView& y) {
718 return !(x == y);
719 }
720
721
722 forceinline bool
723 operator ==(const EmptyView&, const EmptyView&) {
724 return true;
725 }
726 forceinline bool
727 operator !=(const EmptyView&, const EmptyView&) {
728 return false;
729 }
730
731 forceinline bool
732 operator ==(const UniverseView&, const UniverseView&) {
733 return true;
734 }
735 forceinline bool
736 operator !=(const UniverseView&, const UniverseView&) {
737 return false;
738 }
739
740}}
741
742// STATISTICS: set-var
743