Correct calculation of usable space for reserved area.
[wmaker-crm.git] / src / placement.c
blob29ee695935fc7af70513b8b0424724d434f437ce
1 /* placement.c - window and icon placement on screen
3 * Window Maker window manager
5 * Copyright (c) 1997-2003 Alfredo K. Kojima
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.
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.
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.
22 #include "wconfig.h"
24 #include <X11/Xlib.h>
25 #include <stdlib.h>
26 #include <stdio.h>
27 #include <string.h>
28 #include <limits.h>
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"
43 #define X_ORIGIN WMAX(usableArea.x1,\
44 wPreferences.window_place_origin.x)
46 #define Y_ORIGIN WMAX(usableArea.y1,\
47 wPreferences.window_place_origin.y)
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)
54 void *parent;
55 int ok = 0;
57 parent = wcore->descriptor.parent;
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;
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) {
71 *retX = ((WIcon *) parent)->owner->icon_x;
72 *retY = ((WIcon *) parent)->owner->icon_y;
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;
82 ok = 1;
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;
92 if (*retY < sy1 - wPreferences.icon_size)
93 ok = 0;
94 else if (*retY > sy2)
95 ok = 0;
98 return ok;
101 void PlaceIcon(WScreen *scr, int *x_ret, int *y_ret, int head)
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);
120 /* Do not place icons under the dock. */
121 if (scr->dock) {
122 int offset = wPreferences.icon_size + DOCK_EXTRA_SPACE;
124 if (scr->dock->on_right_side)
125 area.x2 -= offset;
126 else
127 area.x1 += offset;
130 /* Find out screen boundaries. */
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;
140 sw = isize * (sw / isize);
141 sh = isize * (sh / isize);
142 fullW = (sx2 - sx1) / isize;
143 fullH = (sy2 - sy1) / isize;
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;
153 if (wPreferences.icon_yard & IY_RIGHT) {
154 xo = sx2 - isize;
155 xs = -1;
156 } else {
157 xo = sx1;
158 xs = 1;
160 if (wPreferences.icon_yard & IY_TOP) {
161 yo = sy1;
162 ys = 1;
163 } else {
164 yo = sy2 - isize;
165 ys = -1;
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.
176 map = wmalloc((sw + 2) * (sh + 2));
178 #define INDEX(x,y) (((y)+1)*(sw+2) + (x) + 1)
180 WM_ETARETI_BAG(scr->stacking_list, obj, iter) {
182 while (obj) {
183 int x, y;
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 */
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;
198 obj = obj->stacking->under;
201 /* Default position */
202 *x_ret = 0;
203 *y_ret = 0;
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);
215 if (!map[INDEX(x / isize, y / isize)]) {
216 *x_ret = x;
217 *y_ret = y;
218 done = 1;
219 break;
222 if (done)
223 break;
226 wfree(map);
229 /* Computes the intersecting length of two line sections */
230 int calcIntersectionLength(int p1, int l1, int p2, int l2)
232 int isect;
233 int tmp;
235 if (p1 > p2) {
236 tmp = p1;
237 p1 = p2;
238 p2 = tmp;
239 tmp = l1;
240 l1 = l2;
241 l2 = tmp;
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;
251 return isect;
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)
257 return calcIntersectionLength(x1, w1, x2, w2)
258 * calcIntersectionLength(y1, h1, y2, h2);
261 static int calcSumOfCoveredAreas(WWindow *wwin, int x, int y, int w, int h)
263 int sum_isect = 0;
264 WWindow *test_window;
265 int tw, tx, ty, th;
267 test_window = wwin->screen_ptr->focused_window;
268 for (; test_window != NULL && test_window->prev != NULL;)
269 test_window = test_window->prev;
271 for (; test_window != NULL; test_window = test_window->next) {
272 if (test_window->frame->core->stacking->window_level < WMNormalLevel) {
273 continue;
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;
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);
288 return sum_isect;
291 static void set_width_height(WWindow *wwin, unsigned int *width, unsigned int *height)
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;
301 if (HAS_BORDER(wwin)) {
302 *height += 2 * wwin->screen_ptr->frame_border_width;
303 *width += 2 * wwin->screen_ptr->frame_border_width;
307 static Bool
308 window_overlaps(WWindow *win, int x, int y, int w, int h, Bool ignore_sunken)
310 int tw, th, tx, ty;
312 if (ignore_sunken &&
313 win->frame->core->stacking->window_level < WMNormalLevel) {
314 return False;
317 tw = win->frame->core->width;
318 th = win->frame->core->height;
319 tx = win->frame_x;
320 ty = win->frame_y;
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;
331 return False;
334 static Bool
335 screen_has_space(WScreen *scr, int x, int y, int w, int h, Bool ignore_sunken)
337 WWindow *focused = scr->focused_window, *i;
339 for (i = focused; i; i = i->next) {
340 if (window_overlaps(i, x, y, w, h, ignore_sunken)) {
341 return False;
345 for (i = focused; i; i = i->prev) {
346 if (window_overlaps(i, x, y, w, h, ignore_sunken)) {
347 return False;
351 return True;
354 static void
355 smartPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned int width,
356 unsigned int height, WArea usableArea)
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;
364 set_width_height(wwin, &width, &height);
366 sx = X_ORIGIN;
367 min_isect = INT_MAX;
368 min_isect_x = sx;
369 min_isect_y = test_y;
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);
376 if (sum_isect < min_isect) {
377 min_isect = sum_isect;
378 min_isect_x = test_x;
379 min_isect_y = test_y;
382 test_x += PLACETEST_HSTEP;
384 test_y += PLACETEST_VSTEP;
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;
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;
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);
403 if (sum_isect < min_isect) {
404 min_isect = sum_isect;
405 min_isect_x = test_x;
406 min_isect_y = test_y;
411 *x_ret = min_isect_x;
412 *y_ret = min_isect_y;
415 static Bool
416 center_place_window(WWindow *wwin, int *x_ret, int *y_ret,
417 unsigned int width, unsigned int height, WArea usableArea)
419 int swidth, sheight;
421 set_width_height(wwin, &width, &height);
422 swidth = usableArea.x2 - usableArea.x1;
423 sheight = usableArea.y2 - usableArea.y1;
425 if (width > swidth || height > sheight)
426 return False;
428 *x_ret = (usableArea.x1 + usableArea.x2 - width) / 2;
429 *y_ret = (usableArea.y1 + usableArea.y2 - height) / 2;
431 return True;
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)
439 WScreen *scr = wwin->screen_ptr;
440 int x, y;
441 int sw, sh;
443 set_width_height(wwin, &width, &height);
444 sw = usableArea.x2 - usableArea.x1;
445 sh = usableArea.y2 - usableArea.y1;
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;
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;
467 return False;
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)
474 set_width_height(wwin, &width, &height);
476 *x_ret = h * scr->cascade_index + X_ORIGIN;
477 *y_ret = h * scr->cascade_index + Y_ORIGIN;
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;
486 static void randomPlaceWindow(WWindow *wwin, int *x_ret, int *y_ret,
487 unsigned int width, unsigned int height, WArea usableArea)
489 int w, h;
491 set_width_height(wwin, &width, &height);
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;
503 void PlaceWindow(WWindow *wwin, int *x_ret, int *y_ret, unsigned width, unsigned height)
505 WScreen *scr = wwin->screen_ptr;
506 int h = WMFontHeight(scr->title_font)
507 + (wPreferences.window_title_clearance + TITLEBAR_EXTEND_SPACE) * 2;
509 if (h > wPreferences.window_title_max_height)
510 h = wPreferences.window_title_max_height;
512 if (h < wPreferences.window_title_min_height)
513 h = wPreferences.window_title_min_height;
515 WArea usableArea = wGetUsableAreaForHead(scr, wGetHeadForPointerLocation(scr),
516 NULL, True);
518 switch (wPreferences.window_placement) {
519 case WPM_MANUAL:
520 InteractivePlaceWindow(wwin, x_ret, y_ret, width, height);
521 break;
523 case WPM_SMART:
524 smartPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
525 break;
527 case WPM_CENTER:
528 if (center_place_window(wwin, x_ret, y_ret, width, height, usableArea))
529 break;
530 /* Fall through. */
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;
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 */
542 /* Fall through. */
544 case WPM_CASCADE:
545 if (wPreferences.window_placement == WPM_AUTO || wPreferences.window_placement == WPM_CENTER)
546 scr->cascade_index++;
548 cascadeWindow(scr, wwin, x_ret, y_ret, width, height, h, usableArea);
550 if (wPreferences.window_placement == WPM_CASCADE)
551 scr->cascade_index++;
552 break;
554 case WPM_RANDOM:
555 randomPlaceWindow(wwin, x_ret, y_ret, width, height, usableArea);
556 break;
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
564 if (*x_ret + width > usableArea.x2)
565 *x_ret = usableArea.x2 - width;
566 if (*x_ret < usableArea.x1)
567 *x_ret = usableArea.x1;
569 if (*y_ret + height > usableArea.y2)
570 *y_ret = usableArea.y2 - height;
571 if (*y_ret < usableArea.y1)
572 *y_ret = usableArea.y1;