Оптимальный алгоритм гибкого макета окна

Я реализую модуль гибкой компоновки блока CSS3 , как определено W3C, который аналогичен Коробочная модель Mozilla для xul . Хотя эти стандарты определяют, как должна вести себя модель, они не содержат никаких подробностей о том, как они должны быть реализованы.

Меня интересуют следующие части модели:

1. Ящики имеют ширину и высоту.
2. Ящики могут содержать другие ящики.
3. Контейнерные ящики (родительские ящики) отвечают за размер и расположение коробки, которые они содержат (дочерние блоки).
4. Коробки имеют ориентацию, которая может быть горизонтальной или вертикальной. Ориентация определяет, как дочерние блоки располагаются и изменяются в размерах.
5. Дочерние блоки могут быть гибкими или негибкими. Если дочерний блок негибкий, он отрисовывается с размером, указанным в параметрах ширины и высоты. Если он гибкий, то его размер изменяется в соответствии с доступным пространством в родительском контейнере.
6. Гибкость относительно других дочерних блоков в том же контейнере, блоки с большей гибкостью изменяются больше, чем блоки с меньшей гибкостью.
7. ] Дочерние блоки можно ограничить минимальным или максимальным размером. Если дочерний блок является гибким, родительский блок никогда не изменит его размер ниже минимального или выше максимального.

Функции 1-5 могут быть реализованы довольно эффективно. Функция 6 проблематична, поскольку наиболее эффективный алгоритм, который я могу придумать, довольно наивен. Алгоритм работает следующим образом:

1. Поместите все блоки в список.
2. Прокрутите каждый дочерний блок и измените его размер, используя гибкость, чтобы определить величину для изменения его размера.
3. Если размер превышает один из limit, затем установите размер окна до предела, удалите его из списка и начните с начала списка.

На шаге 3 эффективность падает. Например, если в списке десять элементов, а последний имеет ограничение, алгоритм вычисляет размер для первых девяти элементов, а затем, когда он достигает десятого, ему необходимо повторить все вычисления. Я подумал о том, чтобы сохранить список отсортированным и сначала определить размеры всех ограниченных блоков, однако это связано с затратами на дополнительную сложность и накладными расходами на сортировку списка.

Я ожидаю, что существует признанное оптимальное решение, учитывая, что это довольно распространенная функция в браузерах и фреймворках (XUL, .Net, Flex и т. д.).