Re: GtkSpreadTable ('spread-table' branch)

[Tristan Van Berkom <tristanvb openismus com>]

On Fri, 2010-10-08 at 20:56 +0900, Tristan Van Berkom wrote:
> On Fri, 2010-10-08 at 16:51 +0900, Tristan Van Berkom wrote:
> > 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...
> > 
> 
> Well I'm really tempted to "just go with this" because:
> 
>   a.) In the case that most columns are equal height, more widgets
>       always appear to the left than the right where possible, which
>       seems to look good and desirable.
> 
>   b.) The case where trailing empty columns exist is only possible
>       with lots of columns and not enough widgets (columns dont
>       break down enough to spread them all evenly).
> 
> For case b.) I think the best option is to simply eat out widgets
> from the last populated column and put exactly one in each trailing
> empty column, in any case its really corner case and again as
> I mentioned in point a.) ... it seems nice to see more widgets to
> the left than to the right.
> 
> So essentially I think an allocation that ended up like this
> (where the numbers are how many widgets landed in a column):
> 
> +-------------------------------------------+
> | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 0 | 0 |
> +-------------------------------------------+
> 
> We would simply translate that to:
> 
> +-------------------------------------------+
> | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 |
> +-------------------------------------------+

For what its worth I finally applied this algorithm
to the 'spread-table' branch.

In the case that the trailing columns get no
widgets, one widget is placed in each of the trailing
columns (again, only happens with lots of columns
and not enough widgets... and seems to look good
this way IMO)

Cheers,
      -Tristan

> 
> Instead of shooting for something more "spread out"
> (i.e. this would cost more processing, be more complex
> and not even really look more "equalized" in height):
> 
> +-------------------------------------------+
> | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 |
> +-------------------------------------------+
> 
> Thoughts ?
> 
> > 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
> > 
> > _______________________________________________
> > gtk-devel-list mailing list
> > gtk-devel-list gnome org
> > http://mail.gnome.org/mailman/listinfo/gtk-devel-list
> 
> 
> _______________________________________________
> gtk-devel-list mailing list
> gtk-devel-list gnome org
> http://mail.gnome.org/mailman/listinfo/gtk-devel-list