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         overlap += RECT_AREA(rtemp);
 171     }
 172     return overlap;
 173 }
 174
 175 static int find_first_grid_position_greater_or_equal(int search_value,
 176                                                      const int* edges,
 177                                                      int max_edges)
 178 {
 179     g_assert(max_edges >= 2);
 180     g_assert(search_value >= edges[0]);
 181     g_assert(search_value <= edges[max_edges - 1]);
 182
 183     BSEARCH_SETUP();
 184     BSEARCH(int, edges, 0, max_edges, search_value);
 185
 186     if (BSEARCH_FOUND())
 187         return BSEARCH_AT();
 188
 189     g_assert(BSEARCH_FOUND_NEAREST_SMALLER());
 190     /* Get the nearest larger instead. */
 191     return BSEARCH_AT() + 1;
 192 }
 193
 194 static void expand_width(Rect* r, int by)
 195 {
 196     r->width += by;
 197 }
 198
 199 static void expand_height(Rect* r, int by)
 200 {
 201     r->height += by;
 202 }
 203
 204 typedef void ((*ExpandByMethod)(Rect*, int));
 205
 206 /* This structure packs most of the parametars for expand_field() in
 207    order to save pushing the same parameters twice. */
 208 typedef struct _ExpandInfo {
 209     const Point* top_left;
 210     int orig_width;
 211     int orig_height;
 212     const Rect* monitor;
 213     const Rect* client_rects;
 214     int n_client_rects;
 215     int max_edges;
 216 } ExpandInfo;
 217
 218 static int expand_field(int orig_edge_index,
 219                         const int* edges,
 220                         ExpandByMethod expand_by,
 221                         const ExpandInfo* i)
 222 {
 223     Rect field;
 224     RECT_SET(field,
 225              i->top_left->x,
 226              i->top_left->y,
 227              i->orig_width,
 228              i->orig_height);
 229     int edge_index = orig_edge_index;
 230     while (edge_index < i->max_edges - 1) {
 231         int next_edge_index = edge_index + 1;
 232         (*expand_by)(&field, edges[next_edge_index] - edges[edge_index]);
 233         int overlap = total_overlap(i->client_rects, i->n_client_rects, &field);
 234         if (overlap != 0 || !RECT_CONTAINS_RECT(*(i->monitor), field))
 235             break;
 236         edge_index = next_edge_index;
 237     }
 238     return edge_index;
 239 }
 240
 241 /* The algortihm used for centering a rectangle in a grid field: First
 242    find the smallest rectangle of grid lines that enclose the given
 243    rectangle.  By definition, there is no overlap with any of the other
 244    windows if the given rectangle is centered within this minimal
 245    rectangle.  Then, try extending the minimal rectangle in either
 246    direction (x and y) by picking successively further grid lines for
 247    the opposite edge.  If the minimal rectangle can be extended in *one*
 248    direction (x or y) but *not* the other, extend it as far as possible.
 249    Otherwise, just use the minimal one.  */
 250
 251 static void center_in_field(Point* top_left,
 252                             const Size* req_size,
 253                             const Rect *monitor,
 254                             const Rect* client_rects,
 255                             int n_client_rects,
 256                             const int* x_edges,
 257                             const int* y_edges,
 258                             int max_edges)
 259 {
 260     /* Find minimal rectangle. */
 261     int orig_right_edge_index =
 262         find_first_grid_position_greater_or_equal(
 263             top_left->x + req_size->width, x_edges, max_edges);
 264     int orig_bottom_edge_index =
 265         find_first_grid_position_greater_or_equal(
 266             top_left->y + req_size->height, y_edges, max_edges);
 267     ExpandInfo i = {
 268         .top_left = top_left,
 269         .orig_width = x_edges[orig_right_edge_index] - top_left->x,
 270         .orig_height = y_edges[orig_bottom_edge_index] - top_left->y,
 271         .monitor = monitor,
 272         .client_rects = client_rects,
 273         .n_client_rects = n_client_rects,
 274         .max_edges = max_edges};
 275     /* Try extending width. */
 276     int right_edge_index =
 277         expand_field(orig_right_edge_index, x_edges, expand_width, &i);
 278     /* Try extending height. */
 279     int bottom_edge_index =
 280         expand_field(orig_bottom_edge_index, y_edges, expand_height, &i);
 281
 282     int final_width = x_edges[orig_right_edge_index] - top_left->x;
 283     int final_height = y_edges[orig_bottom_edge_index] - top_left->y;
 284     if (right_edge_index == orig_right_edge_index &&
 285         bottom_edge_index != orig_bottom_edge_index)
 286         final_height = y_edges[bottom_edge_index] - top_left->y;
 287     else if (right_edge_index != orig_right_edge_index &&
 288              bottom_edge_index == orig_bottom_edge_index)
 289         final_width = x_edges[right_edge_index] - top_left->x;
 290
 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 }