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
  23 #include <stdlib.h>
  24
  25 static void make_grid(const Rect* client_rects,
  26                       int n_client_rects,
  27                       const Rect* monitor,
  28                       int* x_edges,
  29                       int* y_edges,
  30                       int max_edges);
  31
  32 static int best_direction(const Point* grid_point,
  33                           const Rect* client_rects,
  34                           int n_client_rects,
  35                           const Rect* monitor,
  36                           const Size* req_size,
  37                           Point* best_top_left);
  38
  39 static int total_overlap(const Rect* client_rects,
  40                          int n_client_rects,
  41                          const Rect* proposed_rect);
  42
  43 static void center_in_field(Point* grid_point,
  44                             const Size* req_size,
  45                             const Rect *monitor,
  46                             const Rect* client_rects,
  47                             int n_client_rects,
  48                             const int* x_edges,
  49                             const int* y_edges,
  50                             int max_edges);
  51
  52 /* Choose the placement on a grid with least overlap */
  53
  54 void place_overlap_find_least_placement(const Rect* client_rects,
  55                                         int n_client_rects,
  56                                         const Rect *monitor,
  57                                         const Size* req_size,
  58                                         Point* result)
  59 {
  60     POINT_SET(*result, monitor->x, monitor->y);
  61     int overlap = G_MAXINT;
  62     int max_edges = 2 * (n_client_rects + 1);
  63
  64     int x_edges[max_edges];
  65     int y_edges[max_edges];
  66     make_grid(client_rects, n_client_rects, monitor,
  67             x_edges, y_edges, max_edges);
  68     int i;
  69     for (i = 0; i < max_edges; ++i) {
  70         if (x_edges[i] == G_MAXINT)
  71             break;
  72         int j;
  73         for (j = 0; j < max_edges; ++j) {
  74             if (y_edges[j] == G_MAXINT)
  75                 break;
  76             Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
  77             Point best_top_left;
  78             int this_overlap =
  79                 best_direction(&grid_point, client_rects, n_client_rects,
  80                         monitor, req_size, &best_top_left);
  81             if (this_overlap < overlap) {
  82                 overlap = this_overlap;
  83                 *result = best_top_left;
  84             }
  85             if (overlap == 0)
  86                 break;
  87         }
  88         if (overlap == 0)
  89             break;
  90     }
  91     if (config_place_center && overlap == 0) {
  92         center_in_field(result,
  93                         req_size,
  94                         monitor,
  95                         client_rects,
  96                         n_client_rects,
  97                         x_edges,
  98                         y_edges,
  99                         max_edges);
 100     }
 101 }
 102
 103 static int compare_ints(const void* a,
 104                         const void* b)
 105 {
 106     const int* ia = (const int*)a;
 107     const int* ib = (const int*)b;
 108     return *ia - *ib;
 109 }
 110
 111 static void uniquify(int* edges,
 112                      int n_edges)
 113 {
 114     int i = 0;
 115     int j = 0;
 116
 117     while (j < n_edges) {
 118         int last = edges[j++];
 119         edges[i++] = last;
 120         while (j < n_edges && edges[j] == last)
 121             ++j;
 122     }
 123     /* fill the rest with nonsense */
 124     for (; i < n_edges; ++i)
 125         edges[i] = G_MAXINT;
 126 }
 127
 128 static void make_grid(const Rect* client_rects,
 129                       int n_client_rects,
 130                       const Rect* monitor,
 131                       int* x_edges,
 132                       int* y_edges,
 133                       int max_edges)
 134 {
 135     int i;
 136     int n_edges = 0;
 137     for (i = 0; i < n_client_rects; ++i) {
 138         if (!RECT_INTERSECTS_RECT(client_rects[i], *monitor))
 139             continue;
 140         x_edges[n_edges] = client_rects[i].x;
 141         y_edges[n_edges++] = client_rects[i].y;
 142         x_edges[n_edges] = client_rects[i].x + client_rects[i].width;
 143         y_edges[n_edges++] = client_rects[i].y + client_rects[i].height;
 144     }
 145     x_edges[n_edges] = monitor->x;
 146     y_edges[n_edges++] = monitor->y;
 147     x_edges[n_edges] = monitor->x + monitor->width;
 148     y_edges[n_edges++] = monitor->y + monitor->height;
 149     for (i = n_edges; i < max_edges; ++i)
 150         x_edges[i] = y_edges[i] = G_MAXINT;
 151     qsort(x_edges, n_edges, sizeof(int), compare_ints);
 152     uniquify(x_edges, n_edges);
 153     qsort(y_edges, n_edges, sizeof(int), compare_ints);
 154     uniquify(y_edges, n_edges);
 155 }
 156
 157 static int total_overlap(const Rect* client_rects,
 158                          int n_client_rects,
 159                          const Rect* proposed_rect)
 160 {
 161     int overlap = 0;
 162     int i;
 163     for (i = 0; i < n_client_rects; ++i) {
 164         if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
 165             continue;
 166         Rect rtemp;
 167         RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
 168         overlap += RECT_AREA(rtemp);
 169     }
 170     return overlap;
 171 }
 172
 173 /* Unfortunately, the libc bsearch() function cannot be used to find the
 174    position of a value that is not in the array, and glib doesn't
 175    provide a binary search function at all.  So, tricky as it is, if we
 176    want to avoid linear scan of the edge array, we have to roll our
 177    own. */
 178 static int grid_position(int value,
 179                          const int* edges,
 180                          int max_edges)
 181 {
 182     int low = 0;
 183     int high = max_edges - 1;
 184     int mid = low + (high - low) / 2;
 185     while (low != mid) {
 186         if (value < edges[mid])
 187             high = mid;
 188         else if (value > edges[mid])
 189             low = mid;
 190         else                    /* value == edges[mid] */
 191             return mid;
 192         mid = low + (high - low) / 2;
 193     }
 194     /* we get here when low == mid.  can have low == high or low == high - 1 */
 195     return (value <= edges[low] ? low : high);
 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 ((*expand_method)(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 _expand_info {
 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 } expand_info;
 221
 222 static int expand_field(int orig_edge_index,
 223                         const int* edges,
 224                         expand_method exp,
 225                         const expand_info* 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         (*exp)(&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         grid_position(top_left->x + req_size->width, x_edges, max_edges);
 267     int orig_bottom_edge_index =
 268         grid_position(top_left->y + req_size->height, y_edges, max_edges);
 269     expand_info i = {
 270         .top_left = top_left,
 271         .orig_width = x_edges[orig_right_edge_index] - top_left->x,
 272         .orig_height = y_edges[orig_bottom_edge_index] - top_left->y,
 273         .monitor = monitor,
 274         .client_rects = client_rects,
 275         .n_client_rects = n_client_rects,
 276         .max_edges = max_edges};
 277     /* try extending width */
 278     int right_edge_index =
 279         expand_field(orig_right_edge_index, x_edges, expand_width, &i);
 280     /* try extending height */
 281     int bottom_edge_index =
 282         expand_field(orig_bottom_edge_index, y_edges, expand_height, &i);
 283     int final_width = x_edges[orig_right_edge_index] - top_left->x;
 284     int final_height = y_edges[orig_bottom_edge_index] - top_left->y;
 285     if (right_edge_index == orig_right_edge_index
 286         && bottom_edge_index != orig_bottom_edge_index)
 287         final_height = y_edges[bottom_edge_index] - top_left->y;
 288     else if (right_edge_index != orig_right_edge_index
 289              && bottom_edge_index == orig_bottom_edge_index)
 290         final_width = x_edges[right_edge_index] - top_left->x;
 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 }