Re: GtkSpreadTable ('spread-table' branch)

[Tristan Van Berkom <tristanvb openismus com>]

On Thu, 2010-10-07 at 14:30 +0900, Tristan Van Berkom wrote:
> On Thu, 2010-10-07 at 00:42 -0400, David A Benjamin wrote:
> > On Thu, 7 Oct 2010, Tristan Van Berkom wrote:
> > 
> > > Some technical caveats:
> > >   - When there are over ~12 columns the whole thing slows down
> > >     significantly.
> > >
> > >     The reason for this being, the algorithm in place starts
> > >     by lining up all the widgets in the first column and
> > >     then evening them out column by column... by the time
> > >     we hit the 3rd column; columns 1 & 2 need to be recalculated
> > >     for every widget we pull into the 3rd column, and so on
> > >     as the columns grow.
> > >
> > >     By the time we hit 12 columns things are getting exponentially
> > >     heavier to calculate (I've tried simpler algorithms that were
> > >     much further from perfect results than this one though).
> > >
> > 
> > So, am I understanding your setup and code correctly? You have a number of 
> > columns of equal width that you wish to arrange some widgets into. The 
> > first few widgets get laid out vertically into the first column, the next 
> > into the next column, etc. And your goal is to minimize the height of the 
> > tallest column, computed as the sum of the heights of each widget (plus 
> > some padding between them). Is this correct?
> > 
> > In that case, just binary search for the optimum height; bounds are the 
> > average and the total of the boxes. For a given candidate height, a greedy 
> > algorithm is sufficient to determine whether or not the height is viable. 
> > Just go through column-by-column and stuff widgets into the next column 
> > until you can't fit the next widget and move on to the next column. If you 
> > manage to fit them all, you have a valid height and valid assignment; try 
> > going smaller if you can. If you go through all the columns with widgets 
> > to spare, your height was too big; go larger. Running time is 
> > O(num_widgets * log(total_height)) with a very nice constant.
> 
> I see, a kind of bisection looking for the best height; just go 
> average +  (total - average) / 2 and lower by halves, increase 
> by halves until the best height is reached.
> 
> I was a little weary to try this kind of approach as the whole 
> thing needs layouting for every tested height, but maybe as you 
> say with a "greedy" algorithm the results may be perfect.
> 
> One exception the current writeup does is to ignore the height of
> a widget that is tall enough to span the entire column height
> (thus a smaller target height is chosen to allow the remaining
> widgets to spread more evenly)... but I think that can still be
> accounted for with your approach.
> 
> I'll definitely give this a try, thanks a lot.

Hi,
    I gave this another shot using a bisection/binary search of 
plausible heights as you suggested.

The patch I attached here does indeed speed things up when it
comes to allocating for lots of columns.

However I did not apply the patch to the branch right away as 
there is one problem I noticed off the bat.

Since this new algorithm allocates as many children as
possible in every column consecutively for a given height,
there are some cases where trailing columns are allocated
no widgets.

You can observe this by,
  - Applying the patch to spread-table branch
  - Setting 10 columns in the ./tests/testspreadtable test case
  - Stretch out the test window and notice when the hscrollbar goes away
    there are trailing empty columns... these columns get filled again
    when stretched further to larger widths.

Other than that problem the binary search works pretty much the
same as the other algorithm currently in the branch, and does
speed things up when it comes to setting 20+ columns.

Possibly this can still be done with the optimization
and some short post-processing in the cases of empty
columns... will have to dig deeper...

Cheers,
       -Tristan

> 
> > In fact, I think this should work for variable-width columns, although you 
> > won't be able to cache the heights.
> 
> Eh, the problem here is that if you chose a target height and go
> allocating, you cant very well try lining up widgets in a column
> one by one... as:
>   a.) the width of the column should be determined by the 
>       minimum/natural requests of the widgets in each column
>       (natural distribution of column widths inside the container's
>       allocation).
>   b.) the height of the widgets in each column will then be
>       determined by the decided/allocated width of the columns.
> 
> Another thing to consider is that the height-for-width cache
> is reasonably small (3 requests are cached between resizes);
> it's generally expensive to test every widget in the container's
> height-for-width if you plan on iterating over lots of possible
> widths.
> 
> Am I missing something ? (I think its just a genuinely difficult
> problem).
> 
> > (You can also do a DP, but I've only been able to get that down to 
> > O(num_widgets * num_columns * log(num_widgets)) thus far.)
> > 
> > I can give the implementation a go sometime this weekend if no one else 
> > beats me to it. :-)
> > 
> > David
> 
> 
> 
> _______________________________________________
> gtk-devel-list mailing list
> gtk-devel-list gnome org
> http://mail.gnome.org/mailman/listinfo/gtk-devel-list

diff --git a/gtk/gtkspreadtable.c b/gtk/gtkspreadtable.c
index 71dd00d..e44e482 100644
--- a/gtk/gtkspreadtable.c
+++ b/gtk/gtkspreadtable.c
@@ -62,17 +62,6 @@ struct _GtkSpreadTablePrivate {
   guint16        vertical_spacing;
 };
 
-/* Our column equalizing algorithm splits up
- * children into 'lines' segments and maintains
- * the integrity of the array of line segments while
- * itterating over columns (or 'segments').
- */
-typedef struct {
-  GList *children; /* List of children in this segment */
-  gint   size;     /* Overall size of segment (or 'height of column') */
-} LineSegment;
-
-
 /* GObjectClass */
 static void gtk_spread_table_get_property         (GObject             *object,
 						   guint                prop_id,
@@ -424,182 +413,57 @@ get_segment_length (GtkSpreadTable *table,
   return size;
 }
 
-/* Moves a child from the previous line segment (column) into a given column
- * and keeps the LineSegments array updated */
 static gboolean
-child_forward (GtkSpreadTable *table, 
-	       LineSegment    *line_segments, 
-	       gint            line_thickness,
-	       gint            line_index)
-{
-  GtkSpreadTablePrivate  *priv = table->priv;
-  GtkWidget              *child;
-  GList                  *link;
-  gint                    child_size;
-
-  g_assert (line_index > 0);
- 
-  /* Get the last child from the previous line */
-  link = g_list_last (line_segments[line_index - 1].children);
-
-  if (!link)
-    return FALSE;
-
-  child = link->data;
-  get_widget_size (child, priv->orientation, line_thickness, NULL, &child_size);
-
-  /* Adjust target column size */
-  if (line_segments[line_index].children)
-    line_segments[line_index].size += ITEM_SPACING (table);
-  line_segments[line_index].size += child_size;
-
-  /* Remove it from the previous line */
-  line_segments[line_index - 1].children = 
-    g_list_remove_link (line_segments[line_index - 1].children, link);
-
-  /* Prepend child to this line */
-  line_segments[line_index].children = 
-    g_list_concat (link, line_segments[line_index].children);
-
-  /* Adjust previous column size */
-  if (line_segments[line_index - 1].children)
-    line_segments[line_index - 1].size -= ITEM_SPACING (table);
-  line_segments[line_index - 1].size -= child_size;
-  
-  return TRUE;
-}
-
-/* Gets the largest size of line segments between two inclusive indexes*/
-static gint 
-count_size (LineSegment  *line_segments,
-	    gint          index_from,
-	    gint          index_to)
-{
-  gint total_size = 0;
-  gint i;
-
-  g_assert (index_from < index_to);
-
-  for (i = index_from; i < index_to + 1; i++)
-    {
-      /* Ignore the size of columns which have only one child,
-       * if they are huge widgets then we want to ignore them and
-       * even out the remaining columns, if they are small then we
-       * still want to put at least one widget on every line.
-       */
-      if (line_segments[i].children && 
-	  line_segments[i].children->next)
-	total_size = MAX (total_size, line_segments[i].size);
-    }
-
-  return total_size;
-}
-
-/* Creates a copy of the LineSegments array */
-static LineSegment *
-copy_line_segments (GtkSpreadTable *table,
-		    LineSegment    *segments)
+children_fit_segment_size (GtkSpreadTable *table, 
+			   GList          *children,
+			   gint            line_thickness,
+			   gint            size,
+			   gint           *segments,
+			   gint           *largest_segment_size)
 {
-  GtkSpreadTablePrivate *priv = table->priv;
-  LineSegment           *copy = g_new0 (LineSegment, priv->lines);
-  gint                   i;
-
-  for (i = 0; i < priv->lines; i++)
-    {
-      copy[i].children = g_list_copy (segments[i].children);
-      copy[i].size     = segments[i].size;
-    }
-
-  return copy;
-}
-
-/* Frees the LineSegments array */
-static void
-free_line_segments (GtkSpreadTable *table, 
-		    LineSegment    *segments)
-{
-  GtkSpreadTablePrivate *priv = table->priv;
-  gint                 i;
-
-  for (i = 0; i < priv->lines; i++)
-    g_list_free (segments[i].children);
+  GtkSpreadTablePrivate  *priv;
+  GList                  *l;
+  gint                    segment_size, i;
+  gint                    spacing;
 
-  g_free (segments);
-}
+  priv    = table->priv;
+  spacing = ITEM_SPACING (table);
 
-static void
-merge_line_segments (LineSegment  *dest,
-		     LineSegment  *src,
-		     gint          index)
-{
-  gint i;
+  /* reset segments */
+  memset (segments, 0x0, sizeof (gint) * priv->lines);
 
-  for (i = 0; i < index + 1; i++)
+  for (l = children, i = 0; l && i < priv->lines; i++)
     {
-      g_list_free (dest[i].children);
-      dest[i].children = g_list_copy (src[i].children);
-      dest[i].size     = src[i].size;
-    }
-}
+      segment_size = 0;
 
-/* This algorithm equalizes 2 columns but recurses into previously
- * equalized columns when widgets are moved over from previous columns */
-static void
-equalize_line_segments (GtkSpreadTable *table, 
-			LineSegment    *line_segments,
-			gint            line_thickness,
-			gint            line_index)
-{
-  gint         guess_size, best_size;
-  gboolean     child_moved;
-  LineSegment *segments;
+      /* While we still have children to place and
+       * there is space left on this line */
+      while (l && segment_size < size)
+	{
+	  GtkWidget *child = l->data;
+	  gint       widget_size;
 
-  g_assert (line_index > 0);
+	  get_widget_size (child, priv->orientation, line_thickness, NULL, &widget_size);
 
-  /* Use a local copy to check for a best size of this index and all
-   * previous indexes recursively (this allows us to 'try' our array
-   * and compare it before updating the return value)  */
-  segments = copy_line_segments (table, line_segments);
+	  if (segment_size != 0)
+	    segment_size += spacing;
 
-  /* Get the total best size for all preceeding columns */
-  guess_size = best_size = count_size (segments, 0, line_index);
+	  segment_size += widget_size;
 
-  /* Loop shifting one widget from the previous column over at a time
-   * until the new size is worse than the last size (pull as many widgets
-   * across into the new segment without getting a larger size)
-   */
-  while (guess_size <= best_size)
-    {
-      child_moved = child_forward (table, segments, line_thickness, line_index);
-
-      /* No more children to pull into this column, break out
-       * (never decide to leave a preceeding column empty, stick
-       * with the last result instead)
-       */
-      if (!child_moved)
-	break;
-
-      /* Now that we've pulled a widget over, recurse backwards through the list and see
-       * if we need to shift any widgets in previous lines (columns) 
-       */
-      if (line_index > 1)
-	equalize_line_segments (table, segments, line_thickness, line_index - 1);
-      
-      /* Get the total new best size for columns iterated over so far */
-      guess_size = count_size (segments, 0, line_index);
-
-      /* keep pulling widgets along even if the whole thing stays 
-       * the same size (untill the new guess is actually worse) */
-      if (guess_size <= best_size)
-	{
- 	  best_size = guess_size;
+	  /* Consume this widget in this line segment if it fits the size
+	   * or it is alone taller than the whole tested size */
+	  if (segment_size <= size || segments[i] == 0)
+	    {
+	      *largest_segment_size = MAX (*largest_segment_size, segment_size);
+	      segments[i]++;
 
-	  /* This one's a keeper, override our portion of 'line_segments' */
-	  merge_line_segments (line_segments, segments, line_index);
+	      l = l->next;
+	    }
 	}
     }
 
-  free_line_segments (table, segments);
+  /* If we placed all the widgets in the target size, the size fits. */
+  return (l == NULL);
 }
 
 /* All purpose algorithm entry point, this function takes an allocated size
@@ -616,44 +480,62 @@ segment_lines_for_size (GtkSpreadTable *table,
 			gint            for_size,
 			gint          **segments)
 {
-  GtkSpreadTablePrivate  *priv = table->priv;
-  LineSegment            *line_segments;
+  GtkSpreadTablePrivate  *priv;
+  GList                  *children;
   gint                    line_thickness;
-  gint                    max_segment_length = 0;
-  gint                   *segment_counts = NULL;
-  gint                    i;
-
-  line_segments    = g_new0 (LineSegment, priv->lines);
-  if (segments)
-    segment_counts = g_new0 (gint, priv->lines);
+  gint                   *segment_counts = NULL, *test_counts;
+  gint                    upper, lower, segment_size, largest_size = 0;
 
+  priv           = table->priv;
   line_thickness = get_line_thickness (table, for_size);
 
-  /* Start by lining up all widgets in the first segment */
-  line_segments[0].children = get_visible_children (table);
-  line_segments[0].size     = get_segment_length (table, line_thickness, line_segments[0].children);
+  segment_counts = g_new0 (gint, priv->lines);
+  test_counts    = g_new0 (gint, priv->lines);
+
+  /* Start by getting the child list/total size/average size */
+  children = get_visible_children (table);
+  upper    = get_segment_length (table, line_thickness, children);
+  lower    = upper / priv->lines;
 
-  /* For every segment (column), equalize it and pull widgets from previous segments 
-   * until we've pulled widgets into all columns */
-  for (i = 1; i < priv->lines; i++)
-    equalize_line_segments (table, line_segments, line_thickness, i);
+  /* Start with half way between the average and total height */
+  segment_size = lower + (upper - lower) / 2;
 
-  /* Free the line segments and tally up the 'segment_counts' for size_allocate */
-  for (i = 0; i < priv->lines; i++)
+  while (segment_size > lower && segment_size < upper)
     {
-      max_segment_length = MAX (max_segment_length, line_segments[i].size);
+      gint test_largest = 0;
 
-      if (segment_counts)
-	segment_counts[i] = g_list_length (line_segments[i].children);
+      if (children_fit_segment_size (table, children, line_thickness,
+				     segment_size, test_counts, &test_largest))
+	{
+	  upper         = segment_size;
+	  segment_size -= (segment_size - lower) / 2;
 
-      g_list_free (line_segments[i].children);
+	  /* Save the last arrangement that 'fit' */
+	  largest_size  = test_largest;
+	  memcpy (segment_counts, test_counts, sizeof (gint) * priv->lines);
+	}
+      else
+	{
+	  lower         = segment_size;
+	  segment_size += (upper - segment_size) / 2;
+	}
     }
-  g_free (line_segments);
+
+  {
+    gint i;
+
+    for (i = 0; i < priv->lines; i++)
+      g_print ("column %d has %d widgets\n", i, segment_counts[i]);
+  }
 
   if (segments)
     *segments = segment_counts;
+  else
+    g_free (segment_counts);
+
+  g_free (test_counts);
 
-  return max_segment_length;
+  return largest_size;
 }