1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
3 overlap.c for the Openbox window manager
4 Copyright (c) 2011, 2013 Ian Zimmerman
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 See the COPYING file for a copy of the GNU General Public License.
21 #include "place_overlap.h"
25 static void make_grid(const Rect* client_rects,
32 static int best_direction(const Point* grid_point,
33 const Rect* client_rects,
37 Point* best_top_left);
39 static int total_overlap(const Rect* client_rects,
41 const Rect* proposed_rect);
43 static void center_in_field(Point* grid_point,
46 const Rect* client_rects,
52 /* Choose the placement on a grid with least overlap */
54 void place_overlap_find_least_placement(const Rect* client_rects,
60 POINT_SET(*result, monitor->x, monitor->y);
61 int overlap = G_MAXINT;
62 int max_edges = 2 * (n_client_rects + 1);
64 int x_edges[max_edges];
65 int y_edges[max_edges];
66 make_grid(client_rects, n_client_rects, monitor,
67 x_edges, y_edges, max_edges);
69 for (i = 0; i < max_edges; ++i) {
70 if (x_edges[i] == G_MAXINT)
73 for (j = 0; j < max_edges; ++j) {
74 if (y_edges[j] == G_MAXINT)
76 Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
79 best_direction(&grid_point, client_rects, n_client_rects,
80 monitor, req_size, &best_top_left);
81 if (this_overlap < overlap) {
82 overlap = this_overlap;
83 *result = best_top_left;
91 if (config_place_center && overlap == 0) {
92 center_in_field(result,
103 static int compare_ints(const void* a,
106 const int* ia = (const int*)a;
107 const int* ib = (const int*)b;
111 static void uniquify(int* edges,
117 while (j < n_edges) {
118 int last = edges[j++];
120 while (j < n_edges && edges[j] == last)
123 /* fill the rest with nonsense */
124 for (; i < n_edges; ++i)
128 static void make_grid(const Rect* client_rects,
137 for (i = 0; i < n_client_rects; ++i) {
138 if (!RECT_INTERSECTS_RECT(client_rects[i], *monitor))
140 x_edges[n_edges] = client_rects[i].x;
141 y_edges[n_edges++] = client_rects[i].y;
142 x_edges[n_edges] = client_rects[i].x + client_rects[i].width;
143 y_edges[n_edges++] = client_rects[i].y + client_rects[i].height;
145 x_edges[n_edges] = monitor->x;
146 y_edges[n_edges++] = monitor->y;
147 x_edges[n_edges] = monitor->x + monitor->width;
148 y_edges[n_edges++] = monitor->y + monitor->height;
149 for (i = n_edges; i < max_edges; ++i)
150 x_edges[i] = y_edges[i] = G_MAXINT;
151 qsort(x_edges, n_edges, sizeof(int), compare_ints);
152 uniquify(x_edges, n_edges);
153 qsort(y_edges, n_edges, sizeof(int), compare_ints);
154 uniquify(y_edges, n_edges);
157 static int total_overlap(const Rect* client_rects,
159 const Rect* proposed_rect)
163 for (i = 0; i < n_client_rects; ++i) {
164 if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
167 RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
168 overlap += RECT_AREA(rtemp);
173 /* Unfortunately, the libc bsearch() function cannot be used to find the
174 position of a value that is not in the array, and glib doesn't
175 provide a binary search function at all. So, tricky as it is, if we
176 want to avoid linear scan of the edge array, we have to roll our
178 static int grid_position(int value,
183 int high = max_edges - 1;
184 int mid = low + (high - low) / 2;
186 if (value < edges[mid])
188 else if (value > edges[mid])
190 else /* value == edges[mid] */
192 mid = low + (high - low) / 2;
194 /* we get here when low == mid. can have low == high or low == high - 1 */
195 return (value <= edges[low] ? low : high);
198 static void expand_width(Rect* r, int by)
203 static void expand_height(Rect* r, int by)
208 typedef void ((*ExpandByMethod)(Rect*, int));
210 /* This structure packs most of the parametars for expand_field() in
211 order to save pushing the same parameters twice. */
212 typedef struct _ExpandInfo {
213 const Point* top_left;
217 const Rect* client_rects;
222 static int expand_field(int orig_edge_index,
224 ExpandByMethod expand_by,
233 int edge_index = orig_edge_index;
234 while (edge_index < i->max_edges - 1) {
235 int next_edge_index = edge_index + 1;
236 (*expand_by)(&field, edges[next_edge_index] - edges[edge_index]);
237 int overlap = total_overlap(i->client_rects, i->n_client_rects, &field);
238 if (overlap != 0 || !RECT_CONTAINS_RECT(*(i->monitor), field))
240 edge_index = next_edge_index;
245 /* The algortihm used for centering a rectangle in a grid field: First
246 find the smallest rectangle of grid lines that enclose the given
247 rectangle. By definition, there is no overlap with any of the other
248 windows if the given rectangle is centered within this minimal
249 rectangle. Then, try extending the minimal rectangle in either
250 direction (x and y) by picking successively further grid lines for
251 the opposite edge. If the minimal rectangle can be extended in *one*
252 direction (x or y) but *not* the other, extend it as far as possible.
253 Otherwise, just use the minimal one. */
255 static void center_in_field(Point* top_left,
256 const Size* req_size,
258 const Rect* client_rects,
264 /* Find minimal rectangle. */
265 int orig_right_edge_index =
266 grid_position(top_left->x + req_size->width, x_edges, max_edges);
267 int orig_bottom_edge_index =
268 grid_position(top_left->y + req_size->height, y_edges, max_edges);
270 .top_left = top_left,
271 .orig_width = x_edges[orig_right_edge_index] - top_left->x,
272 .orig_height = y_edges[orig_bottom_edge_index] - top_left->y,
274 .client_rects = client_rects,
275 .n_client_rects = n_client_rects,
276 .max_edges = max_edges};
277 /* Try extending width. */
278 int right_edge_index =
279 expand_field(orig_right_edge_index, x_edges, expand_width, &i);
280 /* Try extending height. */
281 int bottom_edge_index =
282 expand_field(orig_bottom_edge_index, y_edges, expand_height, &i);
284 int final_width = x_edges[orig_right_edge_index] - top_left->x;
285 int final_height = y_edges[orig_bottom_edge_index] - top_left->y;
286 if (right_edge_index == orig_right_edge_index &&
287 bottom_edge_index != orig_bottom_edge_index)
288 final_height = y_edges[bottom_edge_index] - top_left->y;
289 else if (right_edge_index != orig_right_edge_index &&
290 bottom_edge_index == orig_bottom_edge_index)
291 final_width = x_edges[right_edge_index] - top_left->x;
293 /* Now center the given rectangle within the field */
294 top_left->x += (final_width - req_size->width) / 2;
295 top_left->y += (final_height - req_size->height) / 2;
298 /* Given a list of Rect RECTS, a Point PT and a Size size, determine the
299 direction from PT which results in the least total overlap with RECTS
300 if a rectangle is placed in that direction. Return the top/left
301 Point of such rectangle and the resulting overlap amount. Only
302 consider placements within BOUNDS. */
304 #define NUM_DIRECTIONS 4
306 static int best_direction(const Point* grid_point,
307 const Rect* client_rects,
310 const Size* req_size,
311 Point* best_top_left)
313 static const Size directions[NUM_DIRECTIONS] = {
314 {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
316 int overlap = G_MAXINT;
318 for (i = 0; i < NUM_DIRECTIONS; ++i) {
320 .x = grid_point->x + (req_size->width * directions[i].width),
321 .y = grid_point->y + (req_size->height * directions[i].height)
324 RECT_SET(r, pt.x, pt.y, req_size->width, req_size->height);
325 if (!RECT_CONTAINS_RECT(*monitor, r))
327 int this_overlap = total_overlap(client_rects, n_client_rects, &r);
328 if (this_overlap < overlap) {
329 overlap = this_overlap;