VolumePacker   A
last analyzed

Complexity

Total Complexity 40

Size/Duplication

Total Lines 392
Duplicated Lines 0 %

Test Coverage

Coverage 100%

Importance

Changes 0
Metric Value
eloc 130
dl 0
loc 392
ccs 138
cts 138
cp 1
rs 9.2
c 0
b 0
f 0
wmc 40

14 Methods

Rating   Name   Duplication   Size   Complexity  
A stabiliseLayers() 0 4 1
A __construct() 0 14 3
A pack() 0 18 3
B packLayer() 0 54 9
A getPackedItemList() 0 10 3
A checkConstraints() 0 5 2
A rotateLayersNinetyDegrees() 0 9 3
A getOrientationForItem() 0 29 2
A checkDimensionalConstraints() 0 6 1
A getCurrentPackedDepth() 0 8 2
A tryAndStackItemsIntoSpace() 0 31 4
A rebuildItemList() 0 9 3
A checkNonDimensionalConstraints() 0 9 3
A hasItemsLeftToPack() 0 3 1

How to fix   Complexity   

Complex Class

Complex classes like VolumePacker often do a lot of different things. To break such a class down, we need to identify a cohesive component within that class. A common approach to find such a component is to look for fields/methods that share the same prefixes, or suffixes.

Once you have determined the fields that belong together, you can apply the Extract Class refactoring. If the component makes sense as a sub-class, Extract Subclass is also a candidate, and is often faster.

While breaking up the class, it is a good idea to analyze how other classes use VolumePacker, and based on these observations, apply Extract Interface, too.

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