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 Psr\Log\LoggerAwareInterface; |
||
11 | use Psr\Log\LoggerAwareTrait; |
||
12 | use Psr\Log\LogLevel; |
||
13 | use Psr\Log\NullLogger; |
||
14 | |||
15 | /** |
||
16 | * Actual packer |
||
17 | * @author Doug Wright |
||
18 | * @package BoxPacker |
||
19 | */ |
||
20 | class WeightRedistributor implements LoggerAwareInterface |
||
21 | { |
||
22 | |||
23 | use LoggerAwareTrait; |
||
24 | |||
25 | /** |
||
26 | * List of box sizes available to pack items into |
||
27 | * @var BoxList |
||
28 | */ |
||
29 | protected $boxes; |
||
30 | |||
31 | /** |
||
32 | * Constructor |
||
33 | * |
||
34 | * @param BoxList $boxList |
||
35 | */ |
||
36 | 6 | public function __construct(BoxList $boxList) |
|
37 | { |
||
38 | 6 | $this->boxes = $boxList; |
|
39 | 6 | $this->logger = new NullLogger(); |
|
40 | } |
||
41 | |||
42 | /** |
||
43 | * Given a solution set of packed boxes, repack them to achieve optimum weight distribution |
||
44 | * |
||
45 | * @param PackedBoxList $originalBoxes |
||
46 | * @return PackedBoxList |
||
47 | */ |
||
48 | 6 | public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList |
|
49 | { |
||
50 | |||
51 | 6 | $targetWeight = $originalBoxes->getMeanWeight(); |
|
52 | 6 | $this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}"); |
|
53 | |||
54 | 6 | $packedBoxes = new PackedBoxList; |
|
55 | |||
56 | 6 | $overWeightBoxes = []; |
|
57 | 6 | $underWeightBoxes = []; |
|
58 | 6 | foreach ($originalBoxes as $packedBox) { |
|
59 | 6 | $boxWeight = $packedBox->getWeight(); |
|
60 | 6 | if ($boxWeight > $targetWeight) { |
|
61 | 4 | $overWeightBoxes[] = $packedBox; |
|
62 | 6 | } elseif ($boxWeight < $targetWeight) { |
|
63 | 4 | $underWeightBoxes[] = $packedBox; |
|
64 | } else { |
||
65 | 2 | $packedBoxes->insert($packedBox); //target weight, so we'll keep these |
|
66 | } |
||
67 | } |
||
68 | |||
69 | do { //Keep moving items from most overweight box to most underweight box |
||
70 | 6 | $tryRepack = false; |
|
71 | 6 | $this->logger->log(LogLevel::DEBUG, 'boxes under/over target: ' . count($underWeightBoxes) . '/' . count($overWeightBoxes)); |
|
72 | |||
73 | 6 | usort($overWeightBoxes, [$this, 'sortMoreSpaceFirst']); |
|
74 | 6 | usort($underWeightBoxes, [$this, 'sortMoreSpaceFirst']); |
|
75 | |||
76 | 6 | foreach ($underWeightBoxes as $u => $underWeightBox) { |
|
77 | 4 | $this->logger->log(LogLevel::DEBUG, 'Underweight Box ' . $u); |
|
78 | 4 | foreach ($overWeightBoxes as $o => $overWeightBox) { |
|
79 | 4 | $this->logger->log(LogLevel::DEBUG, 'Overweight Box ' . $o); |
|
80 | 4 | $overWeightBoxItems = $overWeightBox->getItems()->asItemArray(); |
|
81 | |||
82 | //For each item in the heavier box, try and move it to the lighter one |
||
83 | /** @var Item $overWeightBoxItem */ |
||
84 | 4 | foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) { |
|
85 | 4 | $this->logger->log(LogLevel::DEBUG, 'Overweight Item ' . $oi); |
|
86 | 4 | if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $targetWeight) { |
|
87 | 4 | $this->logger->log(LogLevel::DEBUG, 'Skipping item for hindering weight distribution'); |
|
88 | 4 | continue; //skip if moving this item would hinder rather than help weight distribution |
|
89 | } |
||
90 | |||
91 | 2 | $newItemsForLighterBox = $underWeightBox->getItems()->asItemArray(); |
|
92 | 2 | $newItemsForLighterBox[] = $overWeightBoxItem; |
|
93 | |||
94 | 2 | $newLighterBoxPacker = new Packer(); //we may need a bigger box |
|
95 | 2 | $newLighterBoxPacker->setBoxes($this->boxes); |
|
96 | 2 | $newLighterBoxPacker->setItems($newItemsForLighterBox); |
|
0 ignored issues
–
show
|
|||
97 | 2 | $this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK LIGHTER BOX]"); |
|
98 | 2 | $newLighterBox = $newLighterBoxPacker->doVolumePacking()->top(); |
|
99 | |||
100 | 2 | if ($newLighterBox->getItems()->count() === count($newItemsForLighterBox)) { //new item fits |
|
101 | 2 | $this->logger->log(LogLevel::DEBUG, 'New item fits'); |
|
102 | 2 | unset($overWeightBoxItems[$oi]); //now packed in different box |
|
103 | |||
104 | 2 | if (count($overWeightBoxItems) > 0) { |
|
105 | 2 | $newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box |
|
106 | 2 | $newHeavierBoxPacker->setBoxes($this->boxes); |
|
107 | 2 | $newHeavierBoxPacker->setItems($overWeightBoxItems); |
|
108 | |||
109 | 2 | $this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK HEAVIER BOX]"); |
|
110 | 2 | $newHeavierBoxes = $newHeavierBoxPacker->doVolumePacking(); |
|
111 | 2 | if ($newHeavierBoxes->count() |
|
112 | 2 | > 1) { //found an edge case in packing algorithm that *increased* box count |
|
113 | $this->logger->log( |
||
114 | LogLevel::INFO, |
||
115 | "[REDISTRIBUTING WEIGHT] Abandoning redistribution, because new packing is less efficient than original" |
||
116 | ); |
||
117 | |||
118 | return $originalBoxes; |
||
119 | } |
||
120 | |||
121 | 2 | $overWeightBoxes[$o] = $newHeavierBoxes->top(); |
|
122 | } else { |
||
123 | unset($overWeightBoxes[$o]); |
||
124 | } |
||
125 | 2 | $underWeightBoxes[$u] = $newLighterBox; |
|
126 | |||
127 | 2 | $tryRepack = true; //we did some work, so see if we can do even better |
|
128 | 4 | break 3; |
|
129 | } |
||
130 | } |
||
131 | } |
||
132 | } |
||
133 | 6 | } while ($tryRepack); |
|
134 | |||
135 | //Combine back into a single list |
||
136 | 6 | $packedBoxes->insertFromArray($overWeightBoxes); |
|
137 | 6 | $packedBoxes->insertFromArray($underWeightBoxes); |
|
138 | |||
139 | 6 | return $packedBoxes; |
|
140 | } |
||
141 | |||
142 | /** |
||
143 | * @param PackedBox $boxA |
||
144 | * @param PackedBox $boxB |
||
145 | * |
||
146 | * @return int |
||
147 | */ |
||
148 | 2 | private function sortMoreSpaceFirst(PackedBox $boxA, PackedBox $boxB): int |
|
149 | { |
||
150 | 2 | $choice = $boxB->getItems()->count() - $boxA->getItems()->count(); |
|
151 | 2 | if ($choice === 0) { |
|
152 | 2 | $choice = $boxA->getInnerVolume() - $boxB->getInnerVolume(); |
|
153 | } |
||
154 | 2 | if ($choice === 0) { |
|
155 | 2 | $choice = $boxB->getWeight() - $boxA->getWeight(); |
|
156 | } |
||
157 | 2 | return $choice; |
|
158 | } |
||
159 | } |
||
160 |
It seems like the type of the argument is not accepted by the function/method which you are calling.
In some cases, in particular if PHP’s automatic type-juggling kicks in this might be fine. In other cases, however this might be a bug.
We suggest to add an explicit type cast like in the following example: