Completed
Push — phpdbg_code_coverage ( eb8624...05e6a0 )
by Doug
06:08 queued 01:36
created

VolumePacker.php (4 issues)

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
     * 3D rotation of items is a WIP and should not be used in production environments
24
     */
25
    const ALWAYS_SHIP_FLAT = true;
26
27
    /**
28
     * Box to pack items into
29
     * @var Box
30
     */
31
    protected $box;
32
33
    /**
34
     * List of items to be packed
35
     * @var ItemList
36
     */
37
    protected $items;
38
39
    /**
40
     * Remaining width of the box to pack items into
41
     * @var int
42
     */
43
    protected $widthLeft;
44
45
    /**
46
     * Remaining length of the box to pack items into
47
     * @var int
48
     */
49
    protected $lengthLeft;
50
51
    /**
52
     * Remaining depth of the box to pack items into
53
     * @var int
54
     */
55
    protected $depthLeft;
56
57
    /**
58
     * Remaining weight capacity of the box
59
     * @var int
60
     */
61
    protected $remainingWeight;
62
63
    /**
64
     * Used width inside box for packing items
65
     * @var int
66
     */
67
    protected $usedWidth = 0;
68
69
    /**
70
     * Used length inside box for packing items
71
     * @var int
72
     */
73
    protected $usedLength = 0;
74
75
    /**
76
     * Used depth inside box for packing items
77
     * @var int
78
     */
79
    protected $usedDepth = 0;
80
81
    /**
82
     * Constructor
83
     */
84
    public function __construct(Box $box, ItemList $items)
85
    {
86
        $this->logger = new NullLogger();
87
88
        $this->box = $box;
89
        $this->items = $items;
90
91
        $this->depthLeft = $this->box->getInnerDepth();
92
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
93
        $this->widthLeft = $this->box->getInnerWidth();
94
        $this->lengthLeft = $this->box->getInnerLength();
95
    }
96
97
    /**
98
     * Pack as many items as possible into specific given box
99
     * @return PackedBox packed box
100
     */
101
    public function pack()
102
    {
103
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
104
105
        $packedItems = new ItemList;
106
107
        $layerWidth = $layerLength = $layerDepth = 0;
108
109
        $prevItem = null;
110
111
        while (!$this->items->isEmpty()) {
112
113
            $itemToPack = $this->items->extract();
114
115
            //skip items that are simply too heavy
116
            if ($itemToPack->getWeight() > $this->remainingWeight) {
117
                continue;
118
            }
119
120
            $this->logger->debug(
121
                "evaluating item {$itemToPack->getDescription()}",
122
                [
123
                    'item' => $itemToPack,
124
                    'space' => [
125
                        'widthLeft'   => $this->widthLeft,
126
                        'lengthLeft'  => $this->lengthLeft,
127
                        'depthLeft'   => $this->depthLeft,
128
                        'layerWidth'  => $layerWidth,
129
                        'layerLength' => $layerLength,
130
                        'layerDepth'  => $layerDepth
131
                    ]
132
                ]
133
            );
134
135
            $nextItem = !$this->items->isEmpty() ? $this->items->top() : null;
136
            $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);
137
138
            if ($orientatedItem) {
139
140
                $packedItems->insert($orientatedItem->getItem());
141
                $this->remainingWeight -= $itemToPack->getWeight();
142
143
                $this->lengthLeft -= $orientatedItem->getLength();
144
                $layerLength += $orientatedItem->getLength();
145
                $layerWidth = max($orientatedItem->getWidth(), $layerWidth);
146
147
                $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep
148
149
                $this->usedLength = max($this->usedLength, $layerLength);
150
                $this->usedWidth = max($this->usedWidth, $layerWidth);
151
152
                //allow items to be stacked in place within the same footprint up to current layerdepth
153
                $stackableDepth = $layerDepth - $orientatedItem->getDepth();
154
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);
155
156
                $prevItem = $orientatedItem;
157
158
                if (!$nextItem) {
159
                    $this->usedDepth += $layerDepth;
160
                }
161
            } else {
162
163
                $prevItem = null;
164
165
                if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
166
                    $this->logger->debug("No more fit in lengthwise, resetting for new row");
167
                    $this->lengthLeft += $layerLength;
168
                    $this->widthLeft -= $layerWidth;
169
                    $layerWidth = $layerLength = 0;
170
                    $this->items->insert($itemToPack);
171
                    continue;
172
                } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) {
173
                    $this->logger->debug("doesn't fit on layer even when empty");
174
                    continue;
175
                }
176
177
                $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth();
0 ignored issues
show
Documentation Bug introduced by
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...
178
                $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength();
0 ignored issues
show
Documentation Bug introduced by
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...
179
                $this->depthLeft -= $layerDepth;
180
                $this->usedDepth += $layerDepth;
181
182
                $layerWidth = $layerLength = $layerDepth = 0;
183
                $this->logger->debug("doesn't fit, so starting next vertical layer");
184
                $this->items->insert($itemToPack);
185
            }
186
        }
187
        $this->logger->debug("done with this box");
188
        return new PackedBox(
189
            $this->box,
190
            $packedItems,
191
            $this->widthLeft,
192
            $this->lengthLeft,
193
            $this->depthLeft,
194
            $this->remainingWeight,
195
            $this->usedWidth,
196
            $this->usedLength,
197
            $this->usedDepth);
198
    }
199
200
    /**
201
     * Get the best orientation for an item
202
     * @param Item $item
203
     * @param OrientatedItem|null $prevItem
204
     * @param Item|null $nextItem
205
     * @param int $widthLeft
206
     * @param int $lengthLeft
207
     * @param int $depthLeft
208
     * @return OrientatedItem|false
209
     */
210
    protected function findBestOrientation(Item $item, OrientatedItem $prevItem = null, Item $nextItem = null, $widthLeft, $lengthLeft, $depthLeft) {
211
212
        $orientations = $this->findPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
213
214
        // special casing based on next item
215
        if (isset($orientations[0]) && $nextItem == $item && $lengthLeft >= 2 * $item->getLength()) {
216
            $this->logger->debug("not rotating based on next item");
217
            return $orientations[0]; // XXX this is tied to the ordering from ->findPossibleOrientations()
218
        }
219
220
        $orientationFits = [];
221
222
        /** @var OrientatedItem $orientation */
223
        foreach ($orientations as $o => $orientation) {
224
            $orientationFit = min($widthLeft   - $orientation->getWidth(), $lengthLeft  - $orientation->getLength());
225
            $orientationFits[$o] = $orientationFit;
226
        }
227
228
        if (!empty($orientationFits)) {
229
            asort($orientationFits);
230
            reset($orientationFits);
231
            $bestFit = key($orientationFits);
232
            $this->logger->debug("Using orientation #{$bestFit}");
233
            return $orientations[$bestFit];
234
        } else {
235
            return false;
236
        }
237
    }
238
239
    /**
240
     * Find all possible orientations for an item
241
     * @param Item $item
242
     * @param OrientatedItem|null $prevItem
243
     * @param int $widthLeft
244
     * @param int $lengthLeft
245
     * @param int $depthLeft
246
     * @return OrientatedItem[]
247
     */
248
    protected function findPossibleOrientations(Item $item, OrientatedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) {
249
250
        $orientations = [];
251
252
        //Special case items that are the same as what we just packed - keep orientation
253
        if ($prevItem && $prevItem->getItem() == $item) {
254
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
255
        } else {
256
257
            //simple 2D rotation
258
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
259
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
260
261
            //add 3D rotation if we're allowed
262
            if (self::ALWAYS_SHIP_FLAT === false && !$item->getKeepFlat()) {
263
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
264
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
265
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
266
                $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
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
273
        });
274
275
    }
276
277
    /**
278
     * Figure out if we can stack the next item vertically on top of this rather than side by side
279
     * Used when we've packed a tall item, and have just put a shorter one next to it
280
     *
281
     * @param ItemList       $packedItems
282
     * @param OrientatedItem $prevItem
0 ignored issues
show
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...
283
     * @param Item           $nextItem
0 ignored issues
show
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...
284
     * @param int            $maxWidth
285
     * @param int            $maxLength
286
     * @param int            $maxDepth
287
     */
288
    protected function tryAndStackItemsIntoSpace(ItemList $packedItems, OrientatedItem $prevItem = null, Item $nextItem = null, $maxWidth, $maxLength, $maxDepth)
289
    {
290
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
291
            $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $maxWidth, $maxLength, $maxDepth);
292
            if ($stackedItem) {
293
                $this->remainingWeight -= $this->items->top()->getWeight();
294
                $maxDepth -= $stackedItem->getDepth();
295
                $packedItems->insert($this->items->extract());
296
            } else {
297
                break;
298
            }
299
        }
300
    }
301
302
    /**
303
     * @param int $layerWidth
304
     * @param int $layerLength
305
     * @param int $layerDepth
306
     * @return bool
307
     */
308
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
309
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
310
    }
311
}
312