1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qlayout.h"

    43 #include "private/qlayoutengine_p.h"

    44 

    45 #include "qvector.h"

    46 #include "qwidget.h"

    47 

    48 #include <qlist.h>

    49 #include <qalgorithms.h>

    50 

    51 #include <qdebug.h>

    52 

    53 QT_BEGIN_NAMESPACE

    54 

    55 //#define QLAYOUT_EXTRA_DEBUG

    56 

    57 typedef qint64 Fixed64;

    58 static inline Fixed64 toFixed(int i) { return (Fixed64)i * 256; }

    59 static inline int fRound(Fixed64 i) {

    60     return (i % 256 < 128) ? i / 256 : 1 + i / 256;

    61 }

    62 

    63 /*

    64   This is the main workhorse of the QGridLayout. It portions out

    65   available space to the chain's children.

    66 

    67   The calculation is done in fixed point: "fixed" variables are

    68   scaled by a factor of 256.

    69 

    70   If the layout runs "backwards" (i.e. RightToLeft or Up) the layout

    71   is computed mirror-reversed, and it's the caller's responsibility

    72   do reverse the values before use.

    73 

    74   chain contains input and output parameters describing the geometry.

    75   count is the count of items in the chain; pos and space give the

    76   interval (relative to parentWidget topLeft).

    77 */

    78 void qGeomCalc(QVector<QLayoutStruct> &chain, int start, int count,

    79                int pos, int space, int spacer)

    80 {

    81     int cHint = 0;

    82     int cMin = 0;

    83     int cMax = 0;

    84     int sumStretch = 0;

    85     int sumSpacing = 0;

    86 

    87     bool wannaGrow = false; // anyone who really wants to grow?

    88     //    bool canShrink = false; // anyone who could be persuaded to shrink?

    89 

    90     bool allEmptyNonstretch = true;

    91     int pendingSpacing = -1;

    92     int spacerCount = 0;

    93     int i;

    94 

    95     for (i = start; i < start + count; i++) {

    96         QLayoutStruct *data = &chain[i];

    97 

    98         data->done = false;

    99         cHint += data->smartSizeHint();

   100         cMin += data->minimumSize;

   101         cMax += data->maximumSize;

   102         sumStretch += data->stretch;

   103         if (!data->empty) {

   104             /*

   105                 Using pendingSpacing, we ensure that the spacing for the last

   106                 (non-empty) item is ignored.

   107             */

   108             if (pendingSpacing >= 0) {

   109                 sumSpacing += pendingSpacing;

   110                 ++spacerCount;

   111             }

   112             pendingSpacing = data->effectiveSpacer(spacer);

   113         }

   114         wannaGrow = wannaGrow || data->expansive || data->stretch > 0;

   115         allEmptyNonstretch = allEmptyNonstretch && !wannaGrow && data->empty;

   116     }

   117 

   118     int extraspace = 0;

   119 

   120     if (space < cMin + sumSpacing) {

   121         /*

   122           Less space than minimumSize; take from the biggest first

   123         */

   124 

   125         int minSize = cMin + sumSpacing;

   126 

   127         // shrink the spacers proportionally

   128         if (spacer >= 0) {

   129             spacer = minSize > 0 ? spacer * space / minSize : 0;

   130             sumSpacing = spacer * spacerCount;

   131         }

   132 

   133         QList<int> list;

   134 

   135         for (i = start; i < start + count; i++)

   136             list << chain.at(i).minimumSize;

   137 

   138         qSort(list);

   139 

   140         int space_left = space - sumSpacing;

   141 

   142         int sum = 0;

   143         int idx = 0;

   144         int space_used=0;

   145         int current = 0;

   146         while (idx < count && space_used < space_left) {

   147             current = list.at(idx);

   148             space_used = sum + current * (count - idx);

   149             sum += current;

   150             ++idx;

   151         }

   152         --idx;

   153         int deficit = space_used - space_left;

   154 

   155         int items = count - idx;

   156         /*

   157          * If we truncate all items to "current", we would get "deficit" too many pixels. Therefore, we have to remove

   158          * deficit/items from each item bigger than maxval. The actual value to remove is deficitPerItem + remainder/items

   159          * "rest" is the accumulated error from using integer arithmetic.

   160         */

   161         int deficitPerItem = deficit/items;

   162         int remainder = deficit % items;

   163         int maxval = current - deficitPerItem;

   164 

   165         int rest = 0;

   166         for (i = start; i < start + count; i++) {

   167             int maxv = maxval;

   168             rest += remainder;

   169             if (rest >= items) {

   170                 maxv--;

   171                 rest-=items;

   172             }

   173             QLayoutStruct *data = &chain[i];

   174             data->size = qMin(data->minimumSize, maxv);

   175             data->done = true;

   176         }

   177     } else if (space < cHint + sumSpacing) {

   178         /*

   179           Less space than smartSizeHint(), but more than minimumSize.

   180           Currently take space equally from each, as in Qt 2.x.

   181           Commented-out lines will give more space to stretchier

   182           items.

   183         */

   184         int n = count;

   185         int space_left = space - sumSpacing;

   186         int overdraft = cHint - space_left;

   187 

   188         // first give to the fixed ones:

   189         for (i = start; i < start + count; i++) {

   190             QLayoutStruct *data = &chain[i];

   191             if (!data->done

   192                  && data->minimumSize >= data->smartSizeHint()) {

   193                 data->size = data->smartSizeHint();

   194                 data->done = true;

   195                 space_left -= data->smartSizeHint();

   196                 // sumStretch -= data->stretch;

   197                 n--;

   198             }

   199         }

   200         bool finished = n == 0;

   201         while (!finished) {

   202             finished = true;

   203             Fixed64 fp_over = toFixed(overdraft);

   204             Fixed64 fp_w = 0;

   205 

   206             for (i = start; i < start+count; i++) {

   207                 QLayoutStruct *data = &chain[i];

   208                 if (data->done)

   209                     continue;

   210                 // if (sumStretch <= 0)

   211                 fp_w += fp_over / n;

   212                 // else

   213                 //    fp_w += (fp_over * data->stretch) / sumStretch;

   214                 int w = fRound(fp_w);

   215                 data->size = data->smartSizeHint() - w;

   216                 fp_w -= toFixed(w); // give the difference to the next

   217                 if (data->size < data->minimumSize) {

   218                     data->done = true;

   219                     data->size = data->minimumSize;

   220                     finished = false;

   221                     overdraft -= data->smartSizeHint() - data->minimumSize;

   222                     // sumStretch -= data->stretch;

   223                     n--;

   224                     break;

   225                 }

   226             }

   227         }

   228     } else { // extra space

   229         int n = count;

   230         int space_left = space - sumSpacing;

   231         // first give to the fixed ones, and handle non-expansiveness

   232         for (i = start; i < start + count; i++) {

   233             QLayoutStruct *data = &chain[i];

   234             if (!data->done

   235                 && (data->maximumSize <= data->smartSizeHint()

   236                     || (wannaGrow && !data->expansive && data->stretch == 0)

   237                     || (!allEmptyNonstretch && data->empty &&

   238                         !data->expansive && data->stretch == 0))) {

   239                 data->size = data->smartSizeHint();

   240                 data->done = true;

   241                 space_left -= data->size;

   242                 sumStretch -= data->stretch;

   243                 n--;

   244             }

   245         }

   246         extraspace = space_left;

   247 

   248         /*

   249           Do a trial distribution and calculate how much it is off.

   250           If there are more deficit pixels than surplus pixels, give

   251           the minimum size items what they need, and repeat.

   252           Otherwise give to the maximum size items, and repeat.

   253 

   254           Paul Olav Tvete has a wonderful mathematical proof of the

   255           correctness of this principle, but unfortunately this

   256           comment is too small to contain it.

   257         */

   258         int surplus, deficit;

   259         do {

   260             surplus = deficit = 0;

   261             Fixed64 fp_space = toFixed(space_left);

   262             Fixed64 fp_w = 0;

   263             for (i = start; i < start + count; i++) {

   264                 QLayoutStruct *data = &chain[i];

   265                 if (data->done)

   266                     continue;

   267                 extraspace = 0;

   268                 if (sumStretch <= 0)

   269                     fp_w += fp_space / n;

   270                 else

   271                     fp_w += (fp_space * data->stretch) / sumStretch;

   272                 int w = fRound(fp_w);

   273                 data->size = w;

   274                 fp_w -= toFixed(w); // give the difference to the next

   275                 if (w < data->smartSizeHint()) {

   276                     deficit +=  data->smartSizeHint() - w;

   277                 } else if (w > data->maximumSize) {

   278                     surplus += w - data->maximumSize;

   279                 }

   280             }

   281             if (deficit > 0 && surplus <= deficit) {

   282                 // give to the ones that have too little

   283                 for (i = start; i < start+count; i++) {

   284                     QLayoutStruct *data = &chain[i];

   285                     if (!data->done && data->size < data->smartSizeHint()) {

   286                         data->size = data->smartSizeHint();

   287                         data->done = true;

   288                         space_left -= data->smartSizeHint();

   289                         sumStretch -= data->stretch;

   290                         n--;

   291                     }

   292                 }

   293             }

   294             if (surplus > 0 && surplus >= deficit) {

   295                 // take from the ones that have too much

   296                 for (i = start; i < start + count; i++) {

   297                     QLayoutStruct *data = &chain[i];

   298                     if (!data->done && data->size > data->maximumSize) {

   299                         data->size = data->maximumSize;

   300                         data->done = true;

   301                         space_left -= data->maximumSize;

   302                         sumStretch -= data->stretch;

   303                         n--;

   304                     }

   305                 }

   306             }

   307         } while (n > 0 && surplus != deficit);

   308         if (n == 0)

   309             extraspace = space_left;

   310     }

   311 

   312     /*

   313       As a last resort, we distribute the unwanted space equally

   314       among the spacers (counting the start and end of the chain). We

   315       could, but don't, attempt a sub-pixel allocation of the extra

   316       space.

   317     */

   318     int extra = extraspace / (spacerCount + 2);

   319     int p = pos + extra;

   320     for (i = start; i < start+count; i++) {

   321         QLayoutStruct *data = &chain[i];

   322         data->pos = p;

   323         p += data->size;

   324         if (!data->empty)

   325             p += data->effectiveSpacer(spacer) + extra;

   326     }

   327 

   328 #ifdef QLAYOUT_EXTRA_DEBUG

   329     qDebug() << "qGeomCalc" << "start" << start <<  "count" << count <<  "pos" << pos

   330              <<  "space" << space <<  "spacer" << spacer;

   331     for (i = start; i < start + count; ++i) {

   332         qDebug() << i << ':' << chain[i].minimumSize << chain[i].smartSizeHint()

   333                  << chain[i].maximumSize << "stretch" << chain[i].stretch

   334                  << "empty" << chain[i].empty << "expansive" << chain[i].expansive

   335                  << "spacing" << chain[i].spacing;

   336         qDebug() << "result pos" << chain[i].pos << "size" << chain[i].size;

   337     }

   338 #endif

   339 }

   340 

   341 Q_GUI_EXPORT QSize qSmartMinSize(const QSize &sizeHint, const QSize &minSizeHint,

   342                                  const QSize &minSize, const QSize &maxSize,

   343                                  const QSizePolicy &sizePolicy)

   344 {

   345     QSize s(0, 0);

   346 

   347     if (sizePolicy.horizontalPolicy() != QSizePolicy::Ignored) {

   348         if (sizePolicy.horizontalPolicy() & QSizePolicy::ShrinkFlag)

   349             s.setWidth(minSizeHint.width());

   350         else

   351             s.setWidth(qMax(sizeHint.width(), minSizeHint.width()));

   352     }

   353 

   354     if (sizePolicy.verticalPolicy() != QSizePolicy::Ignored) {

   355         if (sizePolicy.verticalPolicy() & QSizePolicy::ShrinkFlag) {

   356             s.setHeight(minSizeHint.height());

   357         } else {

   358             s.setHeight(qMax(sizeHint.height(), minSizeHint.height()));

   359         }

   360     }

   361 

   362     s = s.boundedTo(maxSize);

   363     if (minSize.width() > 0)

   364         s.setWidth(minSize.width());

   365     if (minSize.height() > 0)

   366         s.setHeight(minSize.height());

   367 

   368     return s.expandedTo(QSize(0,0));

   369 }

   370 

   371 Q_GUI_EXPORT QSize qSmartMinSize(const QWidgetItem *i)

   372 {

   373     QWidget *w = ((QWidgetItem *)i)->widget();

   374     return qSmartMinSize(w->sizeHint(), w->minimumSizeHint(),

   375                             w->minimumSize(), w->maximumSize(),

   376                             w->sizePolicy());

   377 }

   378 

   379 Q_GUI_EXPORT QSize qSmartMinSize(const QWidget *w)

   380 {

   381     return qSmartMinSize(w->sizeHint(), w->minimumSizeHint(),

   382                             w->minimumSize(), w->maximumSize(),

   383                             w->sizePolicy());

   384 }

   385 

   386 Q_GUI_EXPORT QSize qSmartMaxSize(const QSize &sizeHint,

   387                                  const QSize &minSize, const QSize &maxSize,

   388                                  const QSizePolicy &sizePolicy, Qt::Alignment align)

   389 {

   390     if (align & Qt::AlignHorizontal_Mask && align & Qt::AlignVertical_Mask)

   391         return QSize(QLAYOUTSIZE_MAX, QLAYOUTSIZE_MAX);

   392     QSize s = maxSize;

   393     QSize hint = sizeHint.expandedTo(minSize);

   394     if (s.width() == QWIDGETSIZE_MAX && !(align & Qt::AlignHorizontal_Mask))

   395         if (!(sizePolicy.horizontalPolicy() & QSizePolicy::GrowFlag))

   396             s.setWidth(hint.width());

   397 

   398     if (s.height() == QWIDGETSIZE_MAX && !(align & Qt::AlignVertical_Mask))

   399         if (!(sizePolicy.verticalPolicy() & QSizePolicy::GrowFlag))

   400             s.setHeight(hint.height());

   401 

   402     if (align & Qt::AlignHorizontal_Mask)

   403         s.setWidth(QLAYOUTSIZE_MAX);

   404     if (align & Qt::AlignVertical_Mask)

   405         s.setHeight(QLAYOUTSIZE_MAX);

   406     return s;

   407 }

   408 

   409 Q_GUI_EXPORT QSize qSmartMaxSize(const QWidgetItem *i, Qt::Alignment align)

   410 {

   411     QWidget *w = ((QWidgetItem*)i)->widget();

   412 

   413     return qSmartMaxSize(w->sizeHint().expandedTo(w->minimumSizeHint()), w->minimumSize(), w->maximumSize(),

   414                             w->sizePolicy(), align);

   415 }

   416 

   417 Q_GUI_EXPORT QSize qSmartMaxSize(const QWidget *w, Qt::Alignment align)

   418 {

   419     return qSmartMaxSize(w->sizeHint().expandedTo(w->minimumSizeHint()), w->minimumSize(), w->maximumSize(),

   420                             w->sizePolicy(), align);

   421 }

   422 

   423 Q_GUI_EXPORT int qSmartSpacing(const QLayout *layout, QStyle::PixelMetric pm)

   424 {

   425     QObject *parent = layout->parent();

   426     if (!parent) {

   427         return -1;

   428     } else if (parent->isWidgetType()) {

   429         QWidget *pw = static_cast<QWidget *>(parent);

   430         return pw->style()->pixelMetric(pm, 0, pw);

   431     } else {

   432         return static_cast<QLayout *>(parent)->spacing();

   433     }

   434 }

   435 

   436 QT_END_NAMESPACE