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|null $prevItem |
||
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); |
|
0 ignored issues
–
show
|
|||
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 | * |
||
289 | * @return bool |
||
290 | */ |
||
291 | 36 | protected function checkDimensionalConstraints(Item $itemToPack) |
|
292 | { |
||
293 | 36 | $orientatedItemFactory = new OrientatedItemFactory(); |
|
294 | 36 | $orientatedItemFactory->setLogger($this->logger); |
|
295 | 36 | return !!$orientatedItemFactory->getPossibleOrientationsInEmptyBox($itemToPack, $this->box); |
|
296 | } |
||
297 | |||
298 | /** |
||
299 | * Reintegrate skipped items into main list when nothing left to process |
||
300 | */ |
||
301 | 36 | protected function rebuildItemList() { |
|
302 | 36 | if ($this->items->isEmpty()) { |
|
303 | 36 | $this->items = $this->skippedItems; |
|
304 | 36 | $this->skippedItems = new ItemList(); |
|
305 | } |
||
306 | } |
||
307 | } |
||
308 |
This check compares calls to functions or methods with their respective definitions. If the call has more arguments than are defined, it raises an issue.
If a function is defined several times with a different number of parameters, the check may pick up the wrong definition and report false positives. One codebase where this has been known to happen is Wordpress.
In this case you can add the
@ignore
PhpDoc annotation to the duplicate definition and it will be ignored.