Re: algorithmic question

On Sun, 2004-03-28 at 23:21 -0800, Adam Megacz wrote:
> Brainteaser for yall.  Earlier, I sized grid columns/rows by setting
> each column to its minwidth and then handing out the slack in
> proportion to the column's weight.  This isn't what most people
> "expect", though.

Expectation usually is of the end result, not of the method to achieve
said result.  In this case the result is as expected (although I've
encountered a few bugs).

> I'm trying to figure out how to do it in O(n) time (I figured out O(n
> log n)) -- not because I care so much about the difference between
> those two, but because O(nlgn) solutions are rarely incremental.  In
> other words, I want something where if very little has changed (like,
> for example, only the goal width), we can use the old solution to get
> the new one very quickly.

Having been working on Box.java a bit, one concern here would be how to
store the old solution such that we don't use copious amounts of memory
for each box.  Currently there's a set of static LENGTH [65535] arrays.
Wouldn't that multiplied by several thousand be quite bloated?

> Here's the formal statement of the problem:
>   
>   You have a goal width for the sum of the columns.  You must find 'k'
>   such that when each column is set to:
>   
>      min(maxwidth, max(minwidth, k*weight))
>   
>   the sum of all the columns equals the goal weight.  Basically each
>   column is k*weight, and then you crop it to that column's max/min
>   size.

That sounds nice and elegant but sadly it's not that simple.

What happens when a box, low down in the ascendency chain, resizes such
that it affects the width of the column it is in?  How do you notify the
parent that one of it's column widths has changed?  Or are you proposing
two functions in Box.java, quick_resize() and full_resize(), for this?

> Winner gets a cookie.

What flavour/type?
-- 
- Charlie

Charles Goodwin <[email protected]>
Online @ http://www.charlietech.com