Completed
Push — master ( a3b573...a397ce )
by Doug
01:54
created

VolumePacker::findBestOrientation()   C

Complexity

Conditions 9
Paths 48

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 65
Code Lines 37

Code Coverage

Tests 32
CRAP Score 9

Importance

Changes 0
Metric Value
c 0
b 0
f 0
dl 0
loc 65
ccs 32
cts 32
cp 1
rs 6.4766
cc 9
eloc 37
nc 48
nop 6
crap 9

How to fix   Long Method   

Long Method

Small methods make your code easier to understand, in particular if combined with a good name. Besides, if your method is small, finding a good name is usually much easier.

For example, if you find yourself adding comments to a method's body, this is usually a good sign to extract the commented part to a new method, and use the comment as a starting point when coming up with a good name for this new method.

Commonly applied refactorings include:

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(Item $item, OrientatedItem $prevItem = null, Item $nextItem = null, $widthLeft, $lengthLeft, $depthLeft) {
206
207 29
        $orientations = $this->findPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
208
209
        /*
210
         * Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
211
         */
212 29
        $stableOrientations = [];
213 29
        $unstableOrientations = [];
214
215 29
        foreach ($orientations as $o => $orientation) {
216 29
            if ($orientation->isStable()) {
217 26
                $stableOrientations[] = $orientation;
218
            } else {
219 29
                $unstableOrientations[] = $orientation;
220
            }
221
        }
222
223 29
        $orientationsToUse = [];
224
225
        /*
226
         * We prefer to use stable orientations only, but allow unstable ones if either
227
         * the item is the last one left to pack OR
228
         * the item doesn't fit in the box any other way
229
         */
230 29
        if (count($stableOrientations) > 0) {
231 26
            $orientationsToUse = $stableOrientations;
232 28
        } else if (count($unstableOrientations) > 0) {
233 4
            $orientationsInEmptyBox = $this->findPossibleOrientations(
234
                $item,
235
                $prevItem,
236 4
                $this->box->getInnerWidth(),
237 4
                $this->box->getInnerLength(),
238 4
                $this->box->getInnerDepth()
239
            );
240
241 4
            $stableOrientationsInEmptyBox = array_filter(
242
                $orientationsInEmptyBox,
243
                function(OrientatedItem $orientation) {
244 4
                    return $orientation->isStable();
245 4
                }
246
            );
247
248 4
            if (is_null($nextItem) || count($stableOrientationsInEmptyBox) == 0) {
249 4
                $orientationsToUse = $unstableOrientations;
250
            }
251
        }
252
253 29
        $orientationFits = [];
254
        /** @var OrientatedItem $orientation */
255 29
        foreach ($orientationsToUse as $o => $orientation) {
256 29
            $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft  - $orientation->getLength());
257 29
            $orientationFits[$o] = $orientationFit;
258
        }
259
260 29
        if (!empty($orientationFits)) {
261 29
            asort($orientationFits);
262 29
            reset($orientationFits);
263 29
            $bestFit = $orientationsToUse[key($orientationFits)];
264 29
            $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]);
265 29
            return $bestFit;
266
        } else {
267 27
            return false;
268
        }
269
    }
270
271
    /**
272
     * Find all possible orientations for an item
273
     * @param Item $item
274
     * @param OrientatedItem|null $prevItem
275
     * @param int $widthLeft
276
     * @param int $lengthLeft
277
     * @param int $depthLeft
278
     * @return OrientatedItem[]
279
     */
280 29
    protected function findPossibleOrientations(Item $item, OrientatedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) {
281
282 29
        $orientations = [];
283
284
        //Special case items that are the same as what we just packed - keep orientation
285 29
        if ($prevItem && $prevItem->getItem() == $item) {
286 12
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
287
        } else {
288
289
            //simple 2D rotation
290 29
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
291 29
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
292
293
            //add 3D rotation if we're allowed
294 29
            if (!$item->getKeepFlat()) {
295 10
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
296 10
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
297 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
298 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
299
            }
300
        }
301
302
        //remove any that simply don't fit
303 29
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
304 29
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
305 29
        });
306
307
    }
308
309
    /**
310
     * Figure out if we can stack the next item vertically on top of this rather than side by side
311
     * Used when we've packed a tall item, and have just put a shorter one next to it
312
     *
313
     * @param ItemList       $packedItems
314
     * @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...
315
     * @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...
316
     * @param int            $maxWidth
317
     * @param int            $maxLength
318
     * @param int            $maxDepth
319
     */
320 29
    protected function tryAndStackItemsIntoSpace(ItemList $packedItems, OrientatedItem $prevItem = null, Item $nextItem = null, $maxWidth, $maxLength, $maxDepth)
321
    {
322 29
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
323 27
            $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $maxWidth, $maxLength, $maxDepth);
324 27
            if ($stackedItem) {
325 1
                $this->remainingWeight -= $this->items->top()->getWeight();
326 1
                $maxDepth -= $stackedItem->getDepth();
327 1
                $packedItems->insert($this->items->extract());
328
            } else {
329 27
                break;
330
            }
331
        }
332
    }
333
334
    /**
335
     * @param int $layerWidth
336
     * @param int $layerLength
337
     * @param int $layerDepth
338
     * @return bool
339
     */
340 24
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
341 24
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
342
    }
343
}
344