1 | <?php |
||
2 | /** |
||
3 | * Box packing (3D bin packing, knapsack problem). |
||
4 | * |
||
5 | * @author Doug Wright |
||
6 | */ |
||
7 | declare(strict_types=1); |
||
8 | |||
9 | namespace DVDoug\BoxPacker; |
||
10 | |||
11 | use DVDoug\BoxPacker\Exception\NoBoxesAvailableException; |
||
12 | use Psr\Log\LoggerAwareInterface; |
||
13 | use Psr\Log\LoggerInterface; |
||
14 | use Psr\Log\LogLevel; |
||
15 | use Psr\Log\NullLogger; |
||
16 | use WeakMap; |
||
17 | |||
18 | use function array_pop; |
||
19 | use function count; |
||
20 | use function usort; |
||
21 | |||
22 | use const PHP_INT_MAX; |
||
23 | |||
24 | /** |
||
25 | * Actual packer. |
||
26 | */ |
||
27 | class Packer implements LoggerAwareInterface |
||
28 | { |
||
29 | private LoggerInterface $logger; |
||
30 | |||
31 | protected int $maxBoxesToBalanceWeight = 12; |
||
32 | |||
33 | protected ItemList $items; |
||
34 | |||
35 | protected BoxList $boxes; |
||
36 | |||
37 | /** |
||
38 | * @var WeakMap<Box, int> |
||
39 | */ |
||
40 | protected WeakMap $boxQuantitiesAvailable; |
||
41 | |||
42 | protected PackedBoxSorter $packedBoxSorter; |
||
43 | |||
44 | protected bool $throwOnUnpackableItem = true; |
||
45 | |||
46 | private bool $beStrictAboutItemOrdering = false; |
||
47 | |||
48 | 49 | public function __construct() |
|
49 | { |
||
50 | 49 | $this->items = new ItemList(); |
|
51 | 49 | $this->boxes = new BoxList(); |
|
52 | 49 | $this->packedBoxSorter = new DefaultPackedBoxSorter(); |
|
53 | 49 | $this->boxQuantitiesAvailable = new WeakMap(); |
|
54 | |||
55 | 49 | $this->logger = new NullLogger(); |
|
56 | } |
||
57 | |||
58 | 5 | public function setLogger(LoggerInterface $logger): void |
|
59 | { |
||
60 | 5 | $this->logger = $logger; |
|
61 | } |
||
62 | |||
63 | /** |
||
64 | * Add item to be packed. |
||
65 | */ |
||
66 | 34 | public function addItem(Item $item, int $qty = 1): void |
|
67 | { |
||
68 | 34 | $this->items->insert($item, $qty); |
|
69 | 34 | $this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}", ['item' => $item]); |
|
70 | } |
||
71 | |||
72 | /** |
||
73 | * Set a list of items all at once. |
||
74 | * @param iterable<Item>|ItemList $items |
||
75 | */ |
||
76 | 18 | public function setItems(iterable|ItemList $items): void |
|
77 | { |
||
78 | 18 | if ($items instanceof ItemList) { |
|
79 | 14 | $this->items = clone $items; |
|
80 | } else { |
||
81 | 5 | $this->items = new ItemList(); |
|
82 | 5 | foreach ($items as $item) { |
|
83 | 5 | $this->items->insert($item); |
|
84 | } |
||
85 | } |
||
86 | } |
||
87 | |||
88 | /** |
||
89 | * Add box size. |
||
90 | */ |
||
91 | 35 | public function addBox(Box $box): void |
|
92 | { |
||
93 | 35 | $this->boxes->insert($box); |
|
94 | 35 | $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX); |
|
95 | 35 | $this->logger->log(LogLevel::INFO, "added box {$box->getReference()}", ['box' => $box]); |
|
96 | } |
||
97 | |||
98 | /** |
||
99 | * Add a pre-prepared set of boxes all at once. |
||
100 | */ |
||
101 | 17 | public function setBoxes(BoxList $boxList): void |
|
102 | { |
||
103 | 17 | $this->boxes = $boxList; |
|
104 | 17 | foreach ($this->boxes as $box) { |
|
105 | 17 | $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX); |
|
106 | } |
||
107 | } |
||
108 | |||
109 | /** |
||
110 | * Set the quantity of this box type available. |
||
111 | */ |
||
112 | 47 | public function setBoxQuantity(Box $box, int $qty): void |
|
113 | { |
||
114 | 47 | $this->boxQuantitiesAvailable[$box] = $qty; |
|
115 | } |
||
116 | |||
117 | /** |
||
118 | * Number of boxes at which balancing weight is deemed not worth the extra computation time. |
||
119 | */ |
||
120 | 1 | public function getMaxBoxesToBalanceWeight(): int |
|
121 | { |
||
122 | 1 | return $this->maxBoxesToBalanceWeight; |
|
123 | } |
||
124 | |||
125 | /** |
||
126 | * Number of boxes at which balancing weight is deemed not worth the extra computation time. |
||
127 | */ |
||
128 | 5 | public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight): void |
|
129 | { |
||
130 | 5 | $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight; |
|
131 | } |
||
132 | |||
133 | 1 | public function setPackedBoxSorter(PackedBoxSorter $packedBoxSorter): void |
|
134 | { |
||
135 | 1 | $this->packedBoxSorter = $packedBoxSorter; |
|
136 | } |
||
137 | |||
138 | 13 | public function throwOnUnpackableItem(bool $throwOnUnpackableItem): void |
|
139 | { |
||
140 | 13 | $this->throwOnUnpackableItem = $throwOnUnpackableItem; |
|
141 | } |
||
142 | |||
143 | public function beStrictAboutItemOrdering(bool $beStrict): void |
||
144 | { |
||
145 | $this->beStrictAboutItemOrdering = $beStrict; |
||
146 | } |
||
147 | |||
148 | /** |
||
149 | * Return the items that haven't been packed. |
||
150 | */ |
||
151 | 7 | public function getUnpackedItems(): ItemList |
|
152 | { |
||
153 | 7 | return $this->items; |
|
154 | } |
||
155 | |||
156 | /** |
||
157 | * Pack items into boxes using built-in heuristics for the best solution. |
||
158 | */ |
||
159 | 41 | public function pack(): PackedBoxList |
|
160 | { |
||
161 | 41 | $this->logger->log(LogLevel::INFO, '[PACKING STARTED]'); |
|
162 | |||
163 | 41 | $packedBoxes = $this->doBasicPacking(); |
|
164 | |||
165 | // If we have multiple boxes, try and optimise/even-out weight distribution |
||
166 | 38 | if (!$this->beStrictAboutItemOrdering && $packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) { |
|
167 | 12 | $redistributor = new WeightRedistributor($this->boxes, $this->packedBoxSorter, $this->boxQuantitiesAvailable); |
|
168 | 12 | $redistributor->setLogger($this->logger); |
|
169 | 12 | $packedBoxes = $redistributor->redistributeWeight($packedBoxes); |
|
170 | } |
||
171 | |||
172 | 38 | $this->logger->log(LogLevel::INFO, "[PACKING COMPLETED], {$packedBoxes->count()} boxes"); |
|
173 | |||
174 | 38 | return $packedBoxes; |
|
175 | } |
||
176 | |||
177 | /** |
||
178 | * @internal |
||
179 | */ |
||
180 | 41 | public function doBasicPacking(bool $enforceSingleBox = false): PackedBoxList |
|
181 | { |
||
182 | 41 | $packedBoxes = new PackedBoxList($this->packedBoxSorter); |
|
183 | |||
184 | // Keep going until everything packed |
||
185 | 41 | while ($this->items->count()) { |
|
186 | 41 | $packedBoxesIteration = []; |
|
187 | |||
188 | // Loop through boxes starting with smallest, see what happens |
||
189 | 41 | foreach ($this->getBoxList($enforceSingleBox) as $box) { |
|
190 | 40 | $volumePacker = new VolumePacker($box, $this->items); |
|
0 ignored issues
–
show
Bug
introduced
by
Loading history...
|
|||
191 | 40 | $volumePacker->setLogger($this->logger); |
|
192 | 40 | $volumePacker->beStrictAboutItemOrdering($this->beStrictAboutItemOrdering); |
|
193 | 40 | $packedBox = $volumePacker->pack(); |
|
194 | 40 | if ($packedBox->items->count()) { |
|
195 | 38 | $packedBoxesIteration[] = $packedBox; |
|
196 | |||
197 | // Have we found a single box that contains everything? |
||
198 | 38 | if ($packedBox->items->count() === $this->items->count()) { |
|
199 | 33 | $this->logger->log(LogLevel::DEBUG, "Single box found for remaining {$this->items->count()} items"); |
|
200 | 33 | break; |
|
201 | } |
||
202 | } |
||
203 | } |
||
204 | |||
205 | 41 | if (count($packedBoxesIteration) > 0) { |
|
206 | // Find best box of iteration, and remove packed items from unpacked list |
||
207 | 38 | usort($packedBoxesIteration, $this->packedBoxSorter->compare(...)); |
|
208 | 38 | $bestBox = $packedBoxesIteration[0]; |
|
209 | |||
210 | 38 | $this->items->removePackedItems($bestBox->items); |
|
211 | |||
212 | 38 | $packedBoxes->insert($bestBox); |
|
213 | 38 | --$this->boxQuantitiesAvailable[$bestBox->box]; |
|
214 | 10 | } elseif ($this->throwOnUnpackableItem) { |
|
215 | 3 | throw new NoBoxesAvailableException("No boxes could be found for item '{$this->items->top()->getDescription()}'", $this->items); |
|
216 | } else { |
||
217 | 7 | $this->logger->log(LogLevel::INFO, "{$this->items->count()} unpackable items found"); |
|
218 | 7 | break; |
|
219 | } |
||
220 | } |
||
221 | |||
222 | 38 | return $packedBoxes; |
|
223 | } |
||
224 | |||
225 | /** |
||
226 | * Pack items into boxes returning "all" possible box combination permutations. |
||
227 | * Use with caution (will be slow) with a large number of box types! |
||
228 | * |
||
229 | * @return PackedBoxList[] |
||
230 | */ |
||
231 | 7 | public function packAllPermutations(): array |
|
232 | { |
||
233 | 7 | $this->logger->log(LogLevel::INFO, '[PACKING STARTED (all permutations)]'); |
|
234 | |||
235 | 7 | $boxQuantitiesAvailable = clone $this->boxQuantitiesAvailable; |
|
236 | |||
237 | 7 | $wipPermutations = [['permutation' => new PackedBoxList($this->packedBoxSorter), 'itemsLeft' => $this->items]]; |
|
238 | 7 | $completedPermutations = []; |
|
239 | |||
240 | // Keep going until everything packed |
||
241 | 7 | while ($wipPermutations) { |
|
0 ignored issues
–
show
The expression
$wipPermutations of type array<integer,array<stri...xPacker\PackedBoxList>> is implicitly converted to a boolean; are you sure this is intended? If so, consider using ! empty($expr) instead to make it clear that you intend to check for an array without elements.
This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent. Consider making the comparison explicit by using
Loading history...
|
|||
242 | 7 | $wipPermutation = array_pop($wipPermutations); |
|
243 | 7 | $remainingBoxQuantities = clone $boxQuantitiesAvailable; |
|
244 | 7 | foreach ($wipPermutation['permutation'] as $packedBox) { |
|
245 | 6 | --$remainingBoxQuantities[$packedBox->box]; |
|
246 | } |
||
247 | 7 | if ($wipPermutation['itemsLeft']->count() === 0) { |
|
248 | 3 | $completedPermutations[] = $wipPermutation['permutation']; |
|
249 | 3 | continue; |
|
250 | } |
||
251 | |||
252 | 7 | $additionalPermutationsForThisPermutation = []; |
|
253 | 7 | foreach ($this->boxes as $box) { |
|
254 | 7 | if ($remainingBoxQuantities[$box] > 0) { |
|
255 | 7 | $volumePacker = new VolumePacker($box, $wipPermutation['itemsLeft']); |
|
256 | 7 | $volumePacker->setLogger($this->logger); |
|
257 | 7 | $packedBox = $volumePacker->pack(); |
|
258 | 7 | if ($packedBox->items->count()) { |
|
259 | 6 | $additionalPermutationsForThisPermutation[] = $packedBox; |
|
260 | } |
||
261 | } |
||
262 | } |
||
263 | |||
264 | 7 | if (count($additionalPermutationsForThisPermutation) > 0) { |
|
265 | 6 | foreach ($additionalPermutationsForThisPermutation as $additionalPermutationForThisPermutation) { |
|
266 | 6 | $newPermutation = clone $wipPermutation['permutation']; |
|
267 | 6 | $newPermutation->insert($additionalPermutationForThisPermutation); |
|
268 | 6 | $itemsRemainingOnPermutation = clone $wipPermutation['itemsLeft']; |
|
269 | 6 | $itemsRemainingOnPermutation->removePackedItems($additionalPermutationForThisPermutation->items); |
|
270 | 6 | $wipPermutations[] = ['permutation' => $newPermutation, 'itemsLeft' => $itemsRemainingOnPermutation]; |
|
271 | } |
||
272 | 4 | } elseif ($this->throwOnUnpackableItem) { |
|
273 | 1 | throw new NoBoxesAvailableException("No boxes could be found for item '{$wipPermutation['itemsLeft']->top()->getDescription()}'", $wipPermutation['itemsLeft']); |
|
274 | } else { |
||
275 | 3 | $this->logger->log(LogLevel::INFO, "{$this->items->count()} unpackable items found"); |
|
276 | 3 | if ($wipPermutation['permutation']->count() > 0) { // don't treat initial empty permutation as completed |
|
277 | 2 | $completedPermutations[] = $wipPermutation['permutation']; |
|
278 | } |
||
279 | } |
||
280 | } |
||
281 | |||
282 | 6 | $this->logger->log(LogLevel::INFO, '[PACKING COMPLETED], ' . count($completedPermutations) . ' permutations'); |
|
283 | |||
284 | 6 | foreach ($completedPermutations as $completedPermutation) { |
|
285 | 5 | foreach ($completedPermutation as $packedBox) { |
|
286 | 5 | $this->items->removePackedItems($packedBox->items); |
|
287 | } |
||
288 | } |
||
289 | |||
290 | 6 | return $completedPermutations; |
|
291 | } |
||
292 | |||
293 | /** |
||
294 | * Get a "smart" ordering of the boxes to try packing items into. The initial BoxList is already sorted in order |
||
295 | * so that the smallest boxes are evaluated first, but this means that time is spent on boxes that cannot possibly |
||
296 | * hold the entire set of items due to volume limitations. These should be evaluated first. |
||
297 | * |
||
298 | * @return iterable<Box> |
||
299 | */ |
||
300 | 41 | protected function getBoxList(bool $enforceSingleBox = false): iterable |
|
301 | { |
||
302 | 41 | $this->logger->log(LogLevel::INFO, 'Determining box search pattern', ['enforceSingleBox' => $enforceSingleBox]); |
|
303 | 41 | $itemVolume = 0; |
|
304 | 41 | foreach ($this->items as $item) { |
|
305 | 41 | $itemVolume += $item->getWidth() * $item->getLength() * $item->getDepth(); |
|
306 | } |
||
307 | 41 | $this->logger->log(LogLevel::DEBUG, 'Item volume', ['itemVolume' => $itemVolume]); |
|
308 | |||
309 | 41 | $preferredBoxes = []; |
|
310 | 41 | $otherBoxes = []; |
|
311 | 41 | foreach ($this->boxes as $box) { |
|
312 | 40 | if ($this->boxQuantitiesAvailable[$box] > 0) { |
|
313 | 40 | if ($box->getInnerWidth() * $box->getInnerLength() * $box->getInnerDepth() >= $itemVolume) { |
|
314 | 35 | $preferredBoxes[] = $box; |
|
315 | 19 | } elseif (!$enforceSingleBox) { |
|
316 | 19 | $otherBoxes[] = $box; |
|
317 | } |
||
318 | } |
||
319 | } |
||
320 | |||
321 | 41 | $this->logger->log(LogLevel::INFO, 'Box search pattern complete', ['preferredBoxCount' => count($preferredBoxes), 'otherBoxCount' => count($otherBoxes)]); |
|
322 | |||
323 | 41 | return [...$preferredBoxes, ...$otherBoxes]; |
|
324 | } |
||
325 | } |
||
326 |