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

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