From 4d2ccf19168a4089a6a0de0109610479ec6d5507 Mon Sep 17 00:00:00 2001 From: Ian Zimmerman Date: Sun, 30 Sep 2012 20:51:01 -0400 Subject: [PATCH] LeastOverlap placement option (Fix bug 5385) Adds a new placement algorithm that finds a place on the monitor that overlaps the least amount of windows as possible. Original patch by Ian Zimmerman . Port to Openbox 3.5 by David Vogt . --- Makefile.am | 2 + data/rc.xsd | 1 + openbox/config.c | 6 +- openbox/overlap.c | 175 ++++++++++++++++++++++++++++++++++++++++++++++ openbox/overlap.h | 24 +++++++ openbox/place.c | 57 ++++++++++++++- openbox/place.h | 3 +- 7 files changed, 264 insertions(+), 4 deletions(-) create mode 100644 openbox/overlap.c create mode 100644 openbox/overlap.h diff --git a/Makefile.am b/Makefile.am index bfa3b579..37059ae5 100644 --- a/Makefile.am +++ b/Makefile.am @@ -282,6 +282,8 @@ openbox_openbox_SOURCES = \ openbox/mwm.h \ openbox/openbox.c \ openbox/openbox.h \ + openbox/overlap.c \ + openbox/overlap.h \ openbox/ping.c \ openbox/ping.h \ openbox/place.c \ diff --git a/data/rc.xsd b/data/rc.xsd index ad96994a..07357ad5 100644 --- a/data/rc.xsd +++ b/data/rc.xsd @@ -511,6 +511,7 @@ + diff --git a/openbox/config.c b/openbox/config.c index 0d9eb689..1a3e6ddf 100644 --- a/openbox/config.c +++ b/openbox/config.c @@ -581,9 +581,13 @@ static void parse_placement(xmlNodePtr node, gpointer d) node = node->children; - if ((n = obt_xml_find_node(node, "policy"))) + if ((n = obt_xml_find_node(node, "policy"))) { if (obt_xml_node_contains(n, "UnderMouse")) config_place_policy = OB_PLACE_POLICY_MOUSE; + else if (obt_xml_node_contains(n, "LeastOverlap")) + config_place_policy = OB_PLACE_POLICY_LEASTOVERLAP; + + } if ((n = obt_xml_find_node(node, "center"))) config_place_center = obt_xml_node_bool(n); if ((n = obt_xml_find_node(node, "monitor"))) { diff --git a/openbox/overlap.c b/openbox/overlap.c new file mode 100644 index 00000000..abc600e4 --- /dev/null +++ b/openbox/overlap.c @@ -0,0 +1,175 @@ +/* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*- + + overlap.c for the Openbox window manager + Copyright (c) 2011 Ian Zimmerman + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + See the COPYING file for a copy of the GNU General Public License. +*/ + +#include "config.h" +#include "geom.h" +#include "overlap.h" + +#include + +static void +make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound, + int* x_edges, int* y_edges, int max_edges); + +static int +best_direction(const Point* grid_point, + const Rect* client_rects, int n_client_rects, + const Rect* bound, const Size* req_size, Point* best_top_left); + +/* Choose the placement on a grid with least overlap */ + +void +overlap_find_least_placement(const Rect* client_rects, int n_client_rects, + Rect *const bound, + const Size* req_size, Point* result) +{ + result->x = result->y = 0; + int overlap = G_MAXINT; + int max_edges = 2 * (n_client_rects + 1); + + int x_edges[max_edges]; + int y_edges[max_edges]; + make_grid(client_rects, n_client_rects, bound, + x_edges, y_edges, max_edges); + int i; + for (i = 0; i < max_edges; ++i) { + if (x_edges[i] == G_MAXINT) + break; + int j; + for (j = 0; j < max_edges; ++j) { + if (y_edges[j] == G_MAXINT) + break; + Point grid_point = {.x = x_edges[i], .y = y_edges[j]}; + Point best_top_left; + int this_overlap = + best_direction(&grid_point, client_rects, n_client_rects, + bound, req_size, &best_top_left); + if (this_overlap < overlap) { + overlap = this_overlap; + *result = best_top_left; + } + if (overlap == 0) + break; + } + if (overlap == 0) + break; + } +} + +static int compare_ints(const void* a, const void* b) +{ + const int* ia = (const int*)a; + const int* ib = (const int*)b; + return *ia - *ib; +} + +static void uniquify(int* edges, int n_edges) +{ + int i = 0; + int j = 0; + + while (j < n_edges) { + int last = edges[j++]; + edges[i++] = last; + while (j < n_edges && edges[j] == last) + ++j; + } + /* fill the rest with nonsense */ + for (; i < n_edges ; ++i) + edges[i] = G_MAXINT; +} + +static void +make_grid(const Rect* client_rects, int n_client_rects, const Rect* bound, + int* x_edges, int* y_edges, int max_edges) +{ + int i; + int n_edges = 0; + for (i = 0; i < n_client_rects; ++i) { + if (!RECT_INTERSECTS_RECT(client_rects[i], *bound)) + continue; + x_edges[n_edges] = client_rects[i].x; + y_edges[n_edges++] = client_rects[i].y; + x_edges[n_edges] = client_rects[i].x + client_rects[i].width; + y_edges[n_edges++] = client_rects[i].y + client_rects[i].height; + } + x_edges[n_edges] = bound->x; + y_edges[n_edges++] = bound->y; + x_edges[n_edges] = bound->x + bound->width; + y_edges[n_edges++] = bound->y + bound->height; + for (i = n_edges; i < max_edges; ++i) + x_edges[i] = y_edges[i] = G_MAXINT; + qsort(x_edges, n_edges, sizeof(int), compare_ints); + uniquify(x_edges, n_edges); + qsort(y_edges, n_edges, sizeof(int), compare_ints); + uniquify(y_edges, n_edges); +} + +static int total_overlap(const Rect* client_rects, int n_client_rects, + const Rect* proposed_rect) +{ + int overlap = 0; + int i; + for (i = 0; i < n_client_rects; ++i) { + if (!RECT_INTERSECTS_RECT(*proposed_rect, client_rects[i])) + continue; + Rect rtemp; + RECT_SET_INTERSECTION(rtemp, *proposed_rect, client_rects[i]); + overlap += RECT_AREA(rtemp); + } + return overlap; +} + +/* Given a list of Rect RECTS, a Point PT and a Size size, determine the + * direction from PT which results in the least total overlap with RECTS + * if a rectangle is placed in that direction. Return the top/left + * Point of such rectangle and the resulting overlap amount. Only + * consider placements within BOUNDS. */ + +#define NUM_DIRECTIONS 4 + +static int +best_direction(const Point* grid_point, + const Rect* client_rects, int n_client_rects, + const Rect* bound, const Size* req_size, Point* best_top_left) +{ + static const Size directions[NUM_DIRECTIONS] = { + {0, 0}, {0, -1}, {-1, 0}, {-1, -1} + }; + int overlap = G_MAXINT; + int i; + for (i = 0; i < NUM_DIRECTIONS; ++i) { + Point pt = { + .x = grid_point->x + (req_size->width * directions[i].width), + .y = grid_point->y + (req_size->height * directions[i].height) + }; + Rect r; + RECT_SET_POINT(r, pt.x, pt.y); + RECT_SET_SIZE(r, req_size->width, req_size->height); + if (!RECT_CONTAINS_RECT(*bound, r)) + continue; + int this_overlap = total_overlap(client_rects, n_client_rects, &r); + if (this_overlap < overlap) { + overlap = this_overlap; + *best_top_left = pt; + } + if (overlap == 0) + break; + } + return overlap; +} diff --git a/openbox/overlap.h b/openbox/overlap.h new file mode 100644 index 00000000..0c61035d --- /dev/null +++ b/openbox/overlap.h @@ -0,0 +1,24 @@ +/* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*- + + overlap.h for the Openbox window manager + Copyright (c) 2011 Ian Zimmerman + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + See the COPYING file for a copy of the GNU General Public License. +*/ + +#include "geom.h" + +void +overlap_find_least_placement(const Rect* client_rects, int n_client_rects, + Rect *const bounds, const Size* req_size, + Point* result); diff --git a/openbox/place.c b/openbox/place.c index 2cd21bb0..579c56bd 100644 --- a/openbox/place.c +++ b/openbox/place.c @@ -25,6 +25,7 @@ #include "config.h" #include "dock.h" #include "debug.h" +#include "overlap.h" extern ObDock *dock; @@ -558,6 +559,56 @@ static gboolean place_transient_splash(ObClient *client, Rect *area, return FALSE; } +static gboolean place_least_overlap(ObClient *c, gint *x, gint *y, Rect * const head) +{ + /* assemble the list of "interesting" windows to calculate overlap against */ + GSList* interesting_clients = NULL; + int n_client_rects = 0; + + /* if we're "showing desktop", ignore all existing windows */ + if (!screen_showing_desktop) { + GList* it; + for (it = client_list; it != NULL; it = g_list_next(it)) { + ObClient* maybe_client = (ObClient*) it->data; + if (maybe_client == c) + continue; + if (maybe_client->iconic) + continue; + if (c->desktop != DESKTOP_ALL) { + if (maybe_client->desktop != c->desktop && + maybe_client->desktop != DESKTOP_ALL) continue; + } else { + if (maybe_client->desktop != screen_desktop && + maybe_client->desktop != DESKTOP_ALL) continue; + } + if (maybe_client->type == OB_CLIENT_TYPE_SPLASH || + maybe_client->type == OB_CLIENT_TYPE_DESKTOP) continue; + /* it is interesting, so add it */ + interesting_clients = g_slist_prepend(interesting_clients, maybe_client); + n_client_rects += 1; + } + } + Rect client_rects[n_client_rects]; + GSList* it; + unsigned int i = 0; + for (it = interesting_clients; it != NULL; it = g_slist_next(it)) { + ObClient* interesting_client = (ObClient*) it->data; + client_rects[i] = interesting_client->frame->area; + i += 1; + } + g_slist_free(interesting_clients); + + Point result; + Size req_size; + SIZE_SET(req_size, c->frame->area.width, c->frame->area.height); + overlap_find_least_placement(client_rects, n_client_rects, head, + &req_size, &result); + *x = result.x; + *y = result.y; + + return TRUE; +} + /*! Return TRUE if openbox chose the position for the window, and FALSE if the application chose it */ gboolean place_client(ObClient *client, gboolean foreground, gint *x, gint *y, @@ -579,8 +630,10 @@ gboolean place_client(ObClient *client, gboolean foreground, gint *x, gint *y, /* try a number of methods */ ret = place_per_app_setting(client, area, x, y, settings) || place_transient_splash(client, area, x, y) || - (config_place_policy == OB_PLACE_POLICY_MOUSE && - place_under_mouse(client, x, y)) || + (config_place_policy == OB_PLACE_POLICY_MOUSE + && place_under_mouse (client, x, y)) || + (config_place_policy == OB_PLACE_POLICY_LEASTOVERLAP + && place_least_overlap(client, x, y, area)) || place_nooverlap(client, area, x, y) || place_random(client, area, x, y); g_assert(ret); diff --git a/openbox/place.h b/openbox/place.h index 94e2dc0f..25df752c 100644 --- a/openbox/place.h +++ b/openbox/place.h @@ -28,7 +28,8 @@ struct _ObAppSettings; typedef enum { OB_PLACE_POLICY_SMART, - OB_PLACE_POLICY_MOUSE + OB_PLACE_POLICY_MOUSE, + OB_PLACE_POLICY_LEASTOVERLAP, } ObPlacePolicy; typedef enum -- 2.45.2