Completed
Push — extract_logic ( 249126...a297ff )
by Doug
13:02
created

VolumePacker.php (1 issue)

Severity

Upgrade to new PHP Analysis Engine

These results are based on our legacy PHP analysis, consider migrating to our new PHP analysis engine instead. Learn more

1
<?php
2
/**
3
 * Box packing (3D bin packing, knapsack problem)
4
 * @package BoxPacker
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
 * @author Doug Wright
16
 * @package BoxPacker
17
 */
18
class VolumePacker implements LoggerAwareInterface
19
{
20
    use LoggerAwareTrait;
21
22
    /**
23
     * Box to pack items into
24
     * @var Box
25
     */
26
    protected $box;
27
28
    /**
29
     * List of items to be packed
30
     * @var ItemList
31
     */
32
    protected $items;
33
34
    /**
35
     * Remaining width of the box to pack items into
36
     * @var int
37
     */
38
    protected $widthLeft;
39
40
    /**
41
     * Remaining length of the box to pack items into
42
     * @var int
43
     */
44
    protected $lengthLeft;
45
46
    /**
47
     * Remaining depth of the box to pack items into
48
     * @var int
49
     */
50
    protected $depthLeft;
51
52
    /**
53
     * Remaining weight capacity of the box
54
     * @var int
55
     */
56
    protected $remainingWeight;
57
58
    /**
59
     * Used width inside box for packing items
60
     * @var int
61
     */
62
    protected $usedWidth = 0;
63
64
    /**
65
     * Used length inside box for packing items
66
     * @var int
67
     */
68
    protected $usedLength = 0;
69
70
    /**
71
     * Used depth inside box for packing items
72
     * @var int
73
     */
74
    protected $usedDepth = 0;
75
76
    /**
77
     * Constructor
78
     *
79
     * @param Box      $box
80
     * @param ItemList $items
81
     */
82 29
    public function __construct(Box $box, ItemList $items)
83
    {
84 29
        $this->logger = new NullLogger();
85
86 29
        $this->box = $box;
87 29
        $this->items = $items;
88
89 29
        $this->depthLeft = $this->box->getInnerDepth();
90 29
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
91 29
        $this->widthLeft = $this->box->getInnerWidth();
92 29
        $this->lengthLeft = $this->box->getInnerLength();
93
    }
94
95
    /**
96
     * Pack as many items as possible into specific given box
97
     *
98
     * @return PackedBox packed box
99
     */
100 29
    public function pack()
101
    {
102 29
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
103
104 29
        $packedItems = new ItemList;
105
106 29
        $layerWidth = $layerLength = $layerDepth = 0;
107
108 29
        $prevItem = null;
109
110 29
        while (!$this->items->isEmpty()) {
111
112 29
            $itemToPack = $this->items->extract();
113
114
            //skip items that are simply too heavy
115 29
            if ($itemToPack->getWeight() > $this->remainingWeight) {
116 4
                continue;
117
            }
118
119 29
            $this->logger->debug("evaluating item {$itemToPack->getDescription()}", ['item' => $itemToPack, 'space' => ['widthLeft'   => $this->widthLeft, 'lengthLeft'  => $this->lengthLeft, 'depthLeft'   => $this->depthLeft, 'layerWidth'  => $layerWidth, 'layerLength' => $layerLength, 'layerDepth'  => $layerDepth]]);
120
121 29
            $nextItem = !$this->items->isEmpty() ? $this->items->top() : null;
122 29
            $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);
123
124 29
            if ($orientatedItem) {
125
126 29
                $packedItems->insert($orientatedItem->getItem());
127 29
                $this->remainingWeight -= $itemToPack->getWeight();
128
129 29
                $this->lengthLeft -= $orientatedItem->getLength();
130 29
                $layerLength += $orientatedItem->getLength();
131 29
                $layerWidth = max($orientatedItem->getWidth(), $layerWidth);
132
133 29
                $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep
134
135 29
                $this->usedLength = max($this->usedLength, $layerLength);
136 29
                $this->usedWidth = max($this->usedWidth, $layerWidth);
137
138
                //allow items to be stacked in place within the same footprint up to current layerdepth
139 29
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem, $layerDepth);
140
141 29
                $prevItem = $orientatedItem;
142
143 29
                if (!$nextItem) {
144 29
                    $this->usedDepth += $layerDepth;
145
                }
146
            } else {
147
148 24
                $prevItem = null;
149
150 24
                if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
151 23
                    $this->logger->debug("No more fit in lengthwise, resetting for new row");
152 23
                    $this->lengthLeft += $layerLength;
153 23
                    $this->widthLeft -= $layerWidth;
154 23
                    $layerWidth = $layerLength = 0;
155 23
                    $this->items->insert($itemToPack);
156 23
                    continue;
157 18
                } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) {
158 7
                    $this->logger->debug("doesn't fit on layer even when empty");
159 7
                    continue;
160
                }
161
162 17
                $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth();
163 17
                $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength();
164 17
                $this->depthLeft -= $layerDepth;
165 17
                $this->usedDepth += $layerDepth;
166
167 17
                $layerWidth = $layerLength = $layerDepth = 0;
168 17
                $this->logger->debug("doesn't fit, so starting next vertical layer");
169 17
                $this->items->insert($itemToPack);
170
            }
171
        }
172 29
        $this->logger->debug("done with this box");
173 29
        return new PackedBox($this->box, $packedItems, $this->widthLeft, $this->lengthLeft, $this->depthLeft, $this->remainingWeight, $this->usedWidth, $this->usedLength, $this->usedDepth);
174
    }
175
176
    /**
177
     * Get the best orientation for an item
178
     * @param Item $item
179
     * @param OrientatedItem|null $prevItem
180
     * @param Item|null $nextItem
181
     * @param int $widthLeft
182
     * @param int $lengthLeft
183
     * @param int $depthLeft
184
     *
185
     * @return OrientatedItem|false
186
     */
187 29
    protected function findBestOrientation(
188
        Item $item,
189
        OrientatedItem $prevItem = null,
190
        Item $nextItem = null,
191
        $widthLeft,
192
        $lengthLeft,
193
        $depthLeft) {
194
195 29
        $possibleOrientations = $this->findAllPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
196 29
        $orientationsToUse = $this->filterStableOrientations($possibleOrientations, $item, $prevItem, $nextItem);
197
198 29
        $orientationFits = [];
199
        /** @var OrientatedItem $orientation */
200 29
        foreach ($orientationsToUse as $o => $orientation) {
201 29
            $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft - $orientation->getLength());
202 29
            $orientationFits[$o] = $orientationFit;
203
        }
204
205 29
        if (!empty($orientationFits)) {
206 29
            asort($orientationFits);
207 29
            reset($orientationFits);
208 29
            $bestFit = $orientationsToUse[key($orientationFits)];
209 29
            $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]);
210 29
            return $bestFit;
211
        } else {
212 27
            return false;
213
        }
214
    }
215
216
    /**
217
     * Find all possible orientations for an item
218
     * @param Item $item
219
     * @param OrientatedItem|null $prevItem
220
     * @param int $widthLeft
221
     * @param int $lengthLeft
222
     * @param int $depthLeft
223
     *
224
     * @return OrientatedItem[]
225
     */
226 29
    protected function findAllPossibleOrientations(
227
        Item $item,
228
        OrientatedItem $prevItem = null,
229
        $widthLeft,
230
        $lengthLeft,
231
        $depthLeft) {
232
233 29
        $orientations = [];
234
235
        //Special case items that are the same as what we just packed - keep orientation
236 29
        if ($prevItem && $prevItem->getItem() == $item) {
237 12
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
238
        } else {
239
240
            //simple 2D rotation
241 29
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
242 29
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
243
244
            //add 3D rotation if we're allowed
245 29
            if (!$item->getKeepFlat()) {
246 10
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
247 10
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
248 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
249 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
250
            }
251
        }
252
253
        //remove any that simply don't fit
254
        return array_filter($orientations, function(OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
255 29
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
256 29
        });
257
258
    }
259
260
    /**
261
     * Filter a set of orientations allow only those that have a stable base OR
262
     * the item doesn't fit in the box any other way
263
     * the item is the last one left to pack
264
     *
265
     * @param OrientatedItem[] $orientations
266
     * @param Item $item
267
     * @param OrientatedItem|null $prevItem
268
     * @param Item|null $nextItem
269
     *
270
     * @return OrientatedItem[]
271
     */
272 29
    protected function filterStableOrientations(
273
        array $orientations,
274
        Item $item,
275
        OrientatedItem $prevItem = null,
0 ignored issues
show
The parameter $prevItem is not used and could be removed.

This check looks from parameters that have been defined for a function or method, but which are not used in the method body.

Loading history...
276
        Item $nextItem = null
277
    ) {
278 29
        $stableOrientations = $unstableOrientations = $orientationsToUse = [];
279
280 29
        foreach ($orientations as $o => $orientation) {
281 29
            if ($orientation->isStable()) {
282 26
                $stableOrientations[] = $orientation;
283
            } else {
284 29
                $unstableOrientations[] = $orientation;
285
            }
286
        }
287
288 29
        if (count($stableOrientations) > 0) {
289 26
            $orientationsToUse = $stableOrientations;
290 28
        } else if (count($unstableOrientations) > 0) {
291 4
            $orientationsInEmptyBox = $this->findAllPossibleOrientations($item, null, $this->box->getInnerWidth(), $this->box->getInnerLength(), $this->box->getInnerDepth());
292
293 4
            $stableOrientationsInEmptyBox = array_filter(
294
                $orientationsInEmptyBox,
295 4
                function(OrientatedItem $orientation) {
296 4
                    return $orientation->isStable();
297 4
                }
298
            );
299
300 4
            if (is_null($nextItem) || count($stableOrientationsInEmptyBox) == 0) {
301 4
                $orientationsToUse = $unstableOrientations;
302
            }
303
        }
304
305 29
        return $orientationsToUse;
306
    }
307
308
    /**
309
     * Figure out if we can stack the next item vertically on top of this rather than side by side
310
     * Used when we've packed a tall item, and have just put a shorter one next to it
311
     *
312
     * @param ItemList       $packedItems
313
     * @param OrientatedItem $prevItem
314
     * @param Item           $nextItem
315
     * @param OrientatedItem $orientatedItem
316
     * @param int            $layerDepth
317
     *
318
     */
319 29
    protected function tryAndStackItemsIntoSpace(
320
        ItemList $packedItems,
321
        OrientatedItem $prevItem = null,
322
        Item $nextItem = null,
323
        OrientatedItem $orientatedItem,
324
        $layerDepth)
325
    {
326 29
        $stackableDepth = $layerDepth - $orientatedItem->getDepth(); //we already packed this
327
328 29
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
329 27
            $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);
330
331 27
            if ($stackedItem) {
332 1
                $this->remainingWeight -= $this->items->top()->getWeight();
333 1
                $stackableDepth -= $stackedItem->getDepth();
334 1
                $packedItems->insert($this->items->extract());
335
            } else {
336 27
                break;
337
            }
338
        }
339
    }
340
341
    /**
342
     * @param int $layerWidth
343
     * @param int $layerLength
344
     * @param int $layerDepth
345
     *
346
     * @return bool
347
     */
348 24
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
349 24
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
350
    }
351
}
352