Completed
Push — master ( a397ce...6ae9f5 )
by Doug
12:41
created

VolumePacker::filterStableOrientations()   C

Complexity

Conditions 7
Paths 12

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 44
Code Lines 29

Code Coverage

Tests 22
CRAP Score 7

Importance

Changes 0
Metric Value
dl 0
loc 44
ccs 22
cts 22
cp 1
rs 6.7272
c 0
b 0
f 0
cc 7
eloc 29
nc 12
nop 4
crap 7
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 29
    public function __construct(Box $box, ItemList $items)
80
    {
81 29
        $this->logger = new NullLogger();
82
83 29
        $this->box = $box;
84 29
        $this->items = $items;
85
86 29
        $this->depthLeft = $this->box->getInnerDepth();
87 29
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
88 29
        $this->widthLeft = $this->box->getInnerWidth();
89 29
        $this->lengthLeft = $this->box->getInnerLength();
90
    }
91
92
    /**
93
     * Pack as many items as possible into specific given box
94
     * @return PackedBox packed box
95
     */
96 29
    public function pack()
97
    {
98 29
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
99
100 29
        $packedItems = new ItemList;
101
102 29
        $layerWidth = $layerLength = $layerDepth = 0;
103
104 29
        $prevItem = null;
105
106 29
        while (!$this->items->isEmpty()) {
107
108 29
            $itemToPack = $this->items->extract();
109
110
            //skip items that are simply too heavy
111 29
            if ($itemToPack->getWeight() > $this->remainingWeight) {
112 4
                continue;
113
            }
114
115 29
            $this->logger->debug(
116 29
                "evaluating item {$itemToPack->getDescription()}",
117
                [
118 29
                    'item' => $itemToPack,
119
                    'space' => [
120 29
                        'widthLeft'   => $this->widthLeft,
121 29
                        'lengthLeft'  => $this->lengthLeft,
122 29
                        'depthLeft'   => $this->depthLeft,
123 29
                        'layerWidth'  => $layerWidth,
124 29
                        'layerLength' => $layerLength,
125 29
                        'layerDepth'  => $layerDepth
126
                    ]
127
                ]
128
            );
129
130 29
            $nextItem = !$this->items->isEmpty() ? $this->items->top() : null;
131 29
            $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);
132
133 29
            if ($orientatedItem) {
134
135 29
                $packedItems->insert($orientatedItem->getItem());
136 29
                $this->remainingWeight -= $itemToPack->getWeight();
137
138 29
                $this->lengthLeft -= $orientatedItem->getLength();
139 29
                $layerLength += $orientatedItem->getLength();
140 29
                $layerWidth = max($orientatedItem->getWidth(), $layerWidth);
141
142 29
                $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep
143
144 29
                $this->usedLength = max($this->usedLength, $layerLength);
145 29
                $this->usedWidth = max($this->usedWidth, $layerWidth);
146
147
                //allow items to be stacked in place within the same footprint up to current layerdepth
148 29
                $stackableDepth = $layerDepth - $orientatedItem->getDepth();
149 29
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);
150
151 29
                $prevItem = $orientatedItem;
152
153 29
                if (!$nextItem) {
154 29
                    $this->usedDepth += $layerDepth;
155
                }
156
            } else {
157
158 24
                $prevItem = null;
159
160 24
                if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
161 23
                    $this->logger->debug("No more fit in lengthwise, resetting for new row");
162 23
                    $this->lengthLeft += $layerLength;
163 23
                    $this->widthLeft -= $layerWidth;
164 23
                    $layerWidth = $layerLength = 0;
165 23
                    $this->items->insert($itemToPack);
166 23
                    continue;
167 18
                } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) {
168 7
                    $this->logger->debug("doesn't fit on layer even when empty");
169 7
                    continue;
170
                }
171
172 17
                $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth();
0 ignored issues
show
Documentation Bug introduced by Doug Wright
It seems like $layerWidth ? min(floor(...s->box->getInnerWidth() can also be of type double. However, the property $widthLeft is declared as type integer. Maybe add an additional type check?

Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a mixed type is assigned to a property that is type hinted more strictly.

For example, imagine you have a variable $accountId that can either hold an Id object or false (if there is no account id yet). Your code now assigns that value to the id property of an instance of the Account class. This class holds a proper account, so the id value must no longer be false.

Either this assignment is in error or a type check should be added for that assignment.

class Id
{
    public $id;

    public function __construct($id)
    {
        $this->id = $id;
    }

}

class Account
{
    /** @var  Id $id */
    public $id;
}

$account_id = false;

if (starsAreRight()) {
    $account_id = new Id(42);
}

$account = new Account();
if ($account instanceof Id)
{
    $account->id = $account_id;
}
Loading history...
173 17
                $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength();
0 ignored issues
show
Documentation Bug introduced by Doug Wright
It seems like $layerLength ? min(floor...->box->getInnerLength() can also be of type double. However, the property $lengthLeft is declared as type integer. Maybe add an additional type check?

Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a mixed type is assigned to a property that is type hinted more strictly.

For example, imagine you have a variable $accountId that can either hold an Id object or false (if there is no account id yet). Your code now assigns that value to the id property of an instance of the Account class. This class holds a proper account, so the id value must no longer be false.

Either this assignment is in error or a type check should be added for that assignment.

class Id
{
    public $id;

    public function __construct($id)
    {
        $this->id = $id;
    }

}

class Account
{
    /** @var  Id $id */
    public $id;
}

$account_id = false;

if (starsAreRight()) {
    $account_id = new Id(42);
}

$account = new Account();
if ($account instanceof Id)
{
    $account->id = $account_id;
}
Loading history...
174 17
                $this->depthLeft -= $layerDepth;
175 17
                $this->usedDepth += $layerDepth;
176
177 17
                $layerWidth = $layerLength = $layerDepth = 0;
178 17
                $this->logger->debug("doesn't fit, so starting next vertical layer");
179 17
                $this->items->insert($itemToPack);
180
            }
181
        }
182 29
        $this->logger->debug("done with this box");
183 29
        return new PackedBox(
184 29
            $this->box,
185
            $packedItems,
186 29
            $this->widthLeft,
187 29
            $this->lengthLeft,
188 29
            $this->depthLeft,
189 29
            $this->remainingWeight,
190 29
            $this->usedWidth,
191 29
            $this->usedLength,
192 29
            $this->usedDepth);
193
    }
194
195
    /**
196
     * Get the best orientation for an item
197
     * @param Item $item
198
     * @param OrientatedItem|null $prevItem
199
     * @param Item|null $nextItem
200
     * @param int $widthLeft
201
     * @param int $lengthLeft
202
     * @param int $depthLeft
203
     * @return OrientatedItem|false
204
     */
205 29
    protected function findBestOrientation(
206
        Item $item,
207
        OrientatedItem $prevItem = null,
208
        Item $nextItem = null,
209
        $widthLeft,
210
        $lengthLeft,
211
        $depthLeft) {
212
213 29
        $possibleOrientations = $this->findAllPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
214 29
        $orientationsToUse = $this->filterStableOrientations($possibleOrientations, $item, $prevItem, $nextItem);
215
216 29
        $orientationFits = [];
217
        /** @var OrientatedItem $orientation */
218 29
        foreach ($orientationsToUse as $o => $orientation) {
219 29
            $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft  - $orientation->getLength());
220 29
            $orientationFits[$o] = $orientationFit;
221
        }
222
223 29
        if (!empty($orientationFits)) {
224 29
            asort($orientationFits);
225 29
            reset($orientationFits);
226 29
            $bestFit = $orientationsToUse[key($orientationFits)];
227 29
            $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]);
228 29
            return $bestFit;
229
        } else {
230 27
            return false;
231
        }
232
    }
233
234
    /**
235
     * Find all possible orientations for an item
236
     * @param Item $item
237
     * @param OrientatedItem|null $prevItem
238
     * @param int $widthLeft
239
     * @param int $lengthLeft
240
     * @param int $depthLeft
241
     * @return OrientatedItem[]
242
     */
243 29
    protected function findAllPossibleOrientations(
244
        Item $item,
245
        OrientatedItem $prevItem = null,
246
        $widthLeft,
247
        $lengthLeft,
248
        $depthLeft) {
249
250 29
        $orientations = [];
251
252
        //Special case items that are the same as what we just packed - keep orientation
253 29
        if ($prevItem && $prevItem->getItem() == $item) {
254 12
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
255
        } else {
256
257
            //simple 2D rotation
258 29
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
259 29
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
260
261
            //add 3D rotation if we're allowed
262 29
            if (!$item->getKeepFlat()) {
263 10
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
264 10
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
265 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
266 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
267
            }
268
        }
269
270
        //remove any that simply don't fit
271
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
272 29
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
273 29
        });
274
275
    }
276
277
    /**
278
     * Filter a set of orientations allow only those that have a stable base OR
279
     * the item doesn't fit in the box any other way
280
     * the item is the last one left to pack
281
     *
282
     * @param array $orientations
283
     * @param Item $item
284
     * @param OrientatedItem|null $prevItem
285
     * @param Item|null $nextItem
286
     *
287
     * @return array
288
     */
289 29
    protected function filterStableOrientations(
290
        array $orientations,
291
        Item $item,
292
        OrientatedItem $prevItem = null,
293
        Item $nextItem = null
294
    ) {
295 29
        $stableOrientations = [];
296 29
        $unstableOrientations = [];
297
298 29
        foreach ($orientations as $o => $orientation) {
299 29
            if ($orientation->isStable()) {
300 26
                $stableOrientations[] = $orientation;
301
            } else {
302 29
                $unstableOrientations[] = $orientation;
303
            }
304
        }
305
306 29
        $orientationsToUse = [];
307
308 29
        if (count($stableOrientations) > 0) {
309 26
            $orientationsToUse = $stableOrientations;
310 28
        } else if (count($unstableOrientations) > 0) {
311 4
            $orientationsInEmptyBox = $this->findAllPossibleOrientations(
312
                $item,
313
                $prevItem,
314 4
                $this->box->getInnerWidth(),
315 4
                $this->box->getInnerLength(),
316 4
                $this->box->getInnerDepth()
317
            );
318
319 4
            $stableOrientationsInEmptyBox = array_filter(
320
                $orientationsInEmptyBox,
321 4
                function(OrientatedItem $orientation) {
322 4
                    return $orientation->isStable();
323 4
                }
324
            );
325
326 4
            if (is_null($nextItem) || count($stableOrientationsInEmptyBox) == 0) {
327 4
                $orientationsToUse = $unstableOrientations;
328
            }
329
        }
330
331 29
        return $orientationsToUse;
332
    }
333
334
    /**
335
     * Figure out if we can stack the next item vertically on top of this rather than side by side
336
     * Used when we've packed a tall item, and have just put a shorter one next to it
337
     *
338
     * @param ItemList       $packedItems
339
     * @param OrientatedItem $prevItem
0 ignored issues
show
Documentation introduced by Doug Wright
Should the type for parameter $prevItem not be null|OrientatedItem?

This check looks for @param annotations where the type inferred by our type inference engine differs from the declared type.

It makes a suggestion as to what type it considers more descriptive.

Most often this is a case of a parameter that can be null in addition to its declared types.

Loading history...
340
     * @param Item           $nextItem
0 ignored issues
show
Documentation introduced by Doug Wright
Should the type for parameter $nextItem not be null|Item?

This check looks for @param annotations where the type inferred by our type inference engine differs from the declared type.

It makes a suggestion as to what type it considers more descriptive.

Most often this is a case of a parameter that can be null in addition to its declared types.

Loading history...
341
     * @param int            $maxWidth
342
     * @param int            $maxLength
343
     * @param int            $maxDepth
344
     */
345 29
    protected function tryAndStackItemsIntoSpace(ItemList $packedItems, OrientatedItem $prevItem = null, Item $nextItem = null, $maxWidth, $maxLength, $maxDepth)
346
    {
347 29
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
348 27
            $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $maxWidth, $maxLength, $maxDepth);
349 27
            if ($stackedItem) {
350 1
                $this->remainingWeight -= $this->items->top()->getWeight();
351 1
                $maxDepth -= $stackedItem->getDepth();
352 1
                $packedItems->insert($this->items->extract());
353
            } else {
354 27
                break;
355
            }
356
        }
357
    }
358
359
    /**
360
     * @param int $layerWidth
361
     * @param int $layerLength
362
     * @param int $layerDepth
363
     * @return bool
364
     */
365 24
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
366 24
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
367
    }
368
}
369