Всегда ли компоновка графического интерфейса имеет экспоненциальную сложность? ⇐ C++

[Anonymous]

Я разрабатываю простую «структуру» графического пользовательского интерфейса с виджетами и макетами. Давайте проиллюстрируем проблему на простом примере базового горизонтального макета, в котором дочерние виджеты располагаются рядом друг с другом, и если в конце остается какое-то место, оно остается пустым. По вертикали все они будут растянуты на всю высоту макета.
Из этого ясно, что размеры виджета заранее не известны полностью. Горизонтальная планировка требует, чтобы каждый ребенок занимал минимально возможное пространство по горизонтали. С другой стороны, размеры корневого макета (который заполняет окно приложения) известны, поэтому, если бы горизонтальный макет был корневым макетом, мы бы знали высоту каждого дочернего элемента.
Поэтому я придумал следующий интерфейс функции верстки:

Код: Выделить всё

Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions);

Итак, для первого дочернего элемента в горизонтальном макете это будет

Код: Выделить всё

child->layout(Dimensions(0, parentMinDimensions.height), parentMaxDimensions);

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

Код: Выделить всё

Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions) {
int remainingWidth = maxDimensions.width;
for (Widget *child : children) {
Dimensions childDimensions = child->layout(
Dimensions(0,              minDimensions.height),
Dimensions(remainingWidth, maxDimensions.height)
);
remainingWidth -= childDimensions.width;
minDimensions.height = max(minDimensions.height, childDimensions.height);
}
return Dimensions(maxDimensions.width-remainingWidth, minDimensions.height);
}

Выглядит неплохо, но есть одна проблема. Предполагалось, что макет растягивает всех дочерних элементов по вертикали до его высоты, но если горизонтальный макет является, например, дочерним элементом вертикального макета, то входные минимальная и максимальная высота различаются, и вместо этого каждый виджет может иметь разную высоту. И вот здесь появляется проблема. Я не верю, что эту проблему можно решить, не оценивая макет каждого дочернего элемента дважды:

Код: Выделить всё

Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions) {
// First pass - determine height
int height = minDimensions.height;
int remainingWidth = maxDimensions.width;
for (Widget *child : children) {
Dimensions childDimensions = child->layout(
Dimensions(0,              minDimensions.height),
Dimensions(remainingWidth, maxDimensions.height)
);
remainingWidth -= childDimensions.width;
height = max(height, childDimensions.height);
}
// Second pass - apply height
remainingWidth = maxDimensions.width;
for (Widget *child : children) {
Dimensions childDimensions = child->layout(
Dimensions(0,              height),
Dimensions(remainingWidth, height)
);
remainingWidth -= childDimensions.width;
}
return Dimensions(maxDimensions.width-remainingWidth, height);
}

Макеты организованы в виде древовидной иерархии произвольного размера и глубины, и оценка всего поддерева в каждом узле более одного раза приводит к экспоненциальной сложности. В некоторых сценариях необходимо быстро пересчитывать макет в каждом кадре, например, когда пользователь изменяет размер окна, и это было бы плохо.
Поскольку инфраструктуры графического интерфейса с этой парадигмой чрезвычайно распространено, мне было интересно, есть ли у них такая же проблема, но, возможно, на практике иерархии недостаточно глубоки, чтобы это стало серьезной проблемой, или действительно есть какой-то способ гарантировать лучше, чем экспоненциальное время выполнения даже в худшем случае (и без ущерба для гибкости макетов).
Сноска
Я осознавая, что вместо того, чтобы дважды вызывать макет, я могу использовать две функции, например

Код: Выделить всё

Dimensions measure(Dimensions minDimensions, Dimensions maxDimensions);
void layout(Dimensions exactDimensions);

и, возможно, даже гарантировать, что первый из них обойдет дерево только один раз, но в приведенном выше примере мне все равно придется вызывать обе функции макета для каждого дочернего элемента, поэтому экспоненциальный сложность все равно есть. Кроме того, у меня больше не было бы возможности пропустить второй раунд, если бы минимальная и максимальная высота были равны, поэтому я не думаю, что это было бы полезно во всех случаях.
Я да. Также известно, что кэширование промежуточных результатов может помочь, но существует ли на самом деле стратегия, которая может окончательно изменить сложность наихудшего случая во всех возможных сценариях? Меня интересует экспоненциальная сложность «большого О», а не оптимизация с постоянным коэффициентом.

Подробнее здесь: https://stackoverflow.com/questions/790 ... complexity