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