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        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, int n_client_rects,
  26                       const Rect* bound, int* x_edges, int* y_edges,
  27                       int max_edges);
  28
  29 static int best_direction(const Point* grid_point,
  30                           const Rect* client_rects, int n_client_rects,
  31                           const Rect* bound, const Size* req_size,
  32                           Point* best_top_left);
  33
  34 /* Choose the placement on a grid with least overlap */
  35
  36 void place_overlap_find_least_placement(const Rect* client_rects,
  37                                         int n_client_rects,
  38                                         Rect *const bound,
  39                                         const Size* req_size,
  40                                         Point* result)
  41 {
  42     result->x = result->y = 0;
  43     int overlap = G_MAXINT;
  44     int max_edges = 2 * (n_client_rects + 1);
  45
  46         int x_edges[max_edges];
  47         int y_edges[max_edges];
  48         make_grid(client_rects, n_client_rects, bound,
  49                           x_edges, y_edges, max_edges);
  50         int i;
  51         for (i = 0; i < max_edges; ++i) {
  52                 if (x_edges[i] == G_MAXINT)
  53                         break;
  54                 int j;
  55                 for (j = 0; j < max_edges; ++j) {
  56                         if (y_edges[j] == G_MAXINT)
  57                                 break;
  58                         Point grid_point = {.x = x_edges[i], .y = y_edges[j]};
  59                         Point best_top_left;
  60                         int this_overlap =
  61                                 best_direction(&grid_point, client_rects, n_client_rects,
  62                                                            bound, req_size, &best_top_left);
  63                         if (this_overlap < overlap) {
  64                                 overlap = this_overlap;
  65                                 *result = best_top_left;
  66                         }
  67                         if (overlap == 0)
  68                                 break;
  69                 }
  70                 if (overlap == 0)
  71                         break;
  72         }
  73 }
  74
  75 static int compare_ints(const void* a, const void* b)
  76 {
  77     const int* ia = (const int*)a;
  78     const int* ib = (const int*)b;
  79     return *ia - *ib;
  80 }
  81
  82 static void uniquify(int* edges, int n_edges)
  83 {
  84     int i = 0;
  85     int j = 0;
  86
  87     while (j < n_edges) {
  88         int last = edges[j++];
  89         edges[i++] = last;
  90         while (j < n_edges && edges[j] == last)
  91             ++j;
  92     }
  93     /* fill the rest with nonsense */
  94     for (; i < n_edges ; ++i)
  95         edges[i] = G_MAXINT;
  96 }
  97
  98 static void make_grid(const Rect* client_rects, int n_client_rects,
  99                       const Rect* bound, int* x_edges, int* y_edges,
 100                       int max_edges)
 101 {
 102     int i;
 103     int n_edges = 0;
 104     for (i = 0; i < n_client_rects; ++i) {
 105         if (!RECT_INTERSECTS_RECT(client_rects[i], *bound))
 106             continue;
 107         x_edges[n_edges] = client_rects[i].x;
 108         y_edges[n_edges++] = client_rects[i].y;
 109         x_edges[n_edges] = client_rects[i].x + client_rects[i].width;
 110         y_edges[n_edges++] = client_rects[i].y + client_rects[i].height;
 111     }
 112     x_edges[n_edges] = bound->x;
 113     y_edges[n_edges++] = bound->y;
 114     x_edges[n_edges] = bound->x + bound->width;
 115     y_edges[n_edges++] = bound->y + bound->height;
 116     for (i = n_edges; i < max_edges; ++i)
 117         x_edges[i] = y_edges[i] = G_MAXINT;
 118     qsort(x_edges, n_edges, sizeof(int), compare_ints);
 119     uniquify(x_edges, n_edges);
 120     qsort(y_edges, n_edges, sizeof(int), compare_ints);
 121     uniquify(y_edges, n_edges);
 122 }
 123
 124 static int total_overlap(const Rect* client_rects, int n_client_rects,
 125                          const Rect* proposed_rect)
 126 {
 127     int overlap = 0;
 128     int i;
 129     for (i = 0; i < n_client_rects; ++i) {
 130         if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i]))
 131             continue;
 132         Rect rtemp;
 133         RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]);
 134         overlap += RECT_AREA(rtemp);
 135     }
 136     return overlap;
 137 }
 138
 139 /* Given a list of Rect RECTS, a Point PT and a Size size, determine the
 140    direction from PT which results in the least total overlap with RECTS
 141    if a rectangle is placed in that direction.  Return the top/left
 142    Point of such rectangle and the resulting overlap amount.  Only
 143    consider placements within BOUNDS. */
 144
 145 #define NUM_DIRECTIONS 4
 146
 147 static int best_direction(const Point* grid_point,
 148                           const Rect* client_rects, int n_client_rects,
 149                           const Rect* bound, const Size* req_size,
 150                           Point* best_top_left)
 151 {
 152     static const Size directions[NUM_DIRECTIONS] = {
 153         {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
 154     };
 155     int overlap = G_MAXINT;
 156     int i;
 157     for (i = 0; i < NUM_DIRECTIONS; ++i) {
 158         Point pt = {
 159             .x = grid_point->x + (req_size->width * directions[i].width),
 160             .y = grid_point->y + (req_size->height * directions[i].height)
 161         };
 162         Rect r;
 163         RECT_SET(r, pt.x, pt.y, 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 }