[gtk+/native-layout-incubator-2] Refactored the allocation loop from GtkBox to a new function gtk_distribute_natural_allocation().

[Tristan Van Berkom <tvb src gnome org>]

commit 31dad0cfe689605e343b9dc536b4e124f206092b
Author: Tristan Van Berkom <tristan van berkom gmail com>
Date:   Wed Jun 30 11:17:18 2010 -0400

    Refactored the allocation loop from GtkBox to a new function gtk_distribute_natural_allocation().

 gtk/gtkbox.c         |  149 ++++---------------------------------------------
 gtk/gtksizerequest.c |  120 +++++++++++++++++++++++++++++++++++++---
 2 files changed, 124 insertions(+), 145 deletions(-)
---
diff --git a/gtk/gtkbox.c b/gtk/gtkbox.c
index 82289f5..c3db663 100644
--- a/gtk/gtkbox.c
+++ b/gtk/gtkbox.c
@@ -110,21 +110,6 @@ struct _GtkBoxPrivate
 
 #define GTK_BOX_GET_PRIVATE(obj) (G_TYPE_INSTANCE_GET_PRIVATE ((obj), GTK_TYPE_BOX, GtkBoxPrivate))
 
-typedef struct _GtkBoxDesiredSizes GtkBoxDesiredSizes;
-typedef struct _GtkBoxSpreading    GtkBoxSpreading;
-
-struct _GtkBoxDesiredSizes
-{
-  gint minimum_size;
-  gint natural_size;
-};
-
-struct _GtkBoxSpreading
-{
-  GtkBoxChild *child;
-  gint index;
-};
-
 static void gtk_box_size_allocate         (GtkWidget              *widget,
                                            GtkAllocation          *allocation);
 
@@ -375,30 +360,6 @@ count_expand_children (GtkBox *box, gint *visible_children, gint *expand_childre
     }
 }
 
-static gint
-gtk_box_compare_gap (gconstpointer p1,
-                      gconstpointer p2,
-                      gpointer      data)
-{
-  GtkBoxDesiredSizes *sizes = data;
-  const GtkBoxSpreading *c1 = p1;
-  const GtkBoxSpreading *c2 = p2;
-
-  const gint d1 = MAX (sizes[c1->index].natural_size -
-                       sizes[c1->index].minimum_size,
-                       0);
-  const gint d2 = MAX (sizes[c2->index].natural_size -
-                       sizes[c2->index].minimum_size,
-                       0);
-
-  gint delta = (d2 - d1);
-
-  if (0 == delta)
-    delta = (c2->index - c1->index);
-
-  return delta;
-}
-
 static void
 gtk_box_size_allocate (GtkWidget     *widget,
                        GtkAllocation *allocation)
@@ -419,8 +380,7 @@ gtk_box_size_allocate (GtkWidget     *widget,
       gint border_width = GTK_CONTAINER (box)->border_width;
       GtkTextDirection direction = gtk_widget_get_direction (widget);
       GtkAllocation child_allocation;
-      GtkBoxSpreading *spreading = g_newa (GtkBoxSpreading, nvis_children);
-      GtkBoxDesiredSizes *sizes = g_newa (GtkBoxDesiredSizes, nvis_children);
+      GtkRequestedSize *sizes = g_newa (GtkRequestedSize, nvis_children);
 
       GtkPackType packing;
 
@@ -476,9 +436,8 @@ gtk_box_size_allocate (GtkWidget     *widget,
 	      
 	      size -= sizes[i].minimum_size;
 	      size -= child->padding * 2;
-	      
-	      spreading[i].index = i;
-	      spreading[i].child = child;
+
+	      sizes[i].data = child;
 	      
 	      i += 1;
 	    }
@@ -498,47 +457,8 @@ gtk_box_size_allocate (GtkWidget     *widget,
         }
       else
 	{
-
-          /* Distribute the container's extra space c_gap. We want to assign
-           * this space such that the sum of extra space assigned to children
-           * (c^i_gap) is equal to c_cap. The case that there's not enough
-           * space for all children to take their natural size needs some
-           * attention. The goals we want to achieve are:
-           *
-           *   a) Maximize number of children taking their natural size.
-           *   b) The allocated size of children should be a continuous
-           *   function of c_gap.  That is, increasing the container size by
-           *   one pixel should never make drastic changes in the distribution.
-           *   c) If child i takes its natural size and child j doesn't,
-           *   child j should have received at least as much gap as child i.
-           *
-           * The following code distributes the additional space by following
-           * this rules.
-           */
-
-          /* Sort descending by gap and position. */
-          g_qsort_with_data (spreading,
-                             nvis_children, sizeof (GtkBoxSpreading),
-                             gtk_box_compare_gap, sizes);
-
-          /* Distribute available space.
-           * This master piece of a loop was conceived by Behdad Esfahbod.
-           */
-          for (i = nvis_children - 1; size > 0 && i >= 0; --i)
-            {
-              /* Divide remaining space by number of remaining children.
-               * Sort order and reducing remaining space by assigned space
-               * ensures that space is distributed equally.
-               */
-              gint glue = (size + i) / (i + 1);
-              gint gap = sizes[spreading[i].index].natural_size
-                       - sizes[spreading[i].index].minimum_size;
-
-              extra = MIN (glue, gap);
-              sizes[spreading[i].index].minimum_size += extra;
-
-              size -= extra;
-            }
+	  /* Bring children up to size first */
+	  size = gtk_distribute_natural_allocation (size, nvis_children, sizes);
 
           /* Calculate space which hasn't distributed yet,
            * and is available for expanding children.
@@ -975,12 +895,10 @@ gtk_box_compute_size_for_opposing_orientation (GtkBox *box,
 
   if (nvis_children > 0)
     {
-      GtkBoxSpreading     *spreading    = g_newa (GtkBoxSpreading, nvis_children);
-      GtkBoxDesiredSizes  *sizes        = g_newa (GtkBoxDesiredSizes, nvis_children);
-      GtkPackType          packing;
-      gint                 size;
-      gint                 extra, i;
-      gint                 child_size, child_minimum, child_natural;
+      GtkRequestedSize *sizes = g_newa (GtkRequestedSize, nvis_children);
+      GtkPackType       packing;
+      gint              size, extra, i;
+      gint              child_size, child_minimum, child_natural;
 
       size = avail_size - border_width * 2 - (nvis_children - 1) * box->spacing;
 
@@ -1016,9 +934,8 @@ gtk_box_compute_size_for_opposing_orientation (GtkBox *box,
 
 	      size -= sizes[i].minimum_size;
 	      size -= child->padding * 2;
-	      
-	      spreading[i].index = i;
-	      spreading[i].child = child;
+
+	      sizes[i].data = child;
 	      
 	      i += 1;
 	    }
@@ -1034,48 +951,8 @@ gtk_box_compute_size_for_opposing_orientation (GtkBox *box,
         }
       else
 	{
-
-          /* Distribute the container's extra space c_gap. We want to assign
-           * this space such that the sum of extra space assigned to children
-           * (c^i_gap) is equal to c_cap. The case that there's not enough
-           * space for all children to take their natural size needs some
-           * attention. The goals we want to achieve are:
-           *
-           *   a) Maximize number of children taking their natural size.
-           *   b) The allocated size of children should be a continuous
-           *   function of c_gap.  That is, increasing the container size by
-           *   one pixel should never make drastic changes in the distribution.
-           *   c) If child i takes its natural size and child j doesn't,
-           *   child j should have received at least as much gap as child i.
-           *
-           * The following code distributes the additional space by following
-           * this rules.
-           */
-
-          /* Sort descending by gap and position. */
-
-          g_qsort_with_data (spreading,
-                             nvis_children, sizeof (GtkBoxSpreading),
-                             gtk_box_compare_gap, sizes);
-
-          /* Distribute available space.
-           * This master piece of a loop was conceived by Behdad Esfahbod.
-           */
-          for (i = nvis_children - 1; size > 0 && i >= 0; --i)
-            {
-              /* Divide remaining space by number of remaining children.
-               * Sort order and reducing remaining space by assigned space
-               * ensures that space is distributed equally.
-               */
-              gint glue = (size + i) / (i + 1);
-              gint gap = sizes[spreading[i].index].natural_size
-                       - sizes[spreading[i].index].minimum_size;
-
-              extra = MIN (glue, gap);
-              sizes[spreading[i].index].minimum_size += extra;
-
-              size -= extra;
-            }
+	  /* Bring children up to size first */
+	  size = gtk_distribute_natural_allocation (size, nvis_children, sizes);
 
           /* Calculate space which hasn't distributed yet,
            * and is available for expanding children.
diff --git a/gtk/gtksizerequest.c b/gtk/gtksizerequest.c
index 5114a72..2556070 100644
--- a/gtk/gtksizerequest.c
+++ b/gtk/gtksizerequest.c
@@ -54,7 +54,7 @@
  * For instance when queried in the normal height-for-width mode:
  * First the default minimum and natural width for each widget
  * in the interface will computed and collectively returned to
- * the toplevel by way of gtk_size_request_get_desired_width().
+ * the toplevel by way of gtk_size_request_get_width().
  * Next, the toplevel will use the minimum width to query for the
  * minimum height contextual to that width using
  * gtk_size_request_get_height_for_width(), which will also be a
@@ -119,6 +119,11 @@ typedef struct {
   guint8      cached_height_age;
 } SizeRequestCache;
 
+typedef struct {
+  gpointer data;
+  gint     index;
+} AllocationSpreading;
+
 static GQuark quark_cache = 0;
 
 
@@ -352,7 +357,7 @@ compute_size_for_orientation (GtkSizeRequest    *request,
 }
 
 /**
- * gtk_size_request_is_height_for_width:
+ * gtk_size_request_get_request_mode:
  * @widget: a #GtkSizeRequest instance
  *
  * Gets whether the widget prefers a height-for-width layout
@@ -363,8 +368,7 @@ compute_size_for_orientation (GtkSizeRequest    *request,
  * context of their children or in context of their allocation
  * capabilities.</para></note>
  *
- * Returns: %TRUE if the widget prefers height-for-width, %FALSE if
- * the widget should be treated with a width-for-height preference.
+ * Returns: The #GtkSizeRequestMode preferred by @widget.
  *
  * Since: 3.0
  */
@@ -398,8 +402,8 @@ gtk_size_request_get_request_mode (GtkSizeRequest *widget)
  */
 void
 gtk_size_request_get_width (GtkSizeRequest *widget,
-                                       gint              *minimum_width,
-                                       gint              *natural_width)
+			    gint           *minimum_width,
+			    gint           *natural_width)
 {
   compute_size_for_orientation (widget, GTK_SIZE_GROUP_HORIZONTAL,
                                 -1, minimum_width, natural_width);
@@ -436,7 +440,7 @@ gtk_size_request_get_height (GtkSizeRequest *widget,
  * @minimum_width: (out) (allow-none): location for storing the minimum width, or %NULL
  * @natural_width: (out) (allow-none): location for storing the natural width, or %NULL
  *
- * Retrieves a widget's desired width if it would be given
+ * Retrieves a widget's minimum and natural width if it would be given
  * the specified @height.
  *
  * Since: 3.0
@@ -458,7 +462,7 @@ gtk_size_request_get_width_for_height (GtkSizeRequest *widget,
  * @minimum_height: (out) (allow-none): location for storing the minimum height, or %NULL
  * @natural_height: (out) (allow-none): location for storing the natural height, or %NULL
  *
- * Retrieves a widget's desired height if it would be given
+ * Retrieves a widget's minimum and natural height if it would be given
  * the specified @width.
  *
  * Since: 3.0
@@ -515,7 +519,7 @@ gtk_size_request_get_size (GtkSizeRequest    *widget,
 						 NULL, &natural_size->height);
 	}
     }
-  else
+  else /* GTK_SIZE_REQUEST_WIDTH_FOR_HEIGHT */
     {
       gtk_size_request_get_height (widget, &min_height, &nat_height);
 
@@ -536,6 +540,104 @@ gtk_size_request_get_size (GtkSizeRequest    *widget,
 }
 
 
+static gint
+compare_gap (gconstpointer p1,
+	     gconstpointer p2,
+	     gpointer      data)
+{
+  GtkRequestedSize *sizes = data;
+  const guint *c1 = p1;
+  const guint *c2 = p2;
+
+  const gint d1 = MAX (sizes[*c1].natural_size -
+                       sizes[*c1].minimum_size,
+                       0);
+  const gint d2 = MAX (sizes[*c2].natural_size -
+                       sizes[*c2].minimum_size,
+                       0);
+
+  gint delta = (d2 - d1);
+
+  if (0 == delta)
+    delta = (*c2 - *c1);
+
+  return delta;
+}
+
+/**
+ * gtk_distribute_natural_allocation: 
+ * @extra_space: Extra space to redistribute among children after subtracting
+ *               minimum sizes and any child padding from the overall allocation
+ * @n_requested_sizes: Number of requests to fit into the allocation
+ * @sizes: An array of structs with a client pointer and a minimum/natural size
+ *         in the orientation of the allocation.
+ *
+ * Distributes @extra_space to child @sizes by bringing up smaller
+ * children up to natural size first.
+ *
+ * The remaining space will be added to the @minimum_size member of the
+ * GtkRequestedSize struct. If all sizes reach their natural size then
+ * the remaining space is returned.
+ *
+ * Returns: The remainder of @extra_space after redistributing space
+ * to @sizes.
+ */
+gint 
+gtk_distribute_natural_allocation (gint              extra_space,
+				   guint             n_requested_sizes,
+				   GtkRequestedSize *sizes)
+{
+  guint *spreading = g_newa (guint, n_requested_sizes);
+  gint   i;
+
+  for (i = 0; i < n_requested_sizes; i++)
+    spreading[i] = i;
+
+  /* Distribute the container's extra space c_gap. We want to assign
+   * this space such that the sum of extra space assigned to children
+   * (c^i_gap) is equal to c_cap. The case that there's not enough
+   * space for all children to take their natural size needs some
+   * attention. The goals we want to achieve are:
+   *
+   *   a) Maximize number of children taking their natural size.
+   *   b) The allocated size of children should be a continuous
+   *   function of c_gap.  That is, increasing the container size by
+   *   one pixel should never make drastic changes in the distribution.
+   *   c) If child i takes its natural size and child j doesn't,
+   *   child j should have received at least as much gap as child i.
+   *
+   * The following code distributes the additional space by following
+   * these rules.
+   */
+  
+  /* Sort descending by gap and position. */
+  g_qsort_with_data (spreading,
+		     n_requested_sizes, sizeof (guint),
+		     compare_gap, sizes);
+  
+  /* Distribute available space.
+   * This master piece of a loop was conceived by Behdad Esfahbod.
+   */
+  for (i = n_requested_sizes - 1; extra_space > 0 && i >= 0; --i)
+    {
+      /* Divide remaining space by number of remaining children.
+       * Sort order and reducing remaining space by assigned space
+       * ensures that space is distributed equally.
+       */
+      gint glue = (extra_space + i) / (i + 1);
+      gint gap = sizes[(spreading[i])].natural_size
+	- sizes[(spreading[i])].minimum_size;
+      
+      gint extra = MIN (glue, gap);
+      
+      sizes[spreading[i]].minimum_size += extra;
+      
+      extra_space -= extra;
+    }
+
+  return extra_space;
+}
+
 
 #define __GTK_SIZE_REQUEST_C__
 #include "gtkaliasdef.c"