LeastOverlap placement option (Fix bug 5385)
[dana/openbox.git] / openbox / 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        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 "overlap.h"
22
23 #include <stdlib.h>
24
25 static void
26 make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound,
27           int* x_edges, int* y_edges, int max_edges);
28
29 static int
30 best_direction(const Point* grid_point,
31                const Rect* client_rects, int n_client_rects,
32                const Rect* bound, const Size* req_size, Point* best_top_left);
33
34 /* Choose the placement on a grid with least overlap */
35
36 void
37 overlap_find_least_placement(const Rect* client_rects, int n_client_rects,
38                              Rect *const bound,
39                              const Size* req_size, Point* result)
40 {
41     result->x = result->y = 0;
42     int overlap = G_MAXINT;
43     int max_edges = 2 * (n_client_rects + 1);
44
45         int x_edges[max_edges];
46         int y_edges[max_edges];
47         make_grid(client_rects, n_client_rects, bound,
48                           x_edges, y_edges, max_edges);
49         int i;
50         for (i = 0; i < max_edges; ++i) {
51                 if (x_edges[i] == G_MAXINT)
52                         break;
53                 int j;
54                 for (j = 0; j < max_edges; ++j) {
55                         if (y_edges[j] == G_MAXINT)
56                                 break;
57                         Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
58                         Point best_top_left;
59                         int this_overlap =
60                                 best_direction(&grid_point, client_rects, n_client_rects,
61                                                            bound, req_size, &best_top_left);
62                         if (this_overlap < overlap) {
63                                 overlap = this_overlap;
64                                 *result = best_top_left;
65                         }
66                         if (overlap == 0)
67                                 break;
68                 }
69                 if (overlap == 0)
70                         break;
71         }
72 }
73
74 static int compare_ints(const void* a, const void* b)
75 {
76     const int* ia = (const int*)a;
77     const int* ib = (const int*)b;
78     return *ia - *ib;
79 }
80
81 static void uniquify(int* edges, int n_edges)
82 {
83     int i = 0;
84     int j = 0;
85
86     while (j < n_edges) {
87         int last = edges[j++];
88         edges[i++] = last;
89         while (j < n_edges && edges[j] == last)
90             ++j;
91     }
92     /* fill the rest with nonsense */
93     for (; i < n_edges ; ++i)
94         edges[i] = G_MAXINT;
95 }
96
97 static void
98 make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound,
99           int* x_edges, int* y_edges, int max_edges)
100 {
101     int i;
102     int n_edges = 0;
103     for (i = 0; i < n_client_rects; ++i) {
104         if (!RECT_INTERSECTS_RECT(client_rects[i], *bound))
105             continue;
106         x_edges[n_edges] = client_rects[i].x;
107         y_edges[n_edges++] = client_rects[i].y;
108         x_edges[n_edges] = client_rects[i].x + client_rects[i].width;
109         y_edges[n_edges++] = client_rects[i].y + client_rects[i].height;
110     }
111     x_edges[n_edges] = bound->x;
112     y_edges[n_edges++] = bound->y;
113     x_edges[n_edges] = bound->x + bound->width;
114     y_edges[n_edges++] = bound->y + bound->height;
115     for (i = n_edges; i < max_edges; ++i)
116         x_edges[i] = y_edges[i] = G_MAXINT;
117     qsort(x_edges, n_edges, sizeof(int), compare_ints);
118     uniquify(x_edges, n_edges);
119     qsort(y_edges, n_edges, sizeof(int), compare_ints);
120     uniquify(y_edges, n_edges);
121 }
122
123 static int total_overlap(const Rect* client_rects, int n_client_rects,
124                          const Rect* proposed_rect)
125 {
126     int overlap = 0;
127     int i;
128     for (i = 0; i < n_client_rects; ++i) {
129         if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
130             continue;
131         Rect rtemp;
132         RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
133         overlap += RECT_AREA(rtemp);
134     }
135     return overlap;
136 }
137
138 /* Given a list of Rect RECTS, a Point PT and a Size size, determine the
139  * direction from PT which results in the least total overlap with RECTS
140  * if a rectangle is placed in that direction.  Return the top/left
141  * Point of such rectangle and the resulting overlap amount.  Only
142  * consider placements within BOUNDS. */
143
144 #define NUM_DIRECTIONS 4
145
146 static int
147 best_direction(const Point* grid_point,
148                const Rect* client_rects, int n_client_rects,
149                const Rect* bound, const Size* req_size, Point* best_top_left)
150 {
151     static const Size directions[NUM_DIRECTIONS] = {
152         {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
153     };
154     int overlap = G_MAXINT;
155     int i;
156     for (i = 0; i < NUM_DIRECTIONS; ++i) {
157         Point pt = {
158             .x = grid_point->x + (req_size->width * directions[i].width),
159             .y = grid_point->y + (req_size->height * directions[i].height)
160         };
161         Rect r;
162         RECT_SET_POINT(r, pt.x, pt.y);
163         RECT_SET_SIZE(r, req_size->width, req_size->height);
164         if (!RECT_CONTAINS_RECT(*bound, r))
165             continue;
166         int this_overlap = total_overlap(client_rects, n_client_rects, &r);
167         if (this_overlap < overlap) {
168             overlap = this_overlap;
169             *best_top_left = pt;
170         }
171         if (overlap == 0)
172             break;
173     }
174     return overlap;
175 }