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\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 |
||
0 ignored issues
–
show
|
|||
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) |
|
0 ignored issues
–
show
|
|||
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.