9eccb97edc5dc4135faf313984011026a41a01cd
[dana/openbox.git] / openbox / place_overlap.c
1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
2
3    overlap.c for the Openbox window manager
4    Copyright (c) 2011, 2013 Ian Zimmerman
5
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.
10
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.
15
16    See the COPYING file for a copy of the GNU General Public License.
17 */
18
19 #include "config.h"
20 #include "geom.h"
21 #include "place_overlap.h"
22
23 #include <stdlib.h>
24
25 static void make_grid(const Rect* client_rects,
26                       int n_client_rects,
27                       const Rect* monitor,
28                       int* x_edges,
29                       int* y_edges,
30                       int max_edges);
31
32 static int best_direction(const Point* grid_point,
33                           const Rect* client_rects,
34                           int n_client_rects,
35                           const Rect* monitor,
36                           const Size* req_size,
37                           Point* best_top_left);
38
39 static int total_overlap(const Rect* client_rects,
40                          int n_client_rects,
41                          const Rect* proposed_rect);
42
43 static void center_in_field(Point* grid_point,
44                             const Size* req_size,
45                             const Rect *monitor,
46                             const Rect* client_rects,
47                             int n_client_rects,
48                             const int* x_edges,
49                             const int* y_edges,
50                             int max_edges);
51
52 /* Choose the placement on a grid with least overlap */
53
54 void place_overlap_find_least_placement(const Rect* client_rects,
55                                         int n_client_rects,
56                                         const Rect *monitor,
57                                         const Size* req_size,
58                                         Point* result)
59 {
60     POINT_SET(*result, monitor->x, monitor->y);
61     int overlap = G_MAXINT;
62     int max_edges = 2 * (n_client_rects + 1);
63
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);
68     int i;
69     for (i = 0; i < max_edges; ++i) {
70         if (x_edges[i] == G_MAXINT)
71             break;
72         int j;
73         for (j = 0; j < max_edges; ++j) {
74             if (y_edges[j] == G_MAXINT)
75                 break;
76             Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
77             Point best_top_left;
78             int this_overlap =
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;
84             }
85             if (overlap == 0)
86                 break;
87         }
88         if (overlap == 0)
89             break;
90     }
91     if (config_place_center && overlap == 0) {
92         center_in_field(result,
93                         req_size,
94                         monitor,
95                         client_rects,
96                         n_client_rects,
97                         x_edges,
98                         y_edges,
99                         max_edges);
100     }
101 }
102
103 static int compare_ints(const void* a,
104                         const void* b)
105 {
106     const int* ia = (const int*)a;
107     const int* ib = (const int*)b;
108     return *ia - *ib;
109 }
110
111 static void uniquify(int* edges,
112                      int n_edges)
113 {
114     int i = 0;
115     int j = 0;
116
117     while (j < n_edges) {
118         int last = edges[j++];
119         edges[i++] = last;
120         while (j < n_edges && edges[j] == last)
121             ++j;
122     }
123     /* fill the rest with nonsense */
124     for (; i < n_edges; ++i)
125         edges[i] = G_MAXINT;
126 }
127
128 static void make_grid(const Rect* client_rects,
129                       int n_client_rects,
130                       const Rect* monitor,
131                       int* x_edges,
132                       int* y_edges,
133                       int max_edges)
134 {
135     int i;
136     int n_edges = 0;
137     for (i = 0; i < n_client_rects; ++i) {
138         if (!RECT_INTERSECTS_RECT(client_rects[i], *monitor))
139             continue;
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;
144     }
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);
155 }
156
157 static int total_overlap(const Rect* client_rects,
158                          int n_client_rects,
159                          const Rect* proposed_rect)
160 {
161     int overlap = 0;
162     int i;
163     for (i = 0; i < n_client_rects; ++i) {
164         if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
165             continue;
166         Rect rtemp;
167         RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
168         overlap += RECT_AREA(rtemp);
169     }
170     return overlap;
171 }
172
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
177    own. */
178 static int grid_position(int value,
179                          const int* edges,
180                          int max_edges)
181 {
182     int low = 0;
183     int high = max_edges - 1;
184     int mid = low + (high - low) / 2;
185     while (low != mid) {
186         if (value < edges[mid])
187             high = mid;
188         else if (value > edges[mid])
189             low = mid;
190         else                    /* value == edges[mid] */
191             return mid;
192         mid = low + (high - low) / 2;
193     }
194     /* we get here when low == mid.  can have low == high or low == high - 1 */
195     return (value <= edges[low] ? low : high);
196 }                         
197
198 static void expand_width(Rect* r, int by)
199 {
200     r->width += by;
201 }
202
203 static void expand_height(Rect* r, int by)
204 {
205     r->height += by;
206 }
207
208 typedef void ((*expand_method)(Rect*, int));
209
210 /* This structure packs most of the parametars for expand_field() in
211    order to save pushing the same parameters twice. */
212 typedef struct _expand_info {
213     const Point* top_left;
214     int orig_width;
215     int orig_height;
216     const Rect* monitor;
217     const Rect* client_rects;
218     int n_client_rects;
219     int max_edges;
220 } expand_info;
221
222 static int expand_field(int orig_edge_index,
223                         const int* edges,
224                         expand_method exp,
225                         const expand_info* i)
226 {
227     Rect field;
228     RECT_SET(field,
229              i->top_left->x,
230              i->top_left->y,
231              i->orig_width,
232              i->orig_height);
233     int edge_index = orig_edge_index;
234     while (edge_index < i->max_edges - 1) {
235         int next_edge_index = edge_index + 1;
236         (*exp)(&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))
239             break;
240         edge_index = next_edge_index;
241     }
242     return edge_index;
243 }
244
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.  */
254
255 static void center_in_field(Point* top_left,
256                             const Size* req_size,
257                             const Rect *monitor,
258                             const Rect* client_rects,
259                             int n_client_rects,
260                             const int* x_edges,
261                             const int* y_edges,
262                             int max_edges)
263 {
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);
269     expand_info i = {
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,
273         .monitor = monitor,
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);
283     int final_width = x_edges[orig_right_edge_index] - top_left->x;
284     int final_height = y_edges[orig_bottom_edge_index] - top_left->y;
285     if (right_edge_index == orig_right_edge_index
286         && bottom_edge_index != orig_bottom_edge_index)
287         final_height = y_edges[bottom_edge_index] - top_left->y;
288     else if (right_edge_index != orig_right_edge_index
289              && bottom_edge_index == orig_bottom_edge_index)
290         final_width = x_edges[right_edge_index] - top_left->x;
291     /* Now center the given rectangle within the field */
292     top_left->x += (final_width - req_size->width) / 2;
293     top_left->y += (final_height - req_size->height) / 2;
294 }
295
296 /* Given a list of Rect RECTS, a Point PT and a Size size, determine the
297    direction from PT which results in the least total overlap with RECTS
298    if a rectangle is placed in that direction.  Return the top/left
299    Point of such rectangle and the resulting overlap amount.  Only
300    consider placements within BOUNDS. */
301
302 #define NUM_DIRECTIONS 4
303
304 static int best_direction(const Point* grid_point,
305                           const Rect* client_rects,
306                           int n_client_rects,
307                           const Rect* monitor,
308                           const Size* req_size,
309                           Point* best_top_left)
310 {
311     static const Size directions[NUM_DIRECTIONS] = {
312         {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
313     };
314     int overlap = G_MAXINT;
315     int i;
316     for (i = 0; i < NUM_DIRECTIONS; ++i) {
317         Point pt = {
318             .x = grid_point->x + (req_size->width * directions[i].width),
319             .y = grid_point->y + (req_size->height * directions[i].height)
320         };
321         Rect r;
322         RECT_SET(r, pt.x, pt.y, req_size->width, req_size->height);
323         if (!RECT_CONTAINS_RECT(*monitor, r))
324             continue;
325         int this_overlap = total_overlap(client_rects, n_client_rects, &r);
326         if (this_overlap < overlap) {
327             overlap = this_overlap;
328             *best_top_left = pt;
329         }
330         if (overlap == 0)
331             break;
332     }
333     return overlap;
334 }