Passed
Push — 1.x-dev ( 8f914b...081a6e )
by Doug
04:31
created

VolumePacker::setLookAheadMode()   A

Complexity

Conditions 1
Paths 1

Size

Total Lines 3
Code Lines 1

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 2
CRAP Score 1

Importance

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