Re: Extended Layout Summary

[Behdad Esfahbod <behdad behdad org>]

On Tue, 2007-11-20 at 20:09 -0500, Behdad Esfahbod wrote:
> On Tue, 2007-11-20 at 07:23 -0500, Mathias Hasselmann wrote:
> > 
> > When a container widget got more space allocated than requested, it
> > considers the difference between natural and requested size of its
> > children to distribute that additional space, in relation to the child's
> > difference between natural and minimum-size. Let's use an example for
> > demonstration:
> > 
> >     Assume we have a container with two children. Both children request
> >     a_min = b_min = 50 pixels as minimum size. The first child announces
> >     a_nat = 100 pixels, the second announces b_nat = 200 pixels as
> >     natural size.
> > 
> >     This gives a requested size of c_min = 100 pixels, and a natural
> >     size of 300 pixels (c_nat) for the container. Now the container gets
> >     allocated at a size of 200 pixels (c_cur). This are 100 pixels to
> >     distribute (c_gap).
> > 
> >     So the first child gets:
> > 
> >       a_cur = a_min + c_gap * (a_nat - a_min) / (c_nat - c_nat) 
> >             = 50    + 100   * 50              / 200
> >             = 75 pixels.
> > 
> >     The second child gets:
> > 
> >       b_cur = b_min + b_gap * (b_nat - b_min) / (c_nat - c_nat) 
> >             = 50    + 100   * 150             / 200
> >             = 125 pixels.
> 
> Something that Ryan brought up, and I was hoping that Havoc answer is
> that the above algorithm is not optimal, you can easily do better.
> Quoting Havoc's words: "bring smaller items up to natural size first".
> Read his entire "TEXT LAYOUT THAT WORKS PROPERLY?" post here:
> 
>   http://log.ometer.com/2006-10.html

Without checking HippoCanvas's implementation, I think this is how it
should work:

  Say there are n child widgets c^0 .. c^{n-1}, let

	c^i_diff = c^i_nat - c^i_min

  We want to assign c^i_gap such that the sum of c^i_gap's is equal to
c_gap, the container's extra space to distribute.  We only consider the
case that there's not enough space for all children to take their
natural size.  The goals we want to achieve:

    a) Maximize number of children taking their natural size.

    b) The allocated size of children should be a continuous function of
c_gap.  That is, increasing the container size by one pixel should never
make drastic changes in the distribution.


Goal a rules your current algorithm out as yours essentially keeps all
children off their natural size until there's enough room for all.

Goal b means that you cannot start from the least child gap, fulfill
them and then distribute the remaining gap between the rest of the
children, because when enough gap becomes available for you to
accommodate one more natural child, the allocations jump
noncontinuously.

This algorithm achieves both goals:  Distribute gap to children equally
(not linearly) and not more than they need.  That is:

  - Sort children with decreasing c^i_diff.  Use child order in the
container to break ties.

  - Allocate like this:

    for (i = n - 1; i >= 0; i--)
      {
        double share = (double) c_gap / (i + 1);

        if (share >= c^i_diff)
          c^i_gap = c^i_diff;
        else
          c^i_gap = ceil (share);

        c_gap -= c^i_gap;
      }



Something completely unrelated: now that you are adding extended layout
features, should we switch to doubles or some fixed subpixel format for
size negotiation?  The idea being, making it easier to make Gtk+
dpi-independent in the future.

-- 
behdad
http://behdad.org/

"Those who would give up Essential Liberty to purchase a little
 Temporary Safety, deserve neither Liberty nor Safety."
        -- Benjamin Franklin, 1759