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