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