35 using Offsets = std::map<SDL_DisplayID, std::pair<SDL_Rect, SDL_Rect>>;
37 inline bool alignX(
const SDL_Rect& a,
const SDL_Rect& b)
46 inline bool alignY(
const SDL_Rect& a,
const SDL_Rect& b)
55 inline std::vector<SDL_DisplayID>
56 updateDisplayOffsetsForNeighbours(Offsets& offsets, SDL_DisplayID
id,
57 const std::vector<SDL_DisplayID>& ignore = {})
59 auto first = offsets.at(
id);
60 std::vector<SDL_DisplayID> neighbours;
62 for (
auto& entry : offsets)
64 if (entry.first ==
id)
66 if (std::find(ignore.begin(), ignore.end(), entry.first) != ignore.end())
69 bool neighbor =
false;
70 const bool ax = alignX(entry.second.first, first.first);
71 const bool ay = alignY(entry.second.first, first.first);
79 auto crossOffset = [](
int ePos,
int fPos,
int fLogical,
int fPixel) ->
int
83 return static_cast<int>(
84 std::lround(
static_cast<double>(ePos - fPos) * fPixel / fLogical));
89 if (entry.second.first.x < first.first.x)
90 entry.second.second.x = first.second.x - entry.second.second.w;
92 entry.second.second.x = first.second.x + first.second.w;
94 entry.second.second.y =
95 first.second.y + crossOffset(entry.second.first.y, first.first.y,
96 first.first.h, first.second.h);
101 if (entry.second.first.y < first.first.y)
102 entry.second.second.y = first.second.y - entry.second.second.h;
104 entry.second.second.y = first.second.y + first.second.h;
106 entry.second.second.x =
107 first.second.x + crossOffset(entry.second.first.x, first.first.x,
108 first.first.w, first.second.w);
113 neighbours.push_back(entry.first);
122 inline void walk(Offsets& offsets, SDL_DisplayID primary)
129 auto it = offsets.find(primary);
130 if (it != offsets.end())
132 it->second.second.x = it->second.first.x;
133 it->second.second.y = it->second.first.y;
135 std::vector<SDL_DisplayID> handled;
136 handled.push_back(primary);
138 auto neighbors = updateDisplayOffsetsForNeighbours(offsets, primary);
139 while (!neighbors.empty())
141 auto neighbor = neighbors.front();
142 neighbors.erase(neighbors.begin());
144 if (std::find(handled.begin(), handled.end(), neighbor) != handled.end())
146 handled.push_back(neighbor);
148 auto next = updateDisplayOffsetsForNeighbours(offsets, neighbor, handled);
149 neighbors.insert(neighbors.end(), next.begin(), next.end());
152 inline bool spans(
int a,
int alen,
int b,
int blen)
154 return (a < b + blen) && (b < a + alen);
159 inline bool touchX(
const SDL_Rect& a,
const SDL_Rect& b)
161 return ((a.x + a.w == b.x) || (b.x + b.w == a.x)) && spans(a.y, a.h, b.y, b.h);
164 inline bool touchY(
const SDL_Rect& a,
const SDL_Rect& b)
166 return ((a.y + a.h == b.y) || (b.y + b.h == a.y)) && spans(a.x, a.w, b.x, b.w);
169 inline bool overlap(
const SDL_Rect& a,
const SDL_Rect& b)
171 return spans(a.x, a.w, b.x, b.w) && spans(a.y, a.h, b.y, b.h);
175 inline int scaled(
int distance,
int logical,
int pixel)
179 return static_cast<int>(std::lround(
static_cast<double>(distance) * pixel / logical));
185 inline int along(
int ePos,
int eLogical,
int ePixel,
int fPos,
int fLogical,
int fPixel,
186 int fPixelPos,
bool fromEnd)
190 const int d = ePos - fPos;
192 ((d >= 0) ? scaled(d, fLogical, fPixel) : scaled(d, eLogical, ePixel));
194 const int d = (ePos + eLogical) - (fPos + fLogical);
195 const int end = fPixelPos + fPixel +
196 ((d <= 0) ? scaled(d, fLogical, fPixel) : scaled(d, eLogical, ePixel));
200 inline bool isPlaced(
const std::vector<SDL_DisplayID>& placed, SDL_DisplayID
id)
202 return std::find(placed.begin(), placed.end(),
id) != placed.end();
207 inline std::vector<SDL_DisplayID> placeNeighbours(Offsets& offsets, SDL_DisplayID
id,
208 std::vector<SDL_DisplayID>& placed)
210 const auto f = offsets.at(
id);
211 std::vector<SDL_DisplayID> result;
212 for (
auto& entry : offsets)
214 const auto& e = entry.second.first;
215 auto& pixel = entry.second.second;
216 const bool beside = touchX(e, f.first);
217 if (isPlaced(placed, entry.first) || (!beside && !touchY(e, f.first)))
220 const auto place = [&](
bool fromEnd)
224 pixel.x = (e.x < f.first.x) ? f.second.x - pixel.w : f.second.x + f.second.w;
225 pixel.y = along(e.y, e.h, pixel.h, f.first.y, f.first.h, f.second.h, f.second.y,
230 pixel.y = (e.y < f.first.y) ? f.second.y - pixel.h : f.second.y + f.second.h;
231 pixel.x = along(e.x, e.w, pixel.w, f.first.x, f.first.w, f.second.w, f.second.x,
234 return std::none_of(placed.begin(), placed.end(), [&](SDL_DisplayID other)
235 { return overlap(pixel, offsets.at(other).second); });
240 if (!place(
false) && !place(
true))
241 std::ignore = place(
false);
242 placed.push_back(entry.first);
243 result.push_back(entry.first);
251 inline void placeOnce(Offsets& offsets, SDL_DisplayID primary)
253 auto& origin = offsets.at(primary);
254 origin.second.x = origin.first.x;
255 origin.second.y = origin.first.y;
256 std::vector<SDL_DisplayID> placed{ primary };
257 std::vector<SDL_DisplayID> next{ primary };
258 for (
size_t i = 0; i < next.size(); i++)
260 const auto more = placeNeighbours(offsets, next[i], placed);
261 next.insert(next.end(), more.begin(), more.end());
267 inline bool valid(
const Offsets& offsets,
const std::vector<SDL_DisplayID>& selection)
269 std::vector<SDL_DisplayID> ids;
270 for (
const auto& entry : offsets)
272 if (selection.empty() || isPlaced(selection, entry.first))
273 ids.push_back(entry.first);
275 for (
size_t i = 0; i < ids.size(); i++)
276 for (
size_t j = i + 1; j < ids.size(); j++)
277 if (overlap(offsets.at(ids[i]).second, offsets.at(ids[j]).second))
282 std::vector<SDL_DisplayID> reached{ ids.front() };
283 for (
size_t i = 0; i < reached.size(); i++)
285 const auto& a = offsets.at(reached[i]).second;
286 for (
const auto id : ids)
288 const auto& b = offsets.at(
id).second;
289 if (!isPlaced(reached,
id) && (touchX(a, b) || touchY(a, b)))
290 reached.push_back(
id);
293 return reached.size() == ids.size();
300 inline void update(Offsets& offsets, SDL_DisplayID primary,
301 const std::vector<SDL_DisplayID>& selection = {})
305 if (offsets.count(primary) == 0)
306 primary = offsets.begin()->first;
308 auto placed = offsets;
309 placeOnce(placed, primary);
310 if (valid(placed, selection))
313 walk(offsets, primary);