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 ArrayIterator; |
||
12 | use Countable; |
||
13 | use IteratorAggregate; |
||
14 | use JsonSerializable; |
||
15 | use Traversable; |
||
16 | |||
17 | use function count; |
||
18 | use function json_encode; |
||
19 | use function reset; |
||
20 | use function round; |
||
21 | use function usort; |
||
22 | use function array_map; |
||
23 | use function iterator_to_array; |
||
24 | use function spl_object_id; |
||
25 | |||
26 | use const JSON_THROW_ON_ERROR; |
||
27 | use const JSON_NUMERIC_CHECK; |
||
28 | use const JSON_UNESCAPED_UNICODE; |
||
29 | use const JSON_UNESCAPED_SLASHES; |
||
30 | |||
31 | /** |
||
32 | * List of packed boxes. |
||
33 | */ |
||
34 | class PackedBoxList implements IteratorAggregate, Countable, JsonSerializable |
||
35 | { |
||
36 | /** |
||
37 | * @var PackedBox[] |
||
38 | */ |
||
39 | private array $list = []; |
||
40 | |||
41 | private bool $isSorted = false; |
||
42 | |||
43 | 56 | public function __construct(private readonly PackedBoxSorter $sorter = new DefaultPackedBoxSorter()) |
|
44 | { |
||
45 | 56 | } |
|
46 | |||
47 | /** |
||
48 | * @return Traversable<PackedBox> |
||
49 | */ |
||
50 | 33 | public function getIterator(): Traversable |
|
51 | { |
||
52 | 33 | if (!$this->isSorted) { |
|
53 | 33 | usort($this->list, $this->sorter->compare(...)); |
|
54 | 33 | $this->isSorted = true; |
|
55 | } |
||
56 | |||
57 | 33 | return new ArrayIterator($this->list); |
|
58 | } |
||
59 | |||
60 | /** |
||
61 | * Number of items in list. |
||
62 | */ |
||
63 | 44 | public function count(): int |
|
64 | { |
||
65 | 44 | return count($this->list); |
|
66 | } |
||
67 | |||
68 | 52 | public function insert(PackedBox $item): void |
|
69 | { |
||
70 | 52 | $this->list[] = $item; |
|
71 | 52 | $this->isSorted = false; |
|
72 | } |
||
73 | |||
74 | /** |
||
75 | * Do a bulk insert. |
||
76 | * |
||
77 | * @internal |
||
78 | * |
||
79 | * @param PackedBox[] $boxes |
||
80 | */ |
||
81 | 13 | public function insertFromArray(array $boxes): void |
|
82 | { |
||
83 | 13 | foreach ($boxes as $box) { |
|
84 | 13 | $this->insert($box); |
|
85 | } |
||
86 | } |
||
87 | |||
88 | /** |
||
89 | * @internal |
||
90 | */ |
||
91 | 10 | public function top(): PackedBox |
|
92 | { |
||
93 | 10 | if (!$this->isSorted) { |
|
94 | 9 | usort($this->list, $this->sorter->compare(...)); |
|
95 | 9 | $this->isSorted = true; |
|
96 | } |
||
97 | |||
98 | 10 | return reset($this->list); |
|
99 | } |
||
100 | |||
101 | /** |
||
102 | * Calculate the average (mean) weight of the boxes. |
||
103 | */ |
||
104 | 14 | public function getMeanWeight(): float |
|
105 | { |
||
106 | 14 | $meanWeight = 0; |
|
107 | |||
108 | 14 | foreach ($this->list as $box) { |
|
109 | 14 | $meanWeight += $box->getWeight(); |
|
110 | } |
||
111 | |||
112 | 14 | return $meanWeight / count($this->list); |
|
113 | } |
||
114 | |||
115 | /** |
||
116 | * Calculate the average (mean) weight of the boxes. |
||
117 | */ |
||
118 | 12 | public function getMeanItemWeight(): float |
|
119 | { |
||
120 | 12 | $meanWeight = 0; |
|
121 | |||
122 | 12 | foreach ($this->list as $box) { |
|
123 | 12 | $meanWeight += $box->getItemWeight(); |
|
124 | } |
||
125 | |||
126 | 12 | return $meanWeight / count($this->list); |
|
127 | } |
||
128 | |||
129 | /** |
||
130 | * Calculate the variance in weight between these boxes. |
||
131 | */ |
||
132 | 13 | public function getWeightVariance(): float |
|
133 | { |
||
134 | 13 | $mean = $this->getMeanWeight(); |
|
135 | |||
136 | 13 | $weightVariance = 0; |
|
137 | 13 | foreach ($this->list as $box) { |
|
138 | 13 | $weightVariance += ($box->getWeight() - $mean) ** 2; |
|
139 | } |
||
140 | |||
141 | 13 | return round($weightVariance / count($this->list), 1); |
|
142 | } |
||
143 | |||
144 | /** |
||
145 | * Get volume utilisation of the set of packed boxes. |
||
146 | */ |
||
147 | 1 | public function getVolumeUtilisation(): float |
|
148 | { |
||
149 | 1 | $itemVolume = 0; |
|
150 | 1 | $boxVolume = 0; |
|
151 | |||
152 | 1 | foreach ($this as $box) { |
|
153 | 1 | $boxVolume += $box->getInnerVolume(); |
|
154 | |||
155 | 1 | foreach ($box->items as $item) { |
|
156 | 1 | $itemVolume += ($item->item->getWidth() * $item->item->getLength() * $item->item->getDepth()); |
|
157 | } |
||
158 | } |
||
159 | |||
160 | 1 | return round($itemVolume / $boxVolume * 100, 1); |
|
161 | } |
||
162 | |||
163 | /** |
||
164 | * Create a custom website visualiser URL for this packing. |
||
165 | */ |
||
166 | 1 | public function generateVisualisationURL(): string |
|
167 | { |
||
168 | 1 | $items = []; |
|
169 | 1 | foreach ($this->list as $packedBox) { |
|
170 | 1 | $items = [...$items, ...$packedBox->items->asItemArray()]; |
|
171 | } |
||
172 | 1 | $dedupedItems = $splIdToIntMap = []; |
|
173 | 1 | $splIdIndex = 0; |
|
174 | 1 | foreach ($items as $item) { |
|
175 | 1 | if (!isset($splIdToIntMap[spl_object_id($item)])) { |
|
176 | 1 | $splIdToIntMap[spl_object_id($item)] = $splIdIndex++; |
|
177 | } |
||
178 | 1 | $dedupedItems[$splIdToIntMap[spl_object_id($item)]] = $item; |
|
179 | } |
||
180 | |||
181 | 1 | foreach ($dedupedItems as $item) { |
|
182 | 1 | $data['items'][$splIdToIntMap[spl_object_id($item)]] = [$item->getDescription(), $item->getWidth(), $item->getLength(), $item->getDepth()]; |
|
183 | } |
||
184 | |||
185 | 1 | $data['boxes'] = []; |
|
186 | 1 | foreach ($this->list as $packedBox) { |
|
187 | 1 | $data['boxes'][] = [ |
|
188 | 1 | $packedBox->box->getReference(), |
|
189 | 1 | $packedBox->box->getInnerWidth(), |
|
190 | 1 | $packedBox->box->getInnerLength(), |
|
191 | 1 | $packedBox->box->getInnerDepth(), |
|
192 | 1 | array_map( |
|
193 | 1 | fn (PackedItem $item) => [$splIdToIntMap[spl_object_id($item->item)], $item->x, $item->y, $item->z, $item->width, $item->length, $item->depth], |
|
194 | 1 | iterator_to_array($packedBox->items) |
|
195 | 1 | ), |
|
196 | 1 | ]; |
|
197 | } |
||
198 | |||
199 | 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...
|
|||
200 | } |
||
201 | |||
202 | 1 | public function jsonSerialize(): array |
|
203 | { |
||
204 | 1 | return $this->list; |
|
205 | } |
||
206 | } |
||
207 |