14#ifndef OR_TOOLS_SAT_DIFFN_UTIL_H_
15#define OR_TOOLS_SAT_DIFFN_UTIL_H_
28#include "absl/container/flat_hash_set.h"
29#include "absl/container/inlined_vector.h"
30#include "absl/log/check.h"
31#include "absl/random/bit_gen_ref.h"
32#include "absl/strings/str_format.h"
33#include "absl/types/optional.h"
34#include "absl/types/span.h"
84 template <
typename Sink>
86 absl::Format(&sink,
"rectangle(x(%i..%i), y(%i..%i))", r.
x_min.value(),
98 return Rectangle{.x_min = IntegerValue(0),
99 .x_max = IntegerValue(0),
100 .y_min = IntegerValue(0),
101 .y_max = IntegerValue(0)};
106 const IntegerValue ret_x_min = std::max(
x_min, other.
x_min);
107 const IntegerValue ret_y_min = std::max(
y_min, other.
y_min);
108 const IntegerValue ret_x_max = std::min(
x_max, other.
x_max);
109 const IntegerValue ret_y_max = std::min(
y_max, other.
y_max);
111 if (ret_x_min >= ret_x_max || ret_y_min >= ret_y_max) {
122 const IntegerValue ret_x_min = std::max(
x_min, other.
x_min);
123 const IntegerValue ret_y_min = std::max(
y_min, other.
y_min);
124 const IntegerValue ret_x_max = std::min(
x_max, other.
x_max);
125 const IntegerValue ret_y_max = std::min(
y_max, other.
y_max);
127 if (ret_x_min >= ret_x_max || ret_y_min >= ret_y_max) {
130 return (ret_x_max - ret_x_min) * (ret_y_max - ret_y_min);
136 const double diff_x =
137 (
static_cast<double>(a.
x_min.value()) + a.
x_max.value()) / 2.0 -
138 (
static_cast<double>(
b.x_min.value()) +
b.x_max.value()) / 2.0;
139 const double diff_y =
140 (
static_cast<double>(a.
y_min.value()) + a.
y_max.value()) / 2.0 -
141 (
static_cast<double>(
b.y_min.value()) +
b.y_max.value()) / 2.0;
142 return std::sqrt(diff_x * diff_x + diff_y * diff_y);
147 const double diff_x =
148 (
static_cast<double>(a.
x_min.value()) + a.
x_max.value()) / 2.0 -
149 (
static_cast<double>(
b.x_min.value()) +
b.x_max.value()) / 2.0;
150 const double diff_y =
151 (
static_cast<double>(a.
y_min.value()) + a.
y_max.value()) / 2.0 -
152 (
static_cast<double>(
b.y_min.value()) +
b.y_max.value()) / 2.0;
153 return std::max(std::abs(diff_x), std::abs(diff_y));
159 absl::Span<const Rectangle> rectangles);
164 absl::Span<const IntegerValue> energies,
165 absl::Span<const int> boxes,
166 Rectangle* conflict =
nullptr);
175 SchedulingConstraintHelper* x,
176 SchedulingConstraintHelper* y);
187 absl::Span<const Rectangle> rectangles,
188 absl::Span<const IntegerValue> rectangle_energies,
189 IntegerValue* x_threshold, IntegerValue* y_threshold,
190 Rectangle* conflict =
nullptr);
196 absl::Span<const Rectangle> cached_rectangles, absl::Span<int> boxes,
197 IntegerValue threshold_x, IntegerValue threshold_y, absl::BitGenRef random);
204 absl::Span<const Rectangle> cached_rectangles,
205 absl::Span<const IntegerValue> energies, absl::Span<int> boxes);
222 std::tie(
b.start,
b.end,
b.index);
231 template <
typename Sink>
233 absl::Format(&sink,
"[%v..%v] (#%v)", interval.
start, interval.
end,
253 CompactVectorVector<int>* result,
254 absl::Span<const int> order = {});
261 std::vector<IndexedInterval>* intervals,
262 std::vector<std::vector<int>>* components);
269 std::vector<IndexedInterval>* intervals);
283 bool IsFixed()
const {
return x.IsFixed() &&
y.IsFixed(); }
285 template <
typename Sink>
287 absl::Format(&sink,
"Item %v: [(%v..%v)-(%v..%v)] x [(%v..%v)-(%v..%v)]",
320 std::vector<PairwiseRestriction>* result);
325 absl::Span<const ItemWithVariableSize> items,
326 absl::Span<const ItemWithVariableSize> other_items,
327 std::vector<PairwiseRestriction>* result);
346 IntegerValue
start = IntegerValue(0);
353 void AddRectangle(IntegerValue x_min, IntegerValue x_max, IntegerValue y_min,
359 IntegerValue y_height);
380 enum EventType { START_RECTANGLE, END_RECTANGLE, CHANGE_MANDATORY_PROFILE };
390 bool operator<(
const Event& other)
const {
return time < other.time; }
394 struct QueueElement {
395 int Index()
const {
return index; }
396 bool operator<(
const QueueElement& o)
const {
return value < o.value; }
402 static Event StartRectangleEvent(
int index, IntegerValue x_min,
403 IntegerValue y_min, IntegerValue y_max) {
404 return {x_min, y_min, y_max, START_RECTANGLE, index};
407 static Event EndRectangleEvent(
int index, IntegerValue x_max) {
411 static Event ChangeMandatoryProfileEvent(IntegerValue x, IntegerValue delta) {
413 CHANGE_MANDATORY_PROFILE, -1};
416 std::vector<Event> events_;
417 int num_rectangles_added_ = 0;
424 IntegerValue range_max, IntegerValue size,
425 IntegerValue interval_min,
426 IntegerValue interval_max);
480 IntegerValue smallest_area = std::numeric_limits<IntegerValue>::max();
482 for (
int corner_idx = 0; corner_idx < 4; ++corner_idx) {
485 const IntegerValue intersection_area = intersection.
Area();
486 if (intersection_area == 0) {
489 if (intersection_area < smallest_area) {
490 smallest_area = intersection_area;
491 best_intersection = std::move(intersection);
494 return best_intersection;
498 const Rectangle& containing_area)
const {
501 containing_area.
x_max) *
504 containing_area.
y_max);
521 const IntegerValue& min_intersect_x,
522 const IntegerValue& min_intersect_y) {
532 DCHECK_GE(
x_size, min_intersect_x);
533 DCHECK_GE(
y_size, min_intersect_y);
536 const IntegerValue x_headroom =
x_size - min_intersect_x;
537 const IntegerValue y_headroom =
y_size - min_intersect_y;
547 template <
typename Sink>
549 absl::Format(&sink,
"item(size=%vx%v, BB=%v)", r.
x_size, r.
y_size,
600 return cached_delta_energy_[edge];
614 const std::vector<RectangleInRange>&
Intervals()
const {
return intervals_; }
622 void CacheShrinkDeltaEnergy(
int dimension);
627 struct IntervalPoint {
632 std::vector<IntervalPoint> interval_points_sorted_by_x_;
633 std::vector<IntervalPoint> interval_points_sorted_by_y_;
637 struct PointsForCoordinate {
638 IntegerValue coordinate;
639 absl::Span<IntervalPoint> items_touching_coordinate;
641 std::vector<PointsForCoordinate> grouped_intervals_sorted_by_x_;
642 std::vector<PointsForCoordinate> grouped_intervals_sorted_by_y_;
644 const std::vector<RectangleInRange>& intervals_;
646 IntegerValue full_energy_;
647 IntegerValue minimum_energy_;
648 IntegerValue probe_area_;
650 int next_indexes_[4];
652 absl::flat_hash_set<int> ranges_touching_both_boundaries_[2];
653 IntegerValue corner_count_[4] = {0, 0, 0, 0};
654 IntegerValue intersect_length_[4] = {0, 0, 0, 0};
655 IntegerValue cached_delta_energy_[4];
677 const std::vector<RectangleInRange>& intervals, absl::BitGenRef random,
678 double temperature,
double candidate_energy_usage_factor);
682std::string
RenderDot(std::optional<Rectangle> bb,
683 absl::Span<const Rectangle>
solution,
684 std::string_view extra_dot_payload =
"");
690 const Rectangle& bounding_box, std::vector<Rectangle> ocupied_rectangles);
697 std::vector<Rectangle> original_region,
698 absl::Span<const Rectangle> area_to_remove);
702 absl::Span<const Rectangle> other) {
725 absl::Span<const Rectangle> rectangles);
736 absl::Span<const Rectangle> rectangles);
741 absl::Span<const Rectangle> rectangles);
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.
IntegerValue GetBoundingArea()
void BuildResidualCapacityProfile(std::vector< Rectangle > *result)
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.
const std::vector< RectangleInRange > & Intervals() const
void ValidateInvariants() const
ProbingRectangle(const std::vector< RectangleInRange > &intervals)
It will initialize with the bounding box of the whole set.
Rectangle GetCurrentRectangle() const
bool CanShrink(Edge edge) const
bool RegionIncludesOther(absl::Span< const Rectangle > region, absl::Span< const Rectangle > other)
The two regions must be defined by non-overlapping rectangles.
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)
std::optional< std::pair< int, int > > FindOneIntersectionIfPresent(absl::Span< const Rectangle > rectangles)
double CenterToCenterLInfinityDistance(const Rectangle &a, const Rectangle &b)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
std::vector< Rectangle > FindEmptySpaces(const Rectangle &bounding_box, std::vector< Rectangle > ocupied_rectangles)
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)
double CenterToCenterL2Distance(const Rectangle &a, const Rectangle &b)
Returns the L2 distance between the centers of the two rectangles.
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)
bool ReportEnergyConflict(Rectangle bounding_box, absl::Span< const int > boxes, SchedulingConstraintHelper *x, SchedulingConstraintHelper *y)
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::optional< std::pair< int, int > > FindOneIntersectionIfPresentWithZeroArea(absl::Span< const Rectangle > rectangles)
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)
IntegerValue CapSubI(IntegerValue a, IntegerValue b)
IntegerValue CapProdI(IntegerValue a, IntegerValue b)
Overflows and saturated arithmetic.
std::string RenderDot(std::optional< Rectangle > bb, absl::Span< const Rectangle > solution, std::string_view extra_dot_payload)
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
bool operator==(const Rectangle &other) const
bool operator<(const Rectangle &other) const
Rectangle(IntegerValue start, IntegerValue height)
std::vector< Rectangle > conflicts
std::vector< Rectangle > candidates
bool operator()(const IndexedInterval &a, const IndexedInterval &b) const
bool operator()(const IndexedInterval &a, const IndexedInterval &b) const
bool operator==(const IndexedInterval &rhs) const
friend void AbslStringify(Sink &sink, const IndexedInterval &interval)
friend void AbslStringify(Sink &sink, const ItemWithVariableSize &item)
PairwiseRestrictionType type
bool operator==(const PairwiseRestriction &rhs) const
Rectangle GetMandatoryRegion() const
Rectangle GetMinimumIntersection(const Rectangle &containing_area) const
Returns an empty rectangle if it is possible for no intersection to happen.
Rectangle GetBoudingBox() const
IntegerValue GetMinimumIntersectionArea(const Rectangle &containing_area) const
friend void AbslStringify(Sink &sink, const RectangleInRange &r)
static RectangleInRange BiggestWithMinIntersection(const Rectangle &containing_area, const RectangleInRange &original, const IntegerValue &min_intersect_x, const IntegerValue &min_intersect_y)
bool operator==(const RectangleInRange &other) const
Rectangle GetAtCorner(Corner p) const
static Rectangle GetEmpty()
bool operator==(const Rectangle &other) const
void GrowToInclude(const Rectangle &other)
bool operator!=(const Rectangle &other) const
IntegerValue CapArea() const
absl::InlinedVector< Rectangle, 4 > RegionDifference(const Rectangle &other) const
IntegerValue Area() const
IntegerValue SizeY() const
bool IsInsideOf(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.
IntegerValue IntersectArea(const Rectangle &other) const
friend void AbslStringify(Sink &sink, const Rectangle &r)