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 JsonSerializable; |
||||||
12 | |||||||
13 | use function iterator_to_array; |
||||||
14 | use function json_encode; |
||||||
15 | use function max; |
||||||
16 | use function round; |
||||||
17 | use function is_iterable; |
||||||
18 | use function count; |
||||||
19 | use function array_pop; |
||||||
20 | use function assert; |
||||||
21 | use function array_map; |
||||||
22 | use function spl_object_id; |
||||||
23 | |||||||
24 | use const JSON_THROW_ON_ERROR; |
||||||
25 | use const JSON_NUMERIC_CHECK; |
||||||
26 | use const JSON_UNESCAPED_UNICODE; |
||||||
27 | use const JSON_UNESCAPED_SLASHES; |
||||||
28 | |||||||
29 | /** |
||||||
30 | * A "box" with items. |
||||||
31 | */ |
||||||
32 | readonly class PackedBox implements JsonSerializable |
||||||
33 | { |
||||||
34 | protected int $itemWeight; |
||||||
35 | |||||||
36 | protected float $volumeUtilisation; |
||||||
37 | |||||||
38 | /** |
||||||
39 | * Get packed weight. |
||||||
40 | * |
||||||
41 | * @return int weight in grams |
||||||
42 | */ |
||||||
43 | 13 | public function getWeight(): int |
|||||
44 | { |
||||||
45 | 13 | return $this->box->getEmptyWeight() + $this->getItemWeight(); |
|||||
46 | } |
||||||
47 | |||||||
48 | /** |
||||||
49 | * Get packed weight of the items only. |
||||||
50 | * |
||||||
51 | * @return int weight in grams |
||||||
52 | */ |
||||||
53 | 14 | public function getItemWeight(): int |
|||||
54 | { |
||||||
55 | 14 | if (!isset($this->itemWeight)) { |
|||||
56 | 14 | $itemWeight = 0; |
|||||
57 | 14 | foreach ($this->items as $item) { |
|||||
58 | 14 | $itemWeight += $item->item->getWeight(); |
|||||
59 | } |
||||||
60 | 14 | $this->itemWeight = $itemWeight; |
|||||
61 | } |
||||||
62 | |||||||
63 | 14 | return $this->itemWeight; |
|||||
64 | } |
||||||
65 | |||||||
66 | /** |
||||||
67 | * Get remaining width inside box for another item. |
||||||
68 | */ |
||||||
69 | 1 | public function getRemainingWidth(): int |
|||||
70 | { |
||||||
71 | 1 | return $this->box->getInnerWidth() - $this->getUsedWidth(); |
|||||
72 | } |
||||||
73 | |||||||
74 | /** |
||||||
75 | * Get remaining length inside box for another item. |
||||||
76 | */ |
||||||
77 | 1 | public function getRemainingLength(): int |
|||||
78 | { |
||||||
79 | 1 | return $this->box->getInnerLength() - $this->getUsedLength(); |
|||||
80 | } |
||||||
81 | |||||||
82 | /** |
||||||
83 | * Get remaining depth inside box for another item. |
||||||
84 | */ |
||||||
85 | 1 | public function getRemainingDepth(): int |
|||||
86 | { |
||||||
87 | 1 | return $this->box->getInnerDepth() - $this->getUsedDepth(); |
|||||
88 | } |
||||||
89 | |||||||
90 | /** |
||||||
91 | * Used width inside box for packing items. |
||||||
92 | */ |
||||||
93 | 5 | public function getUsedWidth(): int |
|||||
94 | { |
||||||
95 | 5 | $maxWidth = 0; |
|||||
96 | |||||||
97 | 5 | foreach ($this->items as $item) { |
|||||
98 | 5 | $maxWidth = max($maxWidth, $item->x + $item->width); |
|||||
99 | } |
||||||
100 | |||||||
101 | 5 | return $maxWidth; |
|||||
102 | } |
||||||
103 | |||||||
104 | /** |
||||||
105 | * Used length inside box for packing items. |
||||||
106 | */ |
||||||
107 | 5 | public function getUsedLength(): int |
|||||
108 | { |
||||||
109 | 5 | $maxLength = 0; |
|||||
110 | |||||||
111 | 5 | foreach ($this->items as $item) { |
|||||
112 | 5 | $maxLength = max($maxLength, $item->y + $item->length); |
|||||
113 | } |
||||||
114 | |||||||
115 | 5 | return $maxLength; |
|||||
116 | } |
||||||
117 | |||||||
118 | /** |
||||||
119 | * Used depth inside box for packing items. |
||||||
120 | */ |
||||||
121 | 5 | public function getUsedDepth(): int |
|||||
122 | { |
||||||
123 | 5 | $maxDepth = 0; |
|||||
124 | |||||||
125 | 5 | foreach ($this->items as $item) { |
|||||
126 | 5 | $maxDepth = max($maxDepth, $item->z + $item->depth); |
|||||
127 | } |
||||||
128 | |||||||
129 | 5 | return $maxDepth; |
|||||
130 | } |
||||||
131 | |||||||
132 | /** |
||||||
133 | * Get remaining weight inside box for another item. |
||||||
134 | */ |
||||||
135 | 1 | public function getRemainingWeight(): int |
|||||
136 | { |
||||||
137 | 1 | return $this->box->getMaxWeight() - $this->getWeight(); |
|||||
138 | } |
||||||
139 | |||||||
140 | 32 | public function getInnerVolume(): int |
|||||
141 | { |
||||||
142 | 32 | return $this->box->getInnerWidth() * $this->box->getInnerLength() * $this->box->getInnerDepth(); |
|||||
143 | } |
||||||
144 | |||||||
145 | /** |
||||||
146 | * Get used volume of the packed box. |
||||||
147 | */ |
||||||
148 | 31 | public function getUsedVolume(): int |
|||||
149 | { |
||||||
150 | 31 | return $this->items->getVolume(); |
|||||
151 | } |
||||||
152 | |||||||
153 | /** |
||||||
154 | * Get unused volume of the packed box. |
||||||
155 | */ |
||||||
156 | 1 | public function getUnusedVolume(): int |
|||||
157 | { |
||||||
158 | 1 | return $this->getInnerVolume() - $this->getUsedVolume(); |
|||||
159 | } |
||||||
160 | |||||||
161 | /** |
||||||
162 | * Get volume utilisation of the packed box. |
||||||
163 | */ |
||||||
164 | 31 | public function getVolumeUtilisation(): float |
|||||
165 | { |
||||||
166 | 31 | if (!isset($this->volumeUtilisation)) { |
|||||
167 | 31 | $this->volumeUtilisation = round($this->getUsedVolume() / ($this->getInnerVolume() ?: 1) * 100, 1); |
|||||
168 | } |
||||||
169 | |||||||
170 | 31 | return $this->volumeUtilisation; |
|||||
171 | } |
||||||
172 | |||||||
173 | /** |
||||||
174 | * Create a custom website visualiser URL for this packing. |
||||||
175 | */ |
||||||
176 | 1 | public function generateVisualisationURL(): string |
|||||
177 | { |
||||||
178 | 1 | $dedupedItems = $splIdToIntMap = []; |
|||||
179 | 1 | $splIdIndex = 0; |
|||||
180 | 1 | foreach ($this->items->asItemArray() as $item) { |
|||||
181 | 1 | if (!isset($splIdToIntMap[spl_object_id($item)])) { |
|||||
182 | 1 | $splIdToIntMap[spl_object_id($item)] = $splIdIndex++; |
|||||
183 | } |
||||||
184 | 1 | $dedupedItems[$splIdToIntMap[spl_object_id($item)]] = $item; |
|||||
185 | } |
||||||
186 | |||||||
187 | 1 | foreach ($dedupedItems as $item) { |
|||||
188 | 1 | $data['items'][$splIdToIntMap[spl_object_id($item)]] = [$item->getDescription(), $item->getWidth(), $item->getLength(), $item->getDepth()]; |
|||||
189 | } |
||||||
190 | |||||||
191 | 1 | $data['boxes'][] = [ |
|||||
192 | 1 | $this->box->getReference(), |
|||||
193 | 1 | $this->box->getInnerWidth(), |
|||||
194 | 1 | $this->box->getInnerLength(), |
|||||
195 | 1 | $this->box->getInnerDepth(), |
|||||
196 | 1 | array_map( |
|||||
197 | 1 | fn (PackedItem $item) => [$splIdToIntMap[spl_object_id($item->item)], $item->x, $item->y, $item->z, $item->width, $item->length, $item->depth], |
|||||
198 | 1 | iterator_to_array($this->items) |
|||||
199 | 1 | ), |
|||||
200 | 1 | ]; |
|||||
201 | |||||||
202 | 1 | return 'https://boxpacker.io/en/master/visualiser.html?packing=' . json_encode($data, flags: JSON_THROW_ON_ERROR | JSON_NUMERIC_CHECK | JSON_UNESCAPED_UNICODE | JSON_UNESCAPED_SLASHES); |
|||||
0 ignored issues
–
show
Comprehensibility
Best Practice
introduced
by
Loading history...
|
|||||||
203 | } |
||||||
204 | |||||||
205 | public function __construct(public Box $box, public PackedItemList $items) |
||||||
206 | { |
||||||
207 | assert($this->assertPackingCompliesWithRealWorld()); |
||||||
208 | } |
||||||
209 | |||||||
210 | 3 | public function jsonSerialize(): array |
|||||
211 | { |
||||||
212 | 3 | $userValues = []; |
|||||
213 | |||||||
214 | 3 | if ($this->box instanceof JsonSerializable) { |
|||||
215 | 2 | $userSerialisation = $this->box->jsonSerialize(); |
|||||
0 ignored issues
–
show
The method
jsonSerialize() does not exist on DVDoug\BoxPacker\Box . It seems like you code against a sub-type of DVDoug\BoxPacker\Box such as DVDoug\BoxPacker\WorkingVolume or DVDoug\BoxPacker\Test\TestBox .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||
216 | 2 | if (is_iterable($userSerialisation)) { |
|||||
217 | 1 | $userValues = $userSerialisation; |
|||||
218 | } else { |
||||||
219 | 1 | $userValues = ['extra' => $userSerialisation]; |
|||||
220 | } |
||||||
221 | } |
||||||
222 | |||||||
223 | 3 | return [ |
|||||
224 | 3 | 'box' => [ |
|||||
225 | 3 | ...$userValues, |
|||||
226 | 3 | 'reference' => $this->box->getReference(), |
|||||
227 | 3 | 'innerWidth' => $this->box->getInnerWidth(), |
|||||
228 | 3 | 'innerLength' => $this->box->getInnerLength(), |
|||||
229 | 3 | 'innerDepth' => $this->box->getInnerDepth(), |
|||||
230 | 3 | ], |
|||||
231 | 3 | 'items' => iterator_to_array($this->items), |
|||||
232 | 3 | ]; |
|||||
233 | } |
||||||
234 | |||||||
235 | /** |
||||||
236 | * Validate that all items are placed solely within the confines of the box, and that no two items are placed |
||||||
237 | * into the same physical space. |
||||||
238 | */ |
||||||
239 | private function assertPackingCompliesWithRealWorld(): true |
||||||
0 ignored issues
–
show
The type
DVDoug\BoxPacker\true was not found. Maybe you did not declare it correctly or list all dependencies?
The issue could also be caused by a filter entry in the build configuration.
If the path has been excluded in your configuration, e.g. filter:
dependency_paths: ["lib/*"]
For further information see https://scrutinizer-ci.com/docs/tools/php/php-scrutinizer/#list-dependency-paths
Loading history...
|
|||||||
240 | { |
||||||
241 | /** @var PackedItem[] $itemsToCheck */ |
||||||
242 | $itemsToCheck = iterator_to_array($this->items); |
||||||
243 | while (count($itemsToCheck) > 0) { |
||||||
244 | $itemToCheck = array_pop($itemsToCheck); |
||||||
245 | |||||||
246 | assert($itemToCheck->x >= 0); |
||||||
247 | assert($itemToCheck->x + $itemToCheck->width <= $this->box->getInnerWidth()); |
||||||
248 | assert($itemToCheck->y >= 0); |
||||||
249 | assert($itemToCheck->y + $itemToCheck->length <= $this->box->getInnerLength()); |
||||||
250 | assert($itemToCheck->z >= 0); |
||||||
251 | assert($itemToCheck->z + $itemToCheck->depth <= $this->box->getInnerDepth()); |
||||||
252 | |||||||
253 | foreach ($itemsToCheck as $otherItem) { |
||||||
254 | $hasXOverlap = $itemToCheck->x < ($otherItem->x + $otherItem->width) && $otherItem->x < ($itemToCheck->x + $itemToCheck->width); |
||||||
255 | $hasYOverlap = $itemToCheck->y < ($otherItem->y + $otherItem->length) && $otherItem->y < ($itemToCheck->y + $itemToCheck->length); |
||||||
256 | $hasZOverlap = $itemToCheck->z < ($otherItem->z + $otherItem->depth) && $otherItem->z < ($itemToCheck->z + $itemToCheck->depth); |
||||||
257 | |||||||
258 | $hasOverlap = $hasXOverlap && $hasYOverlap && $hasZOverlap; |
||||||
259 | assert(!$hasOverlap); |
||||||
260 | } |
||||||
261 | } |
||||||
262 | |||||||
263 | return true; |
||||||
0 ignored issues
–
show
|
|||||||
264 | } |
||||||
265 | } |
||||||
266 |