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