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 | 26 | */ |
|
62 | protected $usedWidth = 0; |
||
63 | 26 | ||
64 | /** |
||
65 | 26 | * Used length inside box for packing items |
|
66 | 26 | * @var int |
|
67 | */ |
||
68 | 26 | protected $usedLength = 0; |
|
69 | 26 | ||
70 | 26 | /** |
|
71 | 26 | * Used depth inside box for packing items |
|
72 | 26 | * @var int |
|
73 | */ |
||
74 | protected $usedDepth = 0; |
||
75 | |||
76 | /** |
||
77 | * Constructor |
||
78 | 26 | */ |
|
79 | public function __construct(Box $box, ItemList $items) |
||
80 | 26 | { |
|
81 | $this->logger = new NullLogger(); |
||
82 | 26 | ||
83 | $this->box = $box; |
||
84 | 26 | $this->items = $items; |
|
85 | |||
86 | 26 | $this->depthLeft = $this->box->getInnerDepth(); |
|
87 | $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight(); |
||
88 | 26 | $this->widthLeft = $this->box->getInnerWidth(); |
|
89 | $this->lengthLeft = $this->box->getInnerLength(); |
||
90 | 26 | } |
|
91 | |||
92 | /** |
||
93 | 26 | * Pack as many items as possible into specific given box |
|
94 | 4 | * @return PackedBox packed box |
|
95 | */ |
||
96 | public function pack() |
||
97 | 26 | { |
|
98 | 26 | $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}"); |
|
99 | 26 | ||
100 | $packedItems = new ItemList; |
||
101 | 26 | ||
102 | 26 | $layerWidth = $layerLength = $layerDepth = 0; |
|
103 | |||
104 | 26 | $prevItem = null; |
|
105 | |||
106 | 26 | while (!$this->items->isEmpty()) { |
|
107 | 26 | ||
108 | $itemToPack = $this->items->extract(); |
||
109 | 26 | ||
110 | 26 | //skip items that are simply too heavy |
|
111 | 26 | if ($itemToPack->getWeight() > $this->remainingWeight) { |
|
112 | continue; |
||
113 | 26 | } |
|
114 | |||
115 | $this->logger->debug( |
||
116 | 26 | "evaluating item {$itemToPack->getDescription()}", |
|
117 | 26 | [ |
|
118 | 'item' => $itemToPack, |
||
119 | 26 | 'space' => [ |
|
120 | 'widthLeft' => $this->widthLeft, |
||
121 | 'lengthLeft' => $this->lengthLeft, |
||
122 | 22 | 'depthLeft' => $this->depthLeft, |
|
123 | 'layerWidth' => $layerWidth, |
||
124 | 22 | 'layerLength' => $layerLength, |
|
125 | 21 | 'layerDepth' => $layerDepth |
|
126 | 21 | ] |
|
127 | 21 | ] |
|
128 | 21 | ); |
|
129 | 21 | ||
130 | 21 | $nextItem = !$this->items->isEmpty() ? $this->items->top() : null; |
|
131 | 18 | $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft); |
|
132 | 7 | ||
133 | 7 | if ($orientatedItem) { |
|
134 | |||
135 | $packedItems->insert($orientatedItem->getItem()); |
||
136 | 17 | $this->remainingWeight -= $itemToPack->getWeight(); |
|
137 | 17 | ||
138 | 17 | $this->lengthLeft -= $orientatedItem->getLength(); |
|
139 | $layerLength += $orientatedItem->getLength(); |
||
140 | 17 | $layerWidth = max($orientatedItem->getWidth(), $layerWidth); |
|
141 | 17 | ||
142 | 17 | $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep |
|
143 | |||
144 | $this->usedLength = max($this->usedLength, $layerLength); |
||
145 | 26 | $this->usedWidth = max($this->usedWidth, $layerWidth); |
|
146 | 26 | ||
147 | //allow items to be stacked in place within the same footprint up to current layerdepth |
||
148 | $stackableDepth = $layerDepth - $orientatedItem->getDepth(); |
||
149 | $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth); |
||
150 | |||
151 | $prevItem = $orientatedItem; |
||
152 | |||
153 | if (!$nextItem) { |
||
154 | $this->usedDepth += $layerDepth; |
||
155 | } |
||
156 | } else { |
||
157 | |||
158 | $prevItem = null; |
||
159 | 26 | ||
160 | if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) { |
||
161 | 26 | $this->logger->debug("No more fit in lengthwise, resetting for new row"); |
|
162 | $this->lengthLeft += $layerLength; |
||
163 | $this->widthLeft -= $layerWidth; |
||
164 | 26 | $layerWidth = $layerLength = 0; |
|
165 | 5 | $this->items->insert($itemToPack); |
|
166 | 5 | continue; |
|
167 | } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) { |
||
168 | $this->logger->debug("doesn't fit on layer even when empty"); |
||
169 | 26 | continue; |
|
170 | } |
||
171 | |||
172 | 26 | $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth(); |
|
173 | 26 | $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength(); |
|
174 | 26 | $this->depthLeft -= $layerDepth; |
|
175 | $this->usedDepth += $layerDepth; |
||
176 | |||
177 | 26 | $layerWidth = $layerLength = $layerDepth = 0; |
|
178 | 26 | $this->logger->debug("doesn't fit, so starting next vertical layer"); |
|
179 | 26 | $this->items->insert($itemToPack); |
|
180 | 26 | } |
|
181 | 26 | } |
|
182 | 26 | $this->logger->debug("done with this box"); |
|
183 | return new PackedBox( |
||
184 | 24 | $this->box, |
|
185 | $packedItems, |
||
186 | $this->widthLeft, |
||
187 | $this->lengthLeft, |
||
188 | $this->depthLeft, |
||
189 | $this->remainingWeight, |
||
190 | $this->usedWidth, |
||
191 | $this->usedLength, |
||
192 | $this->usedDepth); |
||
193 | } |
||
194 | |||
195 | /** |
||
196 | * Get the best orientation for an item |
||
197 | 26 | * @param Item $item |
|
198 | * @param OrientatedItem|null $prevItem |
||
199 | 26 | * @param Item|null $nextItem |
|
200 | * @param int $widthLeft |
||
201 | * @param int $lengthLeft |
||
202 | 26 | * @param int $depthLeft |
|
203 | 9 | * @return OrientatedItem|false |
|
204 | */ |
||
205 | protected function findBestOrientation(Item $item, OrientatedItem $prevItem = null, Item $nextItem = null, $widthLeft, $lengthLeft, $depthLeft) { |
||
206 | |||
207 | 26 | $orientations = $this->findPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft); |
|
208 | 26 | ||
209 | // special casing based on next item |
||
210 | if (isset($orientations[0]) && $nextItem == $item && $lengthLeft >= 2 * $item->getLength()) { |
||
211 | 26 | $this->logger->debug("not rotating based on next item"); |
|
212 | 10 | return $orientations[0]; // XXX this is tied to the ordering from ->findPossibleOrientations() |
|
213 | 10 | } |
|
214 | 10 | ||
215 | 10 | $orientationFits = []; |
|
216 | |||
217 | /** @var OrientatedItem $orientation */ |
||
218 | foreach ($orientations as $o => $orientation) { |
||
219 | $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft - $orientation->getLength()); |
||
220 | 26 | $orientationFits[$o] = $orientationFit; |
|
221 | 26 | } |
|
222 | 26 | ||
223 | if (!empty($orientationFits)) { |
||
224 | asort($orientationFits); |
||
225 | reset($orientationFits); |
||
226 | $bestFit = key($orientationFits); |
||
227 | $this->logger->debug("Using orientation #{$bestFit}"); |
||
228 | return $orientations[$bestFit]; |
||
229 | } else { |
||
230 | return false; |
||
231 | } |
||
232 | } |
||
233 | |||
234 | 26 | /** |
|
235 | * Find all possible orientations for an item |
||
236 | 26 | * @param Item $item |
|
237 | 24 | * @param OrientatedItem|null $prevItem |
|
238 | 24 | * @param int $widthLeft |
|
239 | 1 | * @param int $lengthLeft |
|
240 | 1 | * @param int $depthLeft |
|
241 | 1 | * @return OrientatedItem[] |
|
242 | */ |
||
243 | 24 | protected function findPossibleOrientations(Item $item, OrientatedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) { |
|
244 | |||
245 | $orientations = []; |
||
246 | 26 | ||
247 | //Special case items that are the same as what we just packed - keep orientation |
||
248 | if ($prevItem && $prevItem->getItem() == $item) { |
||
249 | $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()); |
||
250 | } else { |
||
251 | |||
252 | //simple 2D rotation |
||
253 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth()); |
||
254 | 22 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth()); |
|
255 | 22 | ||
256 | //add 3D rotation if we're allowed |
||
257 | if (!$item->getKeepFlat()) { |
||
258 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength()); |
||
259 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth()); |
||
260 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength()); |
||
261 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth()); |
||
262 | } |
||
263 | } |
||
264 | |||
265 | //remove any that simply don't fit |
||
266 | return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) { |
||
267 | return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft; |
||
268 | }); |
||
269 | |||
270 | } |
||
271 | |||
272 | /** |
||
273 | * Figure out if we can stack the next item vertically on top of this rather than side by side |
||
274 | * Used when we've packed a tall item, and have just put a shorter one next to it |
||
275 | * |
||
276 | * @param ItemList $packedItems |
||
277 | * @param OrientatedItem $prevItem |
||
0 ignored issues
–
show
|
|||
278 | * @param Item $nextItem |
||
0 ignored issues
–
show
Should the type for parameter
$nextItem not be null|Item ?
This check looks for 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.
Loading history...
|
|||
279 | * @param int $maxWidth |
||
280 | * @param int $maxLength |
||
281 | * @param int $maxDepth |
||
282 | */ |
||
283 | protected function tryAndStackItemsIntoSpace(ItemList $packedItems, OrientatedItem $prevItem = null, Item $nextItem = null, $maxWidth, $maxLength, $maxDepth) |
||
284 | { |
||
285 | while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) { |
||
286 | $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $maxWidth, $maxLength, $maxDepth); |
||
287 | if ($stackedItem) { |
||
288 | $this->remainingWeight -= $this->items->top()->getWeight(); |
||
289 | $maxDepth -= $stackedItem->getDepth(); |
||
290 | $packedItems->insert($this->items->extract()); |
||
291 | } else { |
||
292 | break; |
||
293 | } |
||
294 | } |
||
295 | } |
||
296 | |||
297 | /** |
||
298 | * @param int $layerWidth |
||
299 | * @param int $layerLength |
||
300 | * @param int $layerDepth |
||
301 | * @return bool |
||
302 | */ |
||
303 | protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) { |
||
304 | return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0; |
||
305 | } |
||
306 | } |
||
307 |
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.