Re: GtkSpreadTable ('spread-table' branch)
- From: David A Benjamin <davidben MIT EDU>
- To: Tristan Van Berkom <tristanvb openismus com>
- Cc: gtk-devel-list gnome org
- Subject: Re: GtkSpreadTable ('spread-table' branch)
- Date: Thu, 7 Oct 2010 00:42:24 -0400 (EDT)
On Thu, 7 Oct 2010, Tristan Van Berkom wrote:
Some technical caveats:
- When there are over ~12 columns the whole thing slows down
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. :-)
] [Thread Prev