src/placement.c

   1 /* placement.c - window and icon placement on screen
   2  *
   3  *  Window Maker window manager
   4  *
   5  *  Copyright (c) 1997-2003 Alfredo K. Kojima
   6  *
   7  *  This program is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  This program is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License along
  18  *  with this program; if not, write to the Free Software Foundation, Inc.,
  19  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20  */
  21
  22 #include "wconfig.h"
  23
  24 #include <X11/Xlib.h>
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27 #include <string.h>
  28 #include <limits.h>
  29
  30 #include "WindowMaker.h"
  31 #include "wcore.h"
  32 #include "framewin.h"
  33 #include "window.h"
  34 #include "icon.h"
  35 #include "appicon.h"
  36 #include "actions.h"
  37 #include "application.h"
  38 #include "dock.h"
  39 #include "xinerama.h"
  40 #include "placement.h"
  41
  42
  43 #define X_ORIGIN WMAX(usableArea.x1,\
  44     wPreferences.window_place_origin.x)
  45
  46 #define Y_ORIGIN WMAX(usableArea.y1,\
  47     wPreferences.window_place_origin.y)
  48
  49 /* Returns True if it is an icon and is in this workspace */
  50 static Bool
  51 iconPosition(WCoreWindow *wcore, int sx1, int sy1, int sx2, int sy2,
  52              int workspace, int *retX, int *retY)
  53 {
  54         void *parent;
  55         int ok = 0;
  56
  57         parent = wcore->descriptor.parent;
  58
  59         /* if it is an application icon */
  60         if (wcore->descriptor.parent_type == WCLASS_APPICON && !((WAppIcon *) parent)->docked) {
  61                 *retX = ((WAppIcon *) parent)->x_pos;
  62                 *retY = ((WAppIcon *) parent)->y_pos;
  63
  64                 ok = 1;
  65         } else if (wcore->descriptor.parent_type == WCLASS_MINIWINDOW &&
  66                    (((WIcon *) parent)->owner->frame->workspace == workspace
  67                     || IS_OMNIPRESENT(((WIcon *) parent)->owner)
  68                     || wPreferences.sticky_icons)
  69                    && ((WIcon *) parent)->mapped) {
  70
  71                 *retX = ((WIcon *) parent)->owner->icon_x;
  72                 *retY = ((WIcon *) parent)->owner->icon_y;
  73
  74                 ok = 1;
  75         } else if (wcore->descriptor.parent_type == WCLASS_WINDOW
  76                    && ((WWindow *) parent)->flags.icon_moved
  77                    && (((WWindow *) parent)->frame->workspace == workspace || IS_OMNIPRESENT((WWindow *) parent)
  78                        || wPreferences.sticky_icons)) {
  79                 *retX = ((WWindow *) parent)->icon_x;
  80                 *retY = ((WWindow *) parent)->icon_y;
  81
  82                 ok = 1;
  83         }
  84
  85         /* Check if it is inside the screen */
  86         if (ok) {
  87                 if (*retX < sx1 - wPreferences.icon_size)
  88                         ok = 0;
  89                 else if (*retX > sx2)
  90                         ok = 0;
  91
  92                 if (*retY < sy1 - wPreferences.icon_size)
  93                         ok = 0;
  94                 else if (*retY > sy2)
  95                         ok = 0;
  96         }
  97
  98         return ok;
  99 }
 100
 101 void PlaceIcon(WScreen *scr, int *x_ret, int *y_ret, int head)
 102 {
 103         int pf;                 /* primary axis */
 104         int sf;                 /* secondary axis */
 105         int fullW;
 106         int fullH;
 107         char *map;
 108         int pi, si;
 109         WCoreWindow *obj;
 110         int sx1, sx2, sy1, sy2; /* screen boundary */
 111         int sw, sh;
 112         int xo, yo;
 113         int xs, ys;
 114         int x, y;
 115         int isize = wPreferences.icon_size;
 116         int done = 0;
 117         WMBagIterator iter;
 118         WArea area = wGetUsableAreaForHead(scr, head, NULL, False);
 119
 120         /* Find out screen boundaries. */
 121
 122         /* Allows each head to have miniwindows */
 123         sx1 = area.x1;
 124         sy1 = area.y1;
 125         sx2 = area.x2;
 126         sy2 = area.y2;
 127         sw = sx2 - sx1;
 128         sh = sy2 - sy1;
 129
 130         sw = isize * (sw / isize);
 131         sh = isize * (sh / isize);
 132         fullW = (sx2 - sx1) / isize;
 133         fullH = (sy2 - sy1) / isize;
 134
 135         /* icon yard boundaries */
 136         if (wPreferences.icon_yard & IY_VERT) {
 137                 pf = fullH;
 138                 sf = fullW;
 139         } else {
 140                 pf = fullW;
 141                 sf = fullH;
 142         }
 143         if (wPreferences.icon_yard & IY_RIGHT) {
 144                 xo = sx2 - isize;
 145                 xs = -1;
 146         } else {
 147                 xo = sx1;
 148                 xs = 1;
 149         }
 150         if (wPreferences.icon_yard & IY_TOP) {
 151                 yo = sy1;
 152                 ys = 1;
 153         } else {
 154                 yo = sy2 - isize;
 155                 ys = -1;
 156         }
 157
 158         /*
 159          * Create a map with the occupied slots. 1 means the slot is used
 160          * or at least partially used.
 161          * The slot usage can be optimized by only marking fully used slots
 162          * or slots that have most of it covered.
 163          * Space usage is worse than the fvwm algorithm (used in the old version)
 164          * but complexity is much better (faster) than it.
 165          */
 166         map = wmalloc((sw + 2) * (sh + 2));
 167
 168 #define INDEX(x,y)      (((y)+1)*(sw+2) + (x) + 1)
 169
 170         WM_ETARETI_BAG(scr->stacking_list, obj, iter) {
 171
 172                 while (obj) {
 173                         int x, y;
 174
 175                         if (iconPosition(obj, sx1, sy1, sx2, sy2, w_global.workspace.current, &x, &y)) {
 176                                 int xdi, ydi;   /* rounded down */
 177                                 int xui, yui;   /* rounded up */
 178
 179                                 xdi = x / isize;
 180                                 ydi = y / isize;
 181                                 xui = (x + isize / 2) / isize;
 182                                 yui = (y + isize / 2) / isize;
 183                                 map[INDEX(xdi, ydi)] = 1;
 184                                 map[INDEX(xdi, yui)] = 1;
 185                                 map[INDEX(xui, ydi)] = 1;
 186                                 map[INDEX(xui, yui)] = 1;
 187                         }
 188                         obj = obj->stacking->under;
 189                 }
 190         }
 191         /* Default position */
 192         *x_ret = 0;
 193         *y_ret = 0;
 194
 195         /* Look for an empty slot */
 196         for (si = 0; si < sf; si++) {
 197                 for (pi = 0; pi < pf; pi++) {
 198                         if (wPreferences.icon_yard & IY_VERT) {
 199                                 x = xo + xs * (si * isize);
 200                                 y = yo + ys * (pi * isize);
 201                         } else {
 202                                 x = xo + xs * (pi * isize);
 203                                 y = yo + ys * (si * isize);
 204                         }
 205                         if (!map[INDEX(x / isize, y / isize)]) {
 206                                 *x_ret = x;
 207                                 *y_ret = y;
 208                                 done = 1;
 209                                 break;
 210                         }
 211                 }
 212                 if (done)
 213                         break;
 214         }
 215
 216         wfree(map);
 217 }
 218
 219 /* Computes the intersecting length of two line sections */
 220 int calcIntersectionLength(int p1, int l1, int p2, int l2)
 221 {
 222         int isect;
 223         int tmp;
 224
 225         if (p1 > p2) {
 226                 tmp = p1;
 227                 p1 = p2;
 228                 p2 = tmp;
 229                 tmp = l1;
 230                 l1 = l2;
 231                 l2 = tmp;
 232         }
 233
 234         if (p1 + l1 < p2)
 235                 isect = 0;
 236         else if (p2 + l2 < p1 + l1)
 237                 isect = l2;
 238         else
 239                 isect = p1 + l1 - p2;
 240
 241         return isect;
 242 }
 243
 244 /* Computes the intersecting area of two rectangles */
 245 int calcIntersectionArea(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2)
 246 {
 247         return calcIntersectionLength(x1, w1, x2, w2)
 248             * calcIntersectionLength(y1, h1, y2, h2);
 249 }
 250
 251 static int calcSumOfCoveredAreas(WWindow *wwin, int x, int y, int w, int h)
 252 {
 253         int sum_isect = 0;
 254         WWindow *test_window;
 255         int tw, tx, ty, th;
 256
 257         test_window = wwin->screen_ptr->focused_window;
 258         for (; test_window != NULL && test_window->prev != NULL;)
 259                 test_window = test_window->prev;
 260
 261         for (; test_window != NULL; test_window = test_window->next) {
 262                 if (test_window->frame->core->stacking->window_level < WMNormalLevel) {
 263                         continue;
 264                 }
 265
 266                 tw = test_window->frame->core->width;
 267                 th = test_window->frame->core->height;
 268                 tx = test_window->frame_x;
 269                 ty = test_window->frame_y;
 270
 271                 if (test_window->flags.mapped || (test_window->flags.shaded &&
 272                      test_window->frame->workspace == w_global.workspace.current &&
 273                      !(test_window->flags.miniaturized || test_window->flags.hidden))) {
 274                         sum_isect += calcIntersectionArea(tx, ty, tw, th, x, y, w, h);
 275                 }
 276         }
 277
 278         return sum_isect;
 279 }
 280
 281 static void set_width_height(WWindow *wwin, unsigned int *width, unsigned int *height)
 282 {
 283         if (wwin->frame) {
 284                 *height += wwin->frame->top_width + wwin->frame->bottom_width;
 285         } else {
 286                 if (HAS_TITLEBAR(wwin))
 287                         *height += TITLEBAR_HEIGHT;
 288                 if (HAS_RESIZEBAR(wwin))
 289                         *height += RESIZEBAR_HEIGHT;
 290         }
 291         if (HAS_BORDER(wwin)) {
 292                 *height += 2 * wwin->screen_ptr->frame_border_width;
 293                 *width  += 2 * wwin->screen_ptr->frame_border_width;
 294         }
 295 }
 296
 297 static Bool
 298 window_overlaps(WWindow *win, int x, int y, int w, int h, Bool ignore_sunken)
 299 {
 300         int tw, th, tx, ty;
 301
 302         if (ignore_sunken &&
 303             win->frame->core->stacking->window_level < WMNormalLevel) {
 304                 return False;
 305         }
 306
 307         tw = win->frame->core->width;
 308         th = win->frame->core->height;
 309         tx = win->frame_x;
 310         ty = win->frame_y;
 311
 312         if ((tx < (x + w)) && ((tx + tw) > x) &&
 313             (ty < (y + h)) && ((ty + th) > y) &&
 314             (win->flags.mapped ||
 315              (win->flags.shaded &&
 316               win->frame->workspace == w_global.workspace.current &&
 317               !(win->flags.miniaturized || win->flags.hidden)))) {
 318                 return True;
 319         }
 320
 321         return False;
 322 }
 323
 324 static Bool
 325 screen_has_space(WScreen *scr, int x, int y, int w, int h, Bool ignore_sunken)
 326 {
 327         WWindow *focused = scr->focused_window, *i;
 328
 329         for (i = focused; i; i = i->next) {
 330                 if (window_overlaps(i, x, y, w, h, ignore_sunken)) {
 331                         return False;
 332                 }
 333         }
 334
 335         for (i = focused; i; i = i->prev) {
 336                 if (window_overlaps(i, x, y, w, h, ignore_sunken)) {
 337                         return False;
 338                 }
 339         }
 340
 341         return True;
 342 }
 343
 344 static void
 345 smartPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned int width,
 346                  unsigned int height, WArea usableArea)
 347 {
 348         int test_x = 0, test_y = Y_ORIGIN;
 349         int from_x, to_x, from_y, to_y;
 350         int sx;
 351         int min_isect, min_isect_x, min_isect_y;
 352         int sum_isect;
 353
 354         set_width_height(wwin, &width, &height);
 355
 356         sx = X_ORIGIN;
 357         min_isect = INT_MAX;
 358         min_isect_x = sx;
 359         min_isect_y = test_y;
 360
 361         while (((test_y + height) < usableArea.y2)) {
 362                 test_x = sx;
 363                 while ((test_x + width) < usableArea.x2) {
 364                         sum_isect = calcSumOfCoveredAreas(wwin, test_x, test_y, width, height);
 365
 366                         if (sum_isect < min_isect) {
 367                                 min_isect = sum_isect;
 368                                 min_isect_x = test_x;
 369                                 min_isect_y = test_y;
 370                         }
 371
 372                         test_x += PLACETEST_HSTEP;
 373                 }
 374                 test_y += PLACETEST_VSTEP;
 375         }
 376
 377         from_x = min_isect_x - PLACETEST_HSTEP + 1;
 378         from_x = WMAX(from_x, X_ORIGIN);
 379         to_x = min_isect_x + PLACETEST_HSTEP;
 380         if (to_x + width > usableArea.x2)
 381                 to_x = usableArea.x2 - width;
 382
 383         from_y = min_isect_y - PLACETEST_VSTEP + 1;
 384         from_y = WMAX(from_y, Y_ORIGIN);
 385         to_y = min_isect_y + PLACETEST_VSTEP;
 386         if (to_y + height > usableArea.y2)
 387                 to_y = usableArea.y2 - height;
 388
 389         for (test_x = from_x; test_x < to_x; test_x++) {
 390                 for (test_y = from_y; test_y < to_y; test_y++) {
 391                         sum_isect = calcSumOfCoveredAreas(wwin, test_x, test_y, width, height);
 392
 393                         if (sum_isect < min_isect) {
 394                                 min_isect = sum_isect;
 395                                 min_isect_x = test_x;
 396                                 min_isect_y = test_y;
 397                         }
 398                 }
 399         }
 400
 401         *x_ret = min_isect_x;
 402         *y_ret = min_isect_y;
 403 }
 404
 405 static Bool
 406 center_place_window(WWindow *wwin, int *x_ret, int *y_ret,
 407                  unsigned int width, unsigned int height, WArea usableArea)
 408 {
 409         int swidth, sheight;
 410
 411         set_width_height(wwin, &width, &height);
 412         swidth = usableArea.x2 - usableArea.x1;
 413         sheight = usableArea.y2 - usableArea.y1;
 414
 415         if (width > swidth || height > sheight)
 416                 return False;
 417
 418         *x_ret = (usableArea.x1 + usableArea.x2 - width) / 2;
 419         *y_ret = (usableArea.y1 + usableArea.y2 - height) / 2;
 420
 421         return True;
 422 }
 423
 424 static Bool
 425 autoPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret,
 426                 unsigned int width, unsigned int height,
 427                 Bool ignore_sunken, WArea usableArea)
 428 {
 429         WScreen *scr = wwin->screen_ptr;
 430         int x, y;
 431         int sw, sh;
 432
 433         set_width_height(wwin, &width, &height);
 434         sw = usableArea.x2 - usableArea.x1;
 435         sh = usableArea.y2 - usableArea.y1;
 436
 437         /* try placing at center first */
 438         if (center_place_window(wwin, &x, &y, width, height, usableArea) &&
 439             screen_has_space(scr, x, y, width, height, False)) {
 440                 *x_ret = x;
 441                 *y_ret = y;
 442                 return True;
 443         }
 444
 445         /* this was based on fvwm2's smart placement */
 446         for (y = Y_ORIGIN; (y + height) < sh; y += PLACETEST_VSTEP) {
 447                 for (x = X_ORIGIN; (x + width) < sw; x += PLACETEST_HSTEP) {
 448                         if (screen_has_space(scr, x, y,
 449                                              width, height, ignore_sunken)) {
 450                                 *x_ret = x;
 451                                 *y_ret = y;
 452                                 return True;
 453                         }
 454                 }
 455         }
 456
 457         return False;
 458 }
 459
 460 static void
 461 cascadeWindow(WScreen *scr, WWindow *wwin, int *x_ret, int *y_ret,
 462               unsigned int width, unsigned int height, int h, WArea usableArea)
 463 {
 464         set_width_height(wwin, &width, &height);
 465
 466         *x_ret = h * scr->cascade_index + X_ORIGIN;
 467         *y_ret = h * scr->cascade_index + Y_ORIGIN;
 468
 469         if (width + *x_ret > usableArea.x2 || height + *y_ret > usableArea.y2) {
 470                 scr->cascade_index = 0;
 471                 *x_ret = X_ORIGIN;
 472                 *y_ret = Y_ORIGIN;
 473         }
 474 }
 475
 476 static void randomPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret,
 477                   unsigned int width, unsigned int height, WArea usableArea)
 478 {
 479         int w, h;
 480
 481         set_width_height(wwin, &width, &height);
 482
 483         w = ((usableArea.x2 - X_ORIGIN) - width);
 484         h = ((usableArea.y2 - Y_ORIGIN) - height);
 485         if (w < 1)
 486                 w = 1;
 487         if (h < 1)
 488                 h = 1;
 489         *x_ret = X_ORIGIN + rand() % w;
 490         *y_ret = Y_ORIGIN + rand() % h;
 491 }
 492
 493 void PlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned width, unsigned height)
 494 {
 495         WScreen *scr = wwin->screen_ptr;
 496         int h = WMFontHeight(scr->title_font)
 497                 + (wPreferences.window_title_clearance + TITLEBAR_EXTEND_SPACE) * 2;
 498
 499         if (h > wPreferences.window_title_max_height)
 500                 h = wPreferences.window_title_max_height;
 501
 502         if (h < wPreferences.window_title_min_height)
 503                 h = wPreferences.window_title_min_height;
 504
 505         WArea usableArea = wGetUsableAreaForHead(scr, wGetHeadForPointerLocation(scr),
 506                                                  NULL, True);
 507
 508         switch (wPreferences.window_placement) {
 509         case WPM_MANUAL:
 510                 InteractivePlaceWindow(wwin, x_ret, y_ret, width, height);
 511                 break;
 512
 513         case WPM_SMART:
 514                 smartPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
 515                 break;
 516
 517         case WPM_CENTER:
 518                 if (center_place_window(wwin, x_ret, y_ret, width, height, usableArea))
 519                         break;
 520
 521         case WPM_AUTO:
 522                 if (autoPlaceWindow(wwin, x_ret, y_ret, width, height, False, usableArea)) {
 523                         break;
 524                 } else if (autoPlaceWindow(wwin, x_ret, y_ret, width, height, True, usableArea)) {
 525                         break;
 526                 }
 527                 /* there isn't a break here, because if we fail, it should fall
 528                    through to cascade placement, as people who want tiling want
 529                    automagicness aren't going to want to place their window */
 530
 531         case WPM_CASCADE:
 532                 if (wPreferences.window_placement == WPM_AUTO || wPreferences.window_placement == WPM_CENTER)
 533                         scr->cascade_index++;
 534
 535                 cascadeWindow(scr, wwin, x_ret, y_ret, width, height, h, usableArea);
 536
 537                 if (wPreferences.window_placement == WPM_CASCADE)
 538                         scr->cascade_index++;
 539                 break;
 540
 541         case WPM_RANDOM:
 542                 randomPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
 543                 break;
 544         }
 545
 546         /*
 547          * clip to usableArea instead of full screen
 548          * this will also take dock/clip etc.. into account
 549          * aswell as being xinerama friendly
 550          */
 551         if (*x_ret + width > usableArea.x2)
 552                 *x_ret = usableArea.x2 - width;
 553         if (*x_ret < usableArea.x1)
 554                 *x_ret = usableArea.x1;
 555
 556         if (*y_ret + height > usableArea.y2)
 557                 *y_ret = usableArea.y2 - height;
 558         if (*y_ret < usableArea.y1)
 559                 *y_ret = usableArea.y1;
 560 }