Completed
Push — issue89 ( 529e43...9b8738 )
by Doug
11:30 queued 02:35
created

VolumePacker::tryAndStackItemsIntoSpace()   B

Complexity

Conditions 4
Paths 3

Size

Total Lines 32
Code Lines 28

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 16
CRAP Score 4

Importance

Changes 0
Metric Value
c 0
b 0
f 0
dl 0
loc 32
ccs 16
cts 16
cp 1
rs 8.5806
cc 4
eloc 28
nc 3
nop 9
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
 *
5
 * @author Doug Wright
6
 */
7
declare(strict_types=1);
8
9
namespace DVDoug\BoxPacker;
10
11
use Psr\Log\LoggerAwareInterface;
12
use Psr\Log\LoggerAwareTrait;
13
use Psr\Log\NullLogger;
14
15
/**
16
 * Actual packer.
17
 *
18
 * @author Doug Wright
19
 */
20
class VolumePacker implements LoggerAwareInterface
21
{
22
    use LoggerAwareTrait;
23
24
    /**
25
     * Box to pack items into.
26
     *
27
     * @var Box
28
     */
29
    protected $box;
30
31
    /**
32
     * @var int
33
     */
34
    protected $boxWidth;
35
36
    /**
37
     * @var int
38
     */
39
    protected $boxLength;
40
41
    /**
42
     * List of items to be packed.
43
     *
44
     * @var ItemList
45
     */
46
    protected $items;
47
48
    /**
49
     * List of items to be packed.
50
     *
51
     * @var ItemList
52
     */
53
    protected $skippedItems;
54
55
    /**
56
     * Remaining weight capacity of the box.
57
     *
58
     * @var int
59
     */
60
    protected $remainingWeight;
61
62
    /**
63
     * Whether the box was rotated for packing.
64
     *
65
     * @var bool
66
     */
67
    protected $boxRotated = false;
68
69
    /**
70
     * Constructor.
71
     *
72
     * @param Box      $box
73
     * @param ItemList $items
74
     */
75 37
    public function __construct(Box $box, ItemList $items)
76
    {
77 37
        $this->box = $box;
78 37
        $this->items = $items;
79
80 37
        $this->boxWidth = max($this->box->getInnerWidth(), $this->box->getInnerLength());
81 37
        $this->boxLength = min($this->box->getInnerWidth(), $this->box->getInnerLength());
82 37
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
83 37
        $this->skippedItems = new ItemList();
84 37
        $this->logger = new NullLogger();
85
86
        // we may have just rotated the box for packing purposes, record if we did
87 37
        if ($this->box->getInnerWidth() != $this->boxWidth || $this->box->getInnerLength() != $this->boxLength) {
88 9
            $this->boxRotated = true;
89
        }
90
    }
91
92
    /**
93
     * Pack as many items as possible into specific given box.
94
     *
95
     * @return PackedBox packed box
96
     */
97 37
    public function pack(): PackedBox
98
    {
99 37
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
100
101 37
        $packedItems = new PackedItemList();
102 37
        $prevItem = null;
103
104 37
        $x = $y = $z = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0;
105
106 37
        $packingWidthLeft = $this->boxWidth;
107 37
        $packingLengthLeft = $this->boxLength;
108 37
        $packingDepthLeft = $this->box->getInnerDepth();
109
110 37
        while (count($this->items) > 0) {
111 37
            $itemToPack = $this->items->extract();
112 37
            $nextItem = count($this->items) ? $this->items->top() : null;
113
114
            //skip items that are simply too heavy or too large
115 37
            if (!$this->checkConstraints($itemToPack, $packedItems)) {
116 10
                $this->rebuildItemList();
117 10
                continue;
118
            }
119
120 37
            $orientatedItem = $this->getOrientationForItem($itemToPack, $prevItem, $nextItem, $this->hasItemsLeftToPack(), $packingWidthLeft, $packingLengthLeft, $packingDepthLeft);
121
122 37
            if ($orientatedItem instanceof OrientatedItem) {
123 37
                $packedItem = PackedItem::fromOrientatedItem($orientatedItem, $x, $y, $z);
124 37
                $packedItems->insert($packedItem);
125 37
                $this->remainingWeight -= $orientatedItem->getItem()->getWeight();
126 37
                $packingWidthLeft -= $orientatedItem->getWidth();
127
128 37
                $rowWidth += $orientatedItem->getWidth();
129 37
                $rowLength = max($rowLength, $orientatedItem->getLength());
130 37
                $layerDepth = max($layerDepth, $orientatedItem->getDepth());
131
132
                //allow items to be stacked in place within the same footprint up to current layer depth
133 37
                $stackableDepth = $layerDepth - $orientatedItem->getDepth();
134 37
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth, $x, $y, $z + $orientatedItem->getDepth());
135 37
                $x += $orientatedItem->getWidth();
136
137 37
                $prevItem = $packedItem;
138
139 37
                $this->rebuildItemList();
140
            } else {
141 25
                if ($layerWidth == 0 && $layerDepth == 0) { // zero items on layer
142 4
                    $this->logger->debug("doesn't fit on layer even when empty, skipping for good");
143 4
                    $prevItem = null;
144 4
                    continue;
145 25
                } elseif (count($this->items) > 0) { // skip for now, move on to the next item
146 22
                    $this->logger->debug("doesn't fit, skipping for now");
147 22
                    $this->skippedItems->insert($itemToPack);
148 25
                } elseif ($x > 0 && $packingLengthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength())) {
149 25
                    $this->logger->debug('No more fit in width wise, resetting for new row');
150 25
                    $layerWidth = max($layerWidth, $rowWidth);
151 25
                    $layerLength += $rowLength;
152 25
                    $packingWidthLeft += $rowWidth;
153 25
                    $packingLengthLeft -= $rowLength;
154 25
                    $y += $rowLength;
155 25
                    $x = $rowWidth = $rowLength = 0;
156 25
                    $this->rebuildItemList();
157 25
                    $this->items->insert($itemToPack);
158 25
                    $prevItem = null;
159 25
                    continue;
160
                } else {
161 19
                    $this->logger->debug('no items fit, so starting next vertical layer');
162
163 19
                    $layerWidth = max($layerWidth, $rowWidth);
164 19
                    $layerLength += $rowLength;
165 19
                    $packingWidthLeft = $rowWidth ? min(intval($layerWidth * 1.1), $this->boxWidth) : $this->boxWidth;
166 19
                    $packingLengthLeft = $rowLength ? min(intval($layerLength * 1.1), $this->boxLength) : $this->boxLength;
167 19
                    $packingDepthLeft -= $layerDepth;
168
169 19
                    $z += $layerDepth;
170 19
                    $x = $y = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0;
171
172 19
                    $this->rebuildItemList();
173 19
                    $this->items->insert($itemToPack);
174 19
                    $prevItem = null;
175
                }
176
            }
177
        }
178 37
        $this->logger->debug('done with this box');
179
180 37
        return $this->createPackedBox($packedItems);
181
    }
182
183
    /**
184
     * @param Item            $itemToPack
185
     * @param PackedItem|null $prevItem
186
     * @param Item|null       $nextItem
187
     * @param bool            $isLastItem
188
     * @param int             $maxWidth
189
     * @param int             $maxLength
190
     * @param int             $maxDepth
191
     *
192
     * @return OrientatedItem|null
193
     */
194 37
    protected function getOrientationForItem(
195
        Item $itemToPack,
196
        ?PackedItem $prevItem,
197
        ?Item $nextItem,
198
        bool $isLastItem,
199
        int $maxWidth,
200
        int $maxLength,
201
        int $maxDepth
202
    ): ?OrientatedItem {
203 37
        $this->logger->debug(
204 37
            "evaluating item {$itemToPack->getDescription()} for fit",
205
            [
206 37
                'item'  => $itemToPack,
207
                'space' => [
208 37
                    'maxWidth'    => $maxWidth,
209 37
                    'maxLength'   => $maxLength,
210 37
                    'maxDepth'    => $maxDepth,
211
                ],
212
            ]
213
        );
214
215 37
        $prevOrientatedItem = $prevItem ? $prevItem->toOrientatedItem() : null;
216
217 37
        $orientatedItemFactory = new OrientatedItemFactory();
218 37
        $orientatedItemFactory->setLogger($this->logger);
219 37
        $orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevOrientatedItem, $nextItem, $isLastItem, $maxWidth, $maxLength, $maxDepth);
220
221 37
        return $orientatedItem;
222
    }
223
224
    /**
225
     * Figure out if we can stack the next item vertically on top of this rather than side by side
226
     * Used when we've packed a tall item, and have just put a shorter one next to it.
227
     *
228
     * @param PackedItemList  $packedItems
229
     * @param PackedItem|null $prevItem
230
     * @param Item|null       $nextItem
231
     * @param int             $maxWidth
232
     * @param int             $maxLength
233
     * @param int             $maxDepth
234
     * @param int             $x
235
     * @param int             $y
236
     * @param int             $z
237
     */
238 37
    protected function tryAndStackItemsIntoSpace(
239
        PackedItemList $packedItems,
240
        ?PackedItem $prevItem,
241
        ?Item $nextItem,
242
        int $maxWidth,
243
        int $maxLength,
244
        int $maxDepth,
245
        int $x,
246
        int $y,
247
        int $z
248
    ): void {
249 37
        while (count($this->items) > 0 && $this->checkNonDimensionalConstraints($this->items->top(), $packedItems)) {
250 33
            $stackedItem = $this->getOrientationForItem(
251 33
                $this->items->top(),
252 33
                $prevItem,
253 33
                $nextItem,
254 33
                $this->items->count() === 1,
255 33
                $maxWidth,
256 33
                $maxLength,
257 33
                $maxDepth
258
            );
259 33
            if ($stackedItem) {
260 3
                $this->remainingWeight -= $this->items->top()->getWeight();
261 3
                $packedItems->insert(PackedItem::fromOrientatedItem($stackedItem, $x, $y, $z));
262 3
                $this->items->extract();
263 3
                $maxDepth -= $stackedItem->getDepth();
264 3
                $z += $stackedItem->getDepth();
265
            } else {
266
                break;
267
            }
268
        }
269
    }
270
271
    /**
272
     * Check item generally fits into box.
273
     *
274
     * @param Item           $itemToPack
275
     * @param PackedItemList $packedItems
276
     *
277
     * @return bool
278
     */
279 37
    protected function checkConstraints(
280
        Item $itemToPack,
281
        PackedItemList $packedItems
282
    ): bool {
283 37
        return $this->checkNonDimensionalConstraints($itemToPack, $packedItems) &&
284 37
               $this->checkDimensionalConstraints($itemToPack);
285
    }
286
287
    /**
288
     * As well as purely dimensional constraints, there are other constraints that need to be met
289
     * e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box).
290
     *
291
     * @param Item           $itemToPack
292
     * @param PackedItemList $packedItems
293
     *
294
     * @return bool
295
     */
296 37
    protected function checkNonDimensionalConstraints(Item $itemToPack, PackedItemList $packedItems): bool
297
    {
298 37
        $weightOK = $itemToPack->getWeight() <= $this->remainingWeight;
299
300 37
        if ($itemToPack instanceof ConstrainedItem) {
301 1
            return $weightOK && $itemToPack->canBePackedInBox($packedItems, $this->box);
302
        }
303
304
        return $weightOK;
305
    }
306
307
    /**
308
     * Check the item physically fits in the box (at all).
309
     *
310
     * @param Item $itemToPack
311
     *
312
     * @return bool
313
     */
314 37
    protected function checkDimensionalConstraints(Item $itemToPack): bool
315
    {
316 37
        $orientatedItemFactory = new OrientatedItemFactory();
317 37
        $orientatedItemFactory->setLogger($this->logger);
318
319 37
        return (bool) $orientatedItemFactory->getPossibleOrientationsInEmptyBox($itemToPack, $this->box);
320
    }
321
322
    /**
323
     * Reintegrate skipped items into main list when nothing left to process.
324
     */
325 37
    protected function rebuildItemList(): void
326
    {
327 37
        if (count($this->items) === 0) {
328 37
            $this->items = $this->skippedItems;
329 37
            $this->skippedItems = new ItemList();
330
        }
331
    }
332
333
    /**
334
     * @param PackedItemList $packedItems
335
     *
336
     * @return PackedBox
337
     */
338 37
    protected function createPackedBox(PackedItemList $packedItems): PackedBox
339
    {
340
        //if we rotated the box for packing, need to swap back width/length of the packed items
341 37
        if ($this->boxRotated) {
342 9
            $items = iterator_to_array($packedItems, false);
343 9
            $packedItems = new PackedItemList();
344
            /** @var PackedItem $item */
345 9
            foreach ($items as $item) {
346 9
                $packedItems->insert(
347 9
                    new PackedItem(
348 9
                        $item->getItem(),
349 9
                        $item->getY(),
350 9
                        $item->getX(),
351 9
                        $item->getZ(),
352 9
                        $item->getLength(),
353 9
                        $item->getWidth(),
354 9
                        $item->getDepth()
355
                    )
356
                );
357
            }
358
        }
359
360 37
        return new PackedBox($this->box, $packedItems);
361
    }
362
363
    /**
364
     * Are there items left to pack?
365
     *
366
     * @return bool
367
     */
368 37
    protected function hasItemsLeftToPack(): bool
369
    {
370 37
        return count($this->skippedItems) + count($this->items) === 0;
371
    }
372
}
373