34#include "absl/algorithm/container.h"
35#include "absl/container/btree_set.h"
36#include "absl/container/flat_hash_map.h"
37#include "absl/container/flat_hash_set.h"
38#include "absl/container/inlined_vector.h"
39#include "absl/log/check.h"
40#include "absl/log/log.h"
41#include "absl/log/vlog_is_on.h"
42#include "absl/random/bit_gen_ref.h"
43#include "absl/types/optional.h"
44#include "absl/types/span.h"
67 if (intersect.
SizeX() == 0) {
78 absl::InlinedVector<Rectangle, 4> result;
81 result.push_back({.x_min =
x_min,
82 .x_max = intersect.
x_min,
88 result.push_back({.x_min = intersect.
x_max,
95 result.push_back({.x_min = intersect.
x_min,
96 .x_max = intersect.
x_max,
98 .y_max = intersect.
y_min});
102 result.push_back({.x_min = intersect.
x_min,
103 .x_max = intersect.
x_max,
104 .y_min = intersect.
y_max,
112 absl::Span<const Rectangle> rectangles) {
113 if (rectangles.empty())
return {};
115 std::vector<std::pair<int, int>> intersections =
117 const int num_intersections = intersections.size();
118 intersections.reserve(num_intersections * 2 + 1);
119 for (
int i = 0;
i < num_intersections; ++
i) {
120 intersections.push_back({intersections[
i].second, intersections[
i].first});
129 for (
int i = 0;
i < components.size(); ++
i) {
130 absl::Span<const int> component = components[
i];
132 for (
const int r : component) {
133 result.AppendToLastVector(r);
144 IntegerValue total_energy(0);
145 for (
const int b : boxes) {
146 const IntegerValue x_min = x->ShiftedStartMin(
b);
147 const IntegerValue x_max = x->ShiftedEndMax(
b);
148 if (x_min < bounding_box.x_min || x_max > bounding_box.x_max)
continue;
151 if (y_min < bounding_box.y_min || y_max > bounding_box.y_max)
continue;
153 x->AddEnergyMinInIntervalReason(
b, bounding_box.x_min, bounding_box.x_max);
156 x->AddPresenceReason(
b);
159 total_energy += x->SizeMin(
b) * y->
SizeMin(
b);
163 if (total_energy > bounding_box.Area())
break;
166 CHECK_GT(total_energy, bounding_box.Area());
167 x->ImportOtherReasons(*y);
168 return x->ReportConflict();
172 absl::Span<const IntegerValue> energies,
173 absl::Span<const int> boxes,
176 std::vector<IntegerValue> x_starts;
177 std::vector<TaskTime> boxes_by_increasing_x_max;
178 for (
const int b : boxes) {
179 x_starts.push_back(rectangles[
b].x_min);
180 boxes_by_increasing_x_max.push_back({
b, rectangles[
b].x_max});
183 std::sort(boxes_by_increasing_x_max.begin(), boxes_by_increasing_x_max.end());
185 std::vector<IntegerValue> y_starts;
186 std::vector<IntegerValue> energy_sum;
187 std::vector<TaskTime> boxes_by_increasing_y_max;
189 std::vector<std::vector<int>> stripes(x_starts.size());
190 for (
int i = 0;
i < boxes_by_increasing_x_max.size(); ++
i) {
191 const int b = boxes_by_increasing_x_max[
i].task_index;
192 const IntegerValue x_min = rectangles[
b].x_min;
193 const IntegerValue x_max = rectangles[
b].x_max;
194 for (
int j = 0; j < x_starts.size(); ++j) {
195 if (x_starts[j] > x_min)
break;
196 stripes[j].push_back(
b);
201 boxes_by_increasing_y_max.clear();
202 for (
const int b : stripes[j]) {
203 y_starts.push_back(rectangles[
b].y_min);
204 boxes_by_increasing_y_max.push_back({
b, rectangles[
b].y_max});
207 std::sort(boxes_by_increasing_y_max.begin(),
208 boxes_by_increasing_y_max.end());
210 const IntegerValue x_size = x_max - x_starts[j];
211 energy_sum.assign(y_starts.size(), IntegerValue(0));
212 for (
int i = 0;
i < boxes_by_increasing_y_max.size(); ++
i) {
213 const int b = boxes_by_increasing_y_max[
i].task_index;
214 const IntegerValue y_min = rectangles[
b].y_min;
215 const IntegerValue y_max = rectangles[
b].y_max;
216 for (
int j = 0; j < y_starts.size(); ++j) {
217 if (y_starts[j] > y_min)
break;
218 energy_sum[j] += energies[
b];
219 if (energy_sum[j] > x_size * (y_max - y_starts[j])) {
220 if (conflict !=
nullptr) {
221 *conflict = rectangles[
b];
222 for (
int k = 0; k <
i; ++k) {
223 const int task_index = boxes_by_increasing_y_max[k].task_index;
224 if (rectangles[task_index].y_min >= y_starts[j]) {
239 absl::Span<const Rectangle> rectangles,
240 absl::Span<const IntegerValue> rectangle_energies,
241 IntegerValue* x_threshold, IntegerValue* y_threshold,
248 std::vector<IntegerValue> starts;
249 std::vector<TaskTime> task_by_increasing_x_max;
250 for (
const int t : local_boxes) {
251 const IntegerValue x_min =
252 transpose ? rectangles[t].y_min : rectangles[t].x_min;
253 const IntegerValue x_max =
254 transpose ? rectangles[t].y_max : rectangles[t].x_max;
255 starts.push_back(x_min);
256 task_by_increasing_x_max.push_back({t, x_max});
262 std::sort(task_by_increasing_x_max.begin(), task_by_increasing_x_max.end());
266 IntegerValue max_conflict_height(0);
269 absl::flat_hash_set<std::pair<IntegerValue, IntegerValue>> stripes;
272 std::vector<IntegerValue> energies(starts.size(), IntegerValue(0));
275 std::vector<IntegerValue> energy_at_max_y(starts.size(), IntegerValue(0));
276 std::vector<IntegerValue> energy_at_min_y(starts.size(), IntegerValue(0));
283 const IntegerValue threshold = transpose ? *y_threshold : *x_threshold;
284 for (
int i = 0;
i < task_by_increasing_x_max.size(); ++
i) {
285 const int t = task_by_increasing_x_max[
i].task_index;
287 const IntegerValue energy = rectangle_energies[t];
288 IntegerValue x_min = rectangles[t].x_min;
289 IntegerValue x_max = rectangles[t].x_max;
290 IntegerValue y_min = rectangles[t].y_min;
291 IntegerValue y_max = rectangles[t].y_max;
293 std::swap(x_min, y_min);
294 std::swap(x_max, y_max);
298 while (first_j + 1 < starts.size() && x_max - starts[first_j] > threshold) {
301 for (
int j = first_j; starts[j] <= x_min; ++j) {
302 const IntegerValue old_energy_at_max = energy_at_max_y[j];
303 const IntegerValue old_energy_at_min = energy_at_min_y[j];
305 energies[j] += energy;
307 const bool is_disjoint = y_min >= y_maxs[j] || y_max <= y_mins[j];
309 if (y_min <= y_mins[j]) {
310 if (y_min < y_mins[j]) {
312 energy_at_min_y[j] = energy;
314 energy_at_min_y[j] += energy;
318 if (y_max >= y_maxs[j]) {
319 if (y_max > y_maxs[j]) {
321 energy_at_max_y[j] = energy;
323 energy_at_max_y[j] += energy;
330 if (is_disjoint)
continue;
332 const IntegerValue width = x_max - starts[j];
333 IntegerValue conflict_height =
CeilRatio(energies[j], width) - 1;
334 if (y_max - y_min > conflict_height)
continue;
335 if (conflict_height >= y_maxs[j] - y_mins[j]) {
337 if (conflict !=
nullptr) {
338 *conflict = rectangles[t];
339 for (
int k = 0; k <
i; ++k) {
340 const int task_index = task_by_increasing_x_max[k].task_index;
341 const IntegerValue task_x_min = transpose
342 ? rectangles[task_index].y_min
343 : rectangles[task_index].x_min;
344 if (task_x_min < starts[j])
continue;
353 IntegerValue can_remove = std::min(old_energy_at_min, old_energy_at_max);
354 if (old_energy_at_min < old_energy_at_max) {
355 if (y_maxs[j] - y_min >=
356 CeilRatio(energies[j] - old_energy_at_min, width)) {
359 can_remove = old_energy_at_max;
361 }
else if (old_energy_at_max < old_energy_at_min) {
362 if (y_max - y_mins[j] >=
363 CeilRatio(energies[j] - old_energy_at_max, width)) {
364 can_remove = old_energy_at_min;
367 conflict_height =
CeilRatio(energies[j] - can_remove, width) - 1;
371 if (y_max - y_min > conflict_height)
continue;
373 if (VLOG_IS_ON(2)) stripes.insert({starts[j], x_max});
374 max_conflict_height = std::max(max_conflict_height, conflict_height);
378 VLOG(2) <<
" num_starts: " << starts.size() - 1 <<
"/" << local_boxes.size()
379 <<
" conflict_height: " << max_conflict_height
380 <<
" num_stripes:" << stripes.size() <<
" (<= " << threshold <<
")";
383 *x_threshold = std::min(*x_threshold, max_conflict_height);
385 *y_threshold = std::min(*y_threshold, max_conflict_height);
391 absl::Span<const Rectangle> cached_rectangles, absl::Span<int> boxes,
392 IntegerValue threshold_x, IntegerValue threshold_y,
393 absl::BitGenRef random) {
395 for (
const int b : boxes) {
397 if (dim.
x_max - dim.
x_min > threshold_x)
continue;
398 if (dim.
y_max - dim.
y_min > threshold_y)
continue;
399 boxes[new_size++] =
b;
401 if (new_size == 0)
return {};
402 std::shuffle(&boxes[0], &boxes[0] + new_size, random);
403 return {&boxes[0], new_size};
407 absl::Span<const Rectangle> cached_rectangles,
408 absl::Span<const IntegerValue> energies, absl::Span<int> boxes) {
410 std::sort(boxes.begin(), boxes.end(), [cached_rectangles](
int a,
int b) {
411 return cached_rectangles[a].Area() < cached_rectangles[b].Area();
414 IntegerValue total_energy(0);
415 for (
const int box : boxes) total_energy += energies[box];
419 int new_size = boxes.size();
420 while (new_size > 0 &&
421 cached_rectangles[boxes[new_size - 1]].Area() >= total_energy) {
423 total_energy -= energies[boxes[new_size]];
425 return boxes.subspan(0, new_size);
429 CompactVectorVector<int>* result,
430 absl::Span<const int> order) {
432 DCHECK(std::is_sorted(intervals.begin(), intervals.end(),
440 const int size = intervals.size();
441 for (
int end_index = 0; end_index < size;) {
442 const IntegerValue time = intervals[end_index].start;
447 if (min_end_in_set <= time) {
449 if (start_index + 1 < end_index) {
451 for (
int i = start_index;
i < end_index; ++
i) {
452 result->AppendToLastVector(intervals[
i].index);
458 int new_start = end_index;
459 for (
int i = end_index; --
i >= start_index;) {
460 if (intervals[
i].
end > time) {
461 min_end_in_set = std::min(min_end_in_set, intervals[
i].
end);
462 intervals[--new_start] = intervals[
i];
465 start_index = new_start;
470 const int old_end = end_index;
471 while (end_index < size && intervals[end_index].start == time) {
472 min_end_in_set = std::min(min_end_in_set, intervals[end_index].
end);
478 if (!order.empty() && end_index > old_end) {
479 std::sort(intervals.data() + old_end, intervals.data() + end_index,
481 return order[a.index] < order[b.index];
484 intervals.data() + start_index, intervals.data() + old_end,
485 intervals.data() + end_index,
487 return order[a.index] < order[b.index];
493 if (start_index + 1 < size) {
495 for (
int i = start_index;
i < size; ++
i) {
496 result->AppendToLastVector(intervals[
i].index);
502 std::vector<IndexedInterval>* intervals,
503 std::vector<std::vector<int>>* components) {
505 if (intervals->empty())
return;
506 if (intervals->size() == 1) {
507 components->push_back({intervals->front().index});
518 std::sort(intervals->begin(), intervals->end(),
521 IntegerValue end_max_so_far = (*intervals)[0].end;
522 components->push_back({(*intervals)[0].index});
523 for (
int i = 1;
i < intervals->size(); ++
i) {
525 if (interval.
start >= end_max_so_far) {
526 components->push_back({interval.
index});
528 components->back().push_back(interval.
index);
530 end_max_so_far = std::max(end_max_so_far, interval.
end);
535 std::vector<IndexedInterval>* intervals) {
536 std::vector<int> articulation_points;
537 if (intervals->size() < 3)
return articulation_points;
540 DCHECK_LT(interval.start, interval.end);
544 std::sort(intervals->begin(), intervals->end(),
545 IndexedInterval::ComparatorByStart());
547 IntegerValue end_max_so_far = (*intervals)[0].end;
548 int index_of_max = 0;
550 for (
int i = 1;
i < intervals->size(); ++
i) {
551 const IndexedInterval& interval = (*intervals)[
i];
552 if (interval.start >= end_max_so_far) {
554 end_max_so_far = interval.end;
563 if (articulation_points.empty() ||
564 articulation_points.back() != index_of_max) {
565 articulation_points.push_back(index_of_max);
569 if (interval.end > end_max_so_far) {
570 prev_end_max = end_max_so_far;
571 end_max_so_far = interval.end;
573 }
else if (interval.end > prev_end_max) {
574 prev_end_max = interval.end;
578 for (
int& index : articulation_points) index = (*intervals)[index].index;
579 return articulation_points;
583bool IsZeroOrPowerOfTwo(
int value) {
return (value & (value - 1)) == 0; }
587 std::vector<PairwiseRestriction>* result) {
590 (item1.x.end_min <= item2.x.start_max) +
592 2 * (item2.x.end_min <= item1.x.start_max) +
594 4 * (item1.y.end_min <= item2.y.start_max) +
596 8 * (item2.y.end_min <= item1.y.start_max);
598 if (!IsZeroOrPowerOfTwo(state)) {
610 if (item1.x.end_min > item2.x.start_min ||
611 item2.x.start_max < item1.x.end_max) {
619 if (item2.x.end_min > item1.x.start_min ||
620 item1.x.start_max < item2.x.end_max) {
628 if (item1.y.end_min > item2.y.start_min ||
629 item2.y.start_max < item1.y.end_max) {
636 if (item2.y.end_min > item1.y.start_min ||
637 item1.y.start_max < item2.y.end_max) {
646 {.first_index = item1.index, .second_index = item2.index, .type = type});
651 std::vector<PairwiseRestriction>* result) {
652 for (
int i1 = 0; i1 + 1 < items.size(); ++i1) {
653 for (
int i2 = i1 + 1; i2 < items.size(); ++i2) {
654 AppendPairwiseRestriction(items[i1], items[i2], result);
660 absl::Span<const ItemWithVariableSize> items,
661 absl::Span<const ItemWithVariableSize> other_items,
662 std::vector<PairwiseRestriction>* result) {
663 for (
int i1 = 0; i1 < items.size(); ++i1) {
664 for (
int i2 = 0; i2 < other_items.size(); ++i2) {
665 AppendPairwiseRestriction(items[i1], other_items[i2], result);
672 num_rectangles_added_ = 0;
676 IntegerValue y_min, IntegerValue y_max) {
677 DCHECK_LE(x_min, x_max);
678 if (x_min == x_max)
return;
681 StartRectangleEvent(num_rectangles_added_, x_min, y_min, y_max));
682 events_.push_back(EndRectangleEvent(num_rectangles_added_, x_max));
683 ++num_rectangles_added_;
688 IntegerValue y_height) {
689 DCHECK_LE(x_min, x_max);
690 if (x_min == x_max)
return;
692 events_.push_back(ChangeMandatoryProfileEvent(x_min, y_height));
693 events_.push_back(ChangeMandatoryProfileEvent(x_max, -y_height));
697 std::vector<CapacityProfile::Rectangle>* result) {
698 std::sort(events_.begin(), events_.end());
701 IntegerValue mandatory_capacity(0);
707 for (
int i = 0;
i < events_.size();) {
708 const IntegerValue current_time = events_[
i].time;
709 for (;
i < events_.size(); ++
i) {
710 const Event&
event = events_[
i];
711 if (event.time != current_time)
break;
713 switch (events_[
i].type) {
714 case START_RECTANGLE: {
715 min_pq.Add({
event.index, -
event.y_min});
716 max_pq.Add({
event.index,
event.y_max});
719 case END_RECTANGLE: {
720 min_pq.Remove(event.index);
721 max_pq.Remove(event.index);
724 case CHANGE_MANDATORY_PROFILE: {
725 mandatory_capacity +=
event.y_min;
731 DCHECK(!max_pq.IsEmpty() || mandatory_capacity == 0);
732 const IntegerValue new_height =
735 : max_pq.Top().value + min_pq.Top().value - mandatory_capacity;
736 if (new_height != result->back().height) {
737 result->push_back({current_time, new_height});
742IntegerValue CapacityProfile::GetBoundingArea() {
743 std::sort(events_.begin(), events_.end());
747 IntegerValue area(0);
749 IntegerValue previous_height(0);
751 for (
int i = 0;
i < events_.size();) {
752 const IntegerValue current_time = events_[
i].time;
753 for (;
i < events_.size(); ++
i) {
754 const Event&
event = events_[
i];
755 if (event.time != current_time)
break;
757 switch (event.type) {
758 case START_RECTANGLE: {
759 min_pq.Add({
event.index, -
event.y_min});
760 max_pq.Add({
event.index,
event.y_max});
763 case END_RECTANGLE: {
764 min_pq.Remove(event.index);
765 max_pq.Remove(event.index);
768 case CHANGE_MANDATORY_PROFILE: {
773 const IntegerValue new_height =
774 max_pq.IsEmpty() ? IntegerValue(0)
775 : max_pq.Top().value + min_pq.Top().value;
776 if (previous_height != 0) {
777 area += previous_height * (current_time - previous_time);
779 previous_time = current_time;
780 previous_height = new_height;
786 IntegerValue range_max, IntegerValue size,
787 IntegerValue interval_min,
788 IntegerValue interval_max) {
791 const IntegerValue overlap_on_left =
792 std::min(range_min + size, interval_max) -
793 std::max(range_min, interval_min);
797 const IntegerValue overlap_on_right =
798 std::min(range_max, interval_max) -
799 std::max(range_max - size, interval_min);
801 return std::max(IntegerValue(0), std::min(overlap_on_left, overlap_on_right));
804ProbingRectangle::ProbingRectangle(
805 const std::vector<RectangleInRange>& intervals)
806 : intervals_(intervals) {
808 if (intervals_.empty()) {
811 interval_points_sorted_by_x_.reserve(intervals_.size() * 4 + 2);
812 interval_points_sorted_by_y_.reserve(intervals_.size() * 4 + 2);
814 Rectangle bounding_box = {.x_min = std::numeric_limits<IntegerValue>::max(),
815 .x_max = std::numeric_limits<IntegerValue>::min(),
816 .y_min = std::numeric_limits<IntegerValue>::max(),
817 .y_max = std::numeric_limits<IntegerValue>::min()};
819 for (
int i = 0;
i < intervals_.size(); ++
i) {
833 interval_points_sorted_by_x_.push_back(
835 interval_points_sorted_by_x_.push_back(
840 interval_points_sorted_by_y_.push_back(
842 interval_points_sorted_by_y_.push_back(
847 full_energy_ = minimum_energy_;
850 interval_points_sorted_by_x_.push_back({bounding_box.x_min - 1, -1});
851 interval_points_sorted_by_x_.push_back({bounding_box.x_max + 1, -1});
852 interval_points_sorted_by_y_.push_back({bounding_box.y_min - 1, -1});
853 interval_points_sorted_by_y_.push_back({bounding_box.y_max + 1, -1});
855 auto comparator = [](
const IntervalPoint& a,
const IntervalPoint&
b) {
856 return std::tie(a.value, a.index) < std::tie(
b.value,
b.index);
861 grouped_intervals_sorted_by_x_.reserve(interval_points_sorted_by_x_.size());
862 grouped_intervals_sorted_by_y_.reserve(interval_points_sorted_by_y_.size());
864 while (
i < interval_points_sorted_by_x_.size()) {
866 while (
i < interval_points_sorted_by_x_.size() &&
867 interval_points_sorted_by_x_[
i].value ==
868 interval_points_sorted_by_x_[idx_begin].value) {
871 grouped_intervals_sorted_by_x_.push_back(
872 {interval_points_sorted_by_x_[idx_begin].value,
873 absl::Span<IntervalPoint>(interval_points_sorted_by_x_)
874 .subspan(idx_begin,
i - idx_begin)});
878 while (
i < interval_points_sorted_by_y_.size()) {
880 while (
i < interval_points_sorted_by_y_.size() &&
881 interval_points_sorted_by_y_[
i].value ==
882 interval_points_sorted_by_y_[idx_begin].value) {
885 grouped_intervals_sorted_by_y_.push_back(
886 {interval_points_sorted_by_y_[idx_begin].value,
887 absl::Span<IntervalPoint>(interval_points_sorted_by_y_)
888 .subspan(idx_begin,
i - idx_begin)});
895 indexes_[Edge::LEFT] = 0;
896 indexes_[
Edge::RIGHT] = grouped_intervals_sorted_by_x_.size() - 1;
898 indexes_[
Edge::TOP] = grouped_intervals_sorted_by_y_.size() - 1;
901 next_indexes_[
Edge::RIGHT] = grouped_intervals_sorted_by_x_.size() - 2;
903 next_indexes_[
Edge::TOP] = grouped_intervals_sorted_by_y_.size() - 2;
905 minimum_energy_ = full_energy_;
906 ranges_touching_both_boundaries_[0].clear();
907 ranges_touching_both_boundaries_[1].clear();
909 for (
int i = 0;
i < 4; ++
i) {
910 corner_count_[
i] = 0;
911 intersect_length_[
i] = 0;
912 cached_delta_energy_[
i] = 0;
917 Shrink(Edge::BOTTOM);
922Rectangle ProbingRectangle::GetCurrentRectangle()
const {
924 .x_min = grouped_intervals_sorted_by_x_[indexes_[
Edge::LEFT]].coordinate,
925 .x_max = grouped_intervals_sorted_by_x_[indexes_[
Edge::RIGHT]].coordinate,
927 grouped_intervals_sorted_by_y_[indexes_[
Edge::BOTTOM]].coordinate,
928 .y_max = grouped_intervals_sorted_by_y_[indexes_[
Edge::TOP]].coordinate};
938bool CanConsumeEnergy(
const Rectangle& rectangle,
939 const RectangleInRange& item) {
940 return (rectangle.x_max > item.bounding_area.x_max - item.x_size) &&
941 (rectangle.y_max > item.bounding_area.y_max - item.y_size) &&
942 (rectangle.x_min < item.bounding_area.x_min + item.x_size) &&
943 (rectangle.y_min < item.bounding_area.y_min + item.y_size);
946std::array<bool, 4> GetPossibleEdgeIntersection(
const Rectangle& rectangle,
947 const RectangleInRange& range) {
948 std::array<bool, 4> result;
949 using Edge = ProbingRectangle::Edge;
950 result[Edge::LEFT] = rectangle.x_min >= range.bounding_area.x_min;
951 result[Edge::BOTTOM] = rectangle.y_min >= range.bounding_area.y_min;
952 result[Edge::RIGHT] = rectangle.x_max <= range.bounding_area.x_max;
953 result[Edge::TOP] = rectangle.y_max <= range.bounding_area.y_max;
961void ProbingRectangle::ValidateInvariants()
const {
962 const Rectangle current_rectangle = GetCurrentRectangle();
964 IntegerValue intersect_length[4] = {0, 0, 0, 0};
965 IntegerValue corner_count[4] = {0, 0, 0, 0};
966 IntegerValue energy = 0;
967 CHECK_LE(next_indexes_[Edge::LEFT], indexes_[Edge::RIGHT]);
968 CHECK_LE(next_indexes_[Edge::BOTTOM], indexes_[Edge::TOP]);
969 CHECK_GE(next_indexes_[Edge::TOP], indexes_[Edge::BOTTOM]);
970 CHECK_GE(next_indexes_[Edge::RIGHT], indexes_[Edge::LEFT]);
972 for (
int interval_idx = 0; interval_idx < intervals_.size(); interval_idx++) {
973 const RectangleInRange& range = intervals_[interval_idx];
975 const Rectangle min_intersect =
976 range.GetMinimumIntersection(current_rectangle);
977 CHECK_LE(min_intersect.SizeX(), range.x_size);
978 CHECK_LE(min_intersect.SizeY(), range.y_size);
979 energy += min_intersect.Area();
981 std::array<bool, 4> touching_boundary = {
false,
false,
false,
false};
982 CHECK_EQ(CanConsumeEnergy(current_rectangle, range) &&
983 current_rectangle.Area() != 0,
984 range.GetMinimumIntersectionArea(current_rectangle) != 0);
985 if (CanConsumeEnergy(current_rectangle, range)) {
986 touching_boundary = GetPossibleEdgeIntersection(current_rectangle, range);
990 touching_boundary[Edge::LEFT] && touching_boundary[Edge::RIGHT],
991 ranges_touching_both_boundaries_[Direction::LEFT_AND_RIGHT].contains(
994 touching_boundary[Edge::TOP] && touching_boundary[Edge::BOTTOM],
995 ranges_touching_both_boundaries_[Direction::TOP_AND_BOTTOM].contains(
998 if (touching_boundary[Edge::LEFT] && !touching_boundary[Edge::RIGHT]) {
1000 range.bounding_area.y_min, range.bounding_area.y_max, range.y_size,
1001 current_rectangle.y_min, current_rectangle.y_max);
1004 if (touching_boundary[Edge::RIGHT] && !touching_boundary[Edge::LEFT]) {
1006 range.bounding_area.y_min, range.bounding_area.y_max, range.y_size,
1007 current_rectangle.y_min, current_rectangle.y_max);
1010 if (touching_boundary[Edge::TOP] && !touching_boundary[Edge::BOTTOM]) {
1012 range.bounding_area.x_min, range.bounding_area.x_max, range.x_size,
1013 current_rectangle.x_min, current_rectangle.x_max);
1016 if (touching_boundary[Edge::BOTTOM] && !touching_boundary[Edge::TOP]) {
1018 range.bounding_area.x_min, range.bounding_area.x_max, range.x_size,
1019 current_rectangle.x_min, current_rectangle.x_max);
1022 if ((touching_boundary[Edge::LEFT] && touching_boundary[Edge::RIGHT]) ||
1023 (touching_boundary[Edge::TOP] && touching_boundary[Edge::BOTTOM])) {
1028 if (touching_boundary[Edge::BOTTOM] && touching_boundary[Edge::LEFT]) {
1029 corner_count[RectangleInRange::Corner::BOTTOM_LEFT]++;
1031 if (touching_boundary[Edge::BOTTOM] && touching_boundary[Edge::RIGHT]) {
1032 corner_count[RectangleInRange::Corner::BOTTOM_RIGHT]++;
1034 if (touching_boundary[Edge::TOP] && touching_boundary[Edge::LEFT]) {
1035 corner_count[RectangleInRange::Corner::TOP_LEFT]++;
1037 if (touching_boundary[Edge::TOP] && touching_boundary[Edge::RIGHT]) {
1038 corner_count[RectangleInRange::Corner::TOP_RIGHT]++;
1042 CHECK_EQ(energy, minimum_energy_);
1043 for (
int i = 0;
i < 4;
i++) {
1044 CHECK_EQ(intersect_length[i], intersect_length_[i]);
1045 CHECK_EQ(corner_count[i], corner_count_[i]);
1052 using Edge = ProbingRectangle::Edge;
1053 using Direction = ProbingRectangle::Direction;
1054 using Corner = RectangleInRange::Corner;
1058 struct OrthogonalInfo {
1060 Corner adjacent_corner;
1063 Direction shrink_direction;
1064 Direction orthogonal_shrink_direction;
1066 OrthogonalInfo orthogonal_edges[2];
1069struct EdgeInfoHolder {
1070 using Edge = ProbingRectangle::Edge;
1071 using Direction = ProbingRectangle::Direction;
1072 using Corner = RectangleInRange::Corner;
1074 static constexpr EdgeInfo kLeft = {
1075 .opposite_edge = Edge::RIGHT,
1076 .shrink_direction = Direction::LEFT_AND_RIGHT,
1077 .orthogonal_shrink_direction = Direction::TOP_AND_BOTTOM,
1078 .orthogonal_edges = {
1079 {.edge = Edge::BOTTOM, .adjacent_corner = Corner::BOTTOM_LEFT},
1080 {.edge = Edge::TOP, .adjacent_corner = Corner::TOP_LEFT}}};
1082 static constexpr EdgeInfo kRight = {
1083 .opposite_edge = Edge::LEFT,
1084 .shrink_direction = Direction::LEFT_AND_RIGHT,
1085 .orthogonal_shrink_direction = Direction::TOP_AND_BOTTOM,
1086 .orthogonal_edges = {
1087 {.edge = Edge::BOTTOM, .adjacent_corner = Corner::BOTTOM_RIGHT},
1088 {.edge = Edge::TOP, .adjacent_corner = Corner::TOP_RIGHT}}};
1089 static constexpr EdgeInfo kBottom = {
1090 .opposite_edge = Edge::TOP,
1091 .shrink_direction = Direction::TOP_AND_BOTTOM,
1092 .orthogonal_shrink_direction = Direction::LEFT_AND_RIGHT,
1093 .orthogonal_edges = {
1094 {.edge = Edge::LEFT, .adjacent_corner = Corner::BOTTOM_LEFT},
1095 {.edge = Edge::RIGHT, .adjacent_corner = Corner::BOTTOM_RIGHT}}};
1096 static constexpr EdgeInfo kTop = {
1097 .opposite_edge = Edge::BOTTOM,
1098 .shrink_direction = Direction::TOP_AND_BOTTOM,
1099 .orthogonal_shrink_direction = Direction::LEFT_AND_RIGHT,
1100 .orthogonal_edges = {
1101 {.edge = Edge::LEFT, .adjacent_corner = Corner::TOP_LEFT},
1102 {.edge = Edge::RIGHT, .adjacent_corner = Corner::TOP_RIGHT}}};
1105constexpr const EdgeInfo& GetEdgeInfo(ProbingRectangle::Edge edge) {
1106 using Edge = ProbingRectangle::Edge;
1109 return EdgeInfoHolder::kLeft;
1111 return EdgeInfoHolder::kRight;
1113 return EdgeInfoHolder::kBottom;
1115 return EdgeInfoHolder::kTop;
1119IntegerValue GetSmallest1DIntersection(ProbingRectangle::Direction direction,
1120 const RectangleInRange& range,
1121 const Rectangle& rectangle) {
1122 switch (direction) {
1123 case ProbingRectangle::Direction::LEFT_AND_RIGHT:
1125 range.bounding_area.x_max, range.x_size,
1126 rectangle.x_min, rectangle.x_max);
1127 case ProbingRectangle::Direction::TOP_AND_BOTTOM:
1129 range.bounding_area.y_max, range.y_size,
1130 rectangle.y_min, rectangle.y_max);
1136template <ProbingRectangle::Edge edge>
1137void ProbingRectangle::ShrinkImpl() {
1138 constexpr EdgeInfo e = GetEdgeInfo(edge);
1140 bool update_next_index[4] = {
false,
false,
false,
false};
1141 update_next_index[edge] =
true;
1143 IntegerValue step_1d_size;
1144 minimum_energy_ -= GetShrinkDeltaEnergy(edge);
1145 const std::vector<PointsForCoordinate>& sorted_intervals =
1146 e.shrink_direction == Direction::LEFT_AND_RIGHT
1147 ? grouped_intervals_sorted_by_x_
1148 : grouped_intervals_sorted_by_y_;
1150 const Rectangle prev_rectangle = GetCurrentRectangle();
1151 indexes_[edge] = next_indexes_[edge];
1152 const Rectangle current_rectangle = GetCurrentRectangle();
1156 step_1d_size = current_rectangle.x_min - prev_rectangle.x_min;
1157 next_indexes_[edge] =
1158 std::min(indexes_[edge] + 1, indexes_[e.opposite_edge]);
1159 next_indexes_[e.opposite_edge] =
1160 std::max(indexes_[edge], next_indexes_[e.opposite_edge]);
1163 step_1d_size = current_rectangle.y_min - prev_rectangle.y_min;
1164 next_indexes_[edge] =
1165 std::min(indexes_[edge] + 1, indexes_[e.opposite_edge]);
1166 next_indexes_[e.opposite_edge] =
1167 std::max(indexes_[edge], next_indexes_[e.opposite_edge]);
1170 step_1d_size = prev_rectangle.x_max - current_rectangle.x_max;
1171 next_indexes_[edge] =
1172 std::max(indexes_[edge] - 1, indexes_[e.opposite_edge]);
1173 next_indexes_[e.opposite_edge] =
1174 std::min(indexes_[edge], next_indexes_[e.opposite_edge]);
1177 step_1d_size = prev_rectangle.y_max - current_rectangle.y_max;
1178 next_indexes_[edge] =
1179 std::max(indexes_[edge] - 1, indexes_[e.opposite_edge]);
1180 next_indexes_[e.opposite_edge] =
1181 std::min(indexes_[edge], next_indexes_[e.opposite_edge]);
1185 absl::Span<ProbingRectangle::IntervalPoint> items_touching_coordinate =
1186 sorted_intervals[indexes_[edge]].items_touching_coordinate;
1188 IntegerValue delta_corner_count[4] = {0, 0, 0, 0};
1189 for (
const auto& item : items_touching_coordinate) {
1190 const RectangleInRange& range = intervals_[item.index];
1191 if (!CanConsumeEnergy(prev_rectangle, range)) {
1196 const std::array<bool, 4> touching_boundary_before =
1197 GetPossibleEdgeIntersection(prev_rectangle, range);
1198 const std::array<bool, 4> touching_boundary_after =
1199 CanConsumeEnergy(current_rectangle, range)
1200 ? GetPossibleEdgeIntersection(current_rectangle, range)
1201 : std::array<bool, 4>({
false,
false,
false,
false});
1203 bool remove_corner[4] = {
false,
false,
false,
false};
1204 auto erase_item = [
this, &prev_rectangle, &range, &touching_boundary_before,
1205 &remove_corner](Edge edge_to_erase) {
1206 const EdgeInfo& erase_info = GetEdgeInfo(edge_to_erase);
1207 intersect_length_[edge_to_erase] -= GetSmallest1DIntersection(
1208 erase_info.orthogonal_shrink_direction, range, prev_rectangle);
1210 if (touching_boundary_before[erase_info.orthogonal_edges[0].edge] &&
1211 touching_boundary_before[erase_info.orthogonal_edges[1].edge]) {
1215 for (
const auto [orthogonal_edge, corner] : erase_info.orthogonal_edges) {
1216 if (touching_boundary_before[orthogonal_edge]) {
1217 remove_corner[corner] =
true;
1222 if (touching_boundary_after[edge] && !touching_boundary_before[edge]) {
1223 if (touching_boundary_before[e.opposite_edge]) {
1224 ranges_touching_both_boundaries_[e.shrink_direction].insert(item.index);
1225 erase_item(e.opposite_edge);
1228 intersect_length_[edge] += GetSmallest1DIntersection(
1229 e.orthogonal_shrink_direction, range, prev_rectangle);
1231 if (!touching_boundary_before[e.orthogonal_edges[0].edge] ||
1232 !touching_boundary_before[e.orthogonal_edges[1].edge]) {
1233 for (
const auto [orthogonal_edge, corner] : e.orthogonal_edges) {
1234 if (touching_boundary_before[orthogonal_edge]) {
1235 delta_corner_count[corner]++;
1242 for (
int i = 0;
i < 4;
i++) {
1243 const Edge edge_to_update = (Edge)i;
1244 const EdgeInfo& info = GetEdgeInfo(edge_to_update);
1245 const bool remove_edge = touching_boundary_before[edge_to_update] &&
1246 !touching_boundary_after[edge_to_update];
1251 update_next_index[edge_to_update] =
true;
1253 if (touching_boundary_before[info.opposite_edge]) {
1254 ranges_touching_both_boundaries_[info.shrink_direction].erase(
1257 erase_item(edge_to_update);
1261 for (
int i = 0;
i < 4;
i++) {
1262 corner_count_[
i] -= remove_corner[
i];
1267 for (
const int idx : ranges_touching_both_boundaries_[e.shrink_direction]) {
1268 const RectangleInRange& range = intervals_[idx];
1269 const std::array<bool, 2> touching_corner =
1270 (e.shrink_direction == Direction::LEFT_AND_RIGHT)
1271 ? std::array<bool, 2>(
1272 {current_rectangle.y_min >= range.bounding_area.y_min,
1273 current_rectangle.y_max <= range.bounding_area.y_max})
1274 : std::array<bool, 2>(
1275 {current_rectangle.x_min >= range.bounding_area.x_min,
1276 current_rectangle.x_max <= range.bounding_area.x_max});
1277 if (touching_corner[0] == touching_corner[1]) {
1284 const IntegerValue incr =
1285 GetSmallest1DIntersection(e.shrink_direction, range, prev_rectangle) -
1286 GetSmallest1DIntersection(e.shrink_direction, range, current_rectangle);
1287 for (
int i = 0;
i < 2;
i++) {
1288 if (touching_corner[i]) {
1289 intersect_length_[e.orthogonal_edges[
i].edge] -= incr;
1294 for (
const auto [orthogonal_edge, corner] : e.orthogonal_edges) {
1295 intersect_length_[orthogonal_edge] -= corner_count_[corner] * step_1d_size;
1298 for (
int i = 0;
i < 4;
i++) {
1299 corner_count_[
i] += delta_corner_count[
i];
1302 auto points_consume_energy =
1304 ¤t_rectangle](absl::Span<ProbingRectangle::IntervalPoint> points) {
1305 for (
const auto& item : points) {
1306 const RectangleInRange& range = intervals_[item.index];
1307 if (CanConsumeEnergy(current_rectangle, range)) {
1313 if (update_next_index[Edge::LEFT]) {
1314 for (; next_indexes_[Edge::LEFT] < indexes_[Edge::RIGHT];
1315 ++next_indexes_[Edge::LEFT]) {
1316 if (points_consume_energy(
1317 grouped_intervals_sorted_by_x_[next_indexes_[Edge::LEFT]]
1318 .items_touching_coordinate)) {
1323 if (update_next_index[Edge::BOTTOM]) {
1324 for (; next_indexes_[Edge::BOTTOM] < indexes_[Edge::TOP];
1325 ++next_indexes_[Edge::BOTTOM]) {
1326 if (points_consume_energy(
1327 grouped_intervals_sorted_by_y_[next_indexes_[Edge::BOTTOM]]
1328 .items_touching_coordinate)) {
1333 if (update_next_index[Edge::RIGHT]) {
1334 for (; next_indexes_[Edge::RIGHT] > indexes_[Edge::LEFT];
1335 --next_indexes_[Edge::RIGHT]) {
1336 if (points_consume_energy(
1337 grouped_intervals_sorted_by_x_[next_indexes_[Edge::RIGHT]]
1338 .items_touching_coordinate)) {
1343 if (update_next_index[Edge::TOP]) {
1344 for (; next_indexes_[Edge::TOP] > indexes_[Edge::BOTTOM];
1345 --next_indexes_[Edge::TOP]) {
1346 if (points_consume_energy(
1347 grouped_intervals_sorted_by_y_[next_indexes_[Edge::TOP]]
1348 .items_touching_coordinate)) {
1354 probe_area_ = current_rectangle.Area();
1355 CacheShrinkDeltaEnergy(0);
1356 CacheShrinkDeltaEnergy(1);
1359void ProbingRectangle::Shrink(Edge edge) {
1362 ShrinkImpl<Edge::LEFT>();
1365 ShrinkImpl<Edge::BOTTOM>();
1368 ShrinkImpl<Edge::RIGHT>();
1371 ShrinkImpl<Edge::TOP>();
1376IntegerValue ProbingRectangle::GetShrinkDeltaArea(Edge edge)
const {
1377 const Rectangle current_rectangle = GetCurrentRectangle();
1378 const std::vector<PointsForCoordinate>& sorted_intervals =
1380 ? grouped_intervals_sorted_by_x_
1381 : grouped_intervals_sorted_by_y_;
1382 const IntegerValue coordinate =
1383 sorted_intervals[next_indexes_[edge]].coordinate;
1386 return (coordinate - current_rectangle.x_min) * current_rectangle.SizeY();
1388 return (coordinate - current_rectangle.y_min) * current_rectangle.SizeX();
1390 return (current_rectangle.x_max - coordinate) * current_rectangle.SizeY();
1392 return (current_rectangle.y_max - coordinate) * current_rectangle.SizeX();
1396void ProbingRectangle::CacheShrinkDeltaEnergy(
int dimension) {
1397 const Rectangle current_rectangle = GetCurrentRectangle();
1398 Rectangle next_rectangle_up = current_rectangle;
1399 Rectangle next_rectangle_down = current_rectangle;
1400 IntegerValue step_1d_size_up, step_1d_size_down;
1401 IntegerValue units_crossed_up, units_crossed_down;
1402 IntegerValue* delta_energy_up_ptr;
1403 IntegerValue* delta_energy_down_ptr;
1405 if (dimension == 0) {
1407 if (!CanShrink(Edge::LEFT)) {
1408 cached_delta_energy_[Edge::LEFT] = 0;
1409 cached_delta_energy_[Edge::RIGHT] = 0;
1413 next_rectangle_up.x_min =
1414 grouped_intervals_sorted_by_x_[next_indexes_[Edge::LEFT]].coordinate;
1415 next_rectangle_down.x_max =
1416 grouped_intervals_sorted_by_x_[next_indexes_[Edge::RIGHT]].coordinate;
1418 step_1d_size_up = next_rectangle_up.x_min - current_rectangle.x_min;
1419 step_1d_size_down = current_rectangle.x_max - next_rectangle_down.x_max;
1420 units_crossed_up = intersect_length_[Edge::LEFT];
1421 units_crossed_down = intersect_length_[Edge::RIGHT];
1422 delta_energy_up_ptr = &cached_delta_energy_[Edge::LEFT];
1423 delta_energy_down_ptr = &cached_delta_energy_[Edge::RIGHT];
1425 if (!CanShrink(Edge::TOP)) {
1426 cached_delta_energy_[Edge::BOTTOM] = 0;
1427 cached_delta_energy_[Edge::TOP] = 0;
1431 next_rectangle_up.y_min =
1432 grouped_intervals_sorted_by_y_[next_indexes_[Edge::BOTTOM]].coordinate;
1433 next_rectangle_down.y_max =
1434 grouped_intervals_sorted_by_y_[next_indexes_[Edge::TOP]].coordinate;
1436 step_1d_size_up = next_rectangle_up.y_min - current_rectangle.y_min;
1437 step_1d_size_down = current_rectangle.y_max - next_rectangle_down.y_max;
1438 units_crossed_up = intersect_length_[Edge::BOTTOM];
1439 units_crossed_down = intersect_length_[Edge::TOP];
1440 delta_energy_up_ptr = &cached_delta_energy_[Edge::BOTTOM];
1441 delta_energy_down_ptr = &cached_delta_energy_[Edge::TOP];
1443 IntegerValue delta_energy_up = 0;
1444 IntegerValue delta_energy_down = 0;
1447 for (
const int idx : ranges_touching_both_boundaries_[dimension]) {
1448 const RectangleInRange& range = intervals_[idx];
1450 range.bounding_area.x_min, range.bounding_area.x_max, range.x_size,
1451 current_rectangle.x_min, current_rectangle.x_max);
1453 range.bounding_area.y_min, range.bounding_area.y_max, range.y_size,
1454 current_rectangle.y_min, current_rectangle.y_max);
1455 const IntegerValue curr = curr_x * curr_y;
1456 delta_energy_up += curr;
1457 delta_energy_down += curr;
1459 if (dimension == 0) {
1461 range.bounding_area.x_min, range.bounding_area.x_max, range.x_size,
1462 next_rectangle_up.x_min, next_rectangle_up.x_max);
1464 range.bounding_area.x_min, range.bounding_area.x_max, range.x_size,
1465 next_rectangle_down.x_min, next_rectangle_down.x_max);
1467 delta_energy_up -= curr_y * up_x;
1468 delta_energy_down -= curr_y * down_x;
1471 range.bounding_area.y_min, range.bounding_area.y_max, range.y_size,
1472 next_rectangle_up.y_min, next_rectangle_up.y_max);
1474 range.bounding_area.y_min, range.bounding_area.y_max, range.y_size,
1475 next_rectangle_down.y_min, next_rectangle_down.y_max);
1477 delta_energy_up -= curr_x * up_y;
1478 delta_energy_down -= curr_x * down_y;
1481 delta_energy_up += units_crossed_up * step_1d_size_up;
1482 delta_energy_down += units_crossed_down * step_1d_size_down;
1483 *delta_energy_up_ptr = delta_energy_up;
1484 *delta_energy_down_ptr = delta_energy_down;
1487bool ProbingRectangle::CanShrink(Edge edge)
const {
1499std::vector<double> GetExpTable() {
1500 std::vector<double> table(101);
1501 for (
int i = 0; i <= 100; ++i) {
1502 table[i] = std::exp(-(i - 50) / 5.0);
1510 const std::vector<RectangleInRange>& intervals, absl::BitGenRef random,
1511 double temperature,
double candidate_energy_usage_factor) {
1515 static const std::vector<double>* cached_probabilities =
1516 new std::vector<double>(GetExpTable());
1518 const double inv_temp = 1.0 / temperature;
1519 absl::InlinedVector<ProbingRectangle::Edge, 4> candidates;
1520 absl::InlinedVector<IntegerValue, 4> energy_deltas;
1521 absl::InlinedVector<double, 4> weights;
1525 if (min_energy > rect_area) {
1527 }
else if (min_energy.value() >
1528 candidate_energy_usage_factor * rect_area.value()) {
1531 if (min_energy == 0) {
1535 energy_deltas.clear();
1537 for (
int border_idx = 0; border_idx < 4; ++border_idx) {
1543 candidates.push_back(border);
1546 energy_deltas.push_back(delta_energy - delta_area);
1548 const IntegerValue min_energy_delta =
1549 *std::min_element(energy_deltas.begin(), energy_deltas.end());
1551 for (
const IntegerValue delta_slack : energy_deltas) {
1552 const int64_t table_lookup =
1553 std::max((int64_t)0,
1554 std::min((int64_t)((delta_slack - min_energy_delta).value() *
1558 weights.push_back((*cached_probabilities)[table_lookup]);
1569std::string RenderDot(std::optional<Rectangle> bb,
1570 absl::Span<const Rectangle>
solution,
1571 std::string_view extra_dot_payload) {
1572 const std::vector<std::string> colors = {
"#0000ff80",
"#ee00ee80",
1573 "#ff000080",
"#eeee0080",
1574 "#00ff0080",
"#00eeee80"};
1575 std::stringstream ss;
1576 ss <<
"digraph {\n";
1577 ss <<
" graph [ bgcolor=lightgray ]\n";
1578 ss <<
" node [style=filled shape=box]\n";
1579 if (bb.has_value()) {
1580 ss <<
" bb [fillcolor=\"grey\" pos=\"" << 2 * bb->x_min + bb->SizeX()
1581 <<
"," << 2 * bb->y_min + bb->SizeY() <<
"!\" width=" << 2 * bb->SizeX()
1582 <<
" height=" << 2 * bb->SizeY() <<
"]\n";
1585 ss <<
" " <<
i <<
" [fillcolor=\"" << colors[
i % colors.size()]
1588 <<
"!\" width=" << 2 *
solution[
i].SizeX()
1589 <<
" height=" << 2 *
solution[
i].SizeY() <<
"]\n";
1591 ss << extra_dot_payload;
1596std::vector<Rectangle> FindEmptySpaces(
1597 const Rectangle& bounding_box, std::vector<Rectangle> ocupied_rectangles) {
1599 std::sort(ocupied_rectangles.begin(), ocupied_rectangles.end(),
1601 return std::tuple(a.x_min, -a.x_max, a.y_min) <
1602 std::tuple(b.x_min, -b.x_max, b.y_min);
1607std::vector<Rectangle> PavedRegionDifference(
1608 std::vector<Rectangle> original_region,
1609 absl::Span<const Rectangle> area_to_remove) {
1610 std::vector<Rectangle> new_area_to_cover;
1611 new_area_to_cover.reserve(original_region.size());
1612 for (
const Rectangle& rectangle : area_to_remove) {
1613 new_area_to_cover.clear();
1614 for (
const Rectangle& r : original_region) {
1615 const auto& new_rectangles = r.RegionDifference(rectangle);
1616 new_area_to_cover.insert(new_area_to_cover.end(), new_rectangles.begin(),
1617 new_rectangles.end());
1619 original_region.swap(new_area_to_cover);
1620 if (original_region.empty())
break;
1622 return original_region;
1631struct BinaryTreeNode {
1662 void RecomputeConnectedComponents(TreeNodeIndex idx) {
1664 if (node.occupying_box_index != -1) {
1665 node.connected_components_descendants = {
1666 union_find.FindRoot(node.occupying_box_index)};
1669 node.connected_components_descendants.clear();
1670 if (tree.IsLeaf(idx))
return;
1671 for (
const TreeNodeIndex child_idx :
1672 {tree.LeftChild(idx), tree.RightChild(idx)}) {
1676 tree_nodes[child_idx].connected_components_descendants) {
1677 node.connected_components_descendants.insert(union_find.FindRoot(c));
1685 void RemoveNodeIfXMaxLowerOrEqual(TreeNodeIndex idx,
int x_threshold) {
1686 BinaryTreeNode& node = tree_nodes[idx];
1687 if (node.occupying_box_index == -1) {
1691 if (node.occupying_box_x_max > x_threshold) {
1695 node.occupying_box_index = -1;
1696 RecomputeConnectedComponents(idx);
1699 void UpdateChildrenIntersecting(TreeNodeIndex idx,
int sweep_line_x_pos,
1700 int component_index,
1701 std::vector<int>* new_connections) {
1702 if (
tree.IsLeaf(idx))
return;
1703 for (
const TreeNodeIndex child_idx :
1704 {
tree.LeftChild(idx),
tree.RightChild(idx)}) {
1707 if (child_node.occupying_box_index != -1) {
1708 if (
union_find.AddEdge(child_node.occupying_box_index,
1710 new_connections->push_back(child_node.occupying_box_index);
1716 const bool had_different_component =
1717 absl::c_any_of(child_node.connected_components_descendants,
1718 [
this, component_index](
const int c) {
1719 return !union_find.Connected(c, component_index);
1723 child_node.connected_components_descendants = {component_index};
1733 if (had_different_component) {
1740 bool UpdateParents(TreeNodeIndex node,
int sweep_line_x_pos,
1741 int component_index, std::vector<int>* new_connections) {
1742 if (node ==
tree.Root())
return false;
1743 for (TreeNodeIndex parent =
tree.Parent(node); parent !=
tree.Root();
1744 parent =
tree.Parent(parent)) {
1747 if (parent_value.occupying_box_index != -1) {
1748 if (
union_find.AddEdge(parent_value.occupying_box_index,
1750 new_connections->push_back(parent_value.occupying_box_index);
1754 parent_value.connected_components_descendants.insert(component_index);
1763 void AddInterval(TreeNodeIndex idx,
int sweep_line_x_pos,
int box_index,
1764 int x_max, std::vector<int>* new_connections) {
1766 int cur_box_component =
union_find.FindRoot(box_index);
1768 if (node.occupying_box_index == -1) {
1769 node.connected_components_descendants = {box_index};
1770 node.occupying_box_index = box_index;
1771 node.occupying_box_x_max = x_max;
1772 const bool had_occupied_parent = UpdateParents(
1773 idx, sweep_line_x_pos, cur_box_component, new_connections);
1776 if (!had_occupied_parent) {
1777 UpdateChildrenIntersecting(idx, sweep_line_x_pos, cur_box_component,
1782 if (union_find.AddEdge(node.occupying_box_index, cur_box_component)) {
1783 new_connections->push_back(node.occupying_box_index);
1784 cur_box_component = union_find.FindRoot(cur_box_component);
1786 node.connected_components_descendants = {cur_box_component};
1787 if (node.occupying_box_x_max < x_max) {
1789 node.occupying_box_index = box_index;
1790 node.occupying_box_x_max = x_max;
1795 FixedShapeBinaryTree tree;
1796 util_intops::StrongVector<TreeNodeIndex, BinaryTreeNode> tree_nodes;
1811 absl::Span<const Rectangle32> rectangles, int32_t
y_max) {
1817 DCHECK(std::is_sorted(rectangles.begin(), rectangles.end(),
1819 return a.x_min < b.x_min;
1824 std::vector<TreeNodeIndex> interval_pieces;
1825 std::vector<int> new_connections;
1826 std::vector<std::pair<int, int>> arcs;
1827 for (
int rectangle_index = 0; rectangle_index < rectangles.size();
1828 ++rectangle_index) {
1829 DCHECK_LT(rectangles[rectangle_index].x_min,
1830 rectangles[rectangle_index].x_max);
1831 DCHECK_LT(rectangles[rectangle_index].y_min,
1832 rectangles[rectangle_index].y_max);
1833 const int sweep_line_x_pos = rectangles[rectangle_index].x_min;
1834 const Rectangle32& r = rectangles[rectangle_index];
1835 interval_pieces.clear();
1836 interval_tree.tree.PartitionIntervalIntoNodes(
1837 LeafIndex(r.
y_min), LeafIndex(r.
y_max - 1), &interval_pieces);
1838 new_connections.clear();
1839 for (
const TreeNodeIndex& node : interval_pieces) {
1840 interval_tree.AddInterval(node, sweep_line_x_pos, rectangle_index,
1841 r.
x_max, &new_connections);
1843 for (
const int new_connection : new_connections) {
1844 arcs.push_back({rectangles[new_connection].index, r.
index});
1851struct PostProcessedResult {
1852 std::vector<Rectangle32> rectangles_sorted_by_x_min;
1853 std::pair<int32_t, int32_t> bounding_box;
1856PostProcessedResult ConvertToRectangle32WithNonZeroSizes(
1857 absl::Span<const Rectangle> rectangles) {
1906 if (rectangles.empty())
return {};
1913 std::vector<std::tuple<IntegerValue, Event, int>> x_events;
1914 std::vector<std::tuple<IntegerValue, Event, int>> y_events;
1915 x_events.reserve(rectangles.size() * 2);
1916 y_events.reserve(rectangles.size() * 2);
1917 for (
int i = 0;
i < rectangles.size(); ++
i) {
1918 const Rectangle& r = rectangles[
i];
1919 DCHECK_GE(r.SizeX(), 0);
1920 DCHECK_GE(r.SizeY(), 0);
1921 if (r.SizeX() == 0) {
1922 x_events.push_back({r.x_min, Event::kPoint,
i});
1924 x_events.push_back({r.x_min, Event::kBegin,
i});
1925 x_events.push_back({r.x_max, Event::kEnd,
i});
1927 if (r.SizeY() == 0) {
1928 y_events.push_back({r.y_min, Event::kPoint,
i});
1930 y_events.push_back({r.y_min, Event::kBegin,
i});
1931 y_events.push_back({r.y_max, Event::kEnd,
i});
1934 std::sort(y_events.begin(), y_events.end());
1936 std::vector<Rectangle32> rectangles32;
1937 rectangles32.resize(rectangles.size());
1938 IntegerValue prev_y = 0;
1939 Event prev_event = Event::kEnd;
1941 for (
const auto [y, event, index] : y_events) {
1942 if ((prev_event != event && prev_event != Event::kEnd) || prev_y != y ||
1943 event == Event::kPoint || cur_index == -1) {
1949 rectangles32[index].y_min = cur_index;
1950 rectangles32[index].index = index;
1953 rectangles32[index].y_max = cur_index;
1956 rectangles32[index].y_min = cur_index;
1957 rectangles32[index].y_max = cur_index + 1;
1958 rectangles32[index].index = index;
1964 const int max_y_index = cur_index + 1;
1968 std::sort(x_events.begin(), x_events.end());
1969 IntegerValue prev_x = 0;
1970 prev_event = Event::kEnd;
1972 for (
const auto [x, event, index] : x_events) {
1973 if ((prev_event != event && prev_event != Event::kEnd) || prev_x != x ||
1974 event == Event::kPoint || cur_index == -1) {
1980 rectangles32[index].x_min = cur_index;
1983 rectangles32[index].x_max = cur_index;
1986 rectangles32[index].x_min = cur_index;
1987 rectangles32[index].x_max = cur_index + 1;
1993 const int max_x_index = cur_index + 1;
1995 std::vector<Rectangle32> sorted_rectangles32;
1996 sorted_rectangles32.reserve(rectangles.size());
1997 for (
const auto [x, event, index] : x_events) {
1998 if (event == Event::kBegin || event == Event::kPoint) {
1999 sorted_rectangles32.push_back(rectangles32[index]);
2003 return {sorted_rectangles32, {max_x_index, max_y_index}};
2005template <
typename RectangleT>
2006std::optional<std::pair<int, int>> FindOneIntersectionIfPresentImpl(
2007 absl::Span<const RectangleT> rectangles) {
2008 using CoordinateType = std::decay_t<
decltype(RectangleT::x_min)>;
2009 DCHECK(absl::c_is_sorted(rectangles,
2010 [](
const RectangleT& a,
const RectangleT& b) {
2011 return a.x_min <
b.x_min;
2018 CoordinateType y_min;
2019 bool operator<(
const Element& other)
const {
return y_min < other.y_min; }
2024 absl::btree_set<Element> interval_set;
2026 for (
int i = 0;
i < rectangles.size(); ++
i) {
2027 const CoordinateType
x = rectangles[
i].x_min;
2028 const CoordinateType y_min = rectangles[
i].y_min;
2029 const CoordinateType y_max = rectangles[
i].y_max;
2032 DCHECK_LE(y_min, y_max);
2037 auto [it, inserted] = interval_set.insert({
i, y_min});
2039 if (rectangles[it->index].x_max <= x) {
2044 return {{it->index,
i}};
2049 if (it != interval_set.begin()) {
2050 auto it_before = it;
2054 if (rectangles[it_before->index].x_max <= x) {
2057 it = interval_set.erase(it_before);
2059 DCHECK_LE(it_before->y_min, y_min);
2060 const CoordinateType y_max_before =
2061 rectangles[it_before->index].y_max;
2062 if (y_max_before > y_min) {
2064 return {{it_before->index,
i}};
2073 while (it != interval_set.end()) {
2075 if (rectangles[it->index].x_max <= x) {
2076 it = interval_set.erase(it);
2080 DCHECK_LE(y_min, it->y_min);
2081 if (y_max > it->y_min) {
2083 return {{it->index,
i}};
2095 absl::Span<const Rectangle> rectangles) {
2096 auto postprocessed = ConvertToRectangle32WithNonZeroSizes(rectangles);
2098 postprocessed.rectangles_sorted_by_x_min,
2099 postprocessed.bounding_box.second);
2102std::optional<std::pair<int, int>> FindOneIntersectionIfPresent(
2103 absl::Span<const Rectangle> rectangles) {
2104 return FindOneIntersectionIfPresentImpl(rectangles);
2107std::optional<std::pair<int, int>> FindOneIntersectionIfPresentWithZeroArea(
2108 absl::Span<const Rectangle> rectangles) {
2109 auto postprocessed = ConvertToRectangle32WithNonZeroSizes(rectangles);
2110 std::optional<std::pair<int, int>> result = FindOneIntersectionIfPresentImpl(
2111 absl::MakeConstSpan(postprocessed.rectangles_sorted_by_x_min));
2112 if (!result.has_value())
return {};
2113 return {{postprocessed.rectangles_sorted_by_x_min[result->first].index,
2114 postprocessed.rectangles_sorted_by_x_min[result->second].index}};
A connected components finder that only works on dense ints.
void AddMandatoryConsumption(IntegerValue x_min, IntegerValue x_max, IntegerValue y_height)
void AddRectangle(IntegerValue x_min, IntegerValue x_max, IntegerValue y_min, IntegerValue y_max)
Adds a rectangle to the current shape.
void BuildResidualCapacityProfile(std::vector< Rectangle > *result)
void ResetFromPairs(const Collection &pairs, int minimum_num_nodes=0)
Similar to ResetFromFlatMapping().
IntegerValue GetShrinkDeltaEnergy(Edge edge) const
How much of GetMinimumEnergy() will change if Shrink() is called.
void Reset()
Reset to the bounding box of the whole set.
IntegerValue GetCurrentRectangleArea() const
IntegerValue GetMinimumEnergy() const
IntegerValue GetShrinkDeltaArea(Edge edge) const
How much of GetCurrentRectangleArea() will change if Shrink() is called.
Rectangle GetCurrentRectangle() const
bool CanShrink(Edge edge) const
void AddPresenceReason(int t)
IntegerValue ShiftedEndMax(int t) const
IntegerValue ShiftedStartMin(int t) const
void ClearReason()
Functions to clear and then set the current reason.
IntegerValue SizeMin(int t) const
void AddEnergyMinInIntervalReason(int t, IntegerValue min, IntegerValue max)
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
void STLClearObject(T *obj)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
CompactVectorVector< int > GetOverlappingRectangleComponents(absl::Span< const Rectangle > rectangles)
absl::Span< int > FilterBoxesAndRandomize(absl::Span< const Rectangle > cached_rectangles, absl::Span< int > boxes, IntegerValue threshold_x, IntegerValue threshold_y, absl::BitGenRef random)
bool AnalyzeIntervals(bool transpose, absl::Span< const int > local_boxes, absl::Span< const Rectangle > rectangles, absl::Span< const IntegerValue > rectangle_energies, IntegerValue *x_threshold, IntegerValue *y_threshold, Rectangle *conflict)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
absl::Span< int > FilterBoxesThatAreTooLarge(absl::Span< const Rectangle > cached_rectangles, absl::Span< const IntegerValue > energies, absl::Span< int > boxes)
std::vector< int > GetIntervalArticulationPoints(std::vector< IndexedInterval > *intervals)
void AppendPairwiseRestrictions(absl::Span< const ItemWithVariableSize > items, std::vector< PairwiseRestriction > *result)
void ConstructOverlappingSets(absl::Span< IndexedInterval > intervals, CompactVectorVector< int > *result, absl::Span< const int > order)
int WeightedPick(absl::Span< const double > input, absl::BitGenRef random)
bool ReportEnergyConflict(Rectangle bounding_box, absl::Span< const int > boxes, SchedulingConstraintHelper *x, SchedulingConstraintHelper *y)
std::vector< std::pair< int, int > > FindPartialRectangleIntersectionsImpl(absl::Span< const Rectangle32 > rectangles, int32_t y_max)
FindRectanglesResult FindRectanglesWithEnergyConflictMC(const std::vector< RectangleInRange > &intervals, absl::BitGenRef random, double temperature, double candidate_energy_usage_factor)
std::vector< Rectangle > PavedRegionDifference(std::vector< Rectangle > original_region, absl::Span< const Rectangle > area_to_remove)
bool BoxesAreInEnergyConflict(absl::Span< const Rectangle > rectangles, absl::Span< const IntegerValue > energies, absl::Span< const int > boxes, Rectangle *conflict)
std::vector< std::pair< int, int > > FindPartialRectangleIntersections(absl::Span< const Rectangle > rectangles)
IntegerValue Smallest1DIntersection(IntegerValue range_min, IntegerValue range_max, IntegerValue size, IntegerValue interval_min, IntegerValue interval_max)
void GetOverlappingIntervalComponents(std::vector< IndexedInterval > *intervals, std::vector< std::vector< int > > *components)
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
ClosedInterval::Iterator end(ClosedInterval interval)
void FindStronglyConnectedComponents(NodeIndex num_nodes, const Graph &graph, SccOutput *components)
Simple wrapper function for most usage.
int occupying_box_index
-1 if not occupied.
absl::flat_hash_set< int > connected_components_descendants
Contains exactly one element if occupying_box_index != -1.
std::vector< Rectangle > conflicts
std::vector< Rectangle > candidates
void GrowToInclude(const Rectangle &other)
absl::InlinedVector< Rectangle, 4 > RegionDifference(const Rectangle &other) const
IntegerValue SizeX() const
bool IsDisjoint(const Rectangle &other) const
Rectangle Intersect(const Rectangle &other) const
The methods below are not meant to be used with zero-area rectangles.
DenseConnectedComponentsFinder union_find
void RemoveNodeIfXMaxLowerOrEqual(TreeNodeIndex idx, int x_threshold)
void UpdateChildrenIntersecting(TreeNodeIndex idx, int sweep_line_x_pos, int component_index, std::vector< int > *new_connections)
FixedShapeBinaryTree tree
util_intops::StrongVector< TreeNodeIndex, BinaryTreeNode > tree_nodes