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(); |
|
|
|
|
173
|
17 |
|
$this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength(); |
|
|
|
|
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 |
|
|
|
|
315
|
|
|
* @param Item $nextItem |
|
|
|
|
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
|
|
|
|
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 theid
property of an instance of theAccount
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.