Reworked a part of grid's geometry computations

to handle some tricky cases better. [Bug #792387]

3 files changed, 200 insertions, 23 deletions

diff --git a/ChangeLog b/ChangeLog
index 11e7c5e..5e7a758 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2003-09-16  Peter Spjuth  <peter.spjuth@space.se>
+	* tests/grid.test:
+	* generic/tkGrid.c: Reworked a part of grid's geometry computations
+	to handle some tricky cases better. [Bug #792387]
+
 2003-09-05  Joe English  <jenglish@users.sourceforge.net>
 	* doc/bind.n: Describe %P and %s substitution for
 	Property events. [BUG #577906 "%P substitution not documented"]
diff --git a/generic/tkGrid.c b/generic/tkGrid.c
index 78fe219..0b6ac23 100644
--- a/generic/tkGrid.c
+++ b/generic/tkGrid.c
@@ -8,7 +8,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tkGrid.c,v 1.26 2003/03/12 00:09:36 mdejong Exp $
+ * RCS: @(#) $Id: tkGrid.c,v 1.27 2003/09/16 21:47:15 pspjuth Exp $
  */
 
 #include "tkInt.h"
@@ -1703,6 +1703,7 @@ ResolveConstraints(masterPtr, slotType, maxOffset)
     int uniformGroupsAlloced;	/* Size of allocated space for uniform groups.
 				 */
     int weight, minSize;
+    int prevGrow, accWeight, grow;
 
     /*
      * For typical sized tables, we'll use stack space for the layout data
@@ -2017,8 +2018,8 @@ ResolveConstraints(masterPtr, slotType, maxOffset)
 	 * It might not be possible to give the span all of the space
 	 * available on this pass without violating the size constraints 
 	 * of one or more of the internal slot boundaries.
-	 * Determine the maximum amount of space that when added to the
-	 * entire span, would cause a slot boundary to have its possible
+	 * Try to determine the maximum amount of space that when added to
+	 * the entire span, would cause a slot boundary to have its possible
 	 * range reduced to one value, and reduce the amount of extra
 	 * space allocated on this pass accordingly.
 	 * 
@@ -2026,29 +2027,94 @@ ResolveConstraints(masterPtr, slotType, maxOffset)
 	 * roundoff errors.
 	 */
 
-	for (weight=0,slot=start; slot<end; slot++) {
-	    int diff = layoutPtr[slot].maxOffset - layoutPtr[slot].minOffset;
-	    weight += noWeights ? 1 : layoutPtr[slot].weight;
-	    if ((noWeights || layoutPtr[slot].weight>0) &&
-		    (diff*totalWeight/weight) < (have-need)) {
-		have = diff * totalWeight / weight + need;
-	    }
-	}
+        while (1) {
+            int prevMinOffset = layoutPtr[start - 1].minOffset;
+            prevGrow = 0;
+            accWeight = 0;
+            for (slot = start; slot <= end; slot++) {
+                weight = noWeights ? 1 : layoutPtr[slot].weight;
+                accWeight += weight;
+                grow = (have - need) * accWeight / totalWeight - prevGrow;
+                prevGrow += grow;
+
+                if ((weight > 0) &&
+                        ((prevMinOffset + layoutPtr[slot].minSize + grow)
+                        > layoutPtr[slot].maxOffset)) {
+                    int newHave;
+                    /* 
+                     * There is not enough room to grow that much.
+                     * Calculate how much this slot can grow and how much
+                     * "have" that corresponds to.
+                     */
+
+                    grow = layoutPtr[slot].maxOffset -
+                            layoutPtr[slot].minSize - prevMinOffset;
+                    newHave = grow * totalWeight / weight;
+                    if (newHave > totalWeight) {
+                        /*
+                         * By distributing multiples of totalWeight
+                         * we minimize rounding errors since they will
+                         * only happen in the last loop(s).
+                         */
+
+                        newHave = newHave / totalWeight * totalWeight;
+                    }
+                    if (newHave <= 0) {
+                        /* 
+                         * We can end up with a "have" of 0 here if
+                         * the previous slots have taken all the space.
+                         * In that case we cannot guess an appropriate
+                         * "have" so we just try some lower "have" that
+                         * is >= 1, to make sure this terminates.
+                         */
+
+                        newHave = (have - need) - 1;
+                        if (newHave > (3 * totalWeight)) {
+                            /* Go down 25% for large values */
+                            newHave = newHave * 3 / 4;
+                        }
+                        if (newHave > totalWeight) {
+                            /* Round down to a multiple of totalWeight. */
+                            newHave = newHave / totalWeight * totalWeight;
+                        }
+                        if (newHave <= 0) {
+                            newHave = 1;
+                        }
+                    }
+                    have = newHave + need;
+                    /*
+                     * Restart loop to check if the new "have" will fit.
+                     */
+
+                    break;
+                }
+                prevMinOffset += layoutPtr[slot].minSize + grow;
+                if (prevMinOffset < layoutPtr[slot].minOffset) {
+                    prevMinOffset = layoutPtr[slot].minOffset;
+                } 
+            }
+            /* Quit the loop if the for loop ran all the way */
+            if (slot > end) break;
+        }
 
 	/*
 	 * Now distribute the extra space among the slots by
 	 * adjusting the minSizes and minOffsets.
 	 */
 
-	for (weight=0,slot=start; slot<end; slot++) {
-	    weight += noWeights ? 1 : layoutPtr[slot].weight;
-	    layoutPtr[slot].minOffset +=
-		(int)((double) (have-need) * weight/totalWeight + 0.5);
-	    layoutPtr[slot].minSize = layoutPtr[slot].minOffset 
-		    - layoutPtr[slot-1].minOffset;
-	}
-	layoutPtr[slot].minSize = layoutPtr[slot].minOffset 
-		- layoutPtr[slot-1].minOffset;
+        prevGrow = 0;
+        accWeight = 0;
+        for (slot = start; slot <= end; slot++) {
+            accWeight += noWeights ? 1 : layoutPtr[slot].weight;
+            grow = (have - need) * accWeight / totalWeight - prevGrow;
+            prevGrow += grow;
+            layoutPtr[slot].minSize += grow;
+            if ((layoutPtr[slot-1].minOffset + layoutPtr[slot].minSize)
+                    > layoutPtr[slot].minOffset) {
+                layoutPtr[slot].minOffset = layoutPtr[slot-1].minOffset +
+                        layoutPtr[slot].minSize;
+            }
+        }
 
 	/*
 	 * Having pushed the top/left boundaries of the slots to
diff --git a/tests/grid.test b/tests/grid.test
index bfbd1f6..063c9f8 100644
--- a/tests/grid.test
+++ b/tests/grid.test
@@ -5,7 +5,7 @@
 # Copyright (c) 1998-1999 by Scriptics Corporation.
 # All rights reserved.
 #
-# RCS: @(#) $Id: grid.test,v 1.19 2003/04/01 21:06:36 dgp Exp $
+# RCS: @(#) $Id: grid.test,v 1.20 2003/09/16 21:47:15 pspjuth Exp $
 
 package require tcltest 2.1
 eval tcltest::configure $argv
@@ -1349,7 +1349,7 @@ test grid-16.8 {layout internal constraints} {
     	append a "[winfo x .$i] "
     }
     set a
-} {0 30 70 250 280 , 0 30 130 230 260 , 0 30 113 197 280 , 0 30 60 90 120 }
+} {0 30 130 230 280 , 0 30 130 230 260 , 0 30 113 196 280 , 0 30 60 90 120 }
 grid_reset 16.8
 
 test grid-16.9 {layout uniform} {
@@ -1414,7 +1414,7 @@ test grid-16.12 {layout uniform (grow)} {
     grid .f1 .f2 .f3 .f4 -sticky news
     grid columnconfigure . {0 1 2} -uniform a
     # Put weight 2 on the biggest in the group to see that the groups
-    # adapts to one of the smaller.
+    # adapt to one of the smaller.
     grid columnconfigure . 2 -weight 2
     grid columnconfigure . {0 3} -weight 1
     update
@@ -1431,6 +1431,112 @@ test grid-16.12 {layout uniform (grow)} {
         {0 0 70 95} {70 0 50 95} {120 0 140 95} {260 0 90 95}]
 grid_reset 16.12
 
+test grid-16.13 {layout span} {
+    frame .f1 -width 24 -height 20
+    frame .f2 -width 38 -height 20
+    frame .f3 -width 150 -height 20
+
+    grid .f1 - - .f2
+    grid .f3 - - -
+
+    set res {}
+    foreach w {{0 1 0 0} {0 0 1 0} {1 3 4 0} {1 2 1 2} {1 1 1 12}} {
+        for {set c 0} {$c < 4} {incr c} {
+            grid columnconfigure . $c -weight [lindex $w $c]
+        }
+        update
+        set res2 {}
+        for {set c 0} {$c <= 4} {incr c} {
+            lappend res2 [lindex [grid bbox . $c 0] 2]
+        }
+        lappend res $res2
+    }
+    set res
+    # The last result below should ideally be 8 8 8 126 but the current
+    # implementation is not exact enough.
+} [list [list 0 112 0 38 0] [list 0 0 112 38 0] [list 14 42 56 38 0] \
+           [list 18 38 18 76 0] [list 7 8 9 126 0]]
+grid_reset 16.13
+
+test grid-16.14 {layout span} {
+    frame .f1 -width 110 -height 20
+    frame .f2 -width 38 -height 20
+    frame .f3 -width 150 -height 20
+
+    grid .f1 - - .f2
+    grid .f3 - - -
+
+    set res {}
+    foreach w {{0 1 0 0} {0 0 1 0} {1 3 4 0} {1 2 1 3} {1 1 1 12}} {
+        for {set c 0} {$c < 4} {incr c} {
+            grid columnconfigure . $c -weight [lindex $w $c]
+        }
+        update
+        set res2 {}
+        for {set c 0} {$c <= 4} {incr c} {
+            lappend res2 [lindex [grid bbox . $c 0] 2]
+        }
+        lappend res $res2
+    }
+    set res
+} [list [list 0 112 0 38 0] [list 0 0 112 38 0] [list 14 42 56 38 0] \
+           [list 27 55 28 40 0] [list 36 37 37 40 0]]
+grid_reset 16.14
+
+test grid-16.15 {layout span} {
+    frame .f1 -width 24 -height 20
+    frame .f2 -width 38 -height 20
+    frame .f3 -width 150 -height 20
+
+    grid .f1 - - .f2
+    grid x .f3 - -
+
+    set res {}
+    foreach w {{0 1 0 0} {0 0 1 0} {1 0 1 0} {0 0 0 0} {1 0 0 6}} {
+        for {set c 0} {$c < 4} {incr c} {
+            grid columnconfigure . $c -weight [lindex $w $c]
+        }
+        update
+        set res2 {}
+        for {set c 0} {$c <= 4} {incr c} {
+            lappend res2 [lindex [grid bbox . $c 0] 2]
+        }
+        lappend res $res2
+    }
+    set res
+} [list [list 0 112 0 38 0] [list 0 0 112 38 0] [list 0 0 112 38 0] \
+           [list 0 37 37 76 0] [list 0 12 12 126 0]]
+grid_reset 16.15
+
+test grid-16.16 {layout span} {
+    frame .f1 -width 64 -height 20
+    frame .f2 -width 38 -height 20
+    frame .f3 -width 150 -height 20
+    frame .f4 -width 15 -height 20
+    frame .f5 -width 18 -height 20
+    frame .f6 -width 20 -height 20
+
+    grid .f1 - x .f2
+    grid .f3 - - -
+    grid .f4 .f5 .f6
+
+    set res {}
+    foreach w {{1 1 5 1} {0 0 1 0} {1 3 4 0} {1 2 1 2} {1 1 1 12}} {
+        for {set c 0} {$c < 4} {incr c} {
+            grid columnconfigure . $c -weight [lindex $w $c]
+        }
+        update
+        set res2 {}
+        for {set c 0} {$c <= 4} {incr c} {
+            lappend res2 [lindex [grid bbox . $c 0] 2]
+        }
+        lappend res $res2
+    }
+    set res
+} [list [list 30 34 43 43 0] [list 30 34 48 38 0] [list 22 42 48 38 0] \
+           [list 25 39 29 57 0] [list 30 34 22 64 0]]
+grid_reset 16.16
+
 test grid-17.1 {forget and pending idle handlers} {
     # This test is intended to detect a crash caused by a failure to remove
     # pending idle handlers when grid forget is invoked.