Re: GtkSpreadTable ('spread-table' branch)

[David A Benjamin <davidben MIT EDU>]

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.

In fact, I think this should work for variable-width columns, although you 
won't be able to cache the heights.

(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