Completed
Push — master ( 440a91...12707d )
by Doug
11:53 queued 13s
created

VolumePacker::createPackedBox()   B

Complexity

Conditions 3
Paths 2

Size

Total Lines 24
Code Lines 15

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 15
CRAP Score 3

Importance

Changes 0
Metric Value
dl 0
loc 24
ccs 15
cts 15
cp 1
rs 8.9713
c 0
b 0
f 0
cc 3
eloc 15
nc 2
nop 1
crap 3
1
<?php
2
/**
3
 * Box packing (3D bin packing, knapsack problem)
4
 * @package BoxPacker
5
 * @author Doug Wright
6
 */
7
declare(strict_types=1);
8
namespace DVDoug\BoxPacker;
9
10
use Psr\Log\LoggerAwareInterface;
11
use Psr\Log\LoggerAwareTrait;
12
use Psr\Log\LoggerInterface;
13
use Psr\Log\NullLogger;
14
15
/**
16
 * Actual packer
17
 * @author Doug Wright
18
 * @package BoxPacker
19
 */
20
class VolumePacker implements LoggerAwareInterface
21
{
22
    use LoggerAwareTrait;
23
24
    /**
25
     * Box to pack items into
26
     * @var Box
27
     */
28
    protected $box;
29
30
    /**
31
     * @var int
32
     */
33
    protected $boxWidth;
34
35
    /**
36
     * @var int
37
     */
38
    protected $boxLength;
39
40
    /**
41
     * List of items to be packed
42
     * @var ItemList
43
     */
44
    protected $items;
45
46
    /**
47
     * List of items to be packed
48
     * @var ItemList
49
     */
50
    protected $skippedItems;
51
52
    /**
53
     * Remaining weight capacity of the box
54
     * @var int
55
     */
56
    protected $remainingWeight;
57
58
    /**
59
     * Whether the box was rotated for packing
60
     * @var bool
61
     */
62
    protected $boxRotated = false;
63
64
    /**
65
     * Constructor
66
     *
67
     * @param Box      $box
68
     * @param ItemList $items
69
     */
70 34
    public function __construct(Box $box, ItemList $items)
71
    {
72 34
        $this->box = $box;
73 34
        $this->items = $items;
74
75 34
        $this->boxWidth = max($this->box->getInnerWidth(), $this->box->getInnerLength());
76 34
        $this->boxLength = min($this->box->getInnerWidth(), $this->box->getInnerLength());
77 34
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
78 34
        $this->skippedItems = new ItemList();
79 34
        $this->logger = new NullLogger();
80
81
        // we may have just rotated the box for packing purposes, record if we did
82 34
        if ($this->box->getInnerWidth() != $this->boxWidth || $this->box->getInnerLength() != $this->boxLength) {
83 9
            $this->boxRotated = true;
84
        }
85
86
    }
87
88
    /**
89
     * Pack as many items as possible into specific given box
90
     *
91
     * @return PackedBox packed box
92
     */
93 34
    public function pack(): PackedBox
94
    {
95 34
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
96
97 34
        $packedItems = new PackedItemList;
98 34
        $prevItem = null;
99
100 34
        $x = $y = $z = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0;
101
102 34
        $packingWidthLeft = $this->boxWidth;
103 34
        $packingLengthLeft = $this->boxLength;
104 34
        $packingDepthLeft = $this->box->getInnerDepth();
105
106 34
        while (!$this->items->isEmpty()) {
107 34
            $itemToPack = $this->items->extract();
108 34
            $isLastItem = $this->skippedItems->isEmpty() && $this->items->isEmpty();
109
110
            //skip items that are simply too heavy or too large
111 34
            if (!$this->checkConstraints($itemToPack, $packedItems)) {
112 8
                $this->rebuildItemList();
113 8
                continue;
114
            }
115
116 34
            $orientatedItem = $this->getOrientationForItem($itemToPack, $prevItem, $isLastItem, $packingWidthLeft, $packingLengthLeft, $packingDepthLeft);
117
118 34
            if ($orientatedItem instanceof OrientatedItem) {
119 34
                $packedItem = PackedItem::fromOrientatedItem($orientatedItem, $x, $y, $z);
120 34
                $packedItems->insert($packedItem);
121 34
                $this->remainingWeight -= $orientatedItem->getItem()->getWeight();
122 34
                $packingWidthLeft -= $orientatedItem->getWidth();
123
124 34
                $rowWidth += $orientatedItem->getWidth();
125 34
                $rowLength = max($rowLength, $orientatedItem->getLength());
126 34
                $layerDepth = max($layerDepth, $orientatedItem->getDepth());
127
128
                //allow items to be stacked in place within the same footprint up to current layer depth
129 34
                $stackableDepth = $layerDepth - $orientatedItem->getDepth();
130 34
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth, $x, $y, $z + $orientatedItem->getDepth());
131 34
                $x += $orientatedItem->getWidth();
132
133 34
                $prevItem = $packedItem;
134
135 34
                $this->rebuildItemList();
136
            } else {
137 22
                if ($layerWidth == 0 && $layerDepth == 0) { // zero items on layer
138 4
                    $this->logger->debug("doesn't fit on layer even when empty, skipping for good");
139 4
                    $prevItem = null;
140 4
                    continue;
141 22
                } elseif (!$this->items->isEmpty()) { // skip for now, move on to the next item
142 19
                    $this->logger->debug("doesn't fit, skipping for now");
143 19
                    $this->skippedItems->insert($itemToPack);
144 22
                } elseif ($x > 0 && $packingLengthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength())) {
145 22
                    $this->logger->debug("No more fit in width wise, resetting for new row");
146 22
                    $layerWidth = max($layerWidth, $rowWidth);
147 22
                    $layerLength += $rowLength;
148 22
                    $packingWidthLeft += $rowWidth;
149 22
                    $packingLengthLeft -= $rowLength;
150 22
                    $y += $rowLength;
151 22
                    $x = $rowWidth = $rowLength = 0;
152 22
                    $this->rebuildItemList();
153 22
                    $this->items->insert($itemToPack);
154 22
                    $prevItem = null;
155 22
                    continue;
156
                } else {
157 17
                    $this->logger->debug("no items fit, so starting next vertical layer");
158
159 17
                    $layerWidth = max($layerWidth, $rowWidth);
160 17
                    $layerLength += $rowLength;
161 17
                    $packingWidthLeft = $rowWidth ? min(intval($layerWidth * 1.1), $this->boxWidth) : $this->boxWidth;
162 17
                    $packingLengthLeft = $rowLength ? min(intval($layerLength * 1.1), $this->boxLength) : $this->boxLength;
163 17
                    $packingDepthLeft -= $layerDepth;
164
165 17
                    $z += $layerDepth;
166 17
                    $x = $y = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0;
167
168 17
                    $this->rebuildItemList();
169 17
                    $this->items->insert($itemToPack);
170 17
                    $prevItem = null;
171
                }
172
            }
173
        }
174 34
        $this->logger->debug("done with this box");
175 34
        return $this->createPackedBox($packedItems);
176
    }
177
178
    /**
179
     * @param Item            $itemToPack
180
     * @param ?PackedItem     $prevItem
0 ignored issues
show
Documentation introduced by Doug Wright
The doc-type ?PackedItem could not be parsed: Unknown type name "?PackedItem" at position 0. (view supported doc-types)

This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.

Loading history...
181
     * @param bool            $isLastItem
182
     * @param int             $maxWidth
183
     * @param int             $maxLength
184
     * @param int             $maxDepth
185
     *
186
     * @return ?OrientatedItem
0 ignored issues
show
Documentation introduced by Doug Wright
The doc-type ?OrientatedItem could not be parsed: Unknown type name "?OrientatedItem" at position 0. (view supported doc-types)

This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.

Loading history...
187
     */
188 34
    protected function getOrientationForItem(
189
        Item $itemToPack,
190
        ?PackedItem $prevItem,
191
        bool $isLastItem,
192
        int $maxWidth,
193
        int $maxLength,
194
        int $maxDepth
195
    ): ?OrientatedItem {
196 34
        $this->logger->debug(
197 34
            "evaluating item {$itemToPack->getDescription()} for fit",
198
            [
199 34
                'item' => $itemToPack,
200
                'space' => [
201 34
                    'maxWidth'    => $maxWidth,
202 34
                    'maxLength'   => $maxLength,
203 34
                    'maxDepth'    => $maxDepth,
204
                ],
205
            ]
206
        );
207
208 34
        $orientatedItemFactory = new OrientatedItemFactory();
209 34
        $orientatedItemFactory->setLogger($this->logger);
210 34
        $orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevItem, $isLastItem, $maxWidth, $maxLength, $maxDepth);
211
212 34
        return $orientatedItem;
213
    }
214
215
    /**
216
     * Figure out if we can stack the next item vertically on top of this rather than side by side
217
     * Used when we've packed a tall item, and have just put a shorter one next to it
218
     *
219
     * @param PackedItemList $packedItems
220
     * @param ?PackedItem $prevItem
0 ignored issues
show
Documentation introduced by Doug Wright
The doc-type ?PackedItem could not be parsed: Unknown type name "?PackedItem" at position 0. (view supported doc-types)

This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.

Loading history...
221
     * @param int $maxWidth
222
     * @param int $maxLength
223
     * @param int $maxDepth
224
     * @param int $x
225
     * @param int $y
226
     * @param int $z
227
     */
228 34
    protected function tryAndStackItemsIntoSpace(
229
        PackedItemList $packedItems,
230
        ?PackedItem $prevItem,
231
        int $maxWidth,
232
        int $maxLength,
233
        int $maxDepth,
234
        int $x,
235
        int $y,
236
        int $z
237
    ): void {
238 34
        while (!$this->items->isEmpty() && $this->checkNonDimensionalConstraints($this->items->top(), $packedItems)) {
239 30
            $stackedItem = $this->getOrientationForItem(
240 30
                $this->items->top(),
241 30
                $prevItem,
242 30
                $this->items->count() === 1,
243 30
                $maxWidth,
244 30
                $maxLength,
245 30
                $maxDepth
246
            );
247 30
            if ($stackedItem) {
248 3
                $this->remainingWeight -= $this->items->top()->getWeight();
249 3
                $packedItems->insert(PackedItem::fromOrientatedItem($stackedItem, $x, $y, $z));
250 3
                $this->items->extract();
251 3
                $maxDepth -= $stackedItem->getDepth();
252 3
                $z += $stackedItem->getDepth();
253
            } else {
254
                break;
255
            }
256
        }
257
    }
258
259
    /**
260
     * Check item generally fits into box
261
     *
262
     * @param Item            $itemToPack
263
     * @param PackedItemList  $packedItems
264
     *
265
     * @return bool
266
     */
267 34
    protected function checkConstraints(
268
        Item $itemToPack,
269
        PackedItemList $packedItems
270
    ): bool {
271 34
        return $this->checkNonDimensionalConstraints($itemToPack, $packedItems) &&
272 34
               $this->checkDimensionalConstraints($itemToPack);
273
    }
274
275
    /**
276
     * As well as purely dimensional constraints, there are other constraints that need to be met
277
     * e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box)
278
     *
279
     * @param Item     $itemToPack
280
     * @param PackedItemList $packedItems
281
     *
282
     * @return bool
283
     */
284 34
    protected function checkNonDimensionalConstraints(Item $itemToPack, PackedItemList $packedItems): bool
285
    {
286 34
        $weightOK = $itemToPack->getWeight() <= $this->remainingWeight;
287
288 34
        if ($itemToPack instanceof ConstrainedItem) {
289 1
            return $weightOK && $itemToPack->canBePackedInBox(clone $packedItems, $this->box);
290
        }
291
292
        return $weightOK;
293
    }
294
295
    /**
296
     * Check the item physically fits in the box (at all)
297
     *
298
     * @param Item            $itemToPack
299
     *
300
     * @return bool
301
     */
302 34
    protected function checkDimensionalConstraints(Item $itemToPack): bool
303
    {
304 34
        $orientatedItemFactory = new OrientatedItemFactory();
305 34
        $orientatedItemFactory->setLogger($this->logger);
306 34
        return !!$orientatedItemFactory->getPossibleOrientationsInEmptyBox($itemToPack, $this->box);
307
    }
308
309
    /**
310
     * Reintegrate skipped items into main list when nothing left to process
311
     */
312 34
    protected function rebuildItemList(): void {
313 34
        if ($this->items->isEmpty()) {
314 34
            $this->items = $this->skippedItems;
315 34
            $this->skippedItems = new ItemList();
316
        }
317
    }
318
319
    /**
320
     * @param PackedItemList $packedItems
321
     *
322
     * @return PackedBox
323
     */
324 34
    protected function createPackedBox(PackedItemList $packedItems): PackedBox
325
    {
326
        //if we rotated the box for packing, need to swap back width/length of the packed items
327 34
        if ($this->boxRotated) {
328 9
            $items = iterator_to_array($packedItems);
329 9
            $packedItems = new PackedItemList();
330
            /** @var PackedItem $item */
331 9
            foreach($items as $item) {
332 9
                $packedItems->insert(
333 9
                    new PackedItem(
334 9
                        $item->getItem(),
335 9
                        $item->getY(),
336 9
                        $item->getX(),
337 9
                        $item->getZ(),
338 9
                        $item->getLength(),
339 9
                        $item->getWidth(),
340 9
                        $item->getDepth()
341
                    )
342
                );
343
            }
344
        }
345
346 34
        return new PackedBox($this->box, $packedItems);
347
    }
348
}
349