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\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 | * @param Box $box |
||
80 | * @param ItemList $items |
||
81 | */ |
||
82 | 29 | public function __construct(Box $box, ItemList $items) |
|
83 | { |
||
84 | 29 | $this->logger = new NullLogger(); |
|
85 | |||
86 | 29 | $this->box = $box; |
|
87 | 29 | $this->items = $items; |
|
88 | |||
89 | 29 | $this->depthLeft = $this->box->getInnerDepth(); |
|
90 | 29 | $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight(); |
|
91 | 29 | $this->widthLeft = $this->box->getInnerWidth(); |
|
92 | 29 | $this->lengthLeft = $this->box->getInnerLength(); |
|
93 | } |
||
94 | |||
95 | /** |
||
96 | * Pack as many items as possible into specific given box |
||
97 | * |
||
98 | * @return PackedBox packed box |
||
99 | */ |
||
100 | 29 | public function pack() |
|
101 | { |
||
102 | 29 | $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}"); |
|
103 | |||
104 | 29 | $packedItems = new ItemList; |
|
105 | |||
106 | 29 | $layerWidth = $layerLength = $layerDepth = 0; |
|
107 | |||
108 | 29 | $prevItem = null; |
|
109 | |||
110 | 29 | while (!$this->items->isEmpty()) { |
|
111 | |||
112 | 29 | $itemToPack = $this->items->extract(); |
|
113 | |||
114 | //skip items that are simply too heavy |
||
115 | 29 | if ($itemToPack->getWeight() > $this->remainingWeight) { |
|
116 | 4 | continue; |
|
117 | } |
||
118 | |||
119 | 29 | $this->logger->debug("evaluating item {$itemToPack->getDescription()}", ['item' => $itemToPack, 'space' => ['widthLeft' => $this->widthLeft, 'lengthLeft' => $this->lengthLeft, 'depthLeft' => $this->depthLeft, 'layerWidth' => $layerWidth, 'layerLength' => $layerLength, 'layerDepth' => $layerDepth]]); |
|
120 | |||
121 | 29 | $nextItem = !$this->items->isEmpty() ? $this->items->top() : null; |
|
122 | 29 | $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft); |
|
123 | |||
124 | 29 | if ($orientatedItem) { |
|
125 | |||
126 | 29 | $packedItems->insert($orientatedItem->getItem()); |
|
127 | 29 | $this->remainingWeight -= $itemToPack->getWeight(); |
|
128 | |||
129 | 29 | $this->lengthLeft -= $orientatedItem->getLength(); |
|
130 | 29 | $layerLength += $orientatedItem->getLength(); |
|
131 | 29 | $layerWidth = max($orientatedItem->getWidth(), $layerWidth); |
|
132 | |||
133 | 29 | $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep |
|
134 | |||
135 | 29 | $this->usedLength = max($this->usedLength, $layerLength); |
|
136 | 29 | $this->usedWidth = max($this->usedWidth, $layerWidth); |
|
137 | |||
138 | //allow items to be stacked in place within the same footprint up to current layerdepth |
||
139 | 29 | $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem, $layerDepth); |
|
140 | |||
141 | 29 | $prevItem = $orientatedItem; |
|
142 | |||
143 | 29 | if (!$nextItem) { |
|
144 | 29 | $this->usedDepth += $layerDepth; |
|
145 | } |
||
146 | } else { |
||
147 | |||
148 | 24 | $prevItem = null; |
|
149 | |||
150 | 24 | if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) { |
|
151 | 23 | $this->logger->debug("No more fit in lengthwise, resetting for new row"); |
|
152 | 23 | $this->lengthLeft += $layerLength; |
|
153 | 23 | $this->widthLeft -= $layerWidth; |
|
154 | 23 | $layerWidth = $layerLength = 0; |
|
155 | 23 | $this->items->insert($itemToPack); |
|
156 | 23 | continue; |
|
157 | 18 | } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) { |
|
158 | 7 | $this->logger->debug("doesn't fit on layer even when empty"); |
|
159 | 7 | continue; |
|
160 | } |
||
161 | |||
162 | 17 | $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth(); |
|
163 | 17 | $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength(); |
|
164 | 17 | $this->depthLeft -= $layerDepth; |
|
165 | 17 | $this->usedDepth += $layerDepth; |
|
166 | |||
167 | 17 | $layerWidth = $layerLength = $layerDepth = 0; |
|
168 | 17 | $this->logger->debug("doesn't fit, so starting next vertical layer"); |
|
169 | 17 | $this->items->insert($itemToPack); |
|
170 | } |
||
171 | } |
||
172 | 29 | $this->logger->debug("done with this box"); |
|
173 | 29 | return new PackedBox($this->box, $packedItems, $this->widthLeft, $this->lengthLeft, $this->depthLeft, $this->remainingWeight, $this->usedWidth, $this->usedLength, $this->usedDepth); |
|
174 | } |
||
175 | |||
176 | /** |
||
177 | * Get the best orientation for an item |
||
178 | * @param Item $item |
||
179 | * @param OrientatedItem|null $prevItem |
||
180 | * @param Item|null $nextItem |
||
181 | * @param int $widthLeft |
||
182 | * @param int $lengthLeft |
||
183 | * @param int $depthLeft |
||
184 | * |
||
185 | * @return OrientatedItem|false |
||
186 | */ |
||
187 | 29 | protected function findBestOrientation( |
|
188 | Item $item, |
||
189 | OrientatedItem $prevItem = null, |
||
190 | Item $nextItem = null, |
||
191 | $widthLeft, |
||
192 | $lengthLeft, |
||
193 | $depthLeft) { |
||
194 | |||
195 | 29 | $possibleOrientations = $this->findAllPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft); |
|
196 | 29 | $orientationsToUse = $this->filterStableOrientations($possibleOrientations, $item, $prevItem, $nextItem); |
|
197 | |||
198 | 29 | $orientationFits = []; |
|
199 | /** @var OrientatedItem $orientation */ |
||
200 | 29 | foreach ($orientationsToUse as $o => $orientation) { |
|
201 | 29 | $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft - $orientation->getLength()); |
|
202 | 29 | $orientationFits[$o] = $orientationFit; |
|
203 | } |
||
204 | |||
205 | 29 | if (!empty($orientationFits)) { |
|
206 | 29 | asort($orientationFits); |
|
207 | 29 | reset($orientationFits); |
|
208 | 29 | $bestFit = $orientationsToUse[key($orientationFits)]; |
|
209 | 29 | $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]); |
|
210 | 29 | return $bestFit; |
|
211 | } else { |
||
212 | 27 | return false; |
|
213 | } |
||
214 | } |
||
215 | |||
216 | /** |
||
217 | * Find all possible orientations for an item |
||
218 | * @param Item $item |
||
219 | * @param OrientatedItem|null $prevItem |
||
220 | * @param int $widthLeft |
||
221 | * @param int $lengthLeft |
||
222 | * @param int $depthLeft |
||
223 | * |
||
224 | * @return OrientatedItem[] |
||
225 | */ |
||
226 | 29 | protected function findAllPossibleOrientations( |
|
227 | Item $item, |
||
228 | OrientatedItem $prevItem = null, |
||
229 | $widthLeft, |
||
230 | $lengthLeft, |
||
231 | $depthLeft) { |
||
232 | |||
233 | 29 | $orientations = []; |
|
234 | |||
235 | //Special case items that are the same as what we just packed - keep orientation |
||
236 | 29 | if ($prevItem && $prevItem->getItem() == $item) { |
|
237 | 12 | $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()); |
|
238 | } else { |
||
239 | |||
240 | //simple 2D rotation |
||
241 | 29 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth()); |
|
242 | 29 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth()); |
|
243 | |||
244 | //add 3D rotation if we're allowed |
||
245 | 29 | if (!$item->getKeepFlat()) { |
|
246 | 10 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength()); |
|
247 | 10 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth()); |
|
248 | 10 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength()); |
|
249 | 10 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth()); |
|
250 | } |
||
251 | } |
||
252 | |||
253 | //remove any that simply don't fit |
||
254 | return array_filter($orientations, function(OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) { |
||
255 | 29 | return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft; |
|
256 | 29 | }); |
|
257 | |||
258 | } |
||
259 | |||
260 | /** |
||
261 | * Filter a set of orientations allow only those that have a stable base OR |
||
262 | * the item doesn't fit in the box any other way |
||
263 | * the item is the last one left to pack |
||
264 | * |
||
265 | * @param OrientatedItem[] $orientations |
||
266 | * @param Item $item |
||
267 | * @param OrientatedItem|null $prevItem |
||
268 | * @param Item|null $nextItem |
||
269 | * |
||
270 | * @return OrientatedItem[] |
||
271 | */ |
||
272 | 29 | protected function filterStableOrientations( |
|
273 | array $orientations, |
||
274 | Item $item, |
||
275 | OrientatedItem $prevItem = null, |
||
0 ignored issues
–
show
|
|||
276 | Item $nextItem = null |
||
277 | ) { |
||
278 | 29 | $stableOrientations = $unstableOrientations = $orientationsToUse = []; |
|
279 | |||
280 | 29 | foreach ($orientations as $o => $orientation) { |
|
281 | 29 | if ($orientation->isStable()) { |
|
282 | 26 | $stableOrientations[] = $orientation; |
|
283 | } else { |
||
284 | 29 | $unstableOrientations[] = $orientation; |
|
285 | } |
||
286 | } |
||
287 | |||
288 | 29 | if (count($stableOrientations) > 0) { |
|
289 | 26 | $orientationsToUse = $stableOrientations; |
|
290 | 28 | } else if (count($unstableOrientations) > 0) { |
|
291 | 4 | $orientationsInEmptyBox = $this->findAllPossibleOrientations($item, null, $this->box->getInnerWidth(), $this->box->getInnerLength(), $this->box->getInnerDepth()); |
|
292 | |||
293 | 4 | $stableOrientationsInEmptyBox = array_filter( |
|
294 | $orientationsInEmptyBox, |
||
295 | 4 | function(OrientatedItem $orientation) { |
|
296 | 4 | return $orientation->isStable(); |
|
297 | 4 | } |
|
298 | ); |
||
299 | |||
300 | 4 | if (is_null($nextItem) || count($stableOrientationsInEmptyBox) == 0) { |
|
301 | 4 | $orientationsToUse = $unstableOrientations; |
|
302 | } |
||
303 | } |
||
304 | |||
305 | 29 | return $orientationsToUse; |
|
306 | } |
||
307 | |||
308 | /** |
||
309 | * Figure out if we can stack the next item vertically on top of this rather than side by side |
||
310 | * Used when we've packed a tall item, and have just put a shorter one next to it |
||
311 | * |
||
312 | * @param ItemList $packedItems |
||
313 | * @param OrientatedItem $prevItem |
||
314 | * @param Item $nextItem |
||
315 | * @param OrientatedItem $orientatedItem |
||
316 | * @param int $layerDepth |
||
317 | * |
||
318 | */ |
||
319 | 29 | protected function tryAndStackItemsIntoSpace( |
|
320 | ItemList $packedItems, |
||
321 | OrientatedItem $prevItem = null, |
||
322 | Item $nextItem = null, |
||
323 | OrientatedItem $orientatedItem, |
||
324 | $layerDepth) |
||
325 | { |
||
326 | 29 | $stackableDepth = $layerDepth - $orientatedItem->getDepth(); //we already packed this |
|
327 | |||
328 | 29 | while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) { |
|
329 | 27 | $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth); |
|
330 | |||
331 | 27 | if ($stackedItem) { |
|
332 | 1 | $this->remainingWeight -= $this->items->top()->getWeight(); |
|
333 | 1 | $stackableDepth -= $stackedItem->getDepth(); |
|
334 | 1 | $packedItems->insert($this->items->extract()); |
|
335 | } else { |
||
336 | 27 | break; |
|
337 | } |
||
338 | } |
||
339 | } |
||
340 | |||
341 | /** |
||
342 | * @param int $layerWidth |
||
343 | * @param int $layerLength |
||
344 | * @param int $layerDepth |
||
345 | * |
||
346 | * @return bool |
||
347 | */ |
||
348 | 24 | protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) { |
|
349 | 24 | return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0; |
|
350 | } |
||
351 | } |
||
352 |
This check looks from parameters that have been defined for a function or method, but which are not used in the method body.