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