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 <itz@buug.org>.
Port to Openbox 3.5 by David Vogt <dv@adfinis.c>.

7 files changed, 264 insertions, 4 deletions

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 @@
         <xsd:restriction base="xsd:string">
             <xsd:enumeration value="Smart"/>
             <xsd:enumeration value="UnderMouse"/>
+            <xsd:enumeration value="LeastOverlap"/>
         </xsd:restriction>
     </xsd:simpleType>
     <xsd:simpleType name="placementmonitor">
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 <stdlib.h>
+
+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