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         /* Do not place icons under the dock. */
 121         if (scr->dock) {
 122                 int offset = wPreferences.icon_size + DOCK_EXTRA_SPACE;
 123
 124                 if (scr->dock->on_right_side)
 125                         area.x2 -= offset;
 126                 else
 127                     area.x1 += offset;
 128         }
 129
 130         /* Find out screen boundaries. */
 131
 132         /* Allows each head to have miniwindows */
 133         sx1 = area.x1;
 134         sy1 = area.y1;
 135         sx2 = area.x2;
 136         sy2 = area.y2;
 137         sw = sx2 - sx1;
 138         sh = sy2 - sy1;
 139
 140         sw = isize * (sw / isize);
 141         sh = isize * (sh / isize);
 142         fullW = (sx2 - sx1) / isize;
 143         fullH = (sy2 - sy1) / isize;
 144
 145         /* icon yard boundaries */
 146         if (wPreferences.icon_yard & IY_VERT) {
 147                 pf = fullH;
 148                 sf = fullW;
 149         } else {
 150                 pf = fullW;
 151                 sf = fullH;
 152         }
 153         if (wPreferences.icon_yard & IY_RIGHT) {
 154                 xo = sx2 - isize;
 155                 xs = -1;
 156         } else {
 157                 xo = sx1;
 158                 xs = 1;
 159         }
 160         if (wPreferences.icon_yard & IY_TOP) {
 161                 yo = sy1;
 162                 ys = 1;
 163         } else {
 164                 yo = sy2 - isize;
 165                 ys = -1;
 166         }
 167
 168         /*
 169          * Create a map with the occupied slots. 1 means the slot is used
 170          * or at least partially used.
 171          * The slot usage can be optimized by only marking fully used slots
 172          * or slots that have most of it covered.
 173          * Space usage is worse than the fvwm algorithm (used in the old version)
 174          * but complexity is much better (faster) than it.
 175          */
 176         map = wmalloc((sw + 2) * (sh + 2));
 177
 178 #define INDEX(x,y)      (((y)+1)*(sw+2) + (x) + 1)
 179
 180         WM_ETARETI_BAG(scr->stacking_list, obj, iter) {
 181
 182                 while (obj) {
 183                         int x, y;
 184
 185                         if (iconPosition(obj, sx1, sy1, sx2, sy2, scr->current_workspace, &x, &y)) {
 186                                 int xdi, ydi;   /* rounded down */
 187                                 int xui, yui;   /* rounded up */
 188
 189                                 xdi = x / isize;
 190                                 ydi = y / isize;
 191                                 xui = (x + isize / 2) / isize;
 192                                 yui = (y + isize / 2) / isize;
 193                                 map[INDEX(xdi, ydi)] = 1;
 194                                 map[INDEX(xdi, yui)] = 1;
 195                                 map[INDEX(xui, ydi)] = 1;
 196                                 map[INDEX(xui, yui)] = 1;
 197                         }
 198                         obj = obj->stacking->under;
 199                 }
 200         }
 201         /* Default position */
 202         *x_ret = 0;
 203         *y_ret = 0;
 204
 205         /* Look for an empty slot */
 206         for (si = 0; si < sf; si++) {
 207                 for (pi = 0; pi < pf; pi++) {
 208                         if (wPreferences.icon_yard & IY_VERT) {
 209                                 x = xo + xs * (si * isize);
 210                                 y = yo + ys * (pi * isize);
 211                         } else {
 212                                 x = xo + xs * (pi * isize);
 213                                 y = yo + ys * (si * isize);
 214                         }
 215                         if (!map[INDEX(x / isize, y / isize)]) {
 216                                 *x_ret = x;
 217                                 *y_ret = y;
 218                                 done = 1;
 219                                 break;
 220                         }
 221                 }
 222                 if (done)
 223                         break;
 224         }
 225
 226         wfree(map);
 227 }
 228
 229 /* Computes the intersecting length of two line sections */
 230 int calcIntersectionLength(int p1, int l1, int p2, int l2)
 231 {
 232         int isect;
 233         int tmp;
 234
 235         if (p1 > p2) {
 236                 tmp = p1;
 237                 p1 = p2;
 238                 p2 = tmp;
 239                 tmp = l1;
 240                 l1 = l2;
 241                 l2 = tmp;
 242         }
 243
 244         if (p1 + l1 < p2)
 245                 isect = 0;
 246         else if (p2 + l2 < p1 + l1)
 247                 isect = l2;
 248         else
 249                 isect = p1 + l1 - p2;
 250
 251         return isect;
 252 }
 253
 254 /* Computes the intersecting area of two rectangles */
 255 int calcIntersectionArea(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2)
 256 {
 257         return calcIntersectionLength(x1, w1, x2, w2)
 258             * calcIntersectionLength(y1, h1, y2, h2);
 259 }
 260
 261 static int calcSumOfCoveredAreas(WWindow *wwin, int x, int y, int w, int h)
 262 {
 263         int sum_isect = 0;
 264         WWindow *test_window;
 265         int tw, tx, ty, th;
 266
 267         test_window = wwin->screen_ptr->focused_window;
 268         for (; test_window != NULL && test_window->prev != NULL;)
 269                 test_window = test_window->prev;
 270
 271         for (; test_window != NULL; test_window = test_window->next) {
 272                 if (test_window->frame->core->stacking->window_level < WMNormalLevel) {
 273                         continue;
 274                 }
 275
 276                 tw = test_window->frame->core->width;
 277                 th = test_window->frame->core->height;
 278                 tx = test_window->frame_x;
 279                 ty = test_window->frame_y;
 280
 281                 if (test_window->flags.mapped || (test_window->flags.shaded &&
 282                      test_window->frame->workspace == wwin->screen_ptr->current_workspace &&
 283                      !(test_window->flags.miniaturized || test_window->flags.hidden))) {
 284                         sum_isect += calcIntersectionArea(tx, ty, tw, th, x, y, w, h);
 285                 }
 286         }
 287
 288         return sum_isect;
 289 }
 290
 291 static void set_width_height(WWindow *wwin, unsigned int *width, unsigned int *height)
 292 {
 293         if (wwin->frame) {
 294                 *height += wwin->frame->top_width + wwin->frame->bottom_width;
 295         } else {
 296                 if (HAS_TITLEBAR(wwin))
 297                         *height += TITLEBAR_HEIGHT;
 298                 if (HAS_RESIZEBAR(wwin))
 299                         *height += RESIZEBAR_HEIGHT;
 300         }
 301         if (HAS_BORDER(wwin)) {
 302                 *height += 2 * wwin->screen_ptr->frame_border_width;
 303                 *width  += 2 * wwin->screen_ptr->frame_border_width;
 304         }
 305 }
 306
 307 static Bool
 308 window_overlaps(WWindow *win, int x, int y, int w, int h, Bool ignore_sunken)
 309 {
 310         int tw, th, tx, ty;
 311
 312         if (ignore_sunken &&
 313             win->frame->core->stacking->window_level < WMNormalLevel) {
 314                 return False;
 315         }
 316
 317         tw = win->frame->core->width;
 318         th = win->frame->core->height;
 319         tx = win->frame_x;
 320         ty = win->frame_y;
 321
 322         if ((tx < (x + w)) && ((tx + tw) > x) &&
 323             (ty < (y + h)) && ((ty + th) > y) &&
 324             (win->flags.mapped ||
 325              (win->flags.shaded &&
 326               win->frame->workspace == win->screen_ptr->current_workspace &&
 327               !(win->flags.miniaturized || win->flags.hidden)))) {
 328                 return True;
 329         }
 330
 331         return False;
 332 }
 333
 334 static Bool
 335 screen_has_space(WScreen *scr, int x, int y, int w, int h, Bool ignore_sunken)
 336 {
 337         WWindow *focused = scr->focused_window, *i;
 338
 339         for (i = focused; i; i = i->next) {
 340                 if (window_overlaps(i, x, y, w, h, ignore_sunken)) {
 341                         return False;
 342                 }
 343         }
 344
 345         for (i = focused; i; i = i->prev) {
 346                 if (window_overlaps(i, x, y, w, h, ignore_sunken)) {
 347                         return False;
 348                 }
 349         }
 350
 351         return True;
 352 }
 353
 354 static void
 355 smartPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned int width,
 356                  unsigned int height, WArea usableArea)
 357 {
 358         int test_x = 0, test_y = Y_ORIGIN;
 359         int from_x, to_x, from_y, to_y;
 360         int sx;
 361         int min_isect, min_isect_x, min_isect_y;
 362         int sum_isect;
 363
 364         set_width_height(wwin, &width, &height);
 365
 366         sx = X_ORIGIN;
 367         min_isect = INT_MAX;
 368         min_isect_x = sx;
 369         min_isect_y = test_y;
 370
 371         while (((test_y + height) < usableArea.y2)) {
 372                 test_x = sx;
 373                 while ((test_x + width) < usableArea.x2) {
 374                         sum_isect = calcSumOfCoveredAreas(wwin, test_x, test_y, width, height);
 375
 376                         if (sum_isect < min_isect) {
 377                                 min_isect = sum_isect;
 378                                 min_isect_x = test_x;
 379                                 min_isect_y = test_y;
 380                         }
 381
 382                         test_x += PLACETEST_HSTEP;
 383                 }
 384                 test_y += PLACETEST_VSTEP;
 385         }
 386
 387         from_x = min_isect_x - PLACETEST_HSTEP + 1;
 388         from_x = WMAX(from_x, X_ORIGIN);
 389         to_x = min_isect_x + PLACETEST_HSTEP;
 390         if (to_x + width > usableArea.x2)
 391                 to_x = usableArea.x2 - width;
 392
 393         from_y = min_isect_y - PLACETEST_VSTEP + 1;
 394         from_y = WMAX(from_y, Y_ORIGIN);
 395         to_y = min_isect_y + PLACETEST_VSTEP;
 396         if (to_y + height > usableArea.y2)
 397                 to_y = usableArea.y2 - height;
 398
 399         for (test_x = from_x; test_x < to_x; test_x++) {
 400                 for (test_y = from_y; test_y < to_y; test_y++) {
 401                         sum_isect = calcSumOfCoveredAreas(wwin, test_x, test_y, width, height);
 402
 403                         if (sum_isect < min_isect) {
 404                                 min_isect = sum_isect;
 405                                 min_isect_x = test_x;
 406                                 min_isect_y = test_y;
 407                         }
 408                 }
 409         }
 410
 411         *x_ret = min_isect_x;
 412         *y_ret = min_isect_y;
 413 }
 414
 415 static Bool
 416 center_place_window(WWindow *wwin, int *x_ret, int *y_ret,
 417                  unsigned int width, unsigned int height, WArea usableArea)
 418 {
 419         int swidth, sheight;
 420
 421         set_width_height(wwin, &width, &height);
 422         swidth = usableArea.x2 - usableArea.x1;
 423         sheight = usableArea.y2 - usableArea.y1;
 424
 425         if (width > swidth || height > sheight)
 426                 return False;
 427
 428         *x_ret = (usableArea.x1 + usableArea.x2 - width) / 2;
 429         *y_ret = (usableArea.y1 + usableArea.y2 - height) / 2;
 430
 431         return True;
 432 }
 433
 434 static Bool
 435 autoPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret,
 436                 unsigned int width, unsigned int height,
 437                 Bool ignore_sunken, WArea usableArea)
 438 {
 439         WScreen *scr = wwin->screen_ptr;
 440         int x, y;
 441         int sw, sh;
 442
 443         set_width_height(wwin, &width, &height);
 444         sw = usableArea.x2 - usableArea.x1;
 445         sh = usableArea.y2 - usableArea.y1;
 446
 447         /* try placing at center first */
 448         if (center_place_window(wwin, &x, &y, width, height, usableArea) &&
 449             screen_has_space(scr, x, y, width, height, False)) {
 450                 *x_ret = x;
 451                 *y_ret = y;
 452                 return True;
 453         }
 454
 455         /* this was based on fvwm2's smart placement */
 456         for (y = Y_ORIGIN; (y + height) < sh; y += PLACETEST_VSTEP) {
 457                 for (x = X_ORIGIN; (x + width) < sw; x += PLACETEST_HSTEP) {
 458                         if (screen_has_space(scr, x, y,
 459                                              width, height, ignore_sunken)) {
 460                                 *x_ret = x;
 461                                 *y_ret = y;
 462                                 return True;
 463                         }
 464                 }
 465         }
 466
 467         return False;
 468 }
 469
 470 static void
 471 cascadeWindow(WScreen *scr, WWindow *wwin, int *x_ret, int *y_ret,
 472               unsigned int width, unsigned int height, int h, WArea usableArea)
 473 {
 474         set_width_height(wwin, &width, &height);
 475
 476         *x_ret = h * scr->cascade_index + X_ORIGIN;
 477         *y_ret = h * scr->cascade_index + Y_ORIGIN;
 478
 479         if (width + *x_ret > usableArea.x2 || height + *y_ret > usableArea.y2) {
 480                 scr->cascade_index = 0;
 481                 *x_ret = X_ORIGIN;
 482                 *y_ret = Y_ORIGIN;
 483         }
 484 }
 485
 486 static void randomPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret,
 487                   unsigned int width, unsigned int height, WArea usableArea)
 488 {
 489         int w, h;
 490
 491         set_width_height(wwin, &width, &height);
 492
 493         w = ((usableArea.x2 - X_ORIGIN) - width);
 494         h = ((usableArea.y2 - Y_ORIGIN) - height);
 495         if (w < 1)
 496                 w = 1;
 497         if (h < 1)
 498                 h = 1;
 499         *x_ret = X_ORIGIN + rand() % w;
 500         *y_ret = Y_ORIGIN + rand() % h;
 501 }
 502
 503 void PlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned width, unsigned height)
 504 {
 505         WScreen *scr = wwin->screen_ptr;
 506         int h = WMFontHeight(scr->title_font)
 507                 + (wPreferences.window_title_clearance + TITLEBAR_EXTEND_SPACE) * 2;
 508
 509         if (h > wPreferences.window_title_max_height)
 510                 h = wPreferences.window_title_max_height;
 511
 512         if (h < wPreferences.window_title_min_height)
 513                 h = wPreferences.window_title_min_height;
 514
 515         WArea usableArea = wGetUsableAreaForHead(scr, wGetHeadForPointerLocation(scr),
 516                                                  NULL, True);
 517
 518         switch (wPreferences.window_placement) {
 519         case WPM_MANUAL:
 520                 InteractivePlaceWindow(wwin, x_ret, y_ret, width, height);
 521                 break;
 522
 523         case WPM_SMART:
 524                 smartPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
 525                 break;
 526
 527         case WPM_CENTER:
 528                 if (center_place_window(wwin, x_ret, y_ret, width, height, usableArea))
 529                         break;
 530                 /* Fall through. */
 531
 532         case WPM_AUTO:
 533                 if (autoPlaceWindow(wwin, x_ret, y_ret, width, height, False, usableArea)) {
 534                         break;
 535                 } else if (autoPlaceWindow(wwin, x_ret, y_ret, width, height, True, usableArea)) {
 536                         break;
 537                 }
 538                 /* there isn't a break here, because if we fail, it should fall
 539                    through to cascade placement, as people who want tiling want
 540                    automagicness aren't going to want to place their window */
 541
 542                 /* Fall through. */
 543
 544         case WPM_CASCADE:
 545                 if (wPreferences.window_placement == WPM_AUTO || wPreferences.window_placement == WPM_CENTER)
 546                         scr->cascade_index++;
 547
 548                 cascadeWindow(scr, wwin, x_ret, y_ret, width, height, h, usableArea);
 549
 550                 if (wPreferences.window_placement == WPM_CASCADE)
 551                         scr->cascade_index++;
 552                 break;
 553
 554         case WPM_RANDOM:
 555                 randomPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
 556                 break;
 557         }
 558
 559         /*
 560          * clip to usableArea instead of full screen
 561          * this will also take dock/clip etc.. into account
 562          * as well as being xinerama friendly
 563          */
 564         if (*x_ret + width > usableArea.x2)
 565                 *x_ret = usableArea.x2 - width;
 566         if (*x_ret < usableArea.x1)
 567                 *x_ret = usableArea.x1;
 568
 569         if (*y_ret + height > usableArea.y2)
 570                 *y_ret = usableArea.y2 - height;
 571         if (*y_ret < usableArea.y1)
 572                 *y_ret = usableArea.y1;
 573 }