--- src/placement.orig.c 2011-01-30 17:51:01.000000000 +0100 +++ src/placement.c 2011-08-01 22:18:25.851819702 +0200 @@ -533,92 +533,248 @@ clientAutoMaximize (Client * c, int full "the window will be maximized vertically.", c->name, frameHeight (c), full_h); FLAG_SET (c->flags, CLIENT_FLAG_MAXIMIZED_VERT); } } +/* Helpers for smartPlacement: */ + +typedef struct _PosNode PosNode; + +struct _PosNode +{ + gint pos; + PosNode *lo; + PosNode *hi; + PosNode *next; +}; + +static void +add_pos (PosNode * node, PosNode ** next) +{ + gint pos = (*next)->pos; + + for (;;) + { + if (pos < node->pos) + { + if (node->lo) + { + node = node->lo; + continue; + } + else + { + node->lo = (*next)++; + break; + } + } + if (pos > node->pos) + { + if (node->hi) + { + node = node->hi; + continue; + } + else + { + node->hi = (*next)++; + break; + } + } + break; /* Position already in tree */ + } +} + +static PosNode ** +sort_pos (PosNode * node, PosNode ** addr) +{ + if (node->lo) + addr = sort_pos (node->lo, addr); + *addr = node; + addr = &node->next; + if (node->hi) + addr = sort_pos (node->hi, addr); + return addr; +} + +static unsigned long +overlap_all (Client * c, gint * px, gint * py, gint frame_w, gint frame_h, + gint full_x, gint full_y, gint full_w, gint full_h) +{ + gint i, d, x2, y2, w2, h2, mod_x, mod_y; + Client *c2; + ScreenInfo *screen_info = c->screen_info; + unsigned long sum_ovl = 0; + gint x = *px; + gint y = *py; + + for (c2 = screen_info->clients, i = 0; i < screen_info->client_count; c2 = c2->next, i++) + { + if ((c2 != c) && (c2->type != WINDOW_DESKTOP) + && (c->win_workspace == c2->win_workspace) + && FLAG_TEST (c2->xfwm_flags, XFWM_FLAG_VISIBLE)) + { + x2 = frameX (c2); + y2 = frameY (c2); + w2 = frameWidth (c2); + h2 = frameHeight (c2); + if (x == x2 && y == y2 && frame_w == w2 && frame_h == h2) + { + /* Avoid identical windows at the same position. + * Try a slightly shifted position instead, if possible. + */ + d = frameTop (c); + if ((x - full_x) * 2 > full_w - frame_w) + mod_x = x - d/2; + else + mod_x = x + d/2; + if ((y - full_y) * 2 > full_h - frame_h) + mod_y = y - d; + else + mod_y = y + d; + if (mod_x >= full_x && mod_x + frame_w <= full_x + full_w && + mod_y >= full_y && mod_y + frame_h <= full_y + full_h) + { + *px = mod_x; + *py = mod_y; + return overlap_all (c, px, py, frame_w, frame_h, + full_x, full_y, full_w, full_h); + } + } + sum_ovl += overlap (x, y, x + frame_w, y + frame_h, + x2, y2, x2 + w2, y2 + h2); + } + } + + return sum_ovl; +} + static void smartPlacement (Client * c, int full_x, int full_y, int full_w, int full_h) { Client *c2; ScreenInfo *screen_info; - gfloat best_overlaps; - guint i; - gint test_x, test_y, xmax, ymax, best_x, best_y; - gint frame_x, frame_y, frame_height, frame_width, frame_left, frame_top; - gboolean first; + guint i, count; + gint pos, x, y, best_x, best_y, min_x, min_y, max_x, max_y; + gint frame_width, frame_height; + PosNode *root_h, *root_v, *next, *first_h, *first_v, *pos_h, *pos_v; + unsigned long ovl, best_ovl; g_return_if_fail (c != NULL); TRACE ("entering smartPlacement"); screen_info = c->screen_info; - frame_x = frameX (c); - frame_y = frameY (c); - frame_height = frameHeight (c); frame_width = frameWidth (c); - frame_left = frameLeft(c); - frame_top = frameTop (c); - test_x = 0; - test_y = 0; - best_overlaps = 0.0; - first = TRUE; - - xmax = full_x + full_w - c->width - frameRight (c); - ymax = full_y + full_h - c->height - frameBottom (c); - best_x = full_x + frameLeft (c); - best_y = full_y + frameTop (c); - - test_y = full_y + frameTop (c); - do - { - test_x = full_x + frameLeft (c); - do - { - gfloat count_overlaps = 0.0; - TRACE ("analyzing %i clients", screen_info->client_count); - for (c2 = screen_info->clients, i = 0; i < screen_info->client_count; c2 = c2->next, i++) - { - if ((c2 != c) && (c2->type != WINDOW_DESKTOP) - && (c->win_workspace == c2->win_workspace) - && FLAG_TEST (c2->xfwm_flags, XFWM_FLAG_VISIBLE)) - { - count_overlaps += overlap (test_x - frame_left, - test_y - frame_top, - test_x - frame_left + frame_width, - test_y - frame_top + frame_height, - frameX (c2), - frameY (c2), - frameX (c2) + frameWidth (c2), - frameY (c2) + frameHeight (c2)); - } + frame_height = frameHeight (c); + min_x = full_x + frame_width; + min_y = full_y + frame_height; + max_x = full_x + full_w - frame_width; + max_y = full_y + full_h - frame_height; + if (max_x < full_x) + max_x = full_x; + if (max_y < full_y) + max_y = full_y; + best_x = full_x; + best_y = full_y; + best_ovl = ULONG_MAX; + count = 0; + + for (c2 = screen_info->clients, i = 0; i < screen_info->client_count; c2 = c2->next, i++) + { + if ((c2 != c) && (c2->type != WINDOW_DESKTOP) + && (c->win_workspace == c2->win_workspace) + && FLAG_TEST (c2->xfwm_flags, XFWM_FLAG_VISIBLE)) + { + count++; + } + } + + root_h = g_malloc0 ((count + 1) * sizeof *root_h * 4); + root_v = root_h + 1; + next = root_v + 1; + + /* Windows may lie at the edges of the placement area */ + root_h->pos = full_x; + root_v->pos = full_y; + next->pos = max_x; + add_pos (root_h, &next); + next->pos = max_y; + add_pos (root_v, &next); + + /* Windows may be adjacent to another window. + * Add possible horizontal and vertical positions into a sorted binary + * tree. This will eliminate duplicates. + */ + for (c2 = screen_info->clients, i = 0; i < count; c2 = c2->next) + { + if ((c2 != c) && (c2->type != WINDOW_DESKTOP) + && (c->win_workspace == c2->win_workspace) + && FLAG_TEST (c2->xfwm_flags, XFWM_FLAG_VISIBLE)) + { + pos = frameX (c2); + if (pos > min_x) + { + next->pos = pos - frame_width; + add_pos (root_h, &next); } - if (count_overlaps < 0.1) + pos += frameWidth (c2); + if (pos < max_x) { - TRACE ("overlaps is 0 so it's the best we can get"); - c->x = test_x; - c->y = test_y; - - return; + next->pos = pos; + add_pos (root_h, &next); + } + pos = frameY (c2); + if (pos > min_y) + { + next->pos = pos - frame_height; + add_pos (root_v, &next); + } + pos += frameHeight (c2); + if (pos < max_y) + { + next->pos = pos; + add_pos (root_v, &next); } - else if ((count_overlaps < best_overlaps) || (first)) + i++; + } + } + + /* Create sorted linked list of position entries */ + sort_pos (root_h, &first_h); + sort_pos (root_v, &first_v); + + /* Try all possible positions */ + for (pos_v = first_v; pos_v; pos_v = pos_v->next) + { + for (pos_h = first_h; pos_h; pos_h = pos_h->next) + { + x = pos_h->pos; + y = pos_v->pos; /* may be modified by overlap_all */ + ovl = overlap_all (c, &x, &y, frame_width, frame_height, + full_x, full_y, full_w, full_h); + /* Take the first opportunity (upper left) if no overlap or + * identical overlaps + */ + if (!ovl) { - best_x = test_x; - best_y = test_y; - best_overlaps = count_overlaps; + best_x = x; + best_y = y; + goto out; } - if (first) + if (ovl < best_ovl) { - first = FALSE; + best_x = x; + best_y = y; + best_ovl = ovl; } - test_x += 8; } - while (test_x <= xmax); - test_y += 8; } - while (test_y <= ymax); - c->x = best_x; - c->y = best_y; +out: + g_free(root_h); + c->x = best_x + frameLeft (c); + c->y = best_y + frameTop (c); } static void centerPlacement (Client * c, int full_x, int full_y, int full_w, int full_h) { @@ -631,11 +787,11 @@ centerPlacement (Client * c, int full_x, static void mousePlacement (Client * c, int full_x, int full_y, int full_w, int full_h, int mx, int my) { g_return_if_fail (c != NULL); - TRACE ("entering centerPlacement"); + TRACE ("entering mousePlacement"); c->x = mx + frameLeft(c) - frameWidth(c) / 2; c->y = my + frameTop(c) - frameHeight(c) / 2; c->x = MIN (c->x, full_x + full_w - frameWidth(c) + frameLeft(c)); @@ -712,11 +868,11 @@ clientInitPosition (Client * c) /* If the windows is smaller than the given ratio of the available screen area, or if the window is larger than the screen area or if the given ratio is higher than 100% place the window at the center. - Otherwise, place the window "smartly", using the good old CPU consuming algorithm... + Otherwise, place the window "smartly". */ if (place) { if ((screen_info->params->placement_ratio >= 100) || (100 * frameWidth(c) * frameHeight(c)) < (screen_info->params->placement_ratio * full_w * full_h))