Generated on for Gecode by doxygen 1.17.0
inter-distance.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Claude-Guy Quimper <claude-guy.quimper@ift.ulaval.ca>
5 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
6 *
7 * Copyright:
8 * Claude-Guy Quimper, 2006
9 * Mikael Zayenz Lagerkvist, 2026
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.dev
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
38
39#include <algorithm>
40#include <limits>
41#include <tuple>
42
43namespace Gecode { namespace Int { namespace InterDistance {
44
45 namespace {
46 typedef long long int Time;
47 typedef std::ptrdiff_t RegionIndex;
48
50 struct Task {
51 Time min;
52 Time max;
53 int minRank;
54 int maxRank;
55 };
56
58 struct Forbidden {
59 Time min;
60 Time max;
61 };
62
64 Time residue(Time t, Time p) {
65 Time q = t % p;
66 return (q < 0) ? q+p : q;
67 }
68
77 class ResidueGroups {
78 Time* keys;
79 int* groups;
80 int* counts;
81 int keyCount;
82 int activeCount;
83 int topBit;
84
86 void update(int i, int delta) {
87 for (unsigned int j=static_cast<unsigned int>(i)+1;
88 j<=static_cast<unsigned int>(keyCount); j+=j & -j)
89 counts[j] += delta;
90 activeCount += delta;
91 }
92
94 int next_active(int i) const {
95 int before = 0;
96 for (unsigned int j=static_cast<unsigned int>(i); j; j-=j & -j)
97 before += counts[j];
98 if (before == activeCount)
99 return keyCount;
100
101 int ordinal = before+1;
102 int rank = 0;
103 for (int bit=topBit; bit; bit/=2)
104 if ((bit <= keyCount-rank) && (counts[rank+bit] < ordinal)) {
105 rank += bit;
106 ordinal -= counts[rank];
107 }
108 return rank;
109 }
110 public:
112 ResidueGroups(Region& r, int n)
113 : keys(r.alloc<Time>(n)), groups(r.alloc<int>(n)),
114 counts(r.alloc<int>(static_cast<unsigned int>(n)+1)),
115 keyCount(0), activeCount(0), topBit(0) {}
116
118 void reset(const Time* deadlines, int n, int p) {
119 for (int i=0; i<n; i++)
120 keys[i] = residue(deadlines[i],p);
121 std::sort(keys,keys+n);
122 keyCount = static_cast<int>(std::unique(keys,keys+n)-keys);
123 std::fill(groups,groups+keyCount,-1);
124 std::fill(counts,counts+keyCount+1,0);
125 activeCount = 0;
126 topBit = 1;
127 while (topBit <= keyCount/2)
128 topBit *= 2;
129 }
130
132 int rank(Time key) const {
133 int i = static_cast<int>(std::lower_bound(keys,keys+keyCount,key)-keys);
134 assert((i < keyCount) && (keys[i] == key));
135 return i;
136 }
137
139 Time key(int i) const { return keys[i]; }
140 int group(int i) const { return groups[i]; }
141
143 void set_group(int i, int root) {
144 if (groups[i] < 0)
145 update(i,1);
146 groups[i] = root;
147 }
148
150 void remove(int i) {
151 assert(groups[i] >= 0);
152 groups[i] = -1;
153 update(i,-1);
154 }
155
157 int first_active(void) const { return next_active(0); }
159 int active_after(Time key) const {
160 return next_active(static_cast<int>(
161 std::upper_bound(keys,keys+keyCount,key)-keys));
162 }
164 bool at_end(int i) const { return i == keyCount; }
165 };
166
178 class Feasibility {
179 const int n;
180 int dc;
181 Task* tasks;
182 Task** release;
184 Time* deadlines;
185 int* loads;
186 int* successor;
187 int* previous;
188 int* parent;
189 int* size;
190 Time* offset;
191 ResidueGroups residues;
193 int find(int i) {
194 int root = i;
195 while (successor[root] != root)
196 root = successor[root];
197 while (successor[i] != i) {
198 int next = successor[i];
199 successor[i] = root;
200 i = next;
201 }
202 return root;
203 }
205 int load(int i) const {
206 int count = 0;
207 for (size_t j=static_cast<size_t>(i)+1; j; j-=j & -j)
208 count += loads[j];
209 return count;
210 }
212 Time displacement(int i) const {
213 if (parent[i] == -1)
214 return 0;
215 Time d = offset[i];
216 while (parent[i] != i) {
217 i = parent[i];
218 d += offset[i];
219 }
220 return d;
221 }
223 int merge(int a, int b) {
224 if (size[a] < size[b])
225 std::swap(a,b);
226 parent[b] = a;
227 offset[b] -= offset[a];
228 size[a] += size[b];
229 return a;
230 }
232 Time critical(int i, Time p) const {
233 return deadlines[i]+p-static_cast<Time>(load(i))*p-displacement(i);
234 }
235
237 void merge_residue_range(int first, Time end, int target, int p) {
238 Time a = residues.key(target);
239 int root = residues.group(target);
240 int i = first;
241 while (!residues.at_end(i) && (residues.key(i) < end)) {
242 Time key = residues.key(i);
243 int group = residues.group(i);
244 offset[group] += residue(key-a,p);
245 root = merge(root,group);
246 residues.remove(i);
247 i = residues.active_after(key);
248 }
249 residues.set_group(target,root);
250 }
251
253 void forbid(Time a, Time b, int p) {
254 int target = residues.rank(a);
255 // The active deadline's group has residue critical(active,p) % p,
256 // so activation has already supplied the target key.
257 assert(residues.group(target) >= 0);
258
259 // At a wraparound, zero is included precisely when it is below b.
260 merge_residue_range(residues.active_after(a),(a < b) ? b : p,target,p);
261 if (a >= b)
262 merge_residue_range(residues.first_active(),b,target,p);
263 }
264 public:
265 Feasibility(Region& r, const ViewArray<IntView>& x)
266 : n(x.size()), dc(0), residues(r,x.size()) {
267 tasks = r.alloc<Task>(n);
268 release = r.alloc<Task*>(n);
269 Task** finish = r.alloc<Task*>(n);
270 deadlines = r.alloc<Time>(n);
271 for (int i=0; i<n; i++) {
272 tasks[i].min = x[i].min();
273 tasks[i].max = x[i].max();
274 release[i] = finish[i] = tasks+i;
275 }
276 std::sort(release,release+n,[](const Task* a, const Task* b) {
277 return std::tie(a->min,a->max) < std::tie(b->min,b->max);
278 });
279 std::sort(finish,finish+n,[](const Task* a, const Task* b) {
280 return a->max < b->max;
281 });
282 for (int i=0; i<n; i++) {
283 if ((i == 0) || (finish[i]->max != deadlines[dc-1]))
284 deadlines[dc++] = finish[i]->max;
285 finish[i]->maxRank = dc-1;
286 }
287 // Include the successor sentinel without overflowing signed int.
288 // Region::alloc has an unsigned-int overload on every platform.
289 const unsigned int count = static_cast<unsigned int>(dc)+1;
290 loads = r.alloc<int>(count);
291 successor = r.alloc<int>(count);
292 previous = r.alloc<int>(dc);
293 parent = r.alloc<int>(dc);
294 size = r.alloc<int>(dc);
295 offset = r.alloc<Time>(dc);
296 }
298 bool check(int p) {
299 if (p == 0)
300 return true;
301
302 std::fill(loads,loads+dc+1,0);
303 for (int i=0; i<dc; i++) {
304 successor[i] = i;
305 previous[i] = i-1;
306 parent[i] = -1;
307 }
308 successor[dc] = dc;
309 residues.reset(deadlines,dc,p);
310
311 int active = dc;
312 int pending = dc-1;
313 for (int i=n; i--;) {
314 int rank = release[i]->maxRank;
315 for (size_t j=static_cast<size_t>(rank)+1;
316 j<=static_cast<size_t>(dc); j+=j & -j)
317 loads[j]++;
318 int d = find(rank);
319 active = std::min(active,d);
320 Time c = critical(d,p);
321 while ((previous[d] >= 0) && (critical(previous[d],p) > c)) {
322 int obsolete = previous[d];
323 successor[obsolete] = d;
324 previous[d] = previous[obsolete];
325 if (active == obsolete)
326 active = d;
327 }
328
329 // Construct regions after processing all tasks at this release time.
330 if ((i > 0) && (release[i-1]->min == release[i]->min))
331 continue;
332 c = critical(active,p);
333 Time r = release[i]->min;
334 if (c < r)
335 return false;
336 if (c-p+1 >= r)
337 continue;
338
339 // Only deadlines whose back-schedule can reach this region
340 // are activated. Earlier deadlines must retain zero offsets.
341 while ((pending >= 0) && (deadlines[pending]+p >= c)) {
342 parent[pending] = pending;
343 size[pending] = 1;
344 offset[pending] = 0;
345 int key = residues.rank(residue(deadlines[pending],p));
346 int group = residues.group(key);
347 residues.set_group(key,(group < 0) ? pending : merge(group,pending));
348 pending--;
349 }
350 forbid(residue(c-p,p),residue(r,p),p);
351 }
352 return true;
353 }
354 };
355
357 struct Adjustment {
358 Time min;
359 Time max;
360 RegionIndex previous;
361 RegionIndex next;
362 };
363
375 class Filter {
376 private:
377 const int n;
378 const Time p;
379 Task** minSorted;
380 Task** maxSorted;
381 Forbidden* forbidden;
382 int forbiddenCount;
383 Time* ectTable;
384 Time* lstTable;
385 Adjustment* regions;
386 RegionIndex regionCount;
387 RegionIndex* firstRegion;
389 RegionIndex* nextRegion;
390 Time* bounds;
391 // links[i] > i forwards to a merged group's representative; otherwise
392 // i is a live representative and links[i] < i is its predecessor (-1
393 // for the first group). Merging preserves this predecessor at the root.
394 int* links;
395 bool* processed;
396 int* leader;
397 public:
399 Task* tasks;
401 Filter(Region& r, int n0, int p0)
402 : n(n0), p(p0), forbiddenCount(0), regionCount(0) {
403 const size_t count = static_cast<size_t>(n);
404 const size_t limit = std::numeric_limits<size_t>::max();
405 // Region::alloc multiplies unchecked. Reject impossible byte sizes
406 // before allocating the quadratic tables or interval list.
407 if ((count > limit / sizeof(Time) / (count+1)) ||
408 (count > (limit / sizeof(Adjustment) - 3) / (count+3)))
409 throw MemoryExhausted();
410 tasks = r.alloc<Task>(n);
411 minSorted = r.alloc<Task*>(n);
412 maxSorted = r.alloc<Task*>(n);
413 forbidden = r.alloc<Forbidden>(n);
414 const size_t entries = count * (count+1);
415 ectTable = static_cast<Time*>(r.ralloc(entries * sizeof(Time)));
416 lstTable = r.alloc<Time>(n+2);
417 const size_t capacity = count * (count+3) / 2 + 3;
418 regions = static_cast<Adjustment*>(
419 r.ralloc(capacity * sizeof(Adjustment)));
420 firstRegion = r.alloc<RegionIndex>(n);
421 nextRegion = r.alloc<RegionIndex>(n);
422 bounds = r.alloc<Time>(n);
423 links = r.alloc<int>(n);
424 processed = r.alloc<bool>(n);
425 leader = r.alloc<int>(n);
426 }
428 Time ect(int i, int q) const {
429 return ectTable[static_cast<size_t>(q)*n+i];
430 }
432 Time lst(int q) const {
433 return lstTable[q];
434 }
436 int find(int i) {
437 int j = i;
438 while (links[j] > j)
439 j = links[j];
440 while (links[i] > i) {
441 int k = links[i];
442 links[i] = j;
443 i = k;
444 }
445 return j;
446 }
448 int notify(RegionIndex r, int vi) {
449 assert((vi >= 0) && (links[vi] < vi));
450 while ((links[vi] >= 0) &&
451 (bounds[links[vi]] >= regions[r].min))
452 vi = links[vi];
453 while (regions[r].min <= bounds[vi]) {
454 if (bounds[vi] <= regions[r].max) {
455 while ((vi < n-1) &&
456 (regions[r].max+1 >= minSorted[vi+1]->min)) {
457 int previous = links[vi];
458 links[vi] = vi+1;
459 vi = find(vi);
460 links[vi] = previous;
461 }
462 if (regions[r].max >= bounds[vi])
463 bounds[vi] = regions[r].max+1;
464 }
465 if (regions[r].min < regions[nextRegion[vi]].min)
466 r = nextRegion[vi];
467 else
468 nextRegion[vi] = r;
469 r = regions[r].next;
470 }
471 assert((vi >= 0) && (links[vi] < vi));
472 return vi;
473 }
474 private:
476 void sort_tasks(void) {
477 for (int i=0; i<n; i++)
478 minSorted[i] = maxSorted[i] = tasks+i;
479 std::sort(minSorted,minSorted+n,[](const Task* a, const Task* b) {
480 return std::tie(a->min,a->max) < std::tie(b->min,b->max);
481 });
482 std::sort(maxSorted,maxSorted+n,[](const Task* a, const Task* b) {
483 return std::tie(a->max,a->min) < std::tie(b->max,b->min);
484 });
485 for (int i=0; i<n; i++)
486 minSorted[i]->minRank = i;
487 }
488
490 bool compute_forbidden_regions(Region& r) {
491 Time* deadlines = r.alloc<Time>(n);
492 int dc = 0;
493 for (int i=0; i<n; i++) {
494 if ((i == 0) || (maxSorted[i]->max > deadlines[dc-1]))
495 deadlines[dc++] = maxSorted[i]->max;
496 maxSorted[i]->maxRank = dc-1;
497 }
498
499 Time* times = r.alloc<Time>(dc);
500 int* cursor = r.alloc<int>(dc);
501 Forbidden* buffer = r.alloc<Forbidden>(n);
502 // Indices keep cursor movement within the allocated forbidden-region
503 // buffer, including its empty-prefix boundary.
504 int last = n-1;
505 for (int i=0; i<dc; i++) {
506 times[i] = deadlines[i];
507 cursor[i] = last;
508 }
509
510 Time min = std::numeric_limits<Time>::max();
511 Time newMin = min;
512 forbiddenCount = 0;
513 for (int i=n; i--;) {
514 for (int j=minSorted[i]->maxRank; j<dc; j++) {
515 times[j] -= p;
516 while ((cursor[j] > last) &&
517 (times[j] < buffer[cursor[j]].min))
518 cursor[j]--;
519 if ((cursor[j] > last) &&
520 (times[j] <= buffer[cursor[j]].max))
521 times[j] = buffer[cursor[j]--].min-1;
522 newMin = std::min(newMin,times[j]);
523 }
524 if ((i == 0) || (minSorted[i-1]->min < minSorted[i]->min))
525 min = newMin;
526 if (min < minSorted[i]->min)
527 return false;
528 if (min-p+1 < minSorted[i]->min) {
529 if ((forbiddenCount > 0) &&
530 (minSorted[i]->min >= buffer[last+1].min)) {
531 // Adjacent integer regions must also be merged: skipping one
532 // region must not land on a forbidden start in its neighbour.
533 buffer[last+1].min = min-p+1;
534 } else {
535 assert(last >= 0);
536 buffer[last--] = {min-p+1,minSorted[i]->min-1};
537 forbiddenCount++;
538 }
539 }
540 }
541 for (int i=0; i<forbiddenCount; i++)
542 forbidden[i] = buffer[last+1+i];
543 return true;
544 }
545
547 void compute_earliest_completions(void) {
548 for (int i=0; i<n; i++) {
549 ectTable[i] = minSorted[i]->min;
550 int er = 0;
551 for (int q=1; q<=n; q++) {
552 Time start = ect(i,q-1);
553 while ((er < forbiddenCount) && (forbidden[er].max < start))
554 er++;
555 if ((er < forbiddenCount) && (forbidden[er].min <= start))
556 start = forbidden[er].max+1;
557 ectTable[static_cast<size_t>(q)*n+i] = start+p;
558 }
559 }
560 }
561
563 void compute_latest_starts(Time deadline, int taskCount) {
564 // Keeping only the current deadline's vector avoids a second
565 // quadratic table without increasing the sweep's complexity.
566 lstTable[0] = deadline;
567 int region = forbiddenCount-1;
568 for (int t=1; t<=taskCount+1; t++) {
569 Time start = lst(t-1)-p;
570 while ((region >= 0) && (forbidden[region].min > start))
571 region--;
572 if ((region >= 0) && (forbidden[region].max >= start))
573 start = forbidden[region].min-1;
574 lstTable[t] = start;
575 }
576 }
577
579 void initialize_adjustments(void) {
580 const Time infinity = std::numeric_limits<Time>::max();
581 regions[0] = {-infinity,-infinity,-1,1};
582 regions[1] = {infinity,infinity,0,-1};
583 regionCount = 2;
584 for (int i=0; i<n; i++) {
585 links[i] = i-1;
586 processed[i] = false;
587 bounds[i] = minSorted[i]->min;
588 nextRegion[i] = 0;
589 }
590 }
591
593 RegionIndex insertion_point(RegionIndex hint, Time min) const {
594 // Intervals are appended in decreasing-minimum runs. Follow previous
595 // links between runs, then next links within the ordered list.
596 while (((hint+1 == regionCount) ? min : regions[hint+1].min) >=
597 regions[hint].min) {
598 hint = regions[hint].previous;
599 if (hint < 0)
600 break;
601 if (regions[hint].min <= min) {
602 hint--;
603 break;
604 }
605 }
606 hint++;
607 while (regions[regions[hint].next].min < min)
608 hint = regions[hint].next;
609 return hint;
610 }
611
613 RegionIndex insert_adjustment(RegionIndex previous, Time min, Time max) {
614 RegionIndex next = regions[previous].next;
615 assert((regions[previous].min <= min) && (min <= regions[next].min));
616 RegionIndex inserted = regionCount++;
617 regions[inserted] = {min,max,previous,next};
618 regions[previous].next = inserted;
619 regions[next].previous = inserted;
620 return inserted;
621 }
622
624 void apply_internal_adjustments(void) {
625 const Time infinity = std::numeric_limits<Time>::max();
626 RegionIndex lastRegion = 0;
627 int minP = n;
628 int maxP = 0;
629 for (int it=0; it<n; it++) {
630 int i = maxSorted[it]->minRank;
631 processed[i] = true;
632 maxP = std::max(maxP,i);
633 minP = std::min(minP,i);
634
635 // Maintain the dominating blocks before generating their intervals.
636 // These cursors share the sweep's task counts and stay together.
637 int l = leader[i] = i;
638 int kp = 1;
639 while (++l <= maxP)
640 if (processed[l])
641 kp++;
642 l = i;
643 int k = kp;
644 if (i > minP) {
645 while (!processed[--l]) {}
646 k++;
647 while (l > leader[l]) {
648 while (!processed[--l]) {}
649 k++;
650 }
651 if (ect(i,1) > ect(l,k-kp+1)) {
652 l = i;
653 k = kp;
654 }
655 }
656 kp = k;
657 int j = l;
658 while (j < maxP) {
659 while (!processed[++j]) {}
660 if (ect(j,1) <= ect(l,k- --kp+1))
661 leader[j] = l;
662 else
663 break;
664 }
665 if ((it < n-1) && (maxSorted[it]->max == maxSorted[it+1]->max))
666 continue;
667
668 compute_latest_starts(maxSorted[it]->max,it+1);
669
670 int q = 0;
671 RegionIndex insertion = 0;
672 int vi = n-1;
673 while (true) {
674 for (int t=q; t<k; t++) {
675 Time min = lst(t+1)+1;
676 // The final empty region allows external adjustments to
677 // expand the preceding intervals by one more task.
678 Time max = (l >= 0) ? ect(l,k-t)-1 : -infinity;
679 if (t > 0) {
680 insertion = insertion_point(insertion,min);
681 } else {
682 insertion = lastRegion;
683 firstRegion[i] = lastRegion = regionCount;
684 }
685 vi = notify(insert_adjustment(insertion,min,max),vi);
686 }
687 if (l == -1)
688 break;
689 q = k++;
690 if (l > minP) {
691 while (!processed[--l]) {}
692 j = leader[l];
693 while (j < l) {
694 while (!processed[--l]) {}
695 k++;
696 }
697 } else {
698 l = -1;
699 }
700 }
701 }
702 }
703
705 void apply_external_adjustments(void) {
706 // A variable is filtered before adding external intervals for its
707 // deadline, so it is never excluded by an interval it helped create.
708 for (int it=0; it<n; it++) {
709 int i = maxSorted[it]->minRank;
710 maxSorted[it]->min = bounds[find(i)];
711 if ((it == n-1) || (maxSorted[it]->max != maxSorted[it+1]->max)) {
712 int vi = n-1;
713 Time lastMax = regions[firstRegion[i]].max;
714 for (RegionIndex r=firstRegion[i]+1;
715 (r < regionCount) && (regions[r].min < regions[r-1].min);
716 r++) {
717 Time oldMax = regions[r].max;
718 regions[r].max = lastMax;
719 lastMax = oldMax;
720 vi = notify(r,vi);
721 }
722 }
723 }
724 }
725 public:
727 bool filter(Region& r) {
728 sort_tasks();
729 if (!compute_forbidden_regions(r))
730 return false;
731 compute_earliest_completions();
732 initialize_adjustments();
733 apply_internal_adjustments();
734 apply_external_adjustments();
735 return true;
736 }
737 };
738
740 int maximum_feasible_distance(Region& region,
741 const ViewArray<IntView>& x,
742 int min, int max) {
743 Feasibility feasibility(region,x);
744 if (!feasibility.check(min))
745 return -1;
746 if ((max == min) || feasibility.check(max))
747 return max;
748
749 // Quimper et al. (2008), Section 5: feasibility is monotone in p.
750 // Keep min feasible and max infeasible without enumerating distances.
751 while (max-min > 1) {
752 int middle = min+(max-min)/2;
753 if (feasibility.check(middle))
754 min = middle;
755 else
756 max = middle;
757 }
758 return min;
759 }
760
762 ExecStatus filter_bounds(Space& home, Region& region,
763 ViewArray<IntView>& x, int p) {
764 Filter f(region,x.size(),p);
765 bool nofix = false;
766 for (int direction=0; direction<2; direction++) {
767 for (int i=0; i<x.size(); i++) {
768 // Reverse task time: [r,d] becomes [-d,-r]. Variables denote
769 // starting times, while the algorithm's maxima are deadlines.
770 f.tasks[i].min = direction ? -static_cast<Time>(x[i].max())-p : x[i].min();
771 f.tasks[i].max = direction ? -static_cast<Time>(x[i].min()) :
772 static_cast<Time>(x[i].max())+p;
773 }
774 if (!f.filter(region))
775 return ES_FAILED;
776 for (int i=0; i<x.size(); i++) {
777 Time bound = direction ? -f.tasks[i].min-p : f.tasks[i].min;
778 if (direction ? (bound < x[i].min()) : (bound > x[i].max()))
779 return ES_FAILED;
780 ModEvent me = direction ? x[i].lq(home,static_cast<int>(bound)) :
781 x[i].gq(home,static_cast<int>(bound));
782 GECODE_ME_CHECK(me);
783 nofix |= (direction ? x[i].max() : x[i].min()) != bound;
784 }
785 }
786 return nofix ? ES_NOFIX : ES_FIX;
787 }
788
790 Time assigned_distance(Region& r, const ViewArray<IntView>& x) {
791 Time* values = r.alloc<Time>(x.size());
792 for (int i=0; i<x.size(); i++)
793 values[i] = x[i].val();
794 std::sort(values,values+x.size());
795 Time gap = std::numeric_limits<Time>::max();
796 for (int i=1; i<x.size(); i++)
797 gap = std::min(gap,values[i]-values[i-1]);
798 return gap;
799 }
800 }
801
802 template<class PView>
803 Bnd<PView>::Bnd(Home home, ViewArray<IntView>& x0, PView p0, bool a)
805 advanced(a) {}
806
807 template<class PView>
811
812 template<class PView>
815 return new (home) Bnd(home,*this);
816 }
817
818 template<class PView>
820 Bnd<PView>::cost(const Space&, const ModEventDelta& med) const {
821 // ME_INT_DOM is a synthetic event: subscriptions only generate bound
822 // or assignment events. It schedules the quadratic stage separately.
823 if (IntView::me(med) == ME_INT_DOM)
824 return PropCost::quadratic(PropCost::HI,x.size());
825 return PropCost::linear(PropCost::HI,x.size());
826 }
827
828 template<class PView>
829 size_t
832 return sizeof(*this);
833 }
834
835 template<class PView>
838 if (x.size() > 1)
839 (void) new (home) Bnd(home,x,p,advanced);
840 return ES_OK;
841 }
842
843 template<class PView>
846 Region region;
847 bool assigned = true;
848 int min = x[0].min();
849 int max = x[0].max();
850 for (int i=0; i<x.size(); i++) {
851 min = std::min(min,x[i].min());
852 max = std::max(max,x[i].max());
853 assigned &= x[i].assigned();
854 }
855
856 if (assigned) {
857 GECODE_ME_CHECK(y.lq(home,assigned_distance(region,x)));
858 return home.ES_SUBSUMED(*this);
859 }
860 if (y.max() == 0)
861 return home.ES_SUBSUMED(*this);
862 if (y.assigned() && (y.val() == 1))
864
865 const int p = y.min();
866 if (IntView::me(med) != ME_INT_DOM) {
867 Time limit = (static_cast<Time>(max)-min)/(x.size()-1);
868 int upper = static_cast<int>(std::min(limit,static_cast<Time>(y.max())));
869 if (upper < p)
870 return ES_FAILED;
871 upper = maximum_feasible_distance(region,x,p,upper);
872 if (upper < 0)
873 return ES_FAILED;
874 GECODE_ME_CHECK(y.lq(home,upper));
875 if (y.max() == 0)
876 return home.ES_SUBSUMED(*this);
877 if (y.assigned() && (y.val() == 1))
879 if (!advanced || (p == 0))
880 return ES_FIX;
881 return home.ES_FIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
882 }
883
884 // A zero minimum gives every x bound a support; only the basic stage
885 // needs to filter the distance. A later increase wakes that stage again.
886 if (p == 0)
887 return ES_FIX;
888 ExecStatus filtered = filter_bounds(home,region,x,p);
889 if (filtered == ES_FAILED)
890 return ES_FAILED;
891
892 assigned = true;
893 for (int i=0; i<x.size(); i++)
894 assigned &= x[i].assigned();
895 if (assigned) {
896 GECODE_ME_CHECK(y.lq(home,assigned_distance(region,x)));
897 return home.ES_SUBSUMED(*this);
898 }
899
900 // Holes can move actual bounds beyond the computed bounds, invalidating
901 // an interval support for x or the distance. Restart the basic stage.
902 return filtered;
903 }
904
905 // Export the compiled view specializations for propagator reuse.
906 template class Bnd<IntView>;
907 template class Bnd<ConstIntView>;
908
909}}}
910
911namespace Gecode {
912
913 void
914 inter_distance(Home home, const IntVarArgs& x, int p, IntPropLevel ipl) {
915 using namespace Int;
916 Limits::nonnegative(p,"Int::inter_distance");
917 if ((p > 0) && same(x))
918 throw ArgumentSame("Int::inter_distance");
920 if ((p == 0) || (x.size() < 2))
921 return;
922 ViewArray<IntView> xv(home,x);
923 if (p == 1) {
925 } else {
927 home,xv,ConstIntView(p),ba(ipl) != IPL_BASIC));
928 }
929 }
930
931 void
933 using namespace Int;
934 if ((x.size() > 1) &&
935 (same(x,p) || ((p.max() > 0) && same(x))))
936 throw ArgumentSame("Int::inter_distance");
938 IntView pv(p);
939 GECODE_ME_FAIL(pv.gq(home,0));
940 if ((pv.max() == 0) || (x.size() < 2))
941 return;
942 if (pv.assigned()) {
943 inter_distance(home,x,pv.val(),ipl);
944 return;
945 }
946 ViewArray<IntView> xv(home,x);
948 home,xv,pv,ba(ipl) != IPL_BASIC));
949 }
950
951}
952
953// STATISTICS: int-post
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:387
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:399
Home class for posting propagators
Definition core.hpp:863
Passing integer variables.
Definition int.hh:681
Integer variables.
Definition int.hh:390
int max(void) const
Return maximum of domain.
Definition int.hpp:70
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Constant integer view.
Definition view.hpp:851
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition bnd.hpp:478
Integer view for integer variables.
Definition view.hpp:129
int med(void) const
Return median of domain (greatest element not greater than the median).
Definition int.hpp:66
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
int val(void) const
Return assigned value (only if assigned).
Definition int.hpp:70
int max(void) const
Return maximum of domain.
Definition int.hpp:62
Bounds-consistent inter-distance propagator.
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost of the current stage.
virtual Propagator * copy(Space &home)
Copy during cloning.
static ExecStatus post(Home home, ViewArray< IntView > &x, PView p, bool advanced)
Post propagator.
bool advanced
Whether to run quadratic filtering after the basic stage.
Bnd(Home home, ViewArray< IntView > &x, PView p, bool advanced)
Constructor for posting.
virtual size_t dispose(Space &home)
Cancel subscriptions and dispose.
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Perform propagation.
Exception: Memory exhausted
Definition exception.hpp:63
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:766
Propagation cost.
Definition core.hpp:493
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:5071
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
@ HI
Expensive.
Definition core.hpp:521
Base-class for propagators.
Definition core.hpp:1073
friend class Space
Definition core.hpp:1075
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1084
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1787
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
View arrays.
Definition array.hpp:255
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1165
const int capacity[n_warehouses]
Capacity of a single warehouse.
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition core.hpp:3786
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
#define GECODE_POST
Check for failure in a constraint post function.
Definition macros.hpp:40
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition macros.hpp:77
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IPL_BASIC
Use basic propagation algorithm.
Definition int.hh:1281
Inter-distance propagator.
void nonnegative(int n, const char *l)
Check whether n is in range and nonnegative, otherwise throw out of limits with information l.
Definition limits.hpp:68
Finite domain integers.
Definition lastval.hh:52
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:80
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition ipl.hpp:43
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1936
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
void inter_distance(Home home, const IntVarArgs &x, int p, IntPropLevel ipl=IPL_DEF)
Post bounds-consistent propagator for for all .
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int ModEvent
Type for modification events.
Definition core.hpp:67