1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
3 overlap.c for the Openbox window manager
4 Copyright (c) 2011 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.
26 make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound,
27 int* x_edges, int* y_edges, int max_edges);
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);
34 /* Choose the placement on a grid with least overlap */
37 overlap_find_least_placement(const Rect* client_rects, int n_client_rects,
39 const Size* req_size, Point* result)
41 result->x = result->y = 0;
42 int overlap = G_MAXINT;
43 int max_edges = 2 * (n_client_rects + 1);
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);
50 for (i = 0; i < max_edges; ++i) {
51 if (x_edges[i] == G_MAXINT)
54 for (j = 0; j < max_edges; ++j) {
55 if (y_edges[j] == G_MAXINT)
57 Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
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;
74 static int compare_ints(const void* a, const void* b)
76 const int* ia = (const int*)a;
77 const int* ib = (const int*)b;
81 static void uniquify(int* edges, int n_edges)
87 int last = edges[j++];
89 while (j < n_edges && edges[j] == last)
92 /* fill the rest with nonsense */
93 for (; i < n_edges ; ++i)
98 make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound,
99 int* x_edges, int* y_edges, int max_edges)
103 for (i = 0; i < n_client_rects; ++i) {
104 if (!RECT_INTERSECTS_RECT(client_rects[i], *bound))
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;
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);
123 static int total_overlap(const Rect* client_rects, int n_client_rects,
124 const Rect* proposed_rect)
128 for (i = 0; i < n_client_rects; ++i) {
129 if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
132 RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
133 overlap += RECT_AREA(rtemp);
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. */
144 #define NUM_DIRECTIONS 4
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)
151 static const Size directions[NUM_DIRECTIONS] = {
152 {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
154 int overlap = G_MAXINT;
156 for (i = 0; i < NUM_DIRECTIONS; ++i) {
158 .x = grid_point->x + (req_size->width * directions[i].width),
159 .y = grid_point->y + (req_size->height * directions[i].height)
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))
166 int this_overlap = total_overlap(client_rects, n_client_rects, &r);
167 if (this_overlap < overlap) {
168 overlap = this_overlap;