Completed
Push — issue_187 ( fb1b49...8952f9 )
by Doug
158:46 queued 155:58
created

VolumePacker::tryAndStackItemsIntoSpace()   A

Complexity

Conditions 4
Paths 3

Size

Total Lines 34
Code Lines 21

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 12
CRAP Score 4

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 4
eloc 21
nc 3
nop 10
dl 0
loc 34
ccs 12
cts 12
cp 1
crap 4
rs 9.584
c 1
b 0
f 0

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