Re: GtkSpreadTable ('spread-table' branch)

[Tristan Van Berkom <tristanvb openismus com>]

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.

> 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