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 "qlist.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(QList<QLayoutStruct> &chain, int start, int count, int pos, int space, int spacer)
77{
78 int cHint = 0;
79 int cMin = 0;
80 int cMax = 0;
81 int sumStretch = 0;
82 int sumSpacing = 0;
83 int expandingCount = 0;
84
85 bool allEmptyNonstretch = true;
86 int pendingSpacing = -1;
87 int spacerCount = 0;
88 int i;
89
90 for (i = start; i < start + count; i++) {
91 QLayoutStruct *data = &chain[i];
92
93 data->done = false;
94 cHint += data->smartSizeHint();
95 cMin += data->minimumSize;
96 cMax += data->maximumSize;
97 sumStretch += data->stretch;
98 if (!data->empty) {
99 /*
100 Using pendingSpacing, we ensure that the spacing for the last
101 (non-empty) item is ignored.
102 */
103 if (pendingSpacing >= 0) {
104 sumSpacing += pendingSpacing;
105 ++spacerCount;
106 }
107 pendingSpacing = data->effectiveSpacer(spacer);
108 }
109 if (data->expansive)
110 expandingCount++;
111 allEmptyNonstretch = allEmptyNonstretch && data->empty && !data->expansive && data->stretch <= 0;
112 }
113
114 int extraspace = 0;
115
116 if (space < cMin + sumSpacing) {
117 /*
118 Less space than minimumSize; take from the biggest first
119 */
120
121 int minSize = cMin + sumSpacing;
122
123 // shrink the spacers proportionally
124 if (spacer >= 0) {
125 spacer = minSize > 0 ? spacer * space / minSize : 0;
126 sumSpacing = spacer * spacerCount;
127 }
128
129 QVarLengthArray<int, 32> minimumSizes;
130 minimumSizes.reserve(count);
131
132 for (i = start; i < start + count; i++)
133 minimumSizes << chain.at(i).minimumSize;
134
135 std::sort(minimumSizes.begin(), minimumSizes.end());
136
137 int space_left = space - sumSpacing;
138
139 int sum = 0;
140 int idx = 0;
141 int space_used=0;
142 int current = 0;
143 while (idx < count && space_used < space_left) {
144 current = minimumSizes.at(idx);
145 space_used = sum + current * (count - idx);
146 sum += current;
147 ++idx;
148 }
149 --idx;
150 int deficit = space_used - space_left;
151
152 int items = count - idx;
153 /*
154 * If we truncate all items to "current", we would get "deficit" too many pixels. Therefore, we have to remove
155 * deficit/items from each item bigger than maxval. The actual value to remove is deficitPerItem + remainder/items
156 * "rest" is the accumulated error from using integer arithmetic.
157 */
158 int deficitPerItem = deficit/items;
159 int remainder = deficit % items;
160 int maxval = current - deficitPerItem;
161
162 int rest = 0;
163 for (i = start; i < start + count; i++) {
164 int maxv = maxval;
165 rest += remainder;
166 if (rest >= items) {
167 maxv--;
168 rest-=items;
169 }
170 QLayoutStruct *data = &chain[i];
171 data->size = qMin(data->minimumSize, maxv);
172 data->done = true;
173 }
174 } else if (space < cHint + sumSpacing) {
175 /*
176 Less space than smartSizeHint(), but more than minimumSize.
177 Currently take space equally from each, as in Qt 2.x.
178 Commented-out lines will give more space to stretchier
179 items.
180 */
181 int n = count;
182 int space_left = space - sumSpacing;
183 int overdraft = cHint - space_left;
184
185 // first give to the fixed ones:
186 for (i = start; i < start + count; i++) {
187 QLayoutStruct *data = &chain[i];
188 if (!data->done
189 && data->minimumSize >= data->smartSizeHint()) {
190 data->size = data->smartSizeHint();
191 data->done = true;
192 space_left -= data->smartSizeHint();
193 // sumStretch -= data->stretch;
194 n--;
195 }
196 }
197 bool finished = n == 0;
198 while (!finished) {
199 finished = true;
200 Fixed64 fp_over = toFixed(overdraft);
201 Fixed64 fp_w = 0;
202
203 for (i = start; i < start+count; i++) {
204 QLayoutStruct *data = &chain[i];
205 if (data->done)
206 continue;
207 // if (sumStretch <= 0)
208 fp_w += fp_over / n;
209 // else
210 // fp_w += (fp_over * data->stretch) / sumStretch;
211 int w = fRound(fp_w);
212 data->size = data->smartSizeHint() - w;
213 fp_w -= toFixed(w); // give the difference to the next
214 if (data->size < data->minimumSize) {
215 data->done = true;
216 data->size = data->minimumSize;
217 finished = false;
218 overdraft -= data->smartSizeHint() - data->minimumSize;
219 // sumStretch -= data->stretch;
220 n--;
221 break;
222 }
223 }
224 }
225 } else { // extra space
226 int n = count;
227 int space_left = space - sumSpacing;
228 // first give to the fixed ones, and handle non-expansiveness
229 for (i = start; i < start + count; i++) {
230 QLayoutStruct *data = &chain[i];
231 if (!data->done
232 && (data->maximumSize <= data->smartSizeHint()
233 || (!allEmptyNonstretch && data->empty &&
234 !data->expansive && data->stretch == 0))) {
235 data->size = data->smartSizeHint();
236 data->done = true;
237 space_left -= data->size;
238 sumStretch -= data->stretch;
239 if (data->expansive)
240 expandingCount--;
241 n--;
242 }
243 }
244 extraspace = space_left;
245
246 /*
247 Do a trial distribution and calculate how much it is off.
248 If there are more deficit pixels than surplus pixels, give
249 the minimum size items what they need, and repeat.
250 Otherwise give to the maximum size items, and repeat.
251
252 Paul Olav Tvete has a wonderful mathematical proof of the
253 correctness of this principle, but unfortunately this
254 comment is too small to contain it.
255 */
256 int surplus, deficit;
257 do {
258 surplus = deficit = 0;
259 Fixed64 fp_space = toFixed(space_left);
260 Fixed64 fp_w = 0;
261 for (i = start; i < start + count; i++) {
262 QLayoutStruct *data = &chain[i];
263 if (data->done)
264 continue;
265 extraspace = 0;
266 if (sumStretch > 0) {
267 fp_w += (fp_space * data->stretch) / sumStretch;
268 } else if (expandingCount > 0) {
269 fp_w += (fp_space * (data->expansive ? 1 : 0)) / expandingCount;
270 } else {
271 fp_w += fp_space * 1 / n;
272 }
273 int w = fRound(fp_w);
274 data->size = w;
275 fp_w -= toFixed(w); // give the difference to the next
276 if (w < data->smartSizeHint()) {
277 deficit += data->smartSizeHint() - w;
278 } else if (w > data->maximumSize) {
279 surplus += w - data->maximumSize;
280 }
281 }
282 if (deficit > 0 && surplus <= deficit) {
283 // give to the ones that have too little
284 for (i = start; i < start+count; i++) {
285 QLayoutStruct *data = &chain[i];
286 if (!data->done && data->size < data->smartSizeHint()) {
287 data->size = data->smartSizeHint();
288 data->done = true;
289 space_left -= data->smartSizeHint();
290 sumStretch -= data->stretch;
291 if (data->expansive)
292 expandingCount--;
293 n--;
294 }
295 }
296 }
297 if (surplus > 0 && surplus >= deficit) {
298 // take from the ones that have too much
299 for (i = start; i < start + count; i++) {
300 QLayoutStruct *data = &chain[i];
301 if (!data->done && data->size > data->maximumSize) {
302 data->size = data->maximumSize;
303 data->done = true;
304 space_left -= data->maximumSize;
305 sumStretch -= data->stretch;
306 if (data->expansive)
307 expandingCount--;
308 n--;
309 }
310 }
311 }
312 } while (n > 0 && surplus != deficit);
313 if (n == 0)
314 extraspace = space_left;
315 }
316
317 /*
318 As a last resort, we distribute the unwanted space equally
319 among the spacers (counting the start and end of the chain). We
320 could, but don't, attempt a sub-pixel allocation of the extra
321 space.
322 */
323 int extra = extraspace / (spacerCount + 2);
324 int p = pos + extra;
325 for (i = start; i < start+count; i++) {
326 QLayoutStruct *data = &chain[i];
327 data->pos = p;
328 p += data->size;
329 if (!data->empty)
330 p += data->effectiveSpacer(spacer) + extra;
331 }
332
333#ifdef QLAYOUT_EXTRA_DEBUG
334 qDebug() << "qGeomCalc" << "start" << start << "count" << count << "pos" << pos
335 << "space" << space << "spacer" << spacer;
336 for (i = start; i < start + count; ++i) {
337 qDebug() << i << ':' << chain[i].minimumSize << chain[i].smartSizeHint()
338 << chain[i].maximumSize << "stretch" << chain[i].stretch
339 << "empty" << chain[i].empty << "expansive" << chain[i].expansive
340 << "spacing" << chain[i].spacing;
341 qDebug() << "result pos" << chain[i].pos << "size" << chain[i].size;
342 }
343#endif
344}
345
346Q_WIDGETS_EXPORT QSize qSmartMinSize(const QSize &sizeHint, const QSize &minSizeHint,
347 const QSize &minSize, const QSize &maxSize,
348 const QSizePolicy &sizePolicy)
349{
350 QSize s(0, 0);
351
352 if (sizePolicy.horizontalPolicy() != QSizePolicy::Ignored) {
353 if (sizePolicy.horizontalPolicy() & QSizePolicy::ShrinkFlag)
354 s.setWidth(minSizeHint.width());
355 else
356 s.setWidth(qMax(sizeHint.width(), minSizeHint.width()));
357 }
358
359 if (sizePolicy.verticalPolicy() != QSizePolicy::Ignored) {
360 if (sizePolicy.verticalPolicy() & QSizePolicy::ShrinkFlag) {
361 s.setHeight(minSizeHint.height());
362 } else {
363 s.setHeight(qMax(sizeHint.height(), minSizeHint.height()));
364 }
365 }
366
367 s = s.boundedTo(maxSize);
368 if (minSize.width() > 0)
369 s.setWidth(minSize.width());
370 if (minSize.height() > 0)
371 s.setHeight(minSize.height());
372
373 return s.expandedTo(QSize(0,0));
374}
375
376Q_WIDGETS_EXPORT QSize qSmartMinSize(const QWidgetItem *i)
377{
378 QWidget *w = i->widget();
379 return qSmartMinSize(w->sizeHint(), w->minimumSizeHint(),
380 w->minimumSize(), w->maximumSize(),
381 w->sizePolicy());
382}
383
384Q_WIDGETS_EXPORT QSize qSmartMinSize(const QWidget *w)
385{
386 return qSmartMinSize(w->sizeHint(), w->minimumSizeHint(),
387 w->minimumSize(), w->maximumSize(),
388 w->sizePolicy());
389}
390
391Q_WIDGETS_EXPORT QSize qSmartMaxSize(const QSize &sizeHint,
392 const QSize &minSize, const QSize &maxSize,
393 const QSizePolicy &sizePolicy, Qt::Alignment align)
394{
395 if (align & Qt::AlignHorizontal_Mask && align & Qt::AlignVertical_Mask)
396 return QSize(QLAYOUTSIZE_MAX, QLAYOUTSIZE_MAX);
397 QSize s = maxSize;
398 QSize hint = sizeHint.expandedTo(minSize);
399 if (s.width() == QWIDGETSIZE_MAX && !(align & Qt::AlignHorizontal_Mask))
400 if (!(sizePolicy.horizontalPolicy() & QSizePolicy::GrowFlag))
401 s.setWidth(hint.width());
402
403 if (s.height() == QWIDGETSIZE_MAX && !(align & Qt::AlignVertical_Mask))
404 if (!(sizePolicy.verticalPolicy() & QSizePolicy::GrowFlag))
405 s.setHeight(hint.height());
406
407 if (align & Qt::AlignHorizontal_Mask)
408 s.setWidth(QLAYOUTSIZE_MAX);
409 if (align & Qt::AlignVertical_Mask)
410 s.setHeight(QLAYOUTSIZE_MAX);
411 return s;
412}
413
414Q_WIDGETS_EXPORT QSize qSmartMaxSize(const QWidgetItem *i, Qt::Alignment align)
415{
416 QWidget *w = i->widget();
417 return qSmartMaxSize(w->sizeHint().expandedTo(w->minimumSizeHint()), w->minimumSize(), w->maximumSize(),
418 w->sizePolicy(), align);
419}
420
421Q_WIDGETS_EXPORT QSize qSmartMaxSize(const QWidget *w, Qt::Alignment align)
422{
423 return qSmartMaxSize(w->sizeHint().expandedTo(w->minimumSizeHint()), w->minimumSize(), w->maximumSize(),
424 w->sizePolicy(), align);
425}
426
427Q_WIDGETS_EXPORT int qSmartSpacing(const QLayout *layout, QStyle::PixelMetric pm)
428{
429 QObject *parent = layout->parent();
430 if (!parent) {
431 return -1;
432 } else if (parent->isWidgetType()) {
433 QWidget *pw = static_cast<QWidget *>(parent);
434 return pw->style()->pixelMetric(pm, nullptr, pw);
435 } else {
436 return static_cast<QLayout *>(parent)->spacing();
437 }
438}
439
440QT_END_NAMESPACE
441