Completed
Push — master ( b1bff8...d49723 )
by Doug
05:05
created

VolumePacker::checkDimensionalConstraints()   A

Complexity

Conditions 1
Paths 1

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 11
Code Lines 8

Code Coverage

Tests 8
CRAP Score 1

Importance

Changes 0
Metric Value
dl 0
loc 11
ccs 8
cts 8
cp 1
rs 9.4285
c 0
b 0
f 0
cc 1
eloc 8
nc 1
nop 3
crap 1
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
     * @var int
78
     */
79
    protected $layerWidth = 0;
80
81
    /**
82
     * @var int
83
     */
84
    protected $layerLength = 0;
85
86
    /**
87
     * @var int
88
     */
89
    protected $layerDepth = 0;
90
91
    /**
92
     * Constructor
93
     *
94
     * @param Box      $box
95
     * @param ItemList $items
96
     */
97 33
    public function __construct(Box $box, ItemList $items)
98
    {
99 33
        $this->logger = new NullLogger();
100
101 33
        $this->box = $box;
102 33
        $this->items = $items;
103
104 33
        $this->depthLeft = $this->box->getInnerDepth();
105 33
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
106 33
        $this->widthLeft = $this->box->getInnerWidth();
107 33
        $this->lengthLeft = $this->box->getInnerLength();
108
    }
109
110
    /**
111
     * Pack as many items as possible into specific given box
112
     * @return PackedBox packed box
113
     */
114 33
    public function pack()
115
    {
116 33
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
117
118 33
        $packedItems = new ItemList;
119
120 33
        $this->layerWidth = $this->layerLength = $this->layerDepth = 0;
121
122 33
        $prevItem = null;
123
124 33
        while (!$this->items->isEmpty()) {
125
126 33
            $itemToPack = $this->items->extract();
127 33
            $nextItem = !$this->items->isEmpty() ? $this->items->top() : null;
128
129
            //skip items that are simply too heavy or too large
130 33
            if (!$this->checkConstraints($itemToPack, $packedItems, $prevItem, $nextItem)) {
131 9
                continue;
132
            }
133
134 33
            $orientatedItem = $this->getOrientationForItem($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);
135
136 33
            if ($orientatedItem) {
137
138 33
                $packedItems->insert($orientatedItem->getItem());
139 33
                $this->remainingWeight -= $orientatedItem->getItem()->getWeight();
140
141 33
                $this->lengthLeft -= $orientatedItem->getLength();
142 33
                $this->layerLength += $orientatedItem->getLength();
143 33
                $this->layerWidth = max($orientatedItem->getWidth(), $this->layerWidth);
144
145 33
                $this->layerDepth = max($this->layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep
146
147 33
                $this->usedLength = max($this->usedLength, $this->layerLength);
148 33
                $this->usedWidth = max($this->usedWidth, $this->layerWidth);
149
150
                //allow items to be stacked in place within the same footprint up to current layerdepth
151 33
                $stackableDepth = $this->layerDepth - $orientatedItem->getDepth();
152 33
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);
153
154 33
                $prevItem = $orientatedItem;
155
156 33
                if ($this->items->isEmpty()) {
157 33
                    $this->usedDepth += $this->layerDepth;
158
                }
159
            } else {
160
161 23
                $prevItem = null;
162
163 23
                if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted()) {
164 23
                    $this->logger->debug("No more fit in lengthwise, resetting for new row");
165 23
                    $this->lengthLeft += $this->layerLength;
166 23
                    $this->widthLeft -= $this->layerWidth;
167 23
                    $this->layerWidth = $this->layerLength = 0;
168 23
                    $this->items->insert($itemToPack);
169 23
                    continue;
170 17
                } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $this->layerDepth == 0) {
171 5
                    $this->logger->debug("doesn't fit on layer even when empty");
172 5
                    $this->usedDepth += $this->layerDepth;
173 5
                    continue;
174
                }
175
176 16
                $this->widthLeft = $this->layerWidth ? min(floor($this->layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth();
0 ignored issues
show
Documentation Bug introduced by Doug Wright
It seems like $this->layerWidth ? min(...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...
177 16
                $this->lengthLeft = $this->layerLength ? min(floor($this->layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength();
0 ignored issues
show
Documentation Bug introduced by Doug Wright
It seems like $this->layerLength ? min...->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...
178 16
                $this->depthLeft -= $this->layerDepth;
179 16
                $this->usedDepth += $this->layerDepth;
180
181 16
                $this->layerWidth = $this->layerLength = $this->layerDepth = 0;
182 16
                $this->logger->debug("doesn't fit, so starting next vertical layer");
183 16
                $this->items->insert($itemToPack);
184
            }
185
        }
186 33
        $this->logger->debug("done with this box");
187 33
        return new PackedBox(
188 33
            $this->box,
189 33
            $packedItems,
190 33
            $this->widthLeft,
191 33
            $this->lengthLeft,
192 33
            $this->depthLeft,
193 33
            $this->remainingWeight,
194 33
            $this->usedWidth,
195 33
            $this->usedLength,
196 33
            $this->usedDepth);
197
    }
198
199
    /**
200
     * @param Item $itemToPack
201
     * @param OrientatedItem|null $prevItem
202
     * @param Item|null $nextItem
203
     * @param int $maxWidth
204
     * @param int $maxLength
205
     * @param int $maxDepth
206
     *
207
     * @return OrientatedItem|false
208
     */
209 33
    protected function getOrientationForItem(
210
        Item $itemToPack,
211
        OrientatedItem $prevItem = null,
212
        Item $nextItem = null,
213
        $maxWidth, $maxLength,
214
        $maxDepth
215
    ) {
216 33
        $this->logger->debug(
217 33
            "evaluating item {$itemToPack->getDescription()} for fit",
218
            [
219 33
                'item' => $itemToPack,
220
                'space' => [
221 33
                    'maxWidth'    => $maxWidth,
222 33
                    'maxLength'   => $maxLength,
223 33
                    'maxDepth'    => $maxDepth,
224 33
                    'layerWidth'  => $this->layerWidth,
225 33
                    'layerLength' => $this->layerLength,
226 33
                    'layerDepth'  => $this->layerDepth
227
                ]
228
            ]
229
        );
230
231 33
        $orientatedItemFactory = new OrientatedItemFactory();
232 33
        $orientatedItemFactory->setLogger($this->logger);
233 33
        $orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevItem, $nextItem, $maxWidth, $maxLength, $maxDepth);
234
235 33
        return $orientatedItem;
236
    }
237
238
    /**
239
     * Figure out if we can stack the next item vertically on top of this rather than side by side
240
     * Used when we've packed a tall item, and have just put a shorter one next to it
241
     *
242
     * @param ItemList       $packedItems
243
     * @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...
244
     * @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...
245
     * @param int            $maxWidth
246
     * @param int            $maxLength
247
     * @param int            $maxDepth
248
     */
249 33
    protected function tryAndStackItemsIntoSpace(
250
        ItemList $packedItems,
251
        OrientatedItem $prevItem = null,
252
        Item $nextItem = null,
253
        $maxWidth,
254
        $maxLength,
255
        $maxDepth
256
    ) {
257 33
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
258 31
            $stackedItem = $this->getOrientationForItem(
259 31
                $this->items->top(),
260 31
                $prevItem,
261 31
                $nextItem,
262 31
                $maxWidth,
263 31
                $maxLength,
264 31
                $maxDepth
265
            );
266 31
            if ($stackedItem) {
267 3
                $this->remainingWeight -= $this->items->top()->getWeight();
268 3
                $maxDepth -= $stackedItem->getDepth();
269 3
                $packedItems->insert($this->items->extract());
270
            } else {
271 31
                break;
272
            }
273
        }
274
    }
275
276
    /**
277
     * @return bool
278
     */
279 23
    protected function isLayerStarted()
280
    {
281 23
        return $this->layerWidth > 0 && $this->layerLength > 0 && $this->layerDepth > 0;
282
    }
283
284
285
    /**
286
     * Check item generally fits into box
287
     *
288
     * @param Item            $itemToPack
289
     * @param ItemList  $packedItems
290
     * @param OrientatedItem|null $prevItem
291
     * @param Item|null       $nextItem
292
     *
293
     * @return bool
294
     */
295 33
    protected function checkConstraints(
296
        Item $itemToPack,
297
        ItemList $packedItems,
298
        OrientatedItem $prevItem = null,
299
        Item $nextItem = null
300
    ) {
301 33
        return $this->checkNonDimensionalConstraints($itemToPack, $packedItems) &&
302 33
               $this->checkDimensionalConstraints($itemToPack, $prevItem, $nextItem);
303
    }
304
305
    /**
306
     * As well as purely dimensional constraints, there are other constraints that need to be met
307
     * e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box)
308
     *
309
     * @param Item     $itemToPack
310
     * @param ItemList $packedItems
311
     *
312
     * @return bool
313
     */
314 33
    protected function checkNonDimensionalConstraints(Item $itemToPack, ItemList $packedItems)
315
    {
316 33
        $weightOK = $itemToPack->getWeight() <= $this->remainingWeight;
317
318 33
        if ($itemToPack instanceof ConstrainedItem) {
319 1
            return $weightOK && $itemToPack->canBePackedInBox(clone $packedItems, $this->box);
320
        }
321
322 32
        return $weightOK;
323
    }
324
325
    /**
326
     * Check the item physically fits in the box (at all)
327
     *
328
     * @param Item            $itemToPack
329
     * @param OrientatedItem|null $prevItem
330
     * @param Item|null       $nextItem
331
     *
332
     * @return bool
333
     */
334 33
    protected function checkDimensionalConstraints(Item $itemToPack, OrientatedItem $prevItem = null, Item $nextItem = null)
335
    {
336 33
        return !!$this->getOrientationForItem(
337 33
            $itemToPack,
338 33
            $prevItem,
339 33
            $nextItem,
340 33
            $this->box->getInnerWidth(),
341 33
            $this->box->getInnerLength(),
342 33
            $this->box->getInnerDepth()
343
        );
344
    }
345
}
346