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 Psr\Log\LoggerAwareInterface; |
||||
12 | use Psr\Log\LoggerInterface; |
||||
13 | use Psr\Log\LogLevel; |
||||
14 | use Psr\Log\NullLogger; |
||||
15 | use WeakMap; |
||||
16 | |||||
17 | use function array_filter; |
||||
18 | use function array_map; |
||||
19 | use function array_merge; |
||||
20 | use function array_sum; |
||||
21 | use function assert; |
||||
22 | use function count; |
||||
23 | use function iterator_to_array; |
||||
24 | use function usort; |
||||
25 | |||||
26 | /** |
||||
27 | * Actual packer. |
||||
28 | * @internal |
||||
29 | */ |
||||
30 | class WeightRedistributor implements LoggerAwareInterface |
||||
31 | { |
||||
32 | private LoggerInterface $logger; |
||||
33 | |||||
34 | /** |
||||
35 | * @param WeakMap<Box, int> $boxQuantitiesAvailable |
||||
36 | */ |
||||
37 | 14 | public function __construct( |
|||
38 | private readonly BoxList $boxes, |
||||
39 | private readonly PackedBoxSorter $packedBoxSorter, |
||||
40 | private WeakMap $boxQuantitiesAvailable |
||||
41 | ) { |
||||
42 | 14 | $this->logger = new NullLogger(); |
|||
43 | } |
||||
44 | |||||
45 | 14 | public function setLogger(LoggerInterface $logger): void |
|||
46 | { |
||||
47 | 14 | $this->logger = $logger; |
|||
48 | } |
||||
49 | |||||
50 | /** |
||||
51 | * Given a solution set of packed boxes, repack them to achieve optimum weight distribution. |
||||
52 | */ |
||||
53 | 14 | public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList |
|||
54 | { |
||||
55 | 14 | $targetWeight = $originalBoxes->getMeanItemWeight(); |
|||
56 | 14 | $this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}"); |
|||
57 | |||||
58 | 14 | $boxes = iterator_to_array($originalBoxes); |
|||
59 | |||||
60 | 14 | usort($boxes, static fn (PackedBox $boxA, PackedBox $boxB) => $boxB->getWeight() <=> $boxA->getWeight()); |
|||
61 | |||||
62 | do { |
||||
63 | 14 | $iterationSuccessful = false; |
|||
64 | |||||
65 | 14 | foreach ($boxes as $a => &$boxA) { |
|||
66 | 14 | foreach ($boxes as $b => &$boxB) { |
|||
67 | 14 | if ($b <= $a || $boxA->getWeight() === $boxB->getWeight()) { |
|||
68 | 14 | continue; // no need to evaluate |
|||
69 | } |
||||
70 | |||||
71 | 10 | $iterationSuccessful = $this->equaliseWeight($boxA, $boxB, $targetWeight); |
|||
72 | 10 | if ($iterationSuccessful) { |
|||
73 | 6 | $boxes = array_filter($boxes, static fn (?PackedBox $box) => $box instanceof PackedBox); // remove any now-empty boxes from the list |
|||
74 | 6 | break 2; |
|||
75 | } |
||||
76 | } |
||||
77 | } |
||||
78 | 14 | } while ($iterationSuccessful); |
|||
79 | |||||
80 | // Combine back into a single list |
||||
81 | 14 | $packedBoxes = new PackedBoxList($this->packedBoxSorter); |
|||
82 | 14 | $packedBoxes->insertFromArray($boxes); |
|||
83 | |||||
84 | 14 | return $packedBoxes; |
|||
85 | } |
||||
86 | |||||
87 | /** |
||||
88 | * Attempt to equalise weight distribution between 2 boxes. |
||||
89 | * |
||||
90 | * @return bool was the weight rebalanced? |
||||
91 | */ |
||||
92 | 10 | private function equaliseWeight(PackedBox &$boxA, PackedBox &$boxB, float $targetWeight): bool |
|||
93 | { |
||||
94 | 10 | $anyIterationSuccessful = false; |
|||
95 | |||||
96 | 10 | if ($boxA->getWeight() > $boxB->getWeight()) { |
|||
97 | 10 | $overWeightBox = $boxA; |
|||
98 | 10 | $underWeightBox = $boxB; |
|||
99 | } else { |
||||
100 | 1 | $overWeightBox = $boxB; |
|||
101 | 1 | $underWeightBox = $boxA; |
|||
102 | } |
||||
103 | |||||
104 | 10 | $overWeightBoxItems = $overWeightBox->items->asItemArray(); |
|||
105 | 10 | $underWeightBoxItems = $underWeightBox->items->asItemArray(); |
|||
106 | |||||
107 | 10 | foreach ($overWeightBoxItems as $key => $overWeightItem) { |
|||
108 | 10 | if (!self::wouldRepackActuallyHelp($overWeightBoxItems, $overWeightItem, $underWeightBoxItems, $targetWeight)) { |
|||
109 | 9 | continue; // moving this item would harm more than help |
|||
110 | } |
||||
111 | |||||
112 | 7 | $newLighterBoxes = $this->doVolumeRepack(array_merge($underWeightBoxItems, [$overWeightItem]), $underWeightBox->box); |
|||
113 | 7 | if ($newLighterBoxes->count() !== 1) { |
|||
114 | 3 | continue; // only want to move this item if it still fits in a single box |
|||
115 | } |
||||
116 | |||||
117 | 6 | $underWeightBoxItems[] = $overWeightItem; |
|||
118 | |||||
119 | 6 | if (count($overWeightBoxItems) === 1) { // sometimes a repack can be efficient enough to eliminate a box |
|||
120 | $boxB = $newLighterBoxes->top(); |
||||
121 | $boxA = null; |
||||
122 | --$this->boxQuantitiesAvailable[$underWeightBox->box]; |
||||
123 | ++$this->boxQuantitiesAvailable[$overWeightBox->box]; |
||||
124 | |||||
125 | return true; |
||||
126 | } |
||||
127 | |||||
128 | 6 | unset($overWeightBoxItems[$key]); |
|||
129 | 6 | $newHeavierBoxes = $this->doVolumeRepack($overWeightBoxItems, $overWeightBox->box); |
|||
130 | 6 | if (count($newHeavierBoxes) !== 1) { |
|||
131 | assert(true, 'Could not pack n-1 items into box, even though n were previously in it'); |
||||
132 | continue; |
||||
133 | } |
||||
134 | |||||
135 | 6 | ++$this->boxQuantitiesAvailable[$overWeightBox->box]; |
|||
136 | 6 | ++$this->boxQuantitiesAvailable[$underWeightBox->box]; |
|||
137 | 6 | --$this->boxQuantitiesAvailable[$newHeavierBoxes->top()->box]; |
|||
138 | 6 | --$this->boxQuantitiesAvailable[$newLighterBoxes->top()->box]; |
|||
139 | 6 | $underWeightBox = $boxB = $newLighterBoxes->top(); |
|||
140 | 6 | $overWeightBox = $boxA = $newHeavierBoxes->top(); |
|||
141 | |||||
142 | 6 | $anyIterationSuccessful = true; |
|||
143 | } |
||||
144 | |||||
145 | 10 | return $anyIterationSuccessful; |
|||
146 | } |
||||
147 | |||||
148 | /** |
||||
149 | * Do a volume repack of a set of items. |
||||
150 | * @param iterable<Item> $items |
||||
151 | */ |
||||
152 | 7 | private function doVolumeRepack(iterable $items, Box $currentBox): PackedBoxList |
|||
153 | { |
||||
154 | 7 | $packer = new Packer(); |
|||
155 | 7 | $packer->throwOnUnpackableItem(false); |
|||
156 | 7 | $packer->setLogger($this->logger); |
|||
157 | 7 | $packer->setBoxes($this->boxes); // use the full set of boxes to allow smaller/larger for full efficiency |
|||
158 | 7 | foreach ($this->boxes as $box) { |
|||
159 | 7 | $packer->setBoxQuantity($box, $this->boxQuantitiesAvailable[$box]); |
|||
160 | } |
||||
161 | 7 | $packer->setBoxQuantity($currentBox, $this->boxQuantitiesAvailable[$currentBox] + 1); |
|||
162 | 7 | $packer->setItems($items); |
|||
163 | |||||
164 | 7 | return $packer->doBasicPacking(true); |
|||
165 | } |
||||
166 | |||||
167 | /** |
||||
168 | * Not every attempted repack is actually helpful - sometimes moving an item between two otherwise identical |
||||
169 | * boxes, or sometimes the box used for the now lighter set of items actually weighs more when empty causing |
||||
170 | * an increase in total weight. |
||||
171 | * @param array<Item> $overWeightBoxItems |
||||
172 | * @param array<Item> $underWeightBoxItems |
||||
173 | */ |
||||
174 | 10 | private static function wouldRepackActuallyHelp(array $overWeightBoxItems, Item $overWeightItem, array $underWeightBoxItems, float $targetWeight): bool |
|||
175 | { |
||||
176 | 10 | $overWeightItemsWeight = array_sum(array_map(static fn (Item $item) => $item->getWeight(), $overWeightBoxItems)); |
|||
177 | 10 | $underWeightItemsWeight = array_sum(array_map(static fn (Item $item) => $item->getWeight(), $underWeightBoxItems)); |
|||
178 | |||||
179 | 10 | if ($overWeightItem->getWeight() + $underWeightItemsWeight > $targetWeight) { |
|||
180 | 9 | return false; |
|||
181 | } |
||||
182 | |||||
183 | 7 | $oldVariance = self::calculateVariance($overWeightItemsWeight, $underWeightItemsWeight); |
|||
0 ignored issues
–
show
Bug
introduced
by
Loading history...
It seems like
$underWeightItemsWeight can also be of type double ; however, parameter $boxBWeight of DVDoug\BoxPacker\WeightR...or::calculateVariance() does only seem to accept integer , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||
184 | 7 | $newVariance = self::calculateVariance($overWeightItemsWeight - $overWeightItem->getWeight(), $underWeightItemsWeight + $overWeightItem->getWeight()); |
|||
185 | |||||
186 | 7 | return $newVariance < $oldVariance; |
|||
187 | } |
||||
188 | |||||
189 | 7 | private static function calculateVariance(int $boxAWeight, int $boxBWeight): float |
|||
190 | { |
||||
191 | 7 | return ($boxAWeight - (($boxAWeight + $boxBWeight) / 2)) ** 2; // don't need to calculate B and รท 2, for a 2-item population the difference from mean is the same for each box |
|||
192 | } |
||||
193 | } |
||||
194 |