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 #include "obt/bsearch.h"
  23
  24 #include <glib.h>
  25 #include <stdlib.h>
  26
  27 static void make_grid(const Rect* client_rects,
  28                       int n_client_rects,
  29                       const Rect* monitor,
  30                       int* x_edges,
  31                       int* y_edges,
  32                       int max_edges);
  33
  34 static int best_direction(const Point* grid_point,
  35                           const Rect* client_rects,
  36                           int n_client_rects,
  37                           const Rect* monitor,
  38                           const Size* req_size,
  39                           Point* best_top_left);
  40
  41 static int total_overlap(const Rect* client_rects,
  42                          int n_client_rects,
  43                          const Rect* proposed_rect);
  44
  45 static void center_in_field(Point* grid_point,
  46                             const Size* req_size,
  47                             const Rect *monitor,
  48                             const Rect* client_rects,
  49                             int n_client_rects,
  50                             const int* x_edges,
  51                             const int* y_edges,
  52                             int max_edges);
  53
  54 /* Choose the placement on a grid with least overlap */
  55
  56 void place_overlap_find_least_placement(const Rect* client_rects,
  57                                         int n_client_rects,
  58                                         const Rect *monitor,
  59                                         const Size* req_size,
  60                                         Point* result)
  61 {
  62     POINT_SET(*result, monitor->x, monitor->y);
  63     int overlap = G_MAXINT;
  64     int max_edges = 2 * (n_client_rects + 1);
  65
  66     int x_edges[max_edges];
  67     int y_edges[max_edges];
  68     make_grid(client_rects, n_client_rects, monitor,
  69             x_edges, y_edges, max_edges);
  70     int i;
  71     for (i = 0; i < max_edges; ++i) {
  72         if (x_edges[i] == G_MAXINT)
  73             break;
  74         int j;
  75         for (j = 0; j < max_edges; ++j) {
  76             if (y_edges[j] == G_MAXINT)
  77                 break;
  78             Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
  79             Point best_top_left;
  80             int this_overlap =
  81                 best_direction(&grid_point, client_rects, n_client_rects,
  82                         monitor, req_size, &best_top_left);
  83             if (this_overlap < overlap) {
  84                 overlap = this_overlap;
  85                 *result = best_top_left;
  86             }
  87             if (overlap == 0)
  88                 break;
  89         }
  90         if (overlap == 0)
  91             break;
  92     }
  93     if (config_place_center && overlap == 0) {
  94         center_in_field(result,
  95                         req_size,
  96                         monitor,
  97                         client_rects,
  98                         n_client_rects,
  99                         x_edges,
 100                         y_edges,
 101                         max_edges);
 102     }
 103 }
 104
 105 static int compare_ints(const void* a,
 106                         const void* b)
 107 {
 108     const int* ia = (const int*)a;
 109     const int* ib = (const int*)b;
 110     return *ia - *ib;
 111 }
 112
 113 static void uniquify(int* edges,
 114                      int n_edges)
 115 {
 116     int i = 0;
 117     int j = 0;
 118
 119     while (j < n_edges) {
 120         int last = edges[j++];
 121         edges[i++] = last;
 122         while (j < n_edges && edges[j] == last)
 123             ++j;
 124     }
 125     /* fill the rest with nonsense */
 126     for (; i < n_edges; ++i)
 127         edges[i] = G_MAXINT;
 128 }
 129
 130 static void make_grid(const Rect* client_rects,
 131                       int n_client_rects,
 132                       const Rect* monitor,
 133                       int* x_edges,
 134                       int* y_edges,
 135                       int max_edges)
 136 {
 137     int i;
 138     int n_edges = 0;
 139     for (i = 0; i < n_client_rects; ++i) {
 140         if (!RECT_INTERSECTS_RECT(client_rects[i], *monitor))
 141             continue;
 142         x_edges[n_edges] = client_rects[i].x;
 143         y_edges[n_edges++] = client_rects[i].y;
 144         x_edges[n_edges] = client_rects[i].x + client_rects[i].width;
 145         y_edges[n_edges++] = client_rects[i].y + client_rects[i].height;
 146     }
 147     x_edges[n_edges] = monitor->x;
 148     y_edges[n_edges++] = monitor->y;
 149     x_edges[n_edges] = monitor->x + monitor->width;
 150     y_edges[n_edges++] = monitor->y + monitor->height;
 151     for (i = n_edges; i < max_edges; ++i)
 152         x_edges[i] = y_edges[i] = G_MAXINT;
 153     qsort(x_edges, n_edges, sizeof(int), compare_ints);
 154     uniquify(x_edges, n_edges);
 155     qsort(y_edges, n_edges, sizeof(int), compare_ints);
 156     uniquify(y_edges, n_edges);
 157 }
 158
 159 static int total_overlap(const Rect* client_rects,
 160                          int n_client_rects,
 161                          const Rect* proposed_rect)
 162 {
 163     int overlap = 0;
 164     int i;
 165     for (i = 0; i < n_client_rects; ++i) {
 166         if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
 167             continue;
 168         Rect rtemp;
 169         RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
 170         /* somewhat penalize #rects, overlapping an additional client is
 171          * only better if it saves ~75x75 pixels. This is so that we don't
 172          * overlap a bunch of windows just because there's a small gap
 173          * between them. */
 174         overlap += RECT_AREA(rtemp) + 6000;
 175     }
 176     return overlap;
 177 }
 178
 179 static int find_first_grid_position_greater_or_equal(int search_value,
 180                                                      const int* edges,
 181                                                      int max_edges)
 182 {
 183     g_assert(max_edges >= 2);
 184     g_assert(search_value >= edges[0]);
 185     g_assert(search_value <= edges[max_edges - 1]);
 186
 187     BSEARCH_SETUP();
 188     BSEARCH(int, edges, 0, max_edges, search_value);
 189
 190     if (BSEARCH_FOUND())
 191         return BSEARCH_AT();
 192
 193     g_assert(BSEARCH_FOUND_NEAREST_SMALLER());
 194     /* Get the nearest larger instead. */
 195     return BSEARCH_AT() + 1;
 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 ((*ExpandByMethod)(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 _ExpandInfo {
 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 } ExpandInfo;
 221
 222 static int expand_field(int orig_edge_index,
 223                         const int* edges,
 224                         ExpandByMethod expand_by,
 225                         const ExpandInfo* 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         (*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))
 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         find_first_grid_position_greater_or_equal(
 267             top_left->x + req_size->width, x_edges, max_edges);
 268     int orig_bottom_edge_index =
 269         find_first_grid_position_greater_or_equal(
 270             top_left->y + req_size->height, y_edges, max_edges);
 271     ExpandInfo i = {
 272         .top_left = top_left,
 273         .orig_width = x_edges[orig_right_edge_index] - top_left->x,
 274         .orig_height = y_edges[orig_bottom_edge_index] - top_left->y,
 275         .monitor = monitor,
 276         .client_rects = client_rects,
 277         .n_client_rects = n_client_rects,
 278         .max_edges = max_edges};
 279     /* Try extending width. */
 280     int right_edge_index =
 281         expand_field(orig_right_edge_index, x_edges, expand_width, &i);
 282     /* Try extending height. */
 283     int bottom_edge_index =
 284         expand_field(orig_bottom_edge_index, y_edges, expand_height, &i);
 285
 286     int final_width = x_edges[orig_right_edge_index] - top_left->x;
 287     int final_height = y_edges[orig_bottom_edge_index] - top_left->y;
 288     if (right_edge_index == orig_right_edge_index &&
 289         bottom_edge_index != orig_bottom_edge_index)
 290         final_height = y_edges[bottom_edge_index] - top_left->y;
 291     else if (right_edge_index != orig_right_edge_index &&
 292              bottom_edge_index == orig_bottom_edge_index)
 293         final_width = x_edges[right_edge_index] - top_left->x;
 294
 295     /* Now center the given rectangle within the field */
 296     top_left->x += (final_width - req_size->width) / 2;
 297     top_left->y += (final_height - req_size->height) / 2;
 298 }
 299
 300 /* Given a list of Rect RECTS, a Point PT and a Size size, determine the
 301    direction from PT which results in the least total overlap with RECTS
 302    if a rectangle is placed in that direction.  Return the top/left
 303    Point of such rectangle and the resulting overlap amount.  Only
 304    consider placements within BOUNDS. */
 305
 306 #define NUM_DIRECTIONS 4
 307
 308 static int best_direction(const Point* grid_point,
 309                           const Rect* client_rects,
 310                           int n_client_rects,
 311                           const Rect* monitor,
 312                           const Size* req_size,
 313                           Point* best_top_left)
 314 {
 315     static const Size directions[NUM_DIRECTIONS] = {
 316         {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
 317     };
 318     int overlap = G_MAXINT;
 319     int i;
 320     for (i = 0; i < NUM_DIRECTIONS; ++i) {
 321         Point pt = {
 322             .x = grid_point->x + (req_size->width * directions[i].width),
 323             .y = grid_point->y + (req_size->height * directions[i].height)
 324         };
 325         Rect r;
 326         RECT_SET(r, pt.x, pt.y, req_size->width, req_size->height);
 327         if (!RECT_CONTAINS_RECT(*monitor, r))
 328             continue;
 329         int this_overlap = total_overlap(client_rects, n_client_rects, &r);
 330         if (this_overlap < overlap) {
 331             overlap = this_overlap;
 332             *best_top_left = pt;
 333         }
 334         if (overlap == 0)
 335             break;
 336     }
 337     return overlap;
 338 }