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

VolumePacker::tryAndStackItemsIntoSpace()   B

Complexity

Conditions 4
Paths 3

Size

Total Lines 30
Code Lines 26

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 15
CRAP Score 4

Importance

Changes 0
Metric Value
dl 0
loc 30
ccs 15
cts 15
cp 1
rs 8.5806
c 0
b 0
f 0
cc 4
eloc 26
nc 3
nop 8
crap 4

How to fix   Many Parameters   

Many Parameters

Methods with many parameters are not only hard to understand, but their parameters also often become inconsistent when you need more, or different data.

There are several approaches to avoid long parameter lists:

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
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
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
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