46 typedef long long int Time;
47 typedef std::ptrdiff_t RegionIndex;
64 Time residue(Time t, Time p) {
66 return (q < 0) ? q+p : q;
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)
94 int next_active(
int i)
const {
96 for (
unsigned int j=
static_cast<unsigned int>(i); j; j-=j & -j)
98 if (before == activeCount)
101 int ordinal = before+1;
103 for (
int bit=topBit; bit; bit/=2)
104 if ((bit <= keyCount-rank) && (counts[rank+bit] < ordinal)) {
106 ordinal -= counts[rank];
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) {}
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);
127 while (topBit <= keyCount/2)
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));
139 Time key(
int i)
const {
return keys[i]; }
140 int group(
int i)
const {
return groups[i]; }
143 void set_group(
int i,
int root) {
151 assert(groups[i] >= 0);
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));
164 bool at_end(
int i)
const {
return i == keyCount; }
191 ResidueGroups residues;
195 while (successor[root] != root)
196 root = successor[root];
197 while (successor[i] != i) {
198 int next = successor[i];
205 int load(
int i)
const {
207 for (
size_t j=
static_cast<size_t>(i)+1; j; j-=j & -j)
212 Time displacement(
int i)
const {
216 while (parent[i] != i) {
223 int merge(
int a,
int b) {
224 if (size[a] < size[b])
227 offset[b] -= offset[a];
232 Time critical(
int i, Time p)
const {
233 return deadlines[i]+p-
static_cast<Time
>(load(i))*p-displacement(i);
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);
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);
247 i = residues.active_after(key);
249 residues.set_group(target,root);
253 void forbid(Time a, Time b,
int p) {
254 int target = residues.rank(a);
257 assert(residues.group(target) >= 0);
260 merge_residue_range(residues.active_after(a),(a < b) ? b : p,target,p);
262 merge_residue_range(residues.first_active(),b,target,p);
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;
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);
279 std::sort(finish,finish+n,[](
const Task* a,
const Task* b) {
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;
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);
302 std::fill(loads,loads+dc+1,0);
303 for (
int i=0; i<dc; i++) {
309 residues.reset(deadlines,dc,p);
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)
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)
330 if ((i > 0) && (release[i-1]->
min == release[i]->
min))
332 c = critical(active,p);
333 Time r = release[i]->min;
341 while ((pending >= 0) && (deadlines[pending]+p >= c)) {
342 parent[pending] = pending;
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));
350 forbid(residue(c-p,p),residue(r,p),p);
360 RegionIndex previous;
381 Forbidden* forbidden;
386 RegionIndex regionCount;
387 RegionIndex* firstRegion;
389 RegionIndex* nextRegion;
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();
407 if ((
count > limit /
sizeof(Time) / (
count+1)) ||
408 (
count > (limit /
sizeof(Adjustment) - 3) / (
count+3)))
410 tasks = r.alloc<Task>(n);
411 minSorted = r.alloc<Task*>(n);
412 maxSorted = r.alloc<Task*>(n);
413 forbidden = r.alloc<Forbidden>(n);
415 ectTable =
static_cast<Time*
>(r.ralloc(entries *
sizeof(Time)));
416 lstTable = r.alloc<Time>(n+2);
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);
428 Time ect(
int i,
int q)
const {
429 return ectTable[
static_cast<size_t>(q)*n+i];
432 Time lst(
int q)
const {
440 while (links[i] > i) {
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))
453 while (regions[r].
min <= bounds[vi]) {
454 if (bounds[vi] <= regions[r].
max) {
456 (regions[r].
max+1 >= minSorted[vi+1]->
min)) {
457 int previous = links[vi];
460 links[vi] = previous;
462 if (regions[r].
max >= bounds[vi])
463 bounds[vi] = regions[r].max+1;
465 if (regions[r].
min < regions[nextRegion[vi]].
min)
471 assert((vi >= 0) && (links[vi] < vi));
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);
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);
485 for (
int i=0; i<n; i++)
486 minSorted[i]->minRank = i;
490 bool compute_forbidden_regions(
Region& r) {
491 Time* deadlines = r.alloc<Time>(n);
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;
499 Time* times = r.alloc<Time>(dc);
500 int* cursor = r.alloc<
int>(dc);
501 Forbidden* buffer = r.alloc<Forbidden>(n);
505 for (
int i=0; i<dc; i++) {
506 times[i] = deadlines[i];
510 Time
min = std::numeric_limits<Time>::max();
513 for (
int i=n; i--;) {
514 for (
int j=minSorted[i]->maxRank; j<dc; j++) {
516 while ((cursor[j] > last) &&
517 (times[j] < buffer[cursor[j]].
min))
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]);
524 if ((i == 0) || (minSorted[i-1]->
min < minSorted[i]->
min))
526 if (
min < minSorted[i]->
min)
528 if (
min-p+1 < minSorted[i]->
min) {
529 if ((forbiddenCount > 0) &&
530 (minSorted[i]->
min >= buffer[last+1].
min)) {
533 buffer[last+1].min =
min-p+1;
536 buffer[last--] = {
min-p+1,minSorted[i]->min-1};
541 for (
int i=0; i<forbiddenCount; i++)
542 forbidden[i] = buffer[last+1+i];
547 void compute_earliest_completions(
void) {
548 for (
int i=0; i<n; i++) {
549 ectTable[i] = minSorted[i]->min;
551 for (
int q=1; q<=n; q++) {
552 Time start = ect(i,q-1);
553 while ((er < forbiddenCount) && (forbidden[er].
max < start))
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;
563 void compute_latest_starts(Time deadline,
int taskCount) {
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))
572 if ((region >= 0) && (forbidden[region].
max >= start))
573 start = forbidden[region].min-1;
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};
584 for (
int i=0; i<n; i++) {
586 processed[i] =
false;
587 bounds[i] = minSorted[i]->min;
593 RegionIndex insertion_point(RegionIndex hint, Time
min)
const {
596 while (((hint+1 == regionCount) ?
min : regions[hint+1].
min) >=
598 hint = regions[hint].previous;
601 if (regions[hint].
min <=
min) {
607 while (regions[regions[hint].next].
min <
min)
608 hint = regions[hint].next;
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;
624 void apply_internal_adjustments(
void) {
625 const Time infinity = std::numeric_limits<Time>::max();
626 RegionIndex lastRegion = 0;
629 for (
int it=0; it<n; it++) {
630 int i = maxSorted[it]->minRank;
632 maxP = std::max(maxP,i);
633 minP = std::min(minP,i);
637 int l = leader[i] = i;
645 while (!processed[--l]) {}
647 while (l > leader[l]) {
648 while (!processed[--l]) {}
651 if (ect(i,1) > ect(l,k-kp+1)) {
659 while (!processed[++j]) {}
660 if (ect(j,1) <= ect(l,k- --kp+1))
665 if ((it < n-1) && (maxSorted[it]->
max == maxSorted[it+1]->
max))
668 compute_latest_starts(maxSorted[it]->
max,it+1);
671 RegionIndex insertion = 0;
674 for (
int t=q; t<k; t++) {
675 Time
min = lst(t+1)+1;
678 Time
max = (l >= 0) ? ect(l,k-t)-1 : -infinity;
680 insertion = insertion_point(insertion,
min);
682 insertion = lastRegion;
683 firstRegion[i] = lastRegion = regionCount;
685 vi = notify(insert_adjustment(insertion,
min,
max),vi);
691 while (!processed[--l]) {}
694 while (!processed[--l]) {}
705 void apply_external_adjustments(
void) {
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)) {
713 Time lastMax = regions[firstRegion[i]].max;
714 for (RegionIndex r=firstRegion[i]+1;
715 (r < regionCount) && (regions[r].min < regions[r-1].min);
717 Time oldMax = regions[r].max;
718 regions[r].max = lastMax;
729 if (!compute_forbidden_regions(r))
731 compute_earliest_completions();
732 initialize_adjustments();
733 apply_internal_adjustments();
734 apply_external_adjustments();
740 int maximum_feasible_distance(
Region& region,
743 Feasibility feasibility(region,x);
744 if (!feasibility.check(
min))
746 if ((
max ==
min) || feasibility.check(
max))
753 if (feasibility.check(middle))
764 Filter f(region,x.
size(),p);
766 for (
int direction=0; direction<2; direction++) {
767 for (
int i=0; i<x.
size(); i++) {
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;
774 if (!f.filter(region))
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()))
780 ModEvent me = direction ? x[i].lq(home,
static_cast<int>(bound)) :
781 x[i].gq(home,
static_cast<int>(bound));
783 nofix |= (direction ? x[i].max() : x[i].
min()) != bound;
792 for (
int i=0; i<x.
size(); i++)
795 Time gap = std::numeric_limits<Time>::max();
796 for (
int i=1; i<x.
size(); i++)
802 template<
class PView>
807 template<
class PView>
812 template<
class PView>
815 return new (home)
Bnd(home,*
this);
818 template<
class PView>
828 template<
class PView>
832 return sizeof(*this);
835 template<
class PView>
843 template<
class PView>
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++) {
853 assigned &=
x[i].assigned();
862 if (
y.assigned() && (
y.val() == 1))
865 const int p =
y.min();
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())));
871 upper = maximum_feasible_distance(region,
x,p,upper);
877 if (
y.assigned() && (
y.val() == 1))
888 ExecStatus filtered = filter_bounds(home,region,
x,p);
893 for (
int i=0; i<
x.size(); i++)
894 assigned &=
x[i].assigned();