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 | declare(strict_types=1); |
||
8 | namespace DVDoug\BoxPacker; |
||
9 | |||
10 | use function array_unshift; |
||
11 | use Psr\Log\LoggerAwareInterface; |
||
12 | use Psr\Log\LoggerAwareTrait; |
||
13 | use Psr\Log\LogLevel; |
||
14 | use Psr\Log\NullLogger; |
||
15 | |||
16 | /** |
||
17 | * Actual packer |
||
18 | * @author Doug Wright |
||
19 | * @package BoxPacker |
||
20 | */ |
||
21 | class Packer implements LoggerAwareInterface |
||
22 | { |
||
23 | use LoggerAwareTrait; |
||
24 | |||
25 | /** |
||
26 | * Number of boxes at which balancing weight is deemed not worth it |
||
27 | * @var int |
||
28 | */ |
||
29 | protected $maxBoxesToBalanceWeight = 12; |
||
30 | |||
31 | /** |
||
32 | * List of items to be packed |
||
33 | * @var ItemList |
||
34 | */ |
||
35 | protected $items; |
||
36 | |||
37 | /** |
||
38 | * List of box sizes available to pack items into |
||
39 | * @var BoxList |
||
40 | */ |
||
41 | protected $boxes; |
||
42 | |||
43 | /** |
||
44 | * Constructor |
||
45 | */ |
||
46 | 27 | public function __construct() |
|
47 | { |
||
48 | 27 | $this->items = new ItemList(); |
|
49 | 27 | $this->boxes = new BoxList(); |
|
50 | |||
51 | 27 | $this->logger = new NullLogger(); |
|
52 | } |
||
53 | |||
54 | /** |
||
55 | * Add item to be packed |
||
56 | * @param Item $item |
||
57 | * @param int $qty |
||
58 | */ |
||
59 | 26 | public function addItem(Item $item, int $qty = 1): void |
|
60 | { |
||
61 | 26 | for ($i = 0; $i < $qty; $i++) { |
|
62 | 26 | $this->items->insert($item); |
|
63 | } |
||
64 | 26 | $this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}"); |
|
65 | } |
||
66 | |||
67 | /** |
||
68 | * Set a list of items all at once |
||
69 | * @param \Traversable|array $items |
||
70 | */ |
||
71 | 2 | public function setItems($items): void |
|
72 | { |
||
73 | 2 | if ($items instanceof ItemList) { |
|
74 | $this->items = clone $items; |
||
75 | } else { |
||
76 | 2 | $this->items = new ItemList(); |
|
77 | 2 | foreach ($items as $item) { |
|
78 | 2 | $this->items->insert($item); |
|
79 | } |
||
80 | } |
||
81 | 2 | } |
|
82 | |||
83 | /** |
||
84 | * Add box size |
||
85 | * @param Box $box |
||
86 | */ |
||
87 | 25 | public function addBox(Box $box): void |
|
88 | { |
||
89 | 25 | $this->boxes->insert($box); |
|
90 | 25 | $this->logger->log(LogLevel::INFO, "added box {$box->getReference()}"); |
|
91 | } |
||
92 | |||
93 | /** |
||
94 | * Add a pre-prepared set of boxes all at once |
||
95 | * @param BoxList $boxList |
||
96 | */ |
||
97 | 2 | public function setBoxes(BoxList $boxList): void |
|
98 | { |
||
99 | 2 | $this->boxes = $boxList; |
|
100 | } |
||
101 | |||
102 | /** |
||
103 | * Number of boxes at which balancing weight is deemed not worth the extra computation time |
||
104 | * @return int |
||
105 | */ |
||
106 | 1 | public function getMaxBoxesToBalanceWeight(): int |
|
107 | { |
||
108 | 1 | return $this->maxBoxesToBalanceWeight; |
|
109 | } |
||
110 | |||
111 | /** |
||
112 | * Number of boxes at which balancing weight is deemed not worth the extra computation time |
||
113 | * @param int $maxBoxesToBalanceWeight |
||
114 | */ |
||
115 | 2 | public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight) |
|
116 | { |
||
117 | 2 | $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight; |
|
118 | } |
||
119 | |||
120 | /** |
||
121 | * Pack items into boxes |
||
122 | * |
||
123 | * @return PackedBoxList |
||
124 | */ |
||
125 | 26 | public function pack(): PackedBoxList |
|
126 | { |
||
127 | 26 | $packedBoxes = $this->doVolumePacking(); |
|
128 | |||
129 | //If we have multiple boxes, try and optimise/even-out weight distribution |
||
130 | 24 | if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) { |
|
131 | 6 | $redistributor = new WeightRedistributor($this->boxes); |
|
132 | 6 | $redistributor->setLogger($this->logger); |
|
133 | 6 | $packedBoxes = $redistributor->redistributeWeight($packedBoxes); |
|
134 | } |
||
135 | |||
136 | 24 | $this->logger->log(LogLevel::INFO, "packing completed, {$packedBoxes->count()} boxes"); |
|
137 | 24 | return $packedBoxes; |
|
138 | } |
||
139 | |||
140 | /** |
||
141 | * Pack items into boxes using the principle of largest volume item first |
||
142 | * |
||
143 | * @throws ItemTooLargeException |
||
144 | * @return PackedBoxList |
||
145 | */ |
||
146 | 26 | public function doVolumePacking(): PackedBoxList |
|
147 | { |
||
148 | |||
149 | 26 | $packedBoxes = new PackedBoxList; |
|
150 | |||
151 | //Keep going until everything packed |
||
152 | 26 | while ($this->items->count()) { |
|
153 | 26 | $packedBoxesIteration = []; |
|
154 | |||
155 | //Loop through boxes starting with smallest, see what happens |
||
156 | 26 | foreach ($this->boxes as $box) { |
|
157 | 25 | $volumePacker = new VolumePacker($box, clone $this->items); |
|
158 | 25 | $volumePacker->setLogger($this->logger); |
|
159 | 25 | $packedBox = $volumePacker->pack(); |
|
160 | 25 | if ($packedBox->getItems()->count()) { |
|
161 | 25 | $packedBoxesIteration[] = $packedBox; |
|
162 | |||
163 | //Have we found a single box that contains everything? |
||
164 | 25 | if ($packedBox->getItems()->count() === $this->items->count()) { |
|
165 | break; |
||
166 | } |
||
167 | } |
||
168 | } |
||
169 | |||
170 | //Check iteration was productive |
||
171 | 26 | if (!$packedBoxesIteration) { |
|
0 ignored issues
–
show
|
|||
172 | 2 | throw new ItemTooLargeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box', $this->items->top()); |
|
173 | } |
||
174 | |||
175 | //Find best box of iteration, and remove packed items from unpacked list |
||
176 | 25 | $bestBox = $this->findBestBoxFromIteration($packedBoxesIteration); |
|
177 | 25 | $unPackedItems = iterator_to_array($this->items, false); |
|
178 | 25 | foreach ($bestBox->getItems() as $packedItem) { |
|
179 | 25 | foreach ($unPackedItems as $unpackedKey => $unpackedItem) { |
|
180 | 25 | if ($packedItem->getItem() === $unpackedItem) { |
|
181 | 25 | unset($unPackedItems[$unpackedKey]); |
|
182 | 25 | break; |
|
183 | } |
||
184 | } |
||
185 | } |
||
186 | 25 | $unpackedItemList = new ItemList(); |
|
187 | 25 | foreach ($unPackedItems as $unpackedItem) { |
|
188 | 8 | $unpackedItemList->insert($unpackedItem); |
|
189 | } |
||
190 | 25 | $this->items = $unpackedItemList; |
|
191 | 25 | $packedBoxes->insert($bestBox); |
|
192 | |||
193 | } |
||
194 | |||
195 | 24 | return $packedBoxes; |
|
196 | } |
||
197 | |||
198 | /** |
||
199 | * @param PackedBox[] $packedBoxes |
||
200 | * |
||
201 | * @return PackedBox |
||
202 | */ |
||
203 | 25 | private function findBestBoxFromIteration($packedBoxes): PackedBox |
|
204 | { |
||
205 | 25 | usort($packedBoxes, [$this, 'compare']); |
|
206 | 25 | return array_shift($packedBoxes); |
|
207 | } |
||
208 | |||
209 | /** |
||
210 | * @param PackedBox $boxA |
||
211 | * @param PackedBox $boxB |
||
212 | * |
||
213 | * @return int |
||
214 | */ |
||
215 | 3 | View Code Duplication | private static function compare(PackedBox $boxA, PackedBox $boxB): int |
0 ignored issues
–
show
This method seems to be duplicated in your project.
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository.
Loading history...
|
|||
216 | { |
||
217 | 3 | $choice = $boxB->getItems()->count() <=> $boxA->getItems()->count(); |
|
218 | 3 | if ($choice === 0) { |
|
219 | $choice = $boxA->getInnerVolume() <=> $boxB->getInnerVolume(); |
||
220 | } |
||
221 | 3 | if ($choice === 0) { |
|
222 | $choice = $boxA->getWeight() <=> $boxB->getWeight(); |
||
223 | } |
||
224 | 3 | return $choice; |
|
225 | } |
||
226 | } |
||
227 |
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
empty(..)
or! empty(...)
instead.