Add the old <center> option for the placement policy. (Bug 5946)

Original commit messages:
. Reformat to move closer to house style
. Add center on top of leat overlap place algo
. Add sentinel value to edge arrays
. Use a Size instead of a Rect for a centering field
. Fix off by one bug
. Need to declare dx and dy
. Pass length of edge array instead of recomputing
. Fix missing open-brace in config.c
. Address the more trivial subset of danakj comments
. Revert "Remove now-unused config_place_center option."
  This reverts commit 5e282dae08be3b900e0337efa0fae8f3ffa92cd7.
. Remove reliance on sentinel value when scanning edge arrays
. Avoid need to initialize Size structure by removing it :)
. Clean up field expansion code somewhat
. Compress code further by using a structure for common args
. Fix search for next grid point
. Squeeze it even more by not using Size at all

5 files changed, 185 insertions, 14 deletions

diff --git a/data/rc.xml b/data/rc.xml
index 932521b7..3e5554ba 100644
--- a/data/rc.xml
+++ b/data/rc.xml
@@ -33,6 +33,9 @@
 <placement>
   <policy>Smart</policy>
   <!-- 'Smart' or 'UnderMouse' -->
+  <center>yes</center>
+  <!-- whether to place windows in the center of the free area found or
+       the top left corner -->
   <monitor>Primary</monitor>
   <!-- with Smart placement on a multi-monitor system, try to place new windows
        on: 'Any' - any monitor, 'Mouse' - where the mouse is, 'Active' - where
diff --git a/data/rc.xsd b/data/rc.xsd
index 425d53c9..75dd660e 100644
--- a/data/rc.xsd
+++ b/data/rc.xsd
@@ -70,6 +70,7 @@
         </xsd:annotation>
         <xsd:sequence>
             <xsd:element minOccurs="0" name="policy" type="ob:placementpolicy"/>
+            <xsd:element minOccurs="0" name="center" type="ob:bool"/>
             <xsd:element minOccurs="0" name="monitor" type="ob:placementmonitor"/>
             <xsd:element minOccurs="0" name="primaryMonitor" type="ob:primarymonitor"/>
         </xsd:sequence>
diff --git a/openbox/config.c b/openbox/config.c
index 8e1bcf89..76f48569 100644
--- a/openbox/config.c
+++ b/openbox/config.c
@@ -37,6 +37,7 @@ gboolean config_focus_under_mouse;
 gboolean config_unfocus_leave;
 
 ObPlacePolicy  config_place_policy;
+gboolean       config_place_center;
 ObPlaceMonitor config_place_monitor;
 
 guint          config_primary_monitor_index;
@@ -625,9 +626,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;
+    }
+    if ((n = obt_xml_find_node(node, "center"))) {
+        config_place_center = obt_xml_node_bool(n);
+    }
     if ((n = obt_xml_find_node(node, "monitor"))) {
         if (obt_xml_node_contains(n, "active"))
             config_place_monitor = OB_PLACE_MONITOR_ACTIVE;
@@ -1055,6 +1060,7 @@ void config_startup(ObtXmlInst *i)
     obt_xml_register(i, "focus", parse_focus, NULL);
 
     config_place_policy = OB_PLACE_POLICY_SMART;
+    config_place_center = TRUE;
     config_place_monitor = OB_PLACE_MONITOR_PRIMARY;
 
     config_primary_monitor_index = 1;
diff --git a/openbox/config.h b/openbox/config.h
index ce1ff885..fc1d217e 100644
--- a/openbox/config.h
+++ b/openbox/config.h
@@ -88,6 +88,8 @@ extern gboolean config_unfocus_leave;
 
 /*! The algorithm to use for placing new windows */
 extern ObPlacePolicy config_place_policy;
+/*! Place windows in the center of the free area */
+extern gboolean config_place_center;
 /*! Place windows on the active monitor (unless they are part of an application
   already on another monitor) */
 extern ObPlaceMonitor config_place_monitor;
diff --git a/openbox/place_overlap.c b/openbox/place_overlap.c
index cb9fd1e5..9eccb97e 100644
--- a/openbox/place_overlap.c
+++ b/openbox/place_overlap.c
@@ -1,7 +1,7 @@
 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
 
    overlap.c for the Openbox window manager
-   Copyright (c) 2011        Ian Zimmerman
+   Copyright (c) 2011, 2013 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
@@ -22,15 +22,33 @@
 
 #include <stdlib.h>
 
-static void make_grid(const Rect* client_rects, int n_client_rects,
-                      const Rect* monitor, int* x_edges, int* y_edges,
+static void make_grid(const Rect* client_rects,
+                      int n_client_rects,
+                      const Rect* monitor,
+                      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* monitor, const Size* req_size,
+                          const Rect* client_rects,
+                          int n_client_rects,
+                          const Rect* monitor,
+                          const Size* req_size,
                           Point* best_top_left);
 
+static int total_overlap(const Rect* client_rects,
+                         int n_client_rects,
+                         const Rect* proposed_rect);
+
+static void center_in_field(Point* grid_point,
+                            const Size* req_size,
+                            const Rect *monitor,
+                            const Rect* client_rects,
+                            int n_client_rects,
+                            const int* x_edges,
+                            const int* y_edges,
+                            int max_edges);
+
 /* Choose the placement on a grid with least overlap */
 
 void place_overlap_find_least_placement(const Rect* client_rects,
@@ -70,16 +88,28 @@ void place_overlap_find_least_placement(const Rect* client_rects,
         if (overlap == 0)
             break;
     }
+    if (config_place_center && overlap == 0) {
+        center_in_field(result,
+                        req_size,
+                        monitor,
+                        client_rects,
+                        n_client_rects,
+                        x_edges,
+                        y_edges,
+                        max_edges);
+    }
 }
 
-static int compare_ints(const void* a, const void* b)
+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)
+static void uniquify(int* edges,
+                     int n_edges)
 {
     int i = 0;
     int j = 0;
@@ -91,12 +121,15 @@ static void uniquify(int* edges, int n_edges)
             ++j;
     }
     /* fill the rest with nonsense */
-    for (; i < n_edges ; ++i)
+    for (; i < n_edges; ++i)
         edges[i] = G_MAXINT;
 }
 
-static void make_grid(const Rect* client_rects, int n_client_rects,
-                      const Rect* monitor, int* x_edges, int* y_edges,
+static void make_grid(const Rect* client_rects,
+                      int n_client_rects,
+                      const Rect* monitor,
+                      int* x_edges,
+                      int* y_edges,
                       int max_edges)
 {
     int i;
@@ -121,7 +154,8 @@ static void make_grid(const Rect* client_rects, int n_client_rects,
     uniquify(y_edges, n_edges);
 }
 
-static int total_overlap(const Rect* client_rects, int n_client_rects,
+static int total_overlap(const Rect* client_rects,
+                         int n_client_rects,
                          const Rect* proposed_rect)
 {
     int overlap = 0;
@@ -136,6 +170,129 @@ static int total_overlap(const Rect* client_rects, int n_client_rects,
     return overlap;
 }
 
+/* Unfortunately, the libc bsearch() function cannot be used to find the
+   position of a value that is not in the array, and glib doesn't
+   provide a binary search function at all.  So, tricky as it is, if we
+   want to avoid linear scan of the edge array, we have to roll our
+   own. */
+static int grid_position(int value,
+                         const int* edges,
+                         int max_edges)
+{
+    int low = 0;
+    int high = max_edges - 1;
+    int mid = low + (high - low) / 2;
+    while (low != mid) {
+        if (value < edges[mid])
+            high = mid;
+        else if (value > edges[mid])
+            low = mid;
+        else                    /* value == edges[mid] */
+            return mid;
+        mid = low + (high - low) / 2;
+    }
+    /* we get here when low == mid.  can have low == high or low == high - 1 */
+    return (value <= edges[low] ? low : high);
+}                         
+
+static void expand_width(Rect* r, int by)
+{
+    r->width += by;
+}
+
+static void expand_height(Rect* r, int by)
+{
+    r->height += by;
+}
+
+typedef void ((*expand_method)(Rect*, int));
+
+/* This structure packs most of the parametars for expand_field() in
+   order to save pushing the same parameters twice. */
+typedef struct _expand_info {
+    const Point* top_left;
+    int orig_width;
+    int orig_height;
+    const Rect* monitor;
+    const Rect* client_rects;
+    int n_client_rects;
+    int max_edges;
+} expand_info;
+
+static int expand_field(int orig_edge_index,
+                        const int* edges,
+                        expand_method exp,
+                        const expand_info* i)
+{
+    Rect field;
+    RECT_SET(field,
+             i->top_left->x,
+             i->top_left->y,
+             i->orig_width,
+             i->orig_height);
+    int edge_index = orig_edge_index;
+    while (edge_index < i->max_edges - 1) {
+        int next_edge_index = edge_index + 1;
+        (*exp)(&field, edges[next_edge_index] - edges[edge_index]);
+        int overlap = total_overlap(i->client_rects, i->n_client_rects, &field);
+        if (overlap != 0 || !RECT_CONTAINS_RECT(*(i->monitor), field))
+            break;
+        edge_index = next_edge_index;
+    }
+    return edge_index;
+}
+
+/* The algortihm used for centering a rectangle in a grid field: First
+   find the smallest rectangle of grid lines that enclose the given
+   rectangle.  By definition, there is no overlap with any of the other
+   windows if the given rectangle is centered within this minimal
+   rectangle.  Then, try extending the minimal rectangle in either
+   direction (x and y) by picking successively further grid lines for
+   the opposite edge.  If the minimal rectangle can be extended in *one*
+   direction (x or y) but *not* the other, extend it as far as possible.
+   Otherwise, just use the minimal one.  */
+
+static void center_in_field(Point* top_left,
+                            const Size* req_size,
+                            const Rect *monitor,
+                            const Rect* client_rects,
+                            int n_client_rects,
+                            const int* x_edges,
+                            const int* y_edges,
+                            int max_edges)
+{
+    /* find minimal rectangle */
+    int orig_right_edge_index =
+        grid_position(top_left->x + req_size->width, x_edges, max_edges);
+    int orig_bottom_edge_index =
+        grid_position(top_left->y + req_size->height, y_edges, max_edges);
+    expand_info i = {
+        .top_left = top_left,
+        .orig_width = x_edges[orig_right_edge_index] - top_left->x,
+        .orig_height = y_edges[orig_bottom_edge_index] - top_left->y,
+        .monitor = monitor,
+        .client_rects = client_rects,
+        .n_client_rects = n_client_rects,
+        .max_edges = max_edges};
+    /* try extending width */
+    int right_edge_index =
+        expand_field(orig_right_edge_index, x_edges, expand_width, &i);
+    /* try extending height */
+    int bottom_edge_index =
+        expand_field(orig_bottom_edge_index, y_edges, expand_height, &i);
+    int final_width = x_edges[orig_right_edge_index] - top_left->x;
+    int final_height = y_edges[orig_bottom_edge_index] - top_left->y;
+    if (right_edge_index == orig_right_edge_index
+        && bottom_edge_index != orig_bottom_edge_index)
+        final_height = y_edges[bottom_edge_index] - top_left->y;
+    else if (right_edge_index != orig_right_edge_index
+             && bottom_edge_index == orig_bottom_edge_index)
+        final_width = x_edges[right_edge_index] - top_left->x;
+    /* Now center the given rectangle within the field */
+    top_left->x += (final_width - req_size->width) / 2;
+    top_left->y += (final_height - req_size->height) / 2;
+}
+
 /* 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
@@ -145,8 +302,10 @@ static int total_overlap(const Rect* client_rects, int n_client_rects,
 #define NUM_DIRECTIONS 4
 
 static int best_direction(const Point* grid_point,
-                          const Rect* client_rects, int n_client_rects,
-                          const Rect* monitor, const Size* req_size,
+                          const Rect* client_rects,
+                          int n_client_rects,
+                          const Rect* monitor,
+                          const Size* req_size,
                           Point* best_top_left)
 {
     static const Size directions[NUM_DIRECTIONS] = {