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\LoggerInterface; |
12
|
|
|
use Psr\Log\NullLogger; |
13
|
|
|
|
14
|
|
|
/** |
15
|
|
|
* Actual packer |
16
|
|
|
* @author Doug Wright |
17
|
|
|
* @package BoxPacker |
18
|
|
|
*/ |
19
|
|
|
class VolumePacker implements LoggerAwareInterface |
20
|
|
|
{ |
21
|
|
|
use LoggerAwareTrait; |
22
|
|
|
|
23
|
|
|
/** |
24
|
|
|
* Box to pack items into |
25
|
|
|
* @var Box |
26
|
|
|
*/ |
27
|
|
|
protected $box; |
28
|
|
|
|
29
|
|
|
/** |
30
|
|
|
* @var int |
31
|
|
|
*/ |
32
|
|
|
protected $boxWidth; |
33
|
|
|
|
34
|
|
|
/** |
35
|
|
|
* @var int |
36
|
|
|
*/ |
37
|
|
|
protected $boxLength; |
38
|
|
|
|
39
|
|
|
/** |
40
|
|
|
* List of items to be packed |
41
|
|
|
* @var ItemList |
42
|
|
|
*/ |
43
|
|
|
protected $items; |
44
|
|
|
|
45
|
|
|
/** |
46
|
|
|
* List of items to be packed |
47
|
|
|
* @var ItemList |
48
|
|
|
*/ |
49
|
|
|
protected $skippedItems; |
50
|
|
|
|
51
|
|
|
/** |
52
|
|
|
* Remaining weight capacity of the box |
53
|
|
|
* @var int |
54
|
|
|
*/ |
55
|
|
|
protected $remainingWeight; |
56
|
|
|
|
57
|
|
|
/** |
58
|
|
|
* Constructor |
59
|
|
|
* |
60
|
|
|
* @param Box $box |
61
|
|
|
* @param ItemList $items |
62
|
|
|
*/ |
63
|
36 |
|
public function __construct(Box $box, ItemList $items) |
64
|
|
|
{ |
65
|
36 |
|
$this->box = $box; |
66
|
36 |
|
$this->items = $items; |
67
|
|
|
|
68
|
36 |
|
$this->boxWidth = max($this->box->getInnerWidth(), $this->box->getInnerLength()); |
69
|
36 |
|
$this->boxLength = min($this->box->getInnerWidth(), $this->box->getInnerLength()); |
70
|
36 |
|
$this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight(); |
71
|
36 |
|
$this->skippedItems = new ItemList(); |
72
|
36 |
|
$this->logger = new NullLogger(); |
73
|
|
|
} |
74
|
|
|
|
75
|
|
|
/** |
76
|
|
|
* Pack as many items as possible into specific given box |
77
|
|
|
* |
78
|
|
|
* @return PackedBox packed box |
79
|
|
|
*/ |
80
|
36 |
|
public function pack() |
81
|
|
|
{ |
82
|
36 |
|
$this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}"); |
83
|
|
|
|
84
|
36 |
|
$packedItems = new PackedItemList; |
85
|
36 |
|
$prevItem = null; |
86
|
|
|
|
87
|
36 |
|
$x = $y = $z = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0; |
88
|
|
|
|
89
|
36 |
|
$packingWidthLeft = $this->boxWidth; |
90
|
36 |
|
$packingLengthLeft = $this->boxLength; |
91
|
36 |
|
$packingDepthLeft = $this->box->getInnerDepth(); |
92
|
|
|
|
93
|
36 |
|
while (!$this->items->isEmpty()) { |
94
|
36 |
|
$itemToPack = $this->items->extract(); |
95
|
36 |
|
$isLastItem = $this->skippedItems->isEmpty() && $this->items->isEmpty(); |
96
|
|
|
|
97
|
|
|
//skip items that are simply too heavy or too large |
98
|
36 |
|
if (!$this->checkConstraints($itemToPack, $packedItems, $prevItem)) { |
99
|
9 |
|
$this->rebuildItemList(); |
100
|
9 |
|
continue; |
101
|
|
|
} |
102
|
|
|
|
103
|
36 |
|
$orientatedItem = $this->getOrientationForItem($itemToPack, $prevItem, $isLastItem, $packingWidthLeft, $packingLengthLeft, $packingDepthLeft); |
104
|
|
|
|
105
|
36 |
|
if ($orientatedItem instanceof OrientatedItem) { |
106
|
36 |
|
$packedItem = PackedItem::fromOrientatedItem($orientatedItem, $x, $y, $z); |
107
|
36 |
|
$packedItems->insert($packedItem); |
108
|
36 |
|
$this->remainingWeight -= $orientatedItem->getItem()->getWeight(); |
109
|
36 |
|
$packingWidthLeft -= $orientatedItem->getWidth(); |
110
|
|
|
|
111
|
36 |
|
$rowWidth += $orientatedItem->getWidth(); |
112
|
36 |
|
$rowLength = max($rowLength, $orientatedItem->getLength()); |
113
|
36 |
|
$layerDepth = max($layerDepth, $orientatedItem->getDepth()); |
114
|
|
|
|
115
|
|
|
//allow items to be stacked in place within the same footprint up to current layer depth |
116
|
36 |
|
$stackableDepth = $layerDepth - $orientatedItem->getDepth(); |
117
|
36 |
|
$this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth, $x, $y, $z + $orientatedItem->getDepth()); |
118
|
36 |
|
$x += $orientatedItem->getWidth(); |
119
|
|
|
|
120
|
36 |
|
$prevItem = $packedItem; |
121
|
|
|
|
122
|
36 |
|
$this->rebuildItemList(); |
123
|
|
|
} else { |
124
|
24 |
|
if ($layerWidth == 0 && $layerDepth == 0) { // zero items on layer |
125
|
5 |
|
$this->logger->debug("doesn't fit on layer even when empty, skipping for good"); |
126
|
5 |
|
$prevItem = null; |
127
|
5 |
|
continue; |
128
|
24 |
|
} elseif (!$this->items->isEmpty()) { // skip for now, move on to the next item |
129
|
20 |
|
$this->logger->debug("doesn't fit, skipping for now"); |
130
|
20 |
|
$this->skippedItems->insert($itemToPack); |
131
|
24 |
|
} elseif ($x > 0 && $packingLengthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength())) { |
132
|
24 |
|
$this->logger->debug("No more fit in width wise, resetting for new row"); |
133
|
24 |
|
$layerWidth = max($layerWidth, $rowWidth); |
134
|
24 |
|
$layerLength += $rowLength; |
135
|
24 |
|
$packingWidthLeft += $rowWidth; |
136
|
24 |
|
$packingLengthLeft -= $rowLength; |
137
|
24 |
|
$y += $rowLength; |
138
|
24 |
|
$x = $rowWidth = $rowLength = 0; |
139
|
24 |
|
$this->rebuildItemList(); |
140
|
24 |
|
$this->items->insert($itemToPack); |
141
|
24 |
|
$prevItem = null; |
142
|
24 |
|
continue; |
143
|
|
|
} else { |
144
|
17 |
|
$this->logger->debug("no items fit, so starting next vertical layer"); |
145
|
|
|
|
146
|
17 |
|
$layerWidth = max($layerWidth, $rowWidth); |
147
|
17 |
|
$layerLength += $rowLength; |
148
|
17 |
|
$packingWidthLeft = $rowWidth ? min(floor($layerWidth * 1.1), $this->boxWidth) : $this->boxWidth; |
149
|
17 |
|
$packingLengthLeft = $rowLength ? min(floor($layerLength * 1.1), $this->boxLength) : $this->boxLength; |
150
|
17 |
|
$packingDepthLeft -= $layerDepth; |
151
|
|
|
|
152
|
17 |
|
$z += $layerDepth; |
153
|
17 |
|
$x = $y = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0; |
154
|
|
|
|
155
|
17 |
|
$this->rebuildItemList(); |
156
|
17 |
|
$this->items->insert($itemToPack); |
157
|
17 |
|
$prevItem = null; |
158
|
|
|
} |
159
|
|
|
} |
160
|
|
|
} |
161
|
36 |
|
$this->logger->debug("done with this box"); |
162
|
36 |
|
return new PackedBox($this->box, $packedItems); |
163
|
|
|
} |
164
|
|
|
|
165
|
|
|
/** |
166
|
|
|
* @param Item $itemToPack |
167
|
|
|
* @param PackedItem|null $prevItem |
168
|
|
|
* @param bool $isLastItem |
169
|
|
|
* @param int $maxWidth |
170
|
|
|
* @param int $maxLength |
171
|
|
|
* @param int $maxDepth |
172
|
|
|
* |
173
|
|
|
* @return OrientatedItem|false |
174
|
|
|
*/ |
175
|
36 |
|
protected function getOrientationForItem( |
176
|
|
|
Item $itemToPack, |
177
|
|
|
PackedItem $prevItem = null, |
178
|
|
|
$isLastItem, |
179
|
|
|
$maxWidth, |
180
|
|
|
$maxLength, |
181
|
|
|
$maxDepth |
182
|
|
|
) { |
183
|
36 |
|
$this->logger->debug( |
184
|
36 |
|
"evaluating item {$itemToPack->getDescription()} for fit", |
185
|
|
|
[ |
186
|
36 |
|
'item' => $itemToPack, |
187
|
|
|
'space' => [ |
188
|
36 |
|
'maxWidth' => $maxWidth, |
189
|
36 |
|
'maxLength' => $maxLength, |
190
|
36 |
|
'maxDepth' => $maxDepth, |
191
|
|
|
] |
192
|
|
|
] |
193
|
|
|
); |
194
|
|
|
|
195
|
36 |
|
$orientatedItemFactory = new OrientatedItemFactory(); |
196
|
36 |
|
$orientatedItemFactory->setLogger($this->logger); |
197
|
36 |
|
$orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevItem, $isLastItem, $maxWidth, $maxLength, $maxDepth); |
198
|
|
|
|
199
|
36 |
|
return $orientatedItem; |
200
|
|
|
} |
201
|
|
|
|
202
|
|
|
/** |
203
|
|
|
* Figure out if we can stack the next item vertically on top of this rather than side by side |
204
|
|
|
* Used when we've packed a tall item, and have just put a shorter one next to it |
205
|
|
|
* |
206
|
|
|
* @param PackedItemList $packedItems |
207
|
|
|
* @param PackedItem $prevItem |
|
|
|
|
208
|
|
|
* @param int $maxWidth |
209
|
|
|
* @param int $maxLength |
210
|
|
|
* @param int $maxDepth |
211
|
|
|
* @param int $x |
212
|
|
|
* @param int $y |
213
|
|
|
* @param int $z |
214
|
|
|
*/ |
215
|
36 |
|
protected function tryAndStackItemsIntoSpace( |
216
|
|
|
PackedItemList $packedItems, |
217
|
|
|
PackedItem $prevItem = null, |
218
|
|
|
$maxWidth, |
219
|
|
|
$maxLength, |
220
|
|
|
$maxDepth, |
221
|
|
|
$x, |
222
|
|
|
$y, |
223
|
|
|
$z |
224
|
|
|
) { |
225
|
36 |
|
while (!$this->items->isEmpty() && $this->checkNonDimensionalConstraints($this->items->top(), $packedItems)) { |
226
|
32 |
|
$stackedItem = $this->getOrientationForItem( |
227
|
32 |
|
$this->items->top(), |
228
|
32 |
|
$prevItem, |
229
|
32 |
|
$this->items->count() === 1, |
230
|
32 |
|
$maxWidth, |
231
|
32 |
|
$maxLength, |
232
|
32 |
|
$maxDepth |
233
|
|
|
); |
234
|
32 |
|
if ($stackedItem) { |
235
|
3 |
|
$this->remainingWeight -= $this->items->top()->getWeight(); |
236
|
3 |
|
$packedItems->insert(PackedItem::fromOrientatedItem($stackedItem, $x, $y, $z)); |
237
|
3 |
|
$this->items->extract(); |
238
|
3 |
|
$maxDepth -= $stackedItem->getDepth(); |
239
|
3 |
|
$z += $stackedItem->getDepth(); |
240
|
|
|
} else { |
241
|
32 |
|
break; |
242
|
|
|
} |
243
|
|
|
} |
244
|
|
|
} |
245
|
|
|
|
246
|
|
|
/** |
247
|
|
|
* Check item generally fits into box |
248
|
|
|
* |
249
|
|
|
* @param Item $itemToPack |
250
|
|
|
* @param PackedItemList $packedItems |
251
|
|
|
* @param PackedItem|null $prevItem |
252
|
|
|
* |
253
|
|
|
* @return bool |
254
|
|
|
*/ |
255
|
36 |
|
protected function checkConstraints( |
256
|
|
|
Item $itemToPack, |
257
|
|
|
PackedItemList $packedItems, |
258
|
|
|
PackedItem $prevItem = null |
259
|
|
|
) { |
260
|
36 |
|
return $this->checkNonDimensionalConstraints($itemToPack, $packedItems) && |
261
|
36 |
|
$this->checkDimensionalConstraints($itemToPack, $prevItem); |
262
|
|
|
} |
263
|
|
|
|
264
|
|
|
/** |
265
|
|
|
* As well as purely dimensional constraints, there are other constraints that need to be met |
266
|
|
|
* e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box) |
267
|
|
|
* |
268
|
|
|
* @param Item $itemToPack |
269
|
|
|
* @param PackedItemList $packedItems |
270
|
|
|
* |
271
|
|
|
* @return bool |
272
|
|
|
*/ |
273
|
36 |
|
protected function checkNonDimensionalConstraints(Item $itemToPack, PackedItemList $packedItems) |
274
|
|
|
{ |
275
|
36 |
|
$weightOK = $itemToPack->getWeight() <= $this->remainingWeight; |
276
|
|
|
|
277
|
36 |
|
if ($itemToPack instanceof ConstrainedItem) { |
278
|
1 |
|
return $weightOK && $itemToPack->canBePackedInBox(clone $packedItems, $this->box); |
279
|
|
|
} |
280
|
|
|
|
281
|
35 |
|
return $weightOK; |
282
|
|
|
} |
283
|
|
|
|
284
|
|
|
/** |
285
|
|
|
* Check the item physically fits in the box (at all) |
286
|
|
|
* |
287
|
|
|
* @param Item $itemToPack |
288
|
|
|
* @param PackedItem|null $prevItem |
289
|
|
|
* |
290
|
|
|
* @return bool |
291
|
|
|
*/ |
292
|
36 |
|
protected function checkDimensionalConstraints(Item $itemToPack, PackedItem $prevItem = null) |
|
|
|
|
293
|
|
|
{ |
294
|
36 |
|
$orientatedItemFactory = new OrientatedItemFactory(); |
295
|
36 |
|
$orientatedItemFactory->setLogger($this->logger); |
296
|
36 |
|
return !!$orientatedItemFactory->getPossibleOrientationsInEmptyBox($itemToPack, $this->box); |
297
|
|
|
} |
298
|
|
|
|
299
|
|
|
/** |
300
|
|
|
* Reintegrate skipped items into main list when nothing left to process |
301
|
|
|
*/ |
302
|
36 |
|
protected function rebuildItemList() { |
303
|
36 |
|
if ($this->items->isEmpty()) { |
304
|
36 |
|
$this->items = $this->skippedItems; |
305
|
36 |
|
$this->skippedItems = new ItemList(); |
306
|
|
|
} |
307
|
|
|
} |
308
|
|
|
} |
309
|
|
|
|
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.