API tools faq
paste
Advertisement
WildReanimator

packager.cpp

WildReanimator
Nov 23rd, 2012
2,328
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ (with Qt extensions) 53.46 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!