最优灵活的盒子布局算法

Question

我正在实现W3C定义的CSS3灵活盒子布局模块,类似于Mozilla的xul盒子模型.虽然这些标准规定了模型应该如何表现,但它们没有提供有关如何实施模型的任何细节.

我感兴趣的模型部分是:

1. 盒子有宽度和高度.
2. 盒子可以包含其他盒子.
3. 容器盒(父盒)负责确定它们所包含的盒子(子盒子)的大小和位置.
4. 盒具有可以是水平或垂直的方向.方向确定子框的定位和调整大小.
5. 儿童盒可以是灵活的或不灵活的.如果子框不灵活,则以width和height参数中指定的大小绘制.如果它是灵活的,则调整大小以适应父容器中的可用空间.
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