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