1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#include "qlayout.h"
5#include "private/qlayoutengine_p.h"
6
7#include "qlist.h"
8#include "qwidget.h"
9
10#include <qvarlengtharray.h>
11#include <qdebug.h>
12
13#include <algorithm>
14
15QT_BEGIN_NAMESPACE
16
17//#define QLAYOUT_EXTRA_DEBUG
18
19typedef qint64 Fixed64;
20static inline Fixed64 toFixed(int i) { return (Fixed64)i * 256; }
21static inline int fRound(Fixed64 i) {
22 return (i % 256 < 128) ? i / 256 : 1 + i / 256;
23}
24
25/*
26 This is the main workhorse of the QGridLayout. It portions out
27 available space to the chain's children.
28
29 The calculation is done in fixed point: "fixed" variables are
30 scaled by a factor of 256.
31
32 If the layout runs "backwards" (i.e. RightToLeft or Up) the layout
33 is computed mirror-reversed, and it's the caller's responsibility
34 do reverse the values before use.
35
36 chain contains input and output parameters describing the geometry.
37 count is the count of items in the chain; pos and space give the
38 interval (relative to parentWidget topLeft).
39*/
40void qGeomCalc(QList<QLayoutStruct> &chain, int start, int count, int pos, int space, int spacer)
41{
42 int cHint = 0;
43 int cMin = 0;
44 int sumStretch = 0;
45 int sumSpacing = 0;
46 int expandingCount = 0;
47
48 bool allEmptyNonstretch = true;
49 int pendingSpacing = -1;
50 int spacerCount = 0;
51 int i;
52
53 for (i = start; i < start + count; i++) {
54 QLayoutStruct *data = &chain[i];
55
56 data->done = false;
57 cHint += data->smartSizeHint();
58 cMin += data->minimumSize;
59 sumStretch += data->stretch;
60 if (!data->empty) {
61 /*
62 Using pendingSpacing, we ensure that the spacing for the last
63 (non-empty) item is ignored.
64 */
65 if (pendingSpacing >= 0) {
66 sumSpacing += pendingSpacing;
67 ++spacerCount;
68 }
69 pendingSpacing = data->effectiveSpacer(uniformSpacer: spacer);
70 }
71 if (data->expansive)
72 expandingCount++;
73 allEmptyNonstretch = allEmptyNonstretch && data->empty && !data->expansive && data->stretch <= 0;
74 }
75
76 int extraspace = 0;
77
78 if (space < cMin + sumSpacing) {
79 /*
80 Less space than minimumSize; take from the biggest first
81 */
82
83 int minSize = cMin + sumSpacing;
84
85 // shrink the spacers proportionally
86 if (spacer >= 0) {
87 spacer = minSize > 0 ? spacer * space / minSize : 0;
88 sumSpacing = spacer * spacerCount;
89 }
90
91 QVarLengthArray<int, 32> minimumSizes;
92 minimumSizes.reserve(sz: count);
93
94 for (i = start; i < start + count; i++)
95 minimumSizes << chain.at(i).minimumSize;
96
97 std::sort(first: minimumSizes.begin(), last: minimumSizes.end());
98
99 int space_left = space - sumSpacing;
100
101 int sum = 0;
102 int idx = 0;
103 int space_used=0;
104 int current = 0;
105 while (idx < count && space_used < space_left) {
106 current = minimumSizes.at(idx);
107 space_used = sum + current * (count - idx);
108 sum += current;
109 ++idx;
110 }
111 --idx;
112 int deficit = space_used - space_left;
113
114 int items = count - idx;
115 /*
116 * If we truncate all items to "current", we would get "deficit" too many pixels. Therefore, we have to remove
117 * deficit/items from each item bigger than maxval. The actual value to remove is deficitPerItem + remainder/items
118 * "rest" is the accumulated error from using integer arithmetic.
119 */
120 int deficitPerItem = deficit/items;
121 int remainder = deficit % items;
122 int maxval = current - deficitPerItem;
123
124 int rest = 0;
125 for (i = start; i < start + count; i++) {
126 int maxv = maxval;
127 rest += remainder;
128 if (rest >= items) {
129 maxv--;
130 rest-=items;
131 }
132 QLayoutStruct *data = &chain[i];
133 data->size = qMin(a: data->minimumSize, b: maxv);
134 data->done = true;
135 }
136 } else if (space < cHint + sumSpacing) {
137 /*
138 Less space than smartSizeHint(), but more than minimumSize.
139 Currently take space equally from each, as in Qt 2.x.
140 Commented-out lines will give more space to stretchier
141 items.
142 */
143 int n = count;
144 int space_left = space - sumSpacing;
145 int overdraft = cHint - space_left;
146
147 // first give to the fixed ones:
148 for (i = start; i < start + count; i++) {
149 QLayoutStruct *data = &chain[i];
150 if (!data->done
151 && data->minimumSize >= data->smartSizeHint()) {
152 data->size = data->smartSizeHint();
153 data->done = true;
154 space_left -= data->smartSizeHint();
155 // sumStretch -= data->stretch;
156 n--;
157 }
158 }
159 bool finished = n == 0;
160 while (!finished) {
161 finished = true;
162 Fixed64 fp_over = toFixed(i: overdraft);
163 Fixed64 fp_w = 0;
164
165 for (i = start; i < start+count; i++) {
166 QLayoutStruct *data = &chain[i];
167 if (data->done)
168 continue;
169 // if (sumStretch <= 0)
170 fp_w += fp_over / n;
171 // else
172 // fp_w += (fp_over * data->stretch) / sumStretch;
173 int w = fRound(i: fp_w);
174 data->size = data->smartSizeHint() - w;
175 fp_w -= toFixed(i: w); // give the difference to the next
176 if (data->size < data->minimumSize) {
177 data->done = true;
178 data->size = data->minimumSize;
179 finished = false;
180 overdraft -= data->smartSizeHint() - data->minimumSize;
181 // sumStretch -= data->stretch;
182 n--;
183 break;
184 }
185 }
186 }
187 } else { // extra space
188 int n = count;
189 int space_left = space - sumSpacing;
190 // first give to the fixed ones, and handle non-expansiveness
191 for (i = start; i < start + count; i++) {
192 QLayoutStruct *data = &chain[i];
193 if (!data->done
194 && (data->maximumSize <= data->smartSizeHint()
195 || (!allEmptyNonstretch && data->empty &&
196 !data->expansive && data->stretch == 0))) {
197 data->size = data->smartSizeHint();
198 data->done = true;
199 space_left -= data->size;
200 sumStretch -= data->stretch;
201 if (data->expansive)
202 expandingCount--;
203 n--;
204 }
205 }
206 extraspace = space_left;
207
208 /*
209 Do a trial distribution and calculate how much it is off.
210 If there are more deficit pixels than surplus pixels, give
211 the minimum size items what they need, and repeat.
212 Otherwise give to the maximum size items, and repeat.
213
214 Paul Olav Tvete has a wonderful mathematical proof of the
215 correctness of this principle, but unfortunately this
216 comment is too small to contain it.
217 */
218 int surplus, deficit;
219 do {
220 surplus = deficit = 0;
221 Fixed64 fp_space = toFixed(i: space_left);
222 Fixed64 fp_w = 0;
223 for (i = start; i < start + count; i++) {
224 QLayoutStruct *data = &chain[i];
225 if (data->done)
226 continue;
227 extraspace = 0;
228 if (sumStretch > 0) {
229 fp_w += (fp_space * data->stretch) / sumStretch;
230 } else if (expandingCount > 0) {
231 fp_w += (fp_space * (data->expansive ? 1 : 0)) / expandingCount;
232 } else {
233 fp_w += fp_space * 1 / n;
234 }
235 int w = fRound(i: fp_w);
236 data->size = w;
237 fp_w -= toFixed(i: w); // give the difference to the next
238 if (w < data->smartSizeHint()) {
239 deficit += data->smartSizeHint() - w;
240 } else if (w > data->maximumSize) {
241 surplus += w - data->maximumSize;
242 }
243 }
244 if (deficit > 0 && surplus <= deficit) {
245 // give to the ones that have too little
246 for (i = start; i < start+count; i++) {
247 QLayoutStruct *data = &chain[i];
248 if (!data->done && data->size < data->smartSizeHint()) {
249 data->size = data->smartSizeHint();
250 data->done = true;
251 space_left -= data->smartSizeHint();
252 sumStretch -= data->stretch;
253 if (data->expansive)
254 expandingCount--;
255 n--;
256 }
257 }
258 }
259 if (surplus > 0 && surplus >= deficit) {
260 // take from the ones that have too much
261 for (i = start; i < start + count; i++) {
262 QLayoutStruct *data = &chain[i];
263 if (!data->done && data->size > data->maximumSize) {
264 data->size = data->maximumSize;
265 data->done = true;
266 space_left -= data->maximumSize;
267 sumStretch -= data->stretch;
268 if (data->expansive)
269 expandingCount--;
270 n--;
271 }
272 }
273 }
274 } while (n > 0 && surplus != deficit);
275 if (n == 0)
276 extraspace = space_left;
277 }
278
279 /*
280 As a last resort, we distribute the unwanted space equally
281 among the spacers (counting the start and end of the chain). We
282 could, but don't, attempt a sub-pixel allocation of the extra
283 space.
284 */
285 int extra = extraspace / (spacerCount + 2);
286 int p = pos + extra;
287 for (i = start; i < start+count; i++) {
288 QLayoutStruct *data = &chain[i];
289 data->pos = p;
290 p += data->size;
291 if (!data->empty)
292 p += data->effectiveSpacer(uniformSpacer: spacer) + extra;
293 }
294
295#ifdef QLAYOUT_EXTRA_DEBUG
296 qDebug() << "qGeomCalc" << "start" << start << "count" << count << "pos" << pos
297 << "space" << space << "spacer" << spacer;
298 for (i = start; i < start + count; ++i) {
299 qDebug() << i << ':' << chain[i].minimumSize << chain[i].smartSizeHint()
300 << chain[i].maximumSize << "stretch" << chain[i].stretch
301 << "empty" << chain[i].empty << "expansive" << chain[i].expansive
302 << "spacing" << chain[i].spacing;
303 qDebug() << "result pos" << chain[i].pos << "size" << chain[i].size;
304 }
305#endif
306}
307
308Q_WIDGETS_EXPORT QSize qSmartMinSize(const QSize &sizeHint, const QSize &minSizeHint,
309 const QSize &minSize, const QSize &maxSize,
310 const QSizePolicy &sizePolicy)
311{
312 QSize s(0, 0);
313
314 if (sizePolicy.horizontalPolicy() != QSizePolicy::Ignored) {
315 if (sizePolicy.horizontalPolicy() & QSizePolicy::ShrinkFlag)
316 s.setWidth(minSizeHint.width());
317 else
318 s.setWidth(qMax(a: sizeHint.width(), b: minSizeHint.width()));
319 }
320
321 if (sizePolicy.verticalPolicy() != QSizePolicy::Ignored) {
322 if (sizePolicy.verticalPolicy() & QSizePolicy::ShrinkFlag) {
323 s.setHeight(minSizeHint.height());
324 } else {
325 s.setHeight(qMax(a: sizeHint.height(), b: minSizeHint.height()));
326 }
327 }
328
329 s = s.boundedTo(otherSize: maxSize);
330 if (minSize.width() > 0)
331 s.setWidth(minSize.width());
332 if (minSize.height() > 0)
333 s.setHeight(minSize.height());
334
335 return s.expandedTo(otherSize: QSize(0,0));
336}
337
338Q_WIDGETS_EXPORT QSize qSmartMinSize(const QWidgetItem *i)
339{
340 QWidget *w = i->widget();
341 return qSmartMinSize(sizeHint: w->sizeHint(), minSizeHint: w->minimumSizeHint(),
342 minSize: w->minimumSize(), maxSize: w->maximumSize(),
343 sizePolicy: w->sizePolicy());
344}
345
346Q_WIDGETS_EXPORT QSize qSmartMinSize(const QWidget *w)
347{
348 return qSmartMinSize(sizeHint: w->sizeHint(), minSizeHint: w->minimumSizeHint(),
349 minSize: w->minimumSize(), maxSize: w->maximumSize(),
350 sizePolicy: w->sizePolicy());
351}
352
353Q_WIDGETS_EXPORT QSize qSmartMaxSize(const QSize &sizeHint,
354 const QSize &minSize, const QSize &maxSize,
355 const QSizePolicy &sizePolicy, Qt::Alignment align)
356{
357 if (align & Qt::AlignHorizontal_Mask && align & Qt::AlignVertical_Mask)
358 return QSize(QLAYOUTSIZE_MAX, QLAYOUTSIZE_MAX);
359 QSize s = maxSize;
360 QSize hint = sizeHint.expandedTo(otherSize: minSize);
361 if (s.width() == QWIDGETSIZE_MAX && !(align & Qt::AlignHorizontal_Mask))
362 if (!(sizePolicy.horizontalPolicy() & QSizePolicy::GrowFlag))
363 s.setWidth(hint.width());
364
365 if (s.height() == QWIDGETSIZE_MAX && !(align & Qt::AlignVertical_Mask))
366 if (!(sizePolicy.verticalPolicy() & QSizePolicy::GrowFlag))
367 s.setHeight(hint.height());
368
369 if (align & Qt::AlignHorizontal_Mask)
370 s.setWidth(QLAYOUTSIZE_MAX);
371 if (align & Qt::AlignVertical_Mask)
372 s.setHeight(QLAYOUTSIZE_MAX);
373 return s;
374}
375
376Q_WIDGETS_EXPORT QSize qSmartMaxSize(const QWidgetItem *i, Qt::Alignment align)
377{
378 QWidget *w = i->widget();
379 return qSmartMaxSize(sizeHint: w->sizeHint().expandedTo(otherSize: w->minimumSizeHint()), minSize: w->minimumSize(), maxSize: w->maximumSize(),
380 sizePolicy: w->sizePolicy(), align);
381}
382
383Q_WIDGETS_EXPORT QSize qSmartMaxSize(const QWidget *w, Qt::Alignment align)
384{
385 return qSmartMaxSize(sizeHint: w->sizeHint().expandedTo(otherSize: w->minimumSizeHint()), minSize: w->minimumSize(), maxSize: w->maximumSize(),
386 sizePolicy: w->sizePolicy(), align);
387}
388
389Q_WIDGETS_EXPORT int qSmartSpacing(const QLayout *layout, QStyle::PixelMetric pm)
390{
391 QObject *parent = layout->parent();
392 if (!parent) {
393 return -1;
394 } else if (parent->isWidgetType()) {
395 QWidget *pw = static_cast<QWidget *>(parent);
396 return pw->style()->pixelMetric(metric: pm, option: nullptr, widget: pw);
397 } else {
398 return static_cast<QLayout *>(parent)->spacing();
399 }
400}
401
402QT_END_NAMESPACE
403

source code of qtbase/src/widgets/kernel/qlayoutengine.cpp