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 ((*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         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     ExpandInfo 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
 284     int final_width = x_edges[orig_right_edge_index] - top_left->x;
 285     int final_height = y_edges[orig_bottom_edge_index] - top_left->y;
 286     if (right_edge_index == orig_right_edge_index &&
 287         bottom_edge_index != orig_bottom_edge_index)
 288         final_height = y_edges[bottom_edge_index] - top_left->y;
 289     else if (right_edge_index != orig_right_edge_index &&
 290              bottom_edge_index == orig_bottom_edge_index)
 291         final_width = x_edges[right_edge_index] - top_left->x;
 292
 293     /* Now center the given rectangle within the field */
 294     top_left->x += (final_width - req_size->width) / 2;
 295     top_left->y += (final_height - req_size->height) / 2;
 296 }
 297
 298 /* Given a list of Rect RECTS, a Point PT and a Size size, determine the
 299    direction from PT which results in the least total overlap with RECTS
 300    if a rectangle is placed in that direction.  Return the top/left
 301    Point of such rectangle and the resulting overlap amount.  Only
 302    consider placements within BOUNDS. */
 303
 304 #define NUM_DIRECTIONS 4
 305
 306 static int best_direction(const Point* grid_point,
 307                           const Rect* client_rects,
 308                           int n_client_rects,
 309                           const Rect* monitor,
 310                           const Size* req_size,
 311                           Point* best_top_left)
 312 {
 313     static const Size directions[NUM_DIRECTIONS] = {
 314         {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
 315     };
 316     int overlap = G_MAXINT;
 317     int i;
 318     for (i = 0; i < NUM_DIRECTIONS; ++i) {
 319         Point pt = {
 320             .x = grid_point->x + (req_size->width * directions[i].width),
 321             .y = grid_point->y + (req_size->height * directions[i].height)
 322         };
 323         Rect r;
 324         RECT_SET(r, pt.x, pt.y, req_size->width, req_size->height);
 325         if (!RECT_CONTAINS_RECT(*monitor, r))
 326             continue;
 327         int this_overlap = total_overlap(client_rects, n_client_rects, &r);
 328         if (this_overlap < overlap) {
 329             overlap = this_overlap;
 330             *best_top_left = pt;
 331         }
 332         if (overlap == 0)
 333             break;
 334     }
 335     return overlap;
 336 }