openbox/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        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 "overlap.h"
  22
  23 #include <stdlib.h>
  24
  25 static void
  26 make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound,
  27           int* x_edges, int* y_edges, int max_edges);
  28
  29 static int
  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);
  33
  34 /* Choose the placement on a grid with least overlap */
  35
  36 void
  37 overlap_find_least_placement(const Rect* client_rects, int n_client_rects,
  38                              Rect *const bound,
  39                              const Size* req_size, Point* result)
  40 {
  41     result->x = result->y = 0;
  42     int overlap = G_MAXINT;
  43     int max_edges = 2 * (n_client_rects + 1);
  44
  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);
  49         int i;
  50         for (i = 0; i < max_edges; ++i) {
  51                 if (x_edges[i] == G_MAXINT)
  52                         break;
  53                 int j;
  54                 for (j = 0; j < max_edges; ++j) {
  55                         if (y_edges[j] == G_MAXINT)
  56                                 break;
  57                         Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
  58                         Point best_top_left;
  59                         int this_overlap =
  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;
  65                         }
  66                         if (overlap == 0)
  67                                 break;
  68                 }
  69                 if (overlap == 0)
  70                         break;
  71         }
  72 }
  73
  74 static int compare_ints(const void* a, const void* b)
  75 {
  76     const int* ia = (const int*)a;
  77     const int* ib = (const int*)b;
  78     return *ia - *ib;
  79 }
  80
  81 static void uniquify(int* edges, int n_edges)
  82 {
  83     int i = 0;
  84     int j = 0;
  85
  86     while (j < n_edges) {
  87         int last = edges[j++];
  88         edges[i++] = last;
  89         while (j < n_edges && edges[j] == last)
  90             ++j;
  91     }
  92     /* fill the rest with nonsense */
  93     for (; i < n_edges ; ++i)
  94         edges[i] = G_MAXINT;
  95 }
  96
  97 static void
  98 make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound,
  99           int* x_edges, int* y_edges, int max_edges)
 100 {
 101     int i;
 102     int n_edges = 0;
 103     for (i = 0; i < n_client_rects; ++i) {
 104         if (!RECT_INTERSECTS_RECT(client_rects[i], *bound))
 105             continue;
 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;
 110     }
 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);
 121 }
 122
 123 static int total_overlap(const Rect* client_rects, int n_client_rects,
 124                          const Rect* proposed_rect)
 125 {
 126     int overlap = 0;
 127     int i;
 128     for (i = 0; i < n_client_rects; ++i) {
 129         if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
 130             continue;
 131         Rect rtemp;
 132         RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
 133         overlap += RECT_AREA(rtemp);
 134     }
 135     return overlap;
 136 }
 137
 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. */
 143
 144 #define NUM_DIRECTIONS 4
 145
 146 static int
 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)
 150 {
 151     static const Size directions[NUM_DIRECTIONS] = {
 152         {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
 153     };
 154     int overlap = G_MAXINT;
 155     int i;
 156     for (i = 0; i < NUM_DIRECTIONS; ++i) {
 157         Point pt = {
 158             .x = grid_point->x + (req_size->width * directions[i].width),
 159             .y = grid_point->y + (req_size->height * directions[i].height)
 160         };
 161         Rect r;
 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))
 165             continue;
 166         int this_overlap = total_overlap(client_rects, n_client_rects, &r);
 167         if (this_overlap < overlap) {
 168             overlap = this_overlap;
 169             *best_top_left = pt;
 170         }
 171         if (overlap == 0)
 172             break;
 173     }
 174     return overlap;
 175 }