最优柔性盒布局算法

Question

我正在实现由CSS3柔性盒布局模块定义的W3C，它类似于用于xul的Mozilla盒模型。虽然这些标准指定了模型的行为方式，但它们没有给出应该如何实现它们的任何细节。

我感兴趣的模型的部分是：

1. 盒子有宽度和高度。
2. 盒子可以包含其他的盒子。
3. 容器盒(父盒)负责调整它们包含的箱子(子盒)的大小和定位。
4. 盒子的方向可以是水平的也可以是垂直的。该方向确定子框的位置和大小。
5. 子盒可以是灵活的，也可以是不灵活的。如果子框不灵活，则按宽度和高度参数中指定的大小绘制。如果它是灵活的，那么它将被调整大小以适应父容器中可用的空间。
6. 灵活性是相对于同一容器中的其他子框而言的，灵活性较高的箱子比灵活性较低的箱子的尺寸调整得更多。
7. 子框可以限制为最小或最大大小。如果子框是灵活的，父框将永远不会将其调整到最小大小以下或大于最大大小。

特性1-5可以非常有效地实现。功能6是有问题的，因为我能想到的最有效的算法是相当天真的。该算法的工作原理如下：

1. 把所有的盒子放在一个列表中。
2. 循环遍历每个子框并调整大小，使用灵活性确定要调整大小的数量。
3. 如果大小超过其中一个限制，则将框大小设置为限制并从列表中删除，然后从列表的开头开始。

步骤3是效率下降的地方。例如，如果列表中有十项，而最后一项具有约束，则算法计算前九项的大小，然后当到达第十项时，需要重做所有计算。我已经考虑过保持列表的排序，并首先调整所有受约束的框的大小，但是这需要增加复杂性和排序列表的开销。

考虑到这是浏览器和框架(XUL、.Net、Flex等)中相当常见的特性，我希望有一个公认的最佳解决方案。

Answer 1

大多数箱/容器布局算法使用2通算法。在.NET (WPF)中，它们被称为“度量衡”和“排列”。每个控件都可以测量其内容，并在递归度量值传递中报告“所需的大小”。

在第二次传递(安排)期间，如果子女所需的大小不适合父级，则父级使用其布局算法向每个子级提供实际大小，例如，通过指定按期望大小加权的实际大小。最小/最大的尺寸，盒子的灵活性等可以在这里发挥作用。

有关WPF布局系统http://msdn.microsoft.com/en-us/library/ms745058.aspx的更多信息

Xul布局http://www-archive.mozilla.org/projects/xul/layout.html