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, scr->current_workspace, &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 == wwin->screen_ptr->current_workspace &&
 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 void
 298 smartPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned int width,
 299                  unsigned int height, WArea usableArea)
 300 {
 301         int test_x = 0, test_y = Y_ORIGIN;
 302         int from_x, to_x, from_y, to_y;
 303         int sx;
 304         int min_isect, min_isect_x, min_isect_y;
 305         int sum_isect;
 306
 307         set_width_height(wwin, &width, &height);
 308
 309         sx = X_ORIGIN;
 310         min_isect = INT_MAX;
 311         min_isect_x = sx;
 312         min_isect_y = test_y;
 313
 314         while (((test_y + height) < usableArea.y2)) {
 315                 test_x = sx;
 316                 while ((test_x + width) < usableArea.x2) {
 317                         sum_isect = calcSumOfCoveredAreas(wwin, test_x, test_y, width, height);
 318
 319                         if (sum_isect < min_isect) {
 320                                 min_isect = sum_isect;
 321                                 min_isect_x = test_x;
 322                                 min_isect_y = test_y;
 323                         }
 324
 325                         test_x += PLACETEST_HSTEP;
 326                 }
 327                 test_y += PLACETEST_VSTEP;
 328         }
 329
 330         from_x = min_isect_x - PLACETEST_HSTEP + 1;
 331         from_x = WMAX(from_x, X_ORIGIN);
 332         to_x = min_isect_x + PLACETEST_HSTEP;
 333         if (to_x + width > usableArea.x2)
 334                 to_x = usableArea.x2 - width;
 335
 336         from_y = min_isect_y - PLACETEST_VSTEP + 1;
 337         from_y = WMAX(from_y, Y_ORIGIN);
 338         to_y = min_isect_y + PLACETEST_VSTEP;
 339         if (to_y + height > usableArea.y2)
 340                 to_y = usableArea.y2 - height;
 341
 342         for (test_x = from_x; test_x < to_x; test_x++) {
 343                 for (test_y = from_y; test_y < to_y; test_y++) {
 344                         sum_isect = calcSumOfCoveredAreas(wwin, test_x, test_y, width, height);
 345
 346                         if (sum_isect < min_isect) {
 347                                 min_isect = sum_isect;
 348                                 min_isect_x = test_x;
 349                                 min_isect_y = test_y;
 350                         }
 351                 }
 352         }
 353
 354         *x_ret = min_isect_x;
 355         *y_ret = min_isect_y;
 356 }
 357
 358 static Bool
 359 center_place_window(WWindow *wwin, int *x_ret, int *y_ret,
 360                  unsigned int width, unsigned int height, WArea usableArea)
 361 {
 362         int swidth, sheight;
 363
 364         set_width_height(wwin, &width, &height);
 365         swidth = usableArea.x2 - usableArea.x1;
 366         sheight = usableArea.y2 - usableArea.y1;
 367
 368         if (width > swidth || height > sheight)
 369                 return False;
 370
 371         *x_ret = (usableArea.x1 + usableArea.x2 - width) / 2;
 372         *y_ret = (usableArea.y1 + usableArea.y2 - height) / 2;
 373
 374         return True;
 375 }
 376
 377 static Bool
 378 autoPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret,
 379                 unsigned int width, unsigned int height, int tryCount, WArea usableArea)
 380 {
 381         WScreen *scr = wwin->screen_ptr;
 382         int test_x = 0, test_y = Y_ORIGIN;
 383         int loc_ok = False, tw, tx, ty, th;
 384         int swidth, sx;
 385         WWindow *test_window;
 386
 387         set_width_height(wwin, &width, &height);
 388         swidth = usableArea.x2 - usableArea.x1;
 389         sx = X_ORIGIN;
 390
 391         /* this was based on fvwm2's smart placement */
 392         while (((test_y + height) < (usableArea.y2 - usableArea.y1)) && !loc_ok) {
 393                 test_x = sx;
 394
 395                 while (((test_x + width) < swidth) && (!loc_ok)) {
 396
 397                         loc_ok = True;
 398                         test_window = scr->focused_window;
 399
 400                         while ((test_window != NULL) && (loc_ok == True)) {
 401
 402                                 if (test_window->frame->core->stacking->window_level
 403                                     < WMNormalLevel && tryCount > 0) {
 404                                         test_window = test_window->next;
 405                                         continue;
 406                                 }
 407                                 tw = test_window->frame->core->width;
 408                                 th = test_window->frame->core->height;
 409                                 tx = test_window->frame_x;
 410                                 ty = test_window->frame_y;
 411
 412                                 if ((tx < (test_x + width)) && ((tx + tw) > test_x) &&
 413                                     (ty < (test_y + height)) && ((ty + th) > test_y) &&
 414                                     (test_window->flags.mapped ||
 415                                      (test_window->flags.shaded &&
 416                                       test_window->frame->workspace == scr->current_workspace &&
 417                                       !(test_window->flags.miniaturized || test_window->flags.hidden)))) {
 418
 419                                         loc_ok = False;
 420                                 }
 421                                 test_window = test_window->next;
 422                         }
 423
 424                         test_window = scr->focused_window;
 425
 426                         while ((test_window != NULL) && (loc_ok == True)) {
 427
 428                                 if (test_window->frame->core->stacking->window_level
 429                                     < WMNormalLevel && tryCount > 0) {
 430                                         test_window = test_window->prev;
 431                                         continue;
 432                                 }
 433                                 tw = test_window->frame->core->width;
 434                                 th = test_window->frame->core->height;
 435                                 tx = test_window->frame_x;
 436                                 ty = test_window->frame_y;
 437
 438                                 if ((tx < (test_x + width)) && ((tx + tw) > test_x) &&
 439                                     (ty < (test_y + height)) && ((ty + th) > test_y) &&
 440                                     (test_window->flags.mapped ||
 441                                      (test_window->flags.shaded &&
 442                                       test_window->frame->workspace == scr->current_workspace &&
 443                                       !(test_window->flags.miniaturized || test_window->flags.hidden)))) {
 444
 445                                         loc_ok = False;
 446                                 }
 447                                 test_window = test_window->prev;
 448                         }
 449                         if (loc_ok == True) {
 450                                 *x_ret = test_x;
 451                                 *y_ret = test_y;
 452                                 break;
 453                         }
 454                         test_x += PLACETEST_HSTEP;
 455                 }
 456                 test_y += PLACETEST_VSTEP;
 457         }
 458
 459         return loc_ok;
 460 }
 461
 462 static void
 463 cascadeWindow(WScreen *scr, WWindow *wwin, int *x_ret, int *y_ret,
 464               unsigned int width, unsigned int height, int h, WArea usableArea)
 465 {
 466         set_width_height(wwin, &width, &height);
 467
 468         *x_ret = h * scr->cascade_index + X_ORIGIN;
 469         *y_ret = h * scr->cascade_index + Y_ORIGIN;
 470
 471         if (width + *x_ret > usableArea.x2 || height + *y_ret > usableArea.y2) {
 472                 scr->cascade_index = 0;
 473                 *x_ret = X_ORIGIN;
 474                 *y_ret = Y_ORIGIN;
 475         }
 476 }
 477
 478 static void randomPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret,
 479                   unsigned int width, unsigned int height, WArea usableArea)
 480 {
 481         int w, h;
 482
 483         set_width_height(wwin, &width, &height);
 484
 485         w = ((usableArea.x2 - X_ORIGIN) - width);
 486         h = ((usableArea.y2 - Y_ORIGIN) - height);
 487         if (w < 1)
 488                 w = 1;
 489         if (h < 1)
 490                 h = 1;
 491         *x_ret = X_ORIGIN + rand() % w;
 492         *y_ret = Y_ORIGIN + rand() % h;
 493 }
 494
 495 void PlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned width, unsigned height)
 496 {
 497         WScreen *scr = wwin->screen_ptr;
 498         int h = WMFontHeight(scr->title_font)
 499                 + (wPreferences.window_title_clearance + TITLEBAR_EXTEND_SPACE) * 2;
 500
 501         if (h > wPreferences.window_title_max_height)
 502                 h = wPreferences.window_title_max_height;
 503
 504         if (h < wPreferences.window_title_min_height)
 505                 h = wPreferences.window_title_min_height;
 506
 507         WArea usableArea = wGetUsableAreaForHead(scr, wGetHeadForPointerLocation(scr),
 508                                                  NULL, True);
 509
 510         switch (wPreferences.window_placement) {
 511         case WPM_MANUAL:
 512                 InteractivePlaceWindow(wwin, x_ret, y_ret, width, height);
 513                 break;
 514
 515         case WPM_SMART:
 516                 smartPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
 517                 break;
 518
 519         case WPM_CENTER:
 520                 if (center_place_window(wwin, x_ret, y_ret, width, height, usableArea))
 521                         break;
 522
 523         case WPM_AUTO:
 524                 if (autoPlaceWindow(wwin, x_ret, y_ret, width, height, 0, usableArea)) {
 525                         break;
 526                 } else if (autoPlaceWindow(wwin, x_ret, y_ret, width, height, 1, usableArea)) {
 527                         break;
 528                 }
 529                 /* there isn't a break here, because if we fail, it should fall
 530                    through to cascade placement, as people who want tiling want
 531                    automagicness aren't going to want to place their window */
 532
 533         case WPM_CASCADE:
 534                 if (wPreferences.window_placement == WPM_AUTO || wPreferences.window_placement == WPM_CENTER)
 535                         scr->cascade_index++;
 536
 537                 cascadeWindow(scr, wwin, x_ret, y_ret, width, height, h, usableArea);
 538
 539                 if (wPreferences.window_placement == WPM_CASCADE)
 540                         scr->cascade_index++;
 541                 break;
 542
 543         case WPM_RANDOM:
 544                 randomPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
 545                 break;
 546         }
 547
 548         /*
 549          * clip to usableArea instead of full screen
 550          * this will also take dock/clip etc.. into account
 551          * aswell as being xinerama friendly
 552          */
 553         if (*x_ret + width > usableArea.x2)
 554                 *x_ret = usableArea.x2 - width;
 555         if (*x_ret < usableArea.x1)
 556                 *x_ret = usableArea.x1;
 557
 558         if (*y_ret + height > usableArea.y2)
 559                 *y_ret = usableArea.y2 - height;
 560         if (*y_ret < usableArea.y1)
 561                 *y_ret = usableArea.y1;
 562 }