in src/Avalonia.Controls/Grid.cs [1785:2232]
private void SetFinalSizeMaxDiscrepancy(
IReadOnlyList<DefinitionBase> definitions,
double finalSize,
bool columns)
{
int defCount = definitions.Count;
int[] definitionIndices = DefinitionIndices;
int minCount = 0, maxCount = 0;
double takenSize = 0.0;
double totalStarWeight = 0.0;
int starCount = 0; // number of unresolved *-definitions
double scale = 1.0; // scale factor applied to each *-weight; negative means "Infinity is present"
// Phase 1. Determine the maximum *-weight and prepare to adjust *-weights
double maxStar = 0.0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
if (def.UserSize.IsStar)
{
++starCount;
def.MeasureSize = 1.0; // meaning "not yet resolved in phase 3"
if (def.UserSize.Value > maxStar)
{
maxStar = def.UserSize.Value;
}
}
}
if (Double.IsPositiveInfinity(maxStar))
{
// negative scale means one or more of the weights was Infinity
scale = -1.0;
}
else if (starCount > 0)
{
// if maxStar * starCount > Double.Max, summing all the weights could cause
// floating-point overflow. To avoid that, scale the weights by a factor to keep
// the sum within limits. Choose a power of 2, to preserve precision.
double power = Math.Floor(Math.Log(Double.MaxValue / maxStar / starCount, 2.0));
if (power < 0.0)
{
scale = Math.Pow(2.0, power - 4.0); // -4 is just for paranoia
}
}
// normally Phases 2 and 3 execute only once. But certain unusual combinations of weights
// and constraints can defeat the algorithm, in which case we repeat Phases 2 and 3.
// More explanation below...
for (bool runPhase2and3 = true; runPhase2and3;)
{
// Phase 2. Compute total *-weight W and available space S.
// For *-items that have Min or Max constraints, compute the ratios used to decide
// whether proportional space is too big or too small and add the item to the
// corresponding list. (The "min" list is in the first half of definitionIndices,
// the "max" list in the second half. DefinitionIndices has capacity at least
// 2*defCount, so there's room for both lists.)
totalStarWeight = 0.0;
takenSize = 0.0;
minCount = maxCount = 0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
if (def.UserSize.IsStar)
{
Debug.Assert(!def.IsShared, "*-defs cannot be shared");
if (def.MeasureSize < 0.0)
{
takenSize += -def.MeasureSize; // already resolved
}
else
{
double starWeight = StarWeight(def, scale);
totalStarWeight += starWeight;
if (def.MinSizeForArrange > 0.0)
{
// store ratio w/min in MeasureSize (for now)
definitionIndices[minCount++] = i;
def.MeasureSize = starWeight / def.MinSizeForArrange;
}
double effectiveMaxSize = Math.Max(def.MinSizeForArrange, def.UserMaxSize);
if (!Double.IsPositiveInfinity(effectiveMaxSize))
{
// store ratio w/max in SizeCache (for now)
definitionIndices[defCount + maxCount++] = i;
def.SizeCache = starWeight / effectiveMaxSize;
}
}
}
else
{
double userSize = 0;
switch (def.UserSize.GridUnitType)
{
case (GridUnitType.Pixel):
userSize = def.UserSize.Value;
break;
case (GridUnitType.Auto):
userSize = def.MinSizeForArrange;
break;
}
double userMaxSize;
if (def.IsShared)
{
// overriding userMaxSize effectively prevents squishy-ness.
// this is a "solution" to avoid shared definitions from been sized to
// different final size at arrange time, if / when different grids receive
// different final sizes.
userMaxSize = userSize;
}
else
{
userMaxSize = def.UserMaxSize;
}
def.SizeCache = Math.Max(def.MinSizeForArrange, Math.Min(userSize, userMaxSize));
takenSize += def.SizeCache;
}
}
// Phase 3. Resolve *-items whose proportional sizes are too big or too small.
int minCountPhase2 = minCount, maxCountPhase2 = maxCount;
double takenStarWeight = 0.0;
double remainingAvailableSize = finalSize - takenSize;
double remainingStarWeight = totalStarWeight - takenStarWeight;
MinRatioIndexComparer minRatioIndexComparer = new MinRatioIndexComparer(definitions);
Array.Sort(definitionIndices, 0, minCount, minRatioIndexComparer);
MaxRatioIndexComparer maxRatioIndexComparer = new MaxRatioIndexComparer(definitions);
Array.Sort(definitionIndices, defCount, maxCount, maxRatioIndexComparer);
while (minCount + maxCount > 0 && remainingAvailableSize > 0.0)
{
// the calculation
// remainingStarWeight = totalStarWeight - takenStarWeight
// is subject to catastrophic cancellation if the two terms are nearly equal,
// which leads to meaningless results. Check for that, and recompute from
// the remaining definitions. [This leads to quadratic behavior in really
// pathological cases - but they'd never arise in practice.]
const double starFactor = 1.0 / 256.0; // lose more than 8 bits of precision -> recalculate
if (remainingStarWeight < totalStarWeight * starFactor)
{
takenStarWeight = 0.0;
totalStarWeight = 0.0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
if (def.UserSize.IsStar && def.MeasureSize > 0.0)
{
totalStarWeight += StarWeight(def, scale);
}
}
remainingStarWeight = totalStarWeight - takenStarWeight;
}
double minRatio = (minCount > 0) ? definitions[definitionIndices[minCount - 1]].MeasureSize : Double.PositiveInfinity;
double maxRatio = (maxCount > 0) ? definitions[definitionIndices[defCount + maxCount - 1]].SizeCache : -1.0;
// choose the def with larger ratio to the current proportion ("max discrepancy")
double proportion = remainingStarWeight / remainingAvailableSize;
bool? chooseMin = Choose(minRatio, maxRatio, proportion);
// if no def was chosen, advance to phase 4; the current proportion doesn't
// conflict with any min or max values.
if (!chooseMin.HasValue)
{
break;
}
// get the chosen definition and its resolved size
int resolvedIndex;
DefinitionBase resolvedDef;
double resolvedSize;
if (chooseMin == true)
{
resolvedIndex = definitionIndices[minCount - 1];
resolvedDef = definitions[resolvedIndex];
resolvedSize = resolvedDef.MinSizeForArrange;
--minCount;
}
else
{
resolvedIndex = definitionIndices[defCount + maxCount - 1];
resolvedDef = definitions[resolvedIndex];
resolvedSize = Math.Max(resolvedDef.MinSizeForArrange, resolvedDef.UserMaxSize);
--maxCount;
}
// resolve the chosen def, deduct its contributions from W and S.
// Defs resolved in phase 3 are marked by storing the negative of their resolved
// size in MeasureSize, to distinguish them from a pending def.
takenSize += resolvedSize;
resolvedDef.MeasureSize = -resolvedSize;
takenStarWeight += StarWeight(resolvedDef, scale);
--starCount;
remainingAvailableSize = finalSize - takenSize;
remainingStarWeight = totalStarWeight - takenStarWeight;
// advance to the next candidate defs, removing ones that have been resolved.
// Both counts are advanced, as a def might appear in both lists.
while (minCount > 0 && definitions[definitionIndices[minCount - 1]].MeasureSize < 0.0)
{
--minCount;
definitionIndices[minCount] = -1;
}
while (maxCount > 0 && definitions[definitionIndices[defCount + maxCount - 1]].MeasureSize < 0.0)
{
--maxCount;
definitionIndices[defCount + maxCount] = -1;
}
}
// decide whether to run Phase2 and Phase3 again. There are 3 cases:
// 1. There is space available, and *-defs remaining. This is the
// normal case - move on to Phase 4 to allocate the remaining
// space proportionally to the remaining *-defs.
// 2. There is space available, but no *-defs. This implies at least one
// def was resolved as 'max', taking less space than its proportion.
// If there are also 'min' defs, reconsider them - we can give
// them more space. If not, all the *-defs are 'max', so there's
// no way to use all the available space.
// 3. We allocated too much space. This implies at least one def was
// resolved as 'min'. If there are also 'max' defs, reconsider
// them, otherwise the over-allocation is an inevitable consequence
// of the given min constraints.
// Note that if we return to Phase2, at least one *-def will have been
// resolved. This guarantees we don't run Phase2+3 infinitely often.
runPhase2and3 = false;
if (starCount == 0 && takenSize < finalSize)
{
// if no *-defs remain and we haven't allocated all the space, reconsider the defs
// resolved as 'min'. Their allocation can be increased to make up the gap.
for (int i = minCount; i < minCountPhase2; ++i)
{
if (definitionIndices[i] >= 0)
{
DefinitionBase def = definitions[definitionIndices[i]];
def.MeasureSize = 1.0; // mark as 'not yet resolved'
++starCount;
runPhase2and3 = true; // found a candidate, so re-run Phases 2 and 3
}
}
}
if (takenSize > finalSize)
{
// if we've allocated too much space, reconsider the defs
// resolved as 'max'. Their allocation can be decreased to make up the gap.
for (int i = maxCount; i < maxCountPhase2; ++i)
{
if (definitionIndices[defCount + i] >= 0)
{
DefinitionBase def = definitions[definitionIndices[defCount + i]];
def.MeasureSize = 1.0; // mark as 'not yet resolved'
++starCount;
runPhase2and3 = true; // found a candidate, so re-run Phases 2 and 3
}
}
}
}
// Phase 4. Resolve the remaining defs proportionally.
starCount = 0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
if (def.UserSize.IsStar)
{
if (def.MeasureSize < 0.0)
{
// this def was resolved in phase 3 - fix up its size
def.SizeCache = -def.MeasureSize;
}
else
{
// this def needs resolution, add it to the list, sorted by *-weight
definitionIndices[starCount++] = i;
def.MeasureSize = StarWeight(def, scale);
}
}
}
if (starCount > 0)
{
StarWeightIndexComparer starWeightIndexComparer = new StarWeightIndexComparer(definitions);
Array.Sort(definitionIndices, 0, starCount, starWeightIndexComparer);
// compute the partial sums of *-weight, in increasing order of weight
// for minimal loss of precision.
totalStarWeight = 0.0;
for (int i = 0; i < starCount; ++i)
{
DefinitionBase def = definitions[definitionIndices[i]];
totalStarWeight += def.MeasureSize;
def.SizeCache = totalStarWeight;
}
// resolve the defs, in decreasing order of weight.
for (int i = starCount - 1; i >= 0; --i)
{
DefinitionBase def = definitions[definitionIndices[i]];
double resolvedSize = (def.MeasureSize > 0.0) ? Math.Max(finalSize - takenSize, 0.0) * (def.MeasureSize / def.SizeCache) : 0.0;
// min and max should have no effect by now, but just in case...
resolvedSize = Math.Min(resolvedSize, def.UserMaxSize);
resolvedSize = Math.Max(def.MinSizeForArrange, resolvedSize);
// Use the raw (unrounded) sizes to update takenSize, so that
// proportions are computed in the same terms as in phase 3;
// this avoids errors arising from min/max constraints.
takenSize += resolvedSize;
def.SizeCache = resolvedSize;
}
}
// Phase 5. Apply layout rounding. We do this after fully allocating
// unrounded sizes, to avoid breaking assumptions in the previous phases
if (UseLayoutRounding)
{
// DpiScale dpiScale = GetDpi();
// double dpi = columns ? dpiScale.DpiScaleX : dpiScale.DpiScaleY;
var dpi = (VisualRoot as ILayoutRoot)?.LayoutScaling ?? 1.0;
double[] roundingErrors = RoundingErrors;
double roundedTakenSize = 0;
// round each of the allocated sizes, keeping track of the deltas
for (int i = 0; i < definitions.Count; ++i)
{
DefinitionBase def = definitions[i];
double roundedSize = LayoutHelper.RoundLayoutValue(def.SizeCache, dpi);
roundingErrors[i] = (roundedSize - def.SizeCache);
def.SizeCache = roundedSize;
roundedTakenSize += roundedSize;
}
// The total allocation might differ from finalSize due to rounding
// effects. Tweak the allocations accordingly.
// Theoretical and historical note. The problem at hand - allocating
// space to columns (or rows) with *-weights, min and max constraints,
// and layout rounding - has a long history. Especially the special
// case of 50 columns with min=1 and available space=435 - allocating
// seats in the U.S. House of Representatives to the 50 states in
// proportion to their population. There are numerous algorithms
// and papers dating back to the 1700's, including the book:
// Balinski, M. and H. Young, Fair Representation, Yale University Press, New Haven, 1982.
//
// One surprising result of all this research is that *any* algorithm
// will suffer from one or more undesirable features such as the
// "population paradox" or the "Alabama paradox", where (to use our terminology)
// increasing the available space by one pixel might actually decrease
// the space allocated to a given column, or increasing the weight of
// a column might decrease its allocation. This is worth knowing
// in case someone complains about this behavior; it's not a bug so
// much as something inherent to the problem. Cite the book mentioned
// above or one of the 100s of references, and resolve as WontFix.
//
// Fortunately, our scenarios tend to have a small number of columns (~10 or fewer)
// each being allocated a large number of pixels (~50 or greater), and
// people don't even notice the kind of 1-pixel anomalies that are
// theoretically inevitable, or don't care if they do. At least they shouldn't
// care - no one should be using the results WPF's grid layout to make
// quantitative decisions; its job is to produce a reasonable display, not
// to allocate seats in Congress.
//
// Our algorithm is more susceptible to paradox than the one currently
// used for Congressional allocation ("Huntington-Hill" algorithm), but
// it is faster to run: O(N log N) vs. O(S * N), where N=number of
// definitions, S = number of available pixels. And it produces
// adequate results in practice, as mentioned above.
//
// To reiterate one point: all this only applies when layout rounding
// is in effect. When fractional sizes are allowed, the algorithm
// behaves as well as possible, subject to the min/max constraints
// and precision of floating-point computation. (However, the resulting
// display is subject to anti-aliasing problems. TANSTAAFL.)
if (!MathUtilities.AreClose(roundedTakenSize, finalSize))
{
// Compute deltas
for (int i = 0; i < definitions.Count; ++i)
{
definitionIndices[i] = i;
}
// Sort rounding errors
RoundingErrorIndexComparer roundingErrorIndexComparer = new RoundingErrorIndexComparer(roundingErrors);
Array.Sort(definitionIndices, 0, definitions.Count, roundingErrorIndexComparer);
double adjustedSize = roundedTakenSize;
double dpiIncrement = 1.0 / dpi;
if (roundedTakenSize > finalSize)
{
int i = definitions.Count - 1;
while ((adjustedSize > finalSize && !MathUtilities.AreClose(adjustedSize, finalSize)) && i >= 0)
{
DefinitionBase definition = definitions[definitionIndices[i]];
double final = definition.SizeCache - dpiIncrement;
final = Math.Max(final, definition.MinSizeForArrange);
if (final < definition.SizeCache)
{
adjustedSize -= dpiIncrement;
}
definition.SizeCache = final;
i--;
}
}
else if (roundedTakenSize < finalSize)
{
int i = 0;
while ((adjustedSize < finalSize && !MathUtilities.AreClose(adjustedSize, finalSize)) && i < definitions.Count)
{
DefinitionBase definition = definitions[definitionIndices[i]];
double final = definition.SizeCache + dpiIncrement;
final = Math.Max(final, definition.MinSizeForArrange);
if (final > definition.SizeCache)
{
adjustedSize += dpiIncrement;
}
definition.SizeCache = final;
i++;
}
}
}
}
double spacing = columns ? ColumnSpacing : RowSpacing;
// Phase 6. Compute final offsets
definitions[0].FinalOffset = 0.0;
for (int i = 0; i < definitions.Count; ++i)
{
definitions[(i + 1) % definitions.Count].FinalOffset = definitions[i].FinalOffset + definitions[i].SizeCache + spacing;
}
}