1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
# Auto-Sizing Columns
Here's a curious problem I've come across: There are N columns in a table of width W, with each column having content that requires a maximum width of M<sub>1</sub>, M<sub>2</sub>, M<sub>3</sub>, ... , M<sub>N</sub>, where M<sub>1</sub> + M<sub>2</sub> + M<sub>3</sub> + ... + M<sub>N</sub> > W. Find an optimal size, O<sub>1</sub>, O<sub>2</sub>, O<sub>3</sub>, ... , O<sub>N</sub>, for all columns in the table, where O<sub>1</sub> + O<sub>2</sub> + O<sub>3</sub> + ... + O<sub>N</sub> = W, and where for all i between 1 and N, O<sub>i</sub> / W ≤ R, where R is an arbitrary ratio less than 1 and greater than 0. That is to say, optimally sized means each O<sub>i</sub> / W = min(R, M<sub>i</sub> / (M<sub>1</sub> + M<sub>2</sub> + M<sub>3</sub> + ... + M<sub>N</sub>)), but when the min function chooses its first argument, the extra space, ([second argument] - [first argument]) * W, needs to be proportionally distributed to the remaining O<sub>j</sub>, where j is between 1 and N and does not equal i, and where "proportionally" means related to the proportions of M<sub>j</sub> / (M<sub>1</sub> + M<sub>2</sub> + M<sub>3</sub> + ... + M<sub>N</sub>). However, proportionally distributing this excess to the remaining columns may push a remaining column's ratio over R, which means some of that excess might further have to be redistributed.
The iterative approach to this problem is easy, but I am interested in determining a non-iterative solution to finding all of the O<sub>i</sub>, where I simply have a formula O<sub>i</sub> = [yada yada yada].
Here's code for the iterative solution when applied to columns of a <a href="http://doc.trolltech.com/4.4/qtreeview.html">QTreeView</a>, with N = 3 and R = .42, which is derived from my <a href="https://git.zx2c4.com/zmusicplayer/tree/AutoSizingList.cpp#n47">AutoSizingList class</a> of <a href="http://blog.zx2c4.com/14">ZMusicPlayer</a>. It uses QTreeView's <a href="http://doc.trolltech.com/4.4/qtreeview.html#sizeHintForColumn">sizeHintForColumn</a> to determine M<sub>i</sub>.
So essentially, the problem is that the do-while should be eliminated. It is required in the first place because when proportionally redistributing the difference between the arguments of the min function (outlined in the first paragraph), the ratios of the columns receiving this extra width may exceed R, which means another iteration must be done to readjust. Anyone have a non-iterative solution? Also, to the Qt experts out there, why is the hack required near the end?
I am interested both in a practical Qt approach and a mathematical approach, the latter being more interesting. Doesn't this seem like functionality that aught to already be a part of Qt?
### Update:
A conversation with a friend over AIM has produced a plain-English explanation in the form of a dialogue of the above problem.
Jason: so you're drawing a table
Jason: on a piece of paper
Jason: making all the lines and rows
Jason: so this table happens to have 3 columns
Jason: and a bunch of rows
Jason: make sense?
Pasternak: yes
Jason: ok
Jason: now each cell of the table is supposed to have some information in it
Jason: different length information takes up more width in the table
Jason: Rob Pasternak takes up more room than Yi Chan, for example
Jason: it's wider
Jason: it has more characters
Jason: right?
Pasternak: yes
Jason: now say that the biggest piece of data in the first column requires a width M1, the biggest in the second column requires a width M2, and in the third, M3
Jason: Rob Pasternak, Yi Chan, and Salvadora Manello Envelopa Dali
Jason: are the biggest pieces of data for each of the three columns respectively
Pasternak: ok
Jason: now let's say you're writing down your table on a napkin
Jason: so you can only make it a certain width
Jason: because the napkin is small
Jason: and you're bad at writing with tiny handwriting
Pasternak: ok
Jason: so you think to yourself "well, i will just make each column have its width be in the same proportion to the tiny width of the entire table as if i had tons of room to draw the table and was able to make each column have the width equal to the column's biggest name"
Jason: make sense?
Pasternak: ok
Pasternak: yes
Jason: so a simple equation for finding how big each column would be would just to do this
Jason: column1 = ( M1 / (M1 + M2 + M3) ) * tinyNapkinWidth
Jason: right?
Jason: and similarly for columns 2 and 3
Pasternak: yeah
Jason: ok so lets say you do that and then you notice that
Jason: Salvadora Manello Envelopa Dali is taking up way too much space on the table
Jason: so much so that the other two columns are too tiny to show any relevant information
Pasternak: but i thought you said
Pasternak: because each of those were the maximum
Pasternak: oh wait
Pasternak: i gotcha
Pasternak: cause the napkin is too small to make Chan visible at the right proportions
Jason: yeah
Jason: even though it's all perfectly proportioned,
Pasternak: yeah
Jason: Salvadora Manello Envelopa Dali is just so big that
Jason: he makes Chan tiny
Jason: so you think to yourself
Jason: "how about i impose a maximum ratio each column may take up. I hereby declare that no column may use more than 40% of the entire width!"
Jason: so, you apply the first process of column1 = ( M1 / (M1 + M2 + M3) ) * tinyNapkinWidth etc
Jason: but then you say something like
Jason: "if column1 is greater than 40% of tinyNapkinWidth, make column1 equal to 40% of tinyNapkinWidth"
Jason: with me?
Pasternak: yes
Jason: so then what are you going to do with that excess width you cut off of column1?
Jason: it has to go somewhere
Jason: since we want to use all of the napkin width
Jason: so you distribute it to the other two columns proportionally
Jason: not half to one and half to the other, but in a proportion equal to the amount of data they contain
Jason: seem reasonable?
Pasternak: yeah but then one of them could go over 40
Jason: exactly!
Jason: that's the problem
Jason: so then you do the process all over again
Jason: asking "does any column exceed 40%?"
Jason: over and over until it's perfect
Jason: this is the iterative method
Jason: i want to figure out an expression of column1,2,3 that is as simple as our original one of "column1 = ( M1 / (M1 + M2 + M3) ) * tinyNapkinWidth" but that takes into consideration our 40% restriction
Jason: and doesn't rely on iteration
Pasternak: for any number of columns i assume
Jason: yeah
Jason: right
|
