WildReanimator

packager.cpp

Nov 23rd, 2012
1,706
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "packager.h"
  2. #include "renderarea.h"
  3.  
  4. #include <QFile>
  5. #include <QTextStream>
  6. #include <QtAlgorithms>
  7. #include <cmath>
  8.  
  9. ///////////////////////////////////////////////////////////////////////////////
  10. //  Packager class implementation
  11. ///////////////////////////////////////////////////////////////////////////////
  12.  
  13. void Packager::init(QString filename) {
  14.     QFile file(filename);
  15.  
  16.     _rectangles.clear();
  17.     if (file.open(QIODevice::ReadOnly | QIODevice::Text)) {
  18.         QTextStream in(&file);
  19.         while (!in.atEnd()) {
  20.             QStringList line = in.readLine().split(",");
  21.             QRect rect;
  22.             if (!line.isEmpty()) {
  23.                 rect.setRect(0, 0, line[0].toInt(), line[1].toInt());
  24.                 _rectangles.push_back(rect);
  25.             }
  26.         }
  27.     }
  28.     file.close();
  29. }
  30.  
  31. int Packager::getSize(void)
  32. {
  33.     return rectangles.size();
  34. }
  35.  
  36. void Packager::UseAlgorithm(void)
  37. {
  38.     rectangles.clear();
  39.     rectangles = algorithm->pack(_rectangles);
  40. }
  41.  
  42. void Packager::SetAlgorithm(Algorithm *a)
  43. {
  44.     algorithm = a;
  45. }
  46.  
  47. const QRect Packager::Level::put(const QRect &rect, bool f, bool leftJustified)
  48. {
  49.     QRect newRect;
  50.  
  51.     if (f) {
  52.         if (leftJustified) {
  53.             newRect.setRect(floor, RenderArea::STRIPH - (bottom + rect.height() + 1),
  54.                             rect.width(), rect.height());
  55.         } else {
  56.             // 'ceiling' is used for right-justified rectangles packed on the floor
  57.             newRect.setRect(RenderArea::STRIPW - (ceiling + rect.width()),
  58.                             RenderArea::STRIPH - (bottom + rect.height() + 1),
  59.                             rect.width(), rect.height());
  60.             ceiling += rect.width();
  61.         }
  62.         floor += rect.width();
  63.     } else {
  64.         newRect.setRect(RenderArea::STRIPW - (ceiling + rect.width()),
  65.                         RenderArea::STRIPH - (bottom + height + 1),
  66.                         rect.width(), rect.height());
  67.         ceiling += rect.width();
  68.     }
  69.  
  70.     return newRect;
  71. }
  72.  
  73. bool Packager::Level::ceilingFeasible(const QRect &rect, const QList<QRect> existing)
  74. {
  75.     QRect testRect;
  76.     testRect.setRect(RenderArea::STRIPW - (ceiling + rect.width()),
  77.                      RenderArea::STRIPH - (bottom + height + 1),
  78.                      rect.width(), rect.height());
  79.     bool intersected = false;
  80.     for (int i = 0; i < existing.size(); i++) {
  81.         if (testRect.intersects(existing[i])) {
  82.             intersected = true;
  83.             break;
  84.         }
  85.     }
  86.     bool fit = rect.width() <= (RenderArea::STRIPW - ceiling - initW);
  87.     return fit && !intersected;
  88. }
  89.  
  90. bool Packager::Level::floorFeasible(const QRect &rect)
  91. {
  92.     return rect.width() <= (RenderArea::STRIPW - floor);
  93. }
  94.  
  95. int Packager::Level::getSpace(bool f)
  96. {
  97.     if (f) {
  98.         return RenderArea::STRIPW - floor;
  99.     } else {
  100.         return RenderArea::STRIPW - ceiling - initW;
  101.     }
  102. }
  103.  
  104. ///////////////////////////////////////////////////////////////////////////////
  105. //  Algorithm class implementation
  106. ///////////////////////////////////////////////////////////////////////////////
  107.  
  108. static bool decreasingHeightComparsion(const QRect &r1, const QRect &r2)
  109. {
  110.     return r1.height() >= r2.height();
  111. }
  112.  
  113. static bool decreasingWidthComparsion(const QRect &r1, const QRect &r2)
  114. {
  115.     return r1.width() >= r2.width();
  116. }
  117.  
  118. const QList<QRect> NFDH::pack(const QList<QRect> rects)
  119. {
  120.     QList<QRect> unpacked = rects;
  121.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  122.     QList<Packager::Level> levels;
  123.     Packager::Level level(0, unpacked[0].height());
  124.     QList<QRect> packed;
  125.  
  126.     packed.push_back(level.put(unpacked[0]));
  127.     levels.push_back(level);
  128.  
  129.     for (int i = 1; i < unpacked.size(); i++) {
  130.         if (levels.last().floorFeasible(unpacked[i])) {
  131.             packed.push_back(levels.last().put(unpacked[i]));
  132.         } else {
  133.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  134.                                      unpacked[i].height());
  135.             packed.push_back(newLevel.put(unpacked[i]));
  136.             levels.push_back(newLevel);
  137.         }
  138.     }
  139.     return packed;
  140. }
  141.  
  142. const QList<QRect> FFDH::pack(const QList<QRect> rects)
  143. {
  144.     QList<QRect> unpacked = rects;
  145.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  146.     QList<Packager::Level> levels;
  147.     Packager::Level level(0, unpacked[0].height());
  148.     QList<QRect> packed;
  149.  
  150.     packed.push_back(level.put(unpacked[0]));
  151.     levels.push_back(level);
  152.  
  153.     for (int i = 1; i < unpacked.size(); i++) {
  154.         int found = -1;
  155.         for (int j = 0; j < levels.size(); j++) {
  156.             if (levels[j].floorFeasible(unpacked[i])) {
  157.                 found = j;
  158.                 break;
  159.             }
  160.         }
  161.         if (found > -1) {
  162.             packed.push_back(levels[found].put(unpacked[i]));
  163.         } else {
  164.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  165.                                      unpacked[i].height());
  166.             packed.push_back(newLevel.put(unpacked[i]));
  167.             levels.push_back(newLevel);
  168.         }
  169.     }
  170.     return packed;
  171. }
  172.  
  173. const QList<QRect> BFDH::pack(const QList<QRect> rects)
  174. {
  175.     QList<QRect> unpacked = rects;
  176.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  177.     QList<Packager::Level> levels;
  178.     Packager::Level level(0, unpacked[0].height());
  179.     QList<QRect> packed;
  180.  
  181.     packed.push_back(level.put(unpacked[0]));
  182.     levels.push_back(level);
  183.  
  184.     for (int i = 1; i < unpacked.size(); i++) {
  185.         int found = -1;
  186.         int min = RenderArea::STRIPW;
  187.         for (int j = 0; j < levels.size(); j++) {
  188.             if (levels[j].floorFeasible(unpacked[i])) {
  189.                 if (levels[j].getSpace() < min) {
  190.                     found = j;
  191.                     min = levels[j].getSpace();
  192.                 }
  193.             }
  194.         }
  195.         if (found > -1) {
  196.             packed.push_back(levels[found].put(unpacked[i]));
  197.         } else {
  198.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  199.                                      unpacked[i].height());
  200.             packed.push_back(newLevel.put(unpacked[i]));
  201.             levels.push_back(newLevel);
  202.         }
  203.     }
  204.     return packed;
  205. }
  206.  
  207. const QList<QRect> KP01::pack(const QList<QRect> rects)
  208. {
  209.     QList<QRect> unpacked = rects;
  210.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  211.     QList<Packager::Level> levels;
  212.     QList<QRect> packed;
  213.     int b = 0;
  214.  
  215.     while (!unpacked.isEmpty()) {
  216.         Packager::Level level(b, unpacked.first().height());
  217.         levels.push_back(level);
  218.         b += unpacked.first().height();
  219.         packed.push_back(levels.last().put(unpacked.first()));
  220.         unpacked.removeFirst();
  221.         // build dynamic matrix for KP01 instance
  222.         int maxWidth = RenderArea::STRIPW - packed.last().width();
  223.         QVector<QVector<int> > knap;
  224.         for (int i = 0; i < unpacked.size() + 1; i++) {
  225.             QVector<int> inner(maxWidth);
  226.             inner[0] = 0;
  227.             knap.push_back(inner);
  228.         }
  229.         for (int k = 1; k <= unpacked.size(); k++) {
  230.             for (int y = 1; y <= maxWidth; y++) {
  231.                 if (y < unpacked[k - 1].width()) {
  232.                     knap[k][y - 1] = knap[k - 1][y - 1];
  233.                 } else if (y > unpacked[k - 1].width()) {
  234.                     knap[k][y - 1] = qMax(knap[k - 1][y - 1],
  235.                                           knap[k - 1][y - 1 - unpacked[k - 1].width()]
  236.                                           + unpacked[k - 1].width()*unpacked[k - 1].height());
  237.                 } else {
  238.                     knap[k][y - 1] = qMax(knap[k - 1][y - 1],
  239.                                           unpacked[k - 1].width()*unpacked[k - 1].height());
  240.                 }
  241.             }
  242.         }
  243.         // find solution using the matrix
  244.         int k = unpacked.size();
  245.         int solution[k];
  246.         for (int j = 0; j < k; j++) {
  247.             solution[j] = 0;
  248.         }
  249.         while(k > 0 && maxWidth > 0)
  250.         {
  251.             if(knap[k][maxWidth - 1]!=knap[k-1][maxWidth - 1])
  252.             {
  253.                 solution[k-1]=1;
  254.                 maxWidth -= unpacked[k-1].width();
  255.             }
  256.             k--;
  257.         }
  258.         // pack selected rectangles
  259.         int removed = 0;
  260.         for (int i = 0; i < unpacked.size(); i++) {
  261.             if (solution[i]) {
  262.                 packed.push_back(levels.last().put(unpacked[i - removed]));
  263.                 unpacked.removeAt(i - removed); // when remove, index is shifted
  264.                 removed++;
  265.             }
  266.         }
  267.     }
  268.     return packed;
  269. }
  270.  
  271. const QList<QRect> SF::pack(const QList<QRect> rects)
  272. {
  273.     QList<Sf> unpacked;
  274.     QList<QRect> selected;
  275.  
  276.     // without loss of generality, all dimensions are scaled to Strip Width.
  277.     for (int i = 0; i < rects.size(); i++) {
  278.         Sf scaledRect;
  279.         scaledRect.rect = rects[i];
  280.         scaledRect.scaledWidth =   static_cast<qreal>(rects[i].width())
  281.                                  / static_cast<qreal>(RenderArea::STRIPW);
  282.         scaledRect.packedFirst = (scaledRect.scaledWidth >   static_cast<qreal>(1)
  283.                                                            / static_cast<qreal>(2));
  284.         unpacked.push_back(scaledRect);
  285.         if (   scaledRect.packedFirst
  286.             && scaledRect.scaledWidth >   static_cast<qreal>(2)
  287.                                         / static_cast<qreal>(3)) {
  288.             selected.push_back(rects[i]);
  289.         }
  290.     }
  291.     QList<Packager::Level> levels;
  292.     QList<QRect> packed;
  293.     if (!selected.isEmpty()) {
  294.         qSort(selected.begin(), selected.end(), decreasingHeightComparsion);
  295.         // pack selected rectangles those of with > 2/3 using FFDH on L1
  296.         Packager::Level level(0, selected[0].height());
  297.  
  298.         packed.push_back(level.put(selected[0]));
  299.         levels.push_back(level);
  300.  
  301.         for (int i = 1; i < selected.size(); i++) {
  302.             int found = -1;
  303.             for (int j = 0; j < levels.size(); j++) {
  304.                 if (levels[j].floorFeasible(selected[i])) {
  305.                     found = j;
  306.                     break;
  307.                 }
  308.             }
  309.             if (found > -1) {
  310.                 packed.push_back(levels[found].put(selected[i]));
  311.             } else {
  312.                 Packager::Level newLevel(levels.last().bottom + levels.last().height,
  313.                                          selected[i].height());
  314.                 packed.push_back(newLevel.put(selected[i]));
  315.                 levels.push_back(newLevel);
  316.             }
  317.         }
  318.     }
  319.     // pack selected rectangles those of with <= 2/3 using FFDH (from the next level)
  320.     selected.clear();
  321.     for (int i = 0; i < unpacked.size(); i++) {
  322.         if (   unpacked[i].packedFirst
  323.             && unpacked[i].scaledWidth <=   static_cast<qreal>(2)
  324.                                           / static_cast<qreal>(3)) {
  325.             selected.push_back(unpacked[i].rect);
  326.         }
  327.     }
  328.     int nextLevelInd = levels.size();
  329.     if (!selected.isEmpty()) {
  330.         qSort(selected.begin(), selected.end(), decreasingWidthComparsion);
  331.  
  332.         Packager::Level nextLevel(levels.last().bottom + levels.last().height,
  333.                                   selected[0].height());
  334.         packed.push_back(nextLevel.put(selected[0]));
  335.         levels.push_back(nextLevel);
  336.  
  337.         for (int i = 1; i < selected.size(); i++) {
  338.             int found = -1;
  339.             for (int j = nextLevelInd; j < levels.size(); j++) {
  340.                 if (levels[j].floorFeasible(selected[i])) {
  341.                     found = j;
  342.                     break;
  343.                 }
  344.             }
  345.             if (found > -1) {
  346.                 packed.push_back(levels[found].put(selected[i]));
  347.             } else {
  348.                 Packager::Level newLevel(levels.last().bottom + levels.last().height,
  349.                                          selected[i].height());
  350.                 packed.push_back(newLevel.put(selected[i]));
  351.                 levels.push_back(newLevel);
  352.             }
  353.         }
  354.     }
  355.     // calc the R region
  356.     int regionBottom = levels[nextLevelInd].bottom;
  357.     int regionWidth = levels[nextLevelInd].getSpace();
  358.     int regionHeight = 0;
  359.     for (int i = nextLevelInd; i < levels.size(); i++) {
  360.         regionHeight += levels[i].height;
  361.     }
  362.     // pack selected rectangles those of with > 2/3 into R
  363.     selected.clear();
  364.     for (int i = 0; i < unpacked.size(); i++) {
  365.         if (!unpacked[i].packedFirst) {
  366.             selected.push_back(unpacked[i].rect);
  367.         }
  368.     }
  369.     if (!selected.isEmpty()) {
  370.         qSort(selected.begin(), selected.end(), decreasingHeightComparsion);
  371.         QList<Packager::Level> regionLevels;
  372.         int fit = 0;
  373.         QList<QRect> remaining;
  374.         while (selected[fit].height() > regionHeight) {
  375.             remaining.push_back(selected[fit++]);
  376.         }
  377.         Packager::Level rLevel(regionBottom, selected[fit].height(),
  378.                                RenderArea::STRIPW - regionWidth);
  379.         packed.push_back(rLevel.put(selected[fit]));
  380.         regionLevels.push_back(rLevel);
  381.         int regionCapacity = regionHeight - rLevel.height;
  382.         for (int i = fit + 1; i < selected.size(); i++) {
  383.             int found = -1;
  384.             for (int j = 0; j < regionLevels.size(); j++) {
  385.                 if (regionLevels[j].floorFeasible(selected[i])) {
  386.                     found = j;
  387.                     break;
  388.                 }
  389.             }
  390.             if (found > -1) { // space on existing level in R
  391.                 packed.push_back(regionLevels[found].put(selected[i]));
  392.             } else if (selected[i].height() <= regionCapacity ){ // remaining space of R
  393.                 Packager::Level newLevel(regionLevels.last().bottom + regionLevels.last().height,
  394.                                          selected[i].height(), RenderArea::STRIPW - regionWidth);
  395.                 packed.push_back(newLevel.put(selected[i]));
  396.                 regionLevels.push_back(newLevel);
  397.                 regionCapacity -= newLevel.height;
  398.             } else { // no space, skip
  399.                 remaining.push_back(selected[i]);
  400.             }
  401.         }
  402.         if (!remaining.isEmpty()) { // pack all other over L1
  403.             int overInd = levels.size();
  404.             Packager::Level level(levels.last().bottom + levels.last().height,
  405.                                   remaining[0].height());
  406.             packed.push_back(level.put(remaining[0]));
  407.             levels.push_back(level);
  408.  
  409.             for (int i = 1; i < remaining.size(); i++) {
  410.                 int found = -1;
  411.                 for (int j = overInd; j < levels.size(); j++) {
  412.                     if (levels[j].floorFeasible(remaining[i])) {
  413.                         found = j;
  414.                         break;
  415.                     }
  416.                 }
  417.                 if (found > -1) {
  418.                     packed.push_back(levels[found].put(remaining[i]));
  419.                 } else {
  420.                     Packager::Level newLevel(levels.last().bottom + levels.last().height,
  421.                                              remaining[i].height());
  422.                     packed.push_back(newLevel.put(remaining[i]));
  423.                     levels.push_back(newLevel);
  424.                 }
  425.             }
  426.         }
  427.     }
  428.     return packed;
  429. }
  430.  
  431. const QList<QRect> JOIN::pack(const QList<QRect> rects)
  432. {
  433.     QList<QRect> unpacked = rects;
  434.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  435.     QList<QRect> joined = unpacked;
  436.  
  437.     int j = 0;
  438.     int removed = 0;
  439.     while (j + 1 < unpacked.size()) {
  440.         if (   static_cast<qreal>((unpacked[j].height() - unpacked[j + 1].height()))
  441.             /  static_cast<qreal>(unpacked[j].height()) <= _gamma
  442.             && unpacked[j].width() + unpacked[j + 1].width() <= RenderArea::STRIPW) {
  443.             joined[j - removed].setWidth(unpacked[j].width() + unpacked[j + 1].width());
  444.             joined.removeAt(j + 1 - removed++);
  445.             j++;
  446.         }
  447.         j++;
  448.     }
  449.     // pack with FFDH
  450.     QList<Packager::Level> levels;
  451.     Packager::Level level(0, unpacked[0].height());
  452.     QList<QRect> packedFFDH;
  453.  
  454.     int rectInd = 0;
  455.     int joinInd = 0;
  456.  
  457.     packedFFDH.push_back(level.put(unpacked[rectInd]));
  458.     if (joined[joinInd++].width() > unpacked[rectInd++].width()) {
  459.         packedFFDH.push_back(level.put(unpacked[rectInd++]));
  460.     }
  461.     levels.push_back(level);
  462.  
  463.     while (joinInd < joined.size()) {
  464.         int found = -1;
  465.         for (int k = 0; k < levels.size(); k++) {
  466.             if (levels[k].floorFeasible(joined[joinInd])) {
  467.                 found = k;
  468.                 break;
  469.             }
  470.         }
  471.         if (found > -1) {
  472.             packedFFDH.push_back(levels[found].put(unpacked[rectInd]));
  473.             if (joined[joinInd++].width() > unpacked[rectInd++].width()) {
  474.                 packedFFDH.push_back(levels[found].put(unpacked[rectInd++]));
  475.             }
  476.         } else {
  477.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  478.                                      unpacked[rectInd].height());
  479.             packedFFDH.push_back(newLevel.put(unpacked[rectInd]));
  480.             if (joined[joinInd++].width() > unpacked[rectInd++].width()) {
  481.                 packedFFDH.push_back(newLevel.put(unpacked[rectInd++]));
  482.             }
  483.             levels.push_back(newLevel);
  484.         }
  485.     }
  486.     int packHeightFFDH = levels.last().bottom + levels.last().height;
  487.     // pack with NFDH
  488.     levels.clear();
  489.     Packager::Level l(0, unpacked[0].height());
  490.     QList<QRect> packedNFDH;
  491.  
  492.     rectInd = 0;
  493.     joinInd = 0;
  494.  
  495.     packedNFDH.push_back(l.put(unpacked[rectInd]));
  496.     if (joined[joinInd++].width() > unpacked[rectInd++].width()) {
  497.         packedNFDH.push_back(l.put(unpacked[rectInd++]));
  498.     }
  499.     levels.push_back(l);
  500.  
  501.     while (joinInd < joined.size()) {
  502.         if (levels.last().floorFeasible(joined[joinInd])) {
  503.             packedNFDH.push_back(levels.last().put(unpacked[rectInd]));
  504.             if (joined[joinInd++].width() > unpacked[rectInd++].width()) {
  505.                 packedNFDH.push_back(levels.last().put(unpacked[rectInd++]));
  506.             }
  507.         } else {
  508.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  509.                                      unpacked[rectInd].height());
  510.             packedNFDH.push_back(newLevel.put(unpacked[rectInd]));
  511.             if (joined[joinInd++].width() > unpacked[rectInd++].width()) {
  512.                 packedNFDH.push_back(newLevel.put(unpacked[rectInd++]));
  513.             }
  514.             levels.push_back(newLevel);
  515.         }
  516.     }
  517.     return   (levels.last().bottom + levels.last().height < packHeightFFDH)
  518.             ? packedNFDH
  519.             : packedFFDH;
  520. }
  521.  
  522. const QList<QRect> FCNR::pack(const QList<QRect> rects)
  523. {
  524.     QList<QRect> unpacked = rects;
  525.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  526.  
  527.     QList<Packager::Level> levels;
  528.     Packager::Level level(0, unpacked[0].height(), 0, unpacked[0].width());
  529.     QList<QRect> packed;
  530.  
  531.     packed.push_back(level.put(unpacked[0]));
  532.     levels.push_back(level);
  533.  
  534.     for (int i = 1; i < unpacked.size(); i++) {
  535.         int found = -1;
  536.         int min = RenderArea::STRIPW;
  537.         for (int j = 0; j < levels.size(); j++) {
  538.             if (levels[j].floorFeasible(unpacked[i])) {
  539.                 if (levels[j].getSpace() < min) {
  540.                     found = j;
  541.                     min = levels[j].getSpace();
  542.                 }
  543.             }
  544.         }
  545.         if (found > -1) { // floor-pack on existing level
  546.             packed.push_back(levels[found].put(unpacked[i]));
  547.         } else {
  548.             int found = -1;
  549.             int min = RenderArea::STRIPW;
  550.             for (int j = 0; j < levels.size(); j++) {
  551.                 if (levels[j].ceilingFeasible(unpacked[i], packed)) {
  552.                     if (levels[j].getSpace(false) < min) {
  553.                         found = j;
  554.                         min = levels[j].getSpace(false);
  555.                     }
  556.                 }
  557.             }
  558.             if (found > -1) { // ceiling-pack on existing level
  559.                 packed.push_back(levels[found].put(unpacked[i], false));
  560.             } else { // a new level
  561.                 Packager::Level newLevel(levels.last().bottom + levels.last().height,
  562.                                          unpacked[i].height(), 0, unpacked[i].width());
  563.                 packed.push_back(newLevel.put(unpacked[i]));
  564.                 levels.push_back(newLevel);
  565.             }
  566.         }
  567.     }
  568.     return packed;
  569. }
  570.  
  571. const QList<QRect> Sleator::pack(const QList<QRect> rects)
  572. {
  573.     QList<QRect> unpacked;
  574.     QList<QRect> selected;
  575.  
  576.     // select rectangles wider than 1/2 of Strip Width.
  577.     for (int i = 0; i < rects.size(); i++) {
  578.         if (rects[i].width() > RenderArea::STRIPW / 2) {
  579.             selected.push_back(rects[i]);
  580.         } else {
  581.             unpacked.push_back(rects[i]);
  582.         }
  583.     }
  584.     QList<QRect> packed;
  585.     int hStack = 0;
  586.     // stack rectangles of width greater than 1/2, if any
  587.     for (int i = 0; i < selected.size(); i++) {
  588.         QRect newRect;
  589.         newRect.setRect(0, RenderArea::STRIPH - (hStack + selected[i].height() + 1),
  590.                         selected[i].width(), selected[i].height());
  591.         packed.push_back(newRect);
  592.         hStack += selected[i].height();
  593.     }
  594.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  595.     int hLeft = hStack + unpacked[0].height();
  596.     int hRight = 0;
  597.     int ind = 0;
  598.     int x = 0;
  599.     while (unpacked[ind].width() <= RenderArea::STRIPW - x) { // pack layer, compute hLeft, hRight
  600.         QRect newRect;
  601.         newRect.setRect(x, RenderArea::STRIPH - (hStack + unpacked[ind].height() + 1),
  602.                         unpacked[ind].width(), unpacked[ind].height());
  603.         packed.push_back(newRect);
  604.         x       += unpacked[ind].width();
  605.         if (hRight == 0 && x >= RenderArea::STRIPW / 2) {
  606.             hRight = hStack + unpacked[ind].height();
  607.         }
  608.         ind++;
  609.     }
  610.     while (ind < unpacked.size()) { // pack remaining
  611.         QRect newRect;
  612.         if (hRight < hLeft && unpacked[ind].width() <= RenderArea::STRIPW / 2) {
  613.             newRect.setRect(RenderArea::STRIPW / 2,
  614.                             RenderArea::STRIPH - (hRight + unpacked[ind].height() + 1),
  615.                             unpacked[ind].width(), unpacked[ind].height());
  616.             hRight += unpacked[ind].height();
  617.         } else {
  618.             newRect.setRect(0, RenderArea::STRIPH - (hLeft + unpacked[ind].height() + 1),
  619.                             unpacked[ind].width(), unpacked[ind].height());
  620.             hLeft += unpacked[ind].height();
  621.         }
  622.         packed.push_back(newRect);
  623.         ind++;
  624.     }
  625.     return packed;
  626. }
  627.  
  628. const QList<QRect> Burke::pack(const QList<QRect> rects)
  629. {
  630.     QList<int> gap;
  631.     QList<QRect> unpacked = rects;
  632.     qSort(unpacked.begin(), unpacked.end(), decreasingHeightComparsion);
  633.     qSort(unpacked.begin(), unpacked.end(), decreasingWidthComparsion);
  634.  
  635.     for (int i = 0; i < RenderArea::STRIPW; i++) {
  636.         gap.push_back(0);
  637.     }
  638.     QList<QRect> packed;
  639.     while (!unpacked.isEmpty()) {
  640.         // find lowest gap
  641.         int min = gap[0];
  642.         int coordX = 0;
  643.         for (int i = 1; i < gap.size(); i++) {
  644.             if (gap[i] < min) {
  645.                 min = gap[i];
  646.                 coordX = i;
  647.             }
  648.         }
  649.         int i = coordX + 1;
  650.         int gapWidth = 1;
  651.         while (i < gap.size() && gap[i] == gap[i - 1]) {
  652.             gapWidth++;
  653.             i++;
  654.         }
  655.         // find best fitting rectangle
  656.         int   ind = -1;
  657.         qreal fit = 0.0;
  658.         for (int j = 0; j < unpacked.size(); j++) {
  659.             qreal curFit =   static_cast<qreal>(unpacked[j].width())
  660.                            / static_cast<qreal>(gapWidth);
  661.             if (curFit < static_cast<qreal>(1) && curFit > fit) {
  662.                 fit = curFit;
  663.                 ind = j;
  664.             }
  665.         }
  666.         if (ind > -1) {
  667.             // place best fitting rectangle using placement policy 'Leftmost'
  668.             QRect newRect;
  669.             newRect.setRect(coordX,
  670.                             RenderArea::STRIPH - (gap[coordX] + unpacked[ind].height()),
  671.                             unpacked[ind].width(), unpacked[ind].height());
  672.             packed.push_back(newRect);
  673.             // raise elements of array to appropriate height
  674.             for (int j = coordX; j < coordX + unpacked[ind].width(); j++) {
  675.                 gap[j] += unpacked[ind].height();
  676.             }
  677.             unpacked.removeAt(ind);
  678.         } else {
  679.             // raise gap to height of the lowest neighbour
  680.             int lowest;
  681.             if (coordX == 0) {
  682.                 lowest = gap[gapWidth];
  683.             } else if (coordX + gapWidth == gap.size()) {
  684.                 lowest = gap[gap.size() - gapWidth - 1];
  685.             } else if (gap[coordX - 1] < gap[coordX + gapWidth]) {
  686.                 lowest = gap[coordX - 1];
  687.             } else {
  688.                 lowest = gap[coordX + gapWidth];
  689.             }
  690.             for (int j = coordX; j < coordX + gapWidth; j++) {
  691.                 gap[j] = lowest;
  692.             }
  693.         }
  694.     }
  695.     return packed;
  696. }
  697.  
  698. /////////////////////////////////////////////////////////////////////////////////////////
  699. const QList<QRect> NFL::pack(const QList<QRect> rects)
  700. {
  701.     QList<QRect> packed;
  702.     QList<Packager::Level> levels;
  703.     Packager::Level level(0, rects[0].height());
  704.  
  705.     packed.push_back(level.put(rects[0]));
  706.     levels.push_back(level);
  707.  
  708.     for (int i = 1; i < rects.size(); i++) {
  709.         if (levels.last().floorFeasible(rects[i])) {
  710.             packed.push_back(levels.last().put(rects[i]));
  711.             if (levels.last().height < rects[i].height()) {
  712.                 levels.last().height = rects[i].height();
  713.             }
  714.         } else {
  715.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  716.                                      rects[i].height());
  717.             packed.push_back(newLevel.put(rects[i]));
  718.             levels.push_back(newLevel);
  719.         }
  720.     }
  721.     return packed;
  722. }
  723.  
  724. const QList<QRect> FFL::pack(const QList<QRect> rects)
  725. {
  726.     QList<QRect> packed;
  727.     QList<Packager::Level> levels;
  728.     Packager::Level level(0, rects[0].height());
  729.  
  730.     packed.push_back(level.put(rects[0]));
  731.     levels.push_back(level);
  732.  
  733.     for (int i = 1; i < rects.size(); i++) {
  734.         int found = -1;
  735.         for (int j = 0; j < levels.size(); j++) {
  736.             if (  (levels[j].height >= rects[i].height() || j == levels.size() - 1)
  737.                 && levels[j].floorFeasible(rects[i])) {
  738.                 found = j;
  739.                 break;
  740.             }
  741.         }
  742.         if (found > -1) {
  743.             packed.push_back(levels[found].put(rects[i]));
  744.             if (   found == (levels.size() - 1)
  745.                 && levels[found].height < rects[i].height()) {
  746.                 levels[found].height = rects[i].height();
  747.             }
  748.         } else {
  749.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  750.                                      rects[i].height());
  751.             packed.push_back(newLevel.put(rects[i]));
  752.             levels.push_back(newLevel);
  753.         }
  754.     }
  755.     return packed;
  756. }
  757.  
  758. const QList<QRect> BFL::pack(const QList<QRect> rects)
  759. {
  760.     QList<QRect> packed;
  761.     QList<Packager::Level> levels;
  762.     Packager::Level level(0, rects[0].height());
  763.  
  764.     packed.push_back(level.put(rects[0]));
  765.     levels.push_back(level);
  766.  
  767.     for (int i = 1; i < rects.size(); i++) {
  768.         int min = RenderArea::STRIPW;
  769.         int found = -1;
  770.         for (int j = 0; j < levels.size(); j++) {
  771.             if (  (levels[j].height >= rects[i].height() || j == levels.size() - 1)
  772.                 && levels[j].floorFeasible(rects[i])
  773.                 && levels[j].getSpace() - rects[i].width() < min) {
  774.                 found = j;
  775.                 min = levels[j].getSpace() - rects[i].width();
  776.             }
  777.         }
  778.         if (found > -1) {
  779.             packed.push_back(levels[found].put(rects[i]));
  780.             if (   found == (levels.size() - 1)
  781.                 && levels[found].height < rects[i].height()) {
  782.                 levels[found].height = rects[i].height();
  783.             }
  784.         } else {
  785.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  786.                                      rects[i].height());
  787.             packed.push_back(newLevel.put(rects[i]));
  788.             levels.push_back(newLevel);
  789.         }
  790.     }
  791.     return packed;
  792. }
  793.  
  794. const QList<QRect> BiNFL::pack(const QList<QRect> rects)
  795. {
  796.     QList<QRect> packed;
  797.     int highest = rects[0].height();
  798.     int bottom = 0;
  799.     int ind = 0;
  800.  
  801.     while (ind < rects.size()) {
  802.         int i = ind;
  803.         //create a new bi-level
  804.         Packager::Level lowerLevel(bottom, 0);
  805.         // pack on lower level
  806.         // first rectangle is packed left-justified
  807.         if (rects[ind].height() > highest) highest = rects[ind].height();
  808.         packed.push_back(lowerLevel.put(rects[ind++]));
  809.         // subsequent rectangles that fit are right justified
  810.         while(ind < rects.size() && lowerLevel.floorFeasible(rects[ind])) {
  811.             if (rects[ind].height() > highest) highest = rects[ind].height();
  812.             packed.push_back(lowerLevel.put(rects[ind++], true, false));
  813.         }
  814.         if (ind < rects.size()) {
  815.             bottom += highest;
  816.             highest = rects[ind].height();
  817.             Packager::Level upperLevel(bottom, 0);
  818.             // pack on upper level
  819.             if (ind == i + 1) {
  820.                 // left justified
  821.                 packed.push_back(upperLevel.put(rects[ind++]));
  822.             } else if (ind == i + 2) {
  823.                 // pack above min
  824.                 if (rects[ind - 1].height() < rects[ind - 2].height()) {
  825.                     packed.push_back(upperLevel.put(rects[ind++], true, false));
  826.                 } else {
  827.                     packed.push_back(upperLevel.put(rects[ind++]));
  828.                 }
  829.             }
  830.             while(ind < rects.size() && upperLevel.floorFeasible(rects[ind])) {
  831.                 if (rects[ind].height() > highest) highest = rects[ind].height();
  832.                 packed.push_back(upperLevel.put(rects[ind++], true, false));
  833.             }
  834.         }
  835.         bottom += highest;
  836.         highest = 0;
  837.     }
  838.     return packed;
  839. }
  840.  
  841. const QList<QRect> NFS::pack(const QList<QRect> rects)
  842. {
  843.     QList<QRect> packed;
  844.     QList<Packager::Level> levels;
  845.     Packager::Level level(0, pow(_base, round(log(rects[0].height()) / log(_base)) - 1));
  846.  
  847.     packed.push_back(level.put(rects[0]));
  848.     levels.push_back(level);
  849.     for (int i = 1; i < rects.size(); i++) {
  850.         // compute k
  851.         qreal k = log(rects[i].height()) / log(_base);
  852.         int aprHeight = static_cast<int>(pow(_base, round(k) - 1));
  853.         // pack if fit
  854.         if (   rects[i].height() <= levels.last().height
  855.             && levels.last().floorFeasible(rects[i])) {
  856.             packed.push_back(levels.last().put(rects[i]));
  857.         } else {
  858.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  859.                                      aprHeight);
  860.             packed.push_back(newLevel.put(rects[i]));
  861.             levels.push_back(newLevel);
  862.         }
  863.     }
  864.     return packed;
  865. }
  866.  
  867. const QList<QRect> FFS::pack(const QList<QRect> rects)
  868. {
  869.     QList<QRect> packed;
  870.     QList<Packager::Level> levels;
  871.     Packager::Level level(0, pow(_base, round(log(rects[0].height()) / log(_base)) - 1));
  872.  
  873.     packed.push_back(level.put(rects[0]));
  874.     levels.push_back(level);
  875.     for (int i = 1; i < rects.size(); i++) {
  876.         // compute k
  877.         qreal k = log(rects[i].height()) / log(_base);
  878.         int aprHeight = static_cast<int>(pow(_base, round(k) - 1));
  879.         // search for lower shelf of appr. height with suff. space
  880.         int found = -1;
  881.         for (int j = 0; j < levels.size(); j++) {
  882.             if (   rects[i].height() <= levels[j].height
  883.                 && levels[j].floorFeasible(rects[i])) {
  884.                 found = j;
  885.                 break;
  886.             }
  887.         }
  888.         if (found > -1) {
  889.             packed.push_back(levels[found].put(rects[i]));
  890.         } else {
  891.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  892.                                      aprHeight);
  893.             packed.push_back(newLevel.put(rects[i]));
  894.             levels.push_back(newLevel);
  895.         }
  896.     }
  897.     return packed;
  898. }
  899.  
  900. const QList<QRect> BFS::pack(const QList<QRect> rects)
  901. {
  902.     QList<QRect> packed;
  903.     QList<Packager::Level> levels;
  904.     Packager::Level level(0, pow(_base, round(log(rects[0].height()) / log(_base)) - 1));
  905.  
  906.     packed.push_back(level.put(rects[0]));
  907.     levels.push_back(level);
  908.     for (int i = 1; i < rects.size(); i++) {
  909.         // compute k
  910.         qreal k = log(rects[i].height()) / log(_base);
  911.         int aprHeight = static_cast<int>(pow(_base, round(k) - 1));
  912.         // search for shelf of appr. height with best space
  913.         int min = RenderArea::STRIPW;
  914.         int found = -1;
  915.         for (int j = 0; j < levels.size(); j++) {
  916.             if (   rects[i].height() <= levels[j].height
  917.                 && levels[j].floorFeasible(rects[i])
  918.                    && levels[j].getSpace() - rects[i].width() < min) {
  919.                 found = j;
  920.                 min = levels[j].getSpace() - rects[i].width();
  921.             }
  922.         }
  923.         if (found > -1) {
  924.             packed.push_back(levels[found].put(rects[i]));
  925.         } else {
  926.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  927.                                      aprHeight);
  928.             packed.push_back(newLevel.put(rects[i]));
  929.             levels.push_back(newLevel);
  930.         }
  931.     }
  932.     return packed;
  933. }
  934.  
  935. const QList<QRect> HS::pack(const QList<QRect> rects)
  936. {
  937.     QList<QRect> packed;
  938.     QList<Packager::Level> levels;
  939.     QList<int> widths;
  940.     Packager::Level level(0, pow(_base, round(log(rects[0].height()) / log(_base)) - 1));
  941.  
  942.     packed.push_back(level.put(rects[0]));
  943.     levels.push_back(level);
  944.     int p = 1;
  945.     while (p < 4 &&   static_cast<qreal>(rects[0].width())
  946.                      / static_cast<qreal>(RenderArea::STRIPW)
  947.                    <   static_cast<qreal>(1)
  948.                      / static_cast<qreal>(p + 1)) p++;
  949.     widths.push_back(p);
  950.     for (int i = 1; i < rects.size(); i++) {
  951.         // compute k
  952.         qreal k = log(rects[i].height()) / log(_base);
  953.         int aprHeight = static_cast<int>(pow(_base, round(k) - 1));
  954.         // compute p. M = 4
  955.         p = 1;
  956.         while (p < 4 &&   static_cast<qreal>(rects[i].width())
  957.                          / static_cast<qreal>(RenderArea::STRIPW)
  958.                        <   static_cast<qreal>(1)
  959.                          / static_cast<qreal>(p + 1)) p++;
  960.         int found = -1;
  961.         for (int j = 0; j < levels.size(); j++) {
  962.             if (   rects[i].height() <= levels[j].height
  963.                 && levels[j].floorFeasible(rects[i])
  964.                 && widths[j] == p) {
  965.                 found = j;
  966.                 break;
  967.             }
  968.         }
  969.         if (found > -1) {
  970.             packed.push_back(levels[found].put(rects[i]));
  971.         } else {
  972.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  973.                                      aprHeight);
  974.             packed.push_back(newLevel.put(rects[i]));
  975.             levels.push_back(newLevel);
  976.             widths.push_back(p);
  977.         }
  978.     }
  979.     return packed;
  980. }
  981.  
  982. const QList<QRect> Azar::pack(const QList<QRect> rects)
  983. {
  984.     QList<QRect> packed;
  985.     QList<Packager::Level> levels;
  986.     Packager::Level level(0, rects[0].height());
  987.  
  988.     packed.push_back(level.put(rects[0]));
  989.     levels.push_back(level);
  990.  
  991.     QList<qreal> widths;
  992.     widths.push_back(round(log(rects[0].width()) / log(2)));
  993.  
  994.     for (int i = 1; i < rects.size(); i++) {
  995.         // compute x
  996.         qreal x = round(log(rects[i].width()) / log(2));
  997.         if (  static_cast<qreal>(rects[i].width())
  998.             / static_cast<qreal>(RenderArea::STRIPW) >= _gamma) {
  999.             Packager::Level newLevel(levels.last().bottom + levels.last().height,
  1000.                                      rects[i].height());
  1001.             packed.push_back(newLevel.put(rects[i]));
  1002.             levels.push_back(newLevel);
  1003.             widths.push_back(x);
  1004.         } else {
  1005.             // compute j
  1006.             qreal j = log(rects[i].height()) / log(2);
  1007.             int found = -1;
  1008.             for (int k = 0; k < levels.size(); k++) {
  1009.                 if (   levels[k].floorFeasible(rects[i])
  1010.                     && levels[k].height >= rects[i].height()
  1011.                     && widths[k] == x) {
  1012.                     found = k;
  1013.                     break;
  1014.                 }
  1015.             }
  1016.             if (found > -1) {
  1017.                 packed.push_back(levels[found].put(rects[i]));
  1018.             } else {
  1019.                 Packager::Level newLevel(levels.last().bottom + levels.last().height,
  1020.                                          pow(2, round(j) + 1));
  1021.                 packed.push_back(newLevel.put(rects[i]));
  1022.                 levels.push_back(newLevel);
  1023.                 widths.push_back(x);
  1024.             }
  1025.         }
  1026.     }
  1027.     return packed;
  1028. }
  1029.  
  1030. const QList<QRect> CA::pack(const QList<QRect> rects)
  1031. {
  1032.     QList<QRect> packed;
  1033.     int highest = rects[0].height();
  1034.     int bottom = 0;
  1035.     int ind = 0;
  1036.  
  1037.     while (ind < rects.size()) {
  1038.         //create a new bi-level
  1039.         Packager::Level lowerLevel(bottom, 0);
  1040.         // pack on lower level
  1041.         // first rectangle is packed left-justified
  1042.         if (rects[ind].height() > highest) highest = rects[ind].height();
  1043.         packed.push_back(lowerLevel.put(rects[ind++]));
  1044.         int shiftTo = packed.last().y() - 1;
  1045.         bool leftJustified = true;
  1046.         // subsequent rectangles that fit are right justified
  1047.         // note if 2nd rectangle is lower
  1048.         if (ind < rects.size() && lowerLevel.floorFeasible(rects[ind])) {
  1049.             if (rects[ind].height() > highest) {
  1050.                 highest = rects[ind].height();
  1051.             } else {
  1052.                 leftJustified = false;
  1053.             }
  1054.             packed.push_back(lowerLevel.put(rects[ind++], true, false));
  1055.             if (!leftJustified) shiftTo = packed.last().y() - 1;
  1056.         }
  1057.         // pack remaining
  1058.         while(ind < rects.size() && lowerLevel.floorFeasible(rects[ind])) {
  1059.             if (rects[ind].height() > highest) highest = rects[ind].height();
  1060.             packed.push_back(lowerLevel.put(rects[ind++], true, false));
  1061.         }
  1062.         if (ind < rects.size()) {
  1063.             bottom += highest;
  1064.             highest = rects[ind].height();
  1065.             Packager::Level upperLevel(bottom, 0);
  1066.             // pack on upper level
  1067.             // first packed should be justified according to the shorter
  1068.             packed.push_back(upperLevel.put(rects[ind++], true, leftJustified));
  1069.             // and shifted downwards, if possible
  1070.             if (shiftTo - packed.last().bottom() >= packed.last().height()) {
  1071.                 bool intersect = false;
  1072.                 QRect tryRect = packed.last();
  1073.                 tryRect.moveBottom(shiftTo);
  1074.                 for (int i = 0; i < packed.size() - 1; i++) {
  1075.                     intersect = packed[i].intersects(tryRect);
  1076.                     if (intersect) break;
  1077.                 }
  1078.                 if (!intersect) packed.last().moveBottom(shiftTo);
  1079.             }
  1080.             // remaining - right justified
  1081.             while(ind < rects.size() && upperLevel.floorFeasible(rects[ind])) {
  1082.                 if (rects[ind].height() > highest) highest = rects[ind].height();
  1083.                 packed.push_back(upperLevel.put(rects[ind++], true, false));
  1084.             }
  1085.         }
  1086.         bottom += highest;
  1087.         highest = 0;
  1088.     }
  1089.     return packed;
  1090. }
  1091.  
  1092. const QList<QRect> CPF::pack(const QList<QRect> rects)
  1093. {
  1094.     QList<QRect> packed;
  1095.     int highest = rects[0].height();
  1096.     int bottom = 0;
  1097.     int ind = 0;
  1098.     QList<int> gap;
  1099.     for (int i = 0; i < RenderArea::STRIPW; i++) gap.push_back(-1);
  1100.  
  1101.     while (ind < rects.size()) {
  1102.         //create a new bi-level
  1103.         Packager::Level lowerLevel(bottom, 0);
  1104.         for (int i = 0; i < gap.size(); i++) gap[i] = bottom;
  1105.         // pack on lower level
  1106.         // first rectangle is packed left-justified
  1107.         if (rects[ind].height() > highest) highest = rects[ind].height();
  1108.         packed.push_back(lowerLevel.put(rects[ind++]));
  1109.         for (int i = packed.last().x(); i < packed.last().x() + packed.last().width(); i++) {
  1110.             gap[i] += packed.last().height();
  1111.         }
  1112.         // subsequent rectangles that fit are right justified
  1113.         while(ind < rects.size() && lowerLevel.floorFeasible(rects[ind])) {
  1114.             if (rects[ind].height() > highest) highest = rects[ind].height();
  1115.             packed.push_back(lowerLevel.put(rects[ind++], true, false));
  1116.             for (int i = packed.last().x(); i < packed.last().x() + packed.last().width(); i++) {
  1117.                 gap[i] += packed.last().height();
  1118.             }
  1119.         }
  1120.         if (ind < rects.size()) {
  1121.             bottom += highest;
  1122.             highest = 0;
  1123.             Packager::Level upperLevel(bottom, 0);
  1124.             // pack on upper level left justified with sliding
  1125.             while(ind < rects.size() && upperLevel.floorFeasible(rects[ind])) {
  1126.                 // check if rectangle may be shifted down
  1127.                 int shiftTo = bottom;
  1128.                 for (int i = upperLevel.floor; i < upperLevel.floor + rects[ind].width(); i++) {
  1129.                     if (bottom - gap[i] < shiftTo) shiftTo = bottom - gap[i];
  1130.                 }
  1131.                 if (shiftTo < rects[ind].height()) {
  1132.                     // pack and shift
  1133.                     if (rects[ind].height() - shiftTo > highest) highest = rects[ind].height() - shiftTo;
  1134.                     packed.push_back(upperLevel.put(rects[ind++]));
  1135.                     packed.last().adjust(0, shiftTo, 0, shiftTo);
  1136.                 } else {
  1137.                     // just pack
  1138.                     if (rects[ind].height() > highest) highest = rects[ind].height();
  1139.                     packed.push_back(upperLevel.put(rects[ind++]));
  1140.                 }
  1141.             }
  1142.         }
  1143.         bottom += highest;
  1144.         highest = 0;
  1145.     }
  1146.     return packed;
  1147. }
  1148.  
  1149. const QList<QRect> CFF::pack(const QList<QRect> rects)
  1150. {
  1151.     QList<QRect> packed;
  1152.     int highest = rects[0].height();
  1153.     int bottom = 0;
  1154.     int ind = 0;
  1155.     QList<int> gap;
  1156.     for (int i = 0; i < RenderArea::STRIPW; i++) gap.push_back(-1);
  1157.  
  1158.     while (ind < rects.size()) {
  1159.         //create a new bi-level
  1160.         Packager::Level lowerLevel(bottom, 0);
  1161.         for (int i = 0; i < gap.size(); i++) gap[i] = bottom;
  1162.         // pack on lower level
  1163.         // first rectangle is packed left-justified
  1164.         if (rects[ind].height() > highest) highest = rects[ind].height();
  1165.         packed.push_back(lowerLevel.put(rects[ind++]));
  1166.         for (int i = packed.last().x(); i < packed.last().x() + packed.last().width(); i++) {
  1167.             gap[i] += packed.last().height();
  1168.         }
  1169.         // subsequent rectangles that fit are right justified
  1170.         while(ind < rects.size() && lowerLevel.floorFeasible(rects[ind])) {
  1171.             if (rects[ind].height() > highest) highest = rects[ind].height();
  1172.             packed.push_back(lowerLevel.put(rects[ind++], true, false));
  1173.             for (int i = packed.last().x(); i < packed.last().x() + packed.last().width(); i++) {
  1174.                 gap[i] += packed.last().height();
  1175.             }
  1176.         }
  1177.         if (ind < rects.size()) {
  1178.             bottom += highest;
  1179.             highest = 0;
  1180.             Packager::Level upperLevel(bottom, 0);
  1181.             // pack on upper level left justified with sliding
  1182.             while(ind < rects.size() && upperLevel.floorFeasible(rects[ind])) {
  1183.                 // check if rectangle may be shifted down
  1184.                 int shiftTo = bottom;
  1185.                 int topIndex;
  1186.                 for (int i = upperLevel.floor; i < upperLevel.floor + rects[ind].width(); i++) {
  1187.                     if (bottom - gap[i] < shiftTo) {
  1188.                         shiftTo = bottom - gap[i];
  1189.                         topIndex = i;
  1190.                     }
  1191.                 }
  1192.                 if (shiftTo >= rects[ind].height()) {
  1193.                     // highest does not change
  1194.                     // pack and shift
  1195.                     packed.push_back(upperLevel.put(rects[ind++]));
  1196.                     packed.last().adjust(0, shiftTo, 0, shiftTo);
  1197.                     // release upper level
  1198.                     upperLevel.floor -= rects[ind - 1].width();
  1199.                     // recalc gap
  1200.                     for (int i = upperLevel.floor; i < upperLevel.floor + rects[ind - 1].width(); i++) {
  1201.                         gap[i] = gap[topIndex] + rects[ind - 1].height();
  1202.                     }
  1203.                 } else {
  1204.                     // just pack
  1205.                     if (rects[ind].height() > highest) highest = rects[ind].height();
  1206.                     packed.push_back(upperLevel.put(rects[ind++]));
  1207.                 }
  1208.             }
  1209.         }
  1210.         bottom += highest;
  1211.         highest = 0;
  1212.     }
  1213.     return packed;
  1214. }
  1215.  
  1216. const QList<QRect> CC::pack(const QList<QRect> rects)
  1217. {
  1218.     QList<QRect> packed;
  1219.     int highest = rects[0].height();
  1220.     int bottom = 0;
  1221.     int ind = 0;
  1222.     QList<int> gap;
  1223.     for (int i = 0; i < RenderArea::STRIPW; i++) gap.push_back(-1);
  1224.  
  1225.     while (ind < rects.size()) {
  1226.         //create a new bi-level
  1227.         Packager::Level lowerLevel(bottom, 0);
  1228.         for (int i = 0; i < gap.size(); i++) gap[i] = bottom;
  1229.         // pack on lower level
  1230.         // first rectangle is packed left-justified
  1231.         if (rects[ind].height() > highest) highest = rects[ind].height();
  1232.         packed.push_back(lowerLevel.put(rects[ind++]));
  1233.         for (int i = packed.last().x(); i < packed.last().x() + packed.last().width(); i++) {
  1234.             gap[i] += packed.last().height();
  1235.         }
  1236.         // subsequent rectangles that fit are right justified
  1237.         while(ind < rects.size() && lowerLevel.floorFeasible(rects[ind])) {
  1238.             if (rects[ind].height() > highest) highest = rects[ind].height();
  1239.             packed.push_back(lowerLevel.put(rects[ind++], true, false));
  1240.             for (int i = packed.last().x(); i < packed.last().x() + packed.last().width(); i++) {
  1241.                 gap[i] += packed.last().height();
  1242.             }
  1243.         }
  1244.         if (ind < rects.size()) {
  1245.             bottom += highest;
  1246.             highest = 0;
  1247.             Packager::Level upperLevel(bottom, 0);
  1248.             // pack on upper level left justified with sliding
  1249.             while(ind < rects.size() && upperLevel.floorFeasible(rects[ind])) {
  1250.                 // check if rectangle may be shifted down
  1251.                 int shiftTo = bottom;
  1252.                 int topIndex;
  1253.                 for (int i = upperLevel.floor; i < upperLevel.floor + rects[ind].width(); i++) {
  1254.                     if (bottom - gap[i] < shiftTo) {
  1255.                         shiftTo = bottom - gap[i];
  1256.                         topIndex = i;
  1257.                     }
  1258.                 }
  1259.                 if (shiftTo > 0) {
  1260.                     if (shiftTo < rects[ind].height()) {
  1261.                         // pack and shift
  1262.                         if (rects[ind].height() - shiftTo > highest) highest = rects[ind].height() - shiftTo;
  1263.                         packed.push_back(upperLevel.put(rects[ind++]));
  1264.                         packed.last().adjust(0, shiftTo, 0, shiftTo);
  1265.                     } else {
  1266.                         // highest does not change
  1267.                         // pack and shift
  1268.                         packed.push_back(upperLevel.put(rects[ind++]));
  1269.                         packed.last().adjust(0, shiftTo, 0, shiftTo);
  1270.                         // release upper level
  1271.                         upperLevel.floor -= rects[ind - 1].width();
  1272.                         // recalc gap
  1273.                         for (int i = upperLevel.floor; i < upperLevel.floor + rects[ind - 1].width(); i++) {
  1274.                             gap[i] = gap[topIndex] + rects[ind - 1].height();
  1275.                         }
  1276.                     }
  1277.                 } else {
  1278.                     // just pack
  1279.                     if (rects[ind].height() > highest) highest = rects[ind].height();
  1280.                     packed.push_back(upperLevel.put(rects[ind++]));
  1281.                 }
  1282.             }
  1283.         }
  1284.         bottom += highest;
  1285.         highest = 0;
  1286.     }
  1287.     return packed;
  1288. }
  1289.  
  1290. const QList<QRect> OF::pack(const QList<QRect> rects)
  1291. {
  1292.     QList<QRect> packed;
  1293.     QList<int> gap;
  1294.     QList<QRect> emptyAreas;
  1295.     int ind;
  1296.  
  1297.     for (int i = 0; i < RenderArea::STRIPW; i++) gap.push_back(0);
  1298.  
  1299.     for (ind = 0; ind < rects.size(); ind++) {
  1300.         // Search the list of empty areas for sufficient space to pack
  1301.         if (!emptyAreas.isEmpty()) {
  1302.             int fitInd = -1;
  1303.             for (int i = 0; i < emptyAreas.size(); i++) {
  1304.                 if (   emptyAreas[i].width() >= rects[ind].width()
  1305.                     && emptyAreas[i].height() >= rects[ind].height()) {
  1306.                     fitInd = i;
  1307.                     break;
  1308.                 }
  1309.             }
  1310.             if (fitInd > -1) {
  1311.                 // pack into empty area
  1312.                 QRect toPack;
  1313.                 toPack.setRect(emptyAreas[fitInd].x(),
  1314.                                emptyAreas[fitInd].y() + emptyAreas[fitInd].height() - rects[ind].height(),
  1315.                                rects[ind].width(), rects[ind].height());
  1316.                 packed.push_back(toPack);
  1317.                 // split area
  1318.                 QRect newArea;
  1319.                 if (  emptyAreas[fitInd].width()  - rects[ind].width()
  1320.                     > emptyAreas[fitInd].height() - rects[ind].height()) {
  1321.                     // vertically
  1322.                     newArea.setRect(emptyAreas[fitInd].x(), emptyAreas[fitInd].y(), rects[ind].width(),
  1323.                                     emptyAreas[fitInd].height() - rects[ind].height());
  1324.                     emptyAreas.push_back(newArea);
  1325.                     emptyAreas[fitInd].adjust(rects[ind].width(), 0, 0, 0);
  1326.                 } else {
  1327.                     // horizontally
  1328.                     newArea.setRect(emptyAreas[fitInd].x() + rects[ind].width(),
  1329.                                     emptyAreas[fitInd].y() + emptyAreas[fitInd].height() - rects[ind].height(),
  1330.                                     emptyAreas[fitInd].width() - rects[ind].width(), rects[ind].height());
  1331.                     emptyAreas.push_back(newArea);
  1332.                     emptyAreas[fitInd].adjust(0, 0, 0, -rects[ind].height());
  1333.                 }
  1334.                 continue;
  1335.             }
  1336.         }
  1337.         // search the linear array for available packing width
  1338.         int index = searchMinGap(gap, rects[ind].width());
  1339.         // analyze packing place
  1340.         if (_level > gap[index]) {
  1341.             QRect emptyArea;
  1342.             int areaWidth = 0;
  1343.             int i = index;
  1344.             while (gap[i++] == gap[index]) {
  1345.                 areaWidth++;
  1346.             }
  1347.             emptyArea.setRect(index, RenderArea::STRIPH - _level, areaWidth, _level - gap[index]);
  1348.             emptyAreas.push_back(emptyArea);
  1349.         } else {
  1350.             int level = gap[index];
  1351.             int areaIndex = index + 1;
  1352.             while (areaIndex < index + rects[ind].width()) {
  1353.                 if (gap[areaIndex] < level) {
  1354.                     QRect emptyArea;
  1355.                     int areaWidth = 0;
  1356.                     int x = areaIndex;
  1357.                     level = gap[areaIndex];
  1358.                     while (gap[areaIndex++] == level && areaIndex < index + rects[ind].width()) {
  1359.                         areaWidth++;
  1360.                     }
  1361.                     emptyArea.setRect(x, RenderArea::STRIPH - gap[index], areaWidth, gap[index] - level);
  1362.                     emptyAreas.push_back(emptyArea);
  1363.                 } else {
  1364.                     areaIndex++;
  1365.                 }
  1366.             }
  1367.         }
  1368.         // pack
  1369.         QRect toPack;
  1370.         toPack.setRect(index, RenderArea::STRIPH - (_level + rects[ind].height()),
  1371.                        rects[ind].width(), rects[ind].height());
  1372.         packed.push_back(toPack);
  1373.         // raise gap
  1374.         for (int i = index; i < index + rects[ind].width(); i++) {
  1375.             gap[i] = _level + rects[ind].height();
  1376.         }
  1377.     }
  1378.     return packed;
  1379. }
  1380.  
  1381. int OF::searchMinGap(const QList<int> gap, int width)
  1382. {
  1383.     // find lowest gap
  1384.     int min = gap[0];
  1385.     int coordX = 0;
  1386.     for (int i = 1; i < gap.size(); i++) {
  1387.         if (gap[i] < min) {
  1388.             min = gap[i];
  1389.             coordX = i;
  1390.         }
  1391.     }
  1392.     int i = coordX + 1;
  1393.     int gapWidth = 1;
  1394.     while (i < gap.size() && gap[i] == gap[i - 1]) {
  1395.         gapWidth++;
  1396.         i++;
  1397.     }
  1398.     if (gapWidth >= width) {
  1399.         _level = gap[coordX];
  1400.         return coordX;
  1401.     } else {
  1402.         // if doesn't fit, raise gap to height of the lowest neighbour
  1403.         int lowest;
  1404.         if (coordX == 0) {
  1405.             lowest = gap[gapWidth];
  1406.         } else if (coordX + gapWidth == gap.size()) {
  1407.             lowest = gap[gap.size() - gapWidth - 1];
  1408.         } else if (gap[coordX - 1] < gap[coordX + gapWidth]) {
  1409.             lowest = gap[coordX - 1];
  1410.         } else {
  1411.             lowest = gap[coordX + gapWidth];
  1412.         }
  1413.         QList<int> newGap = gap;
  1414.         for (int j = coordX; j < coordX + gapWidth; j++) {
  1415.             newGap[j] = lowest;
  1416.         }
  1417.         // and search again
  1418.         return searchMinGap(newGap, width);
  1419.     }
  1420. }
RAW Paste Data