WeightRedistributor::equaliseWeight()   B
last analyzed

Complexity

Conditions 7
Paths 12

Size

Total Lines 55
Code Lines 36

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 27
CRAP Score 7.2944

Importance

Changes 7
Bugs 1 Features 0
Metric Value
cc 7
eloc 36
c 7
b 1
f 0
nc 12
nop 3
dl 0
loc 55
rs 8.4106
ccs 27
cts 33
cp 0.8182
crap 7.2944

How to fix   Long Method   

Long Method

Small methods make your code easier to understand, in particular if combined with a good name. Besides, if your method is small, finding a good name is usually much easier.

For example, if you find yourself adding comments to a method's body, this is usually a good sign to extract the commented part to a new method, and use the comment as a starting point when coming up with a good name for this new method.

Commonly applied refactorings include:

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

186
        $oldVariance = self::calculateVariance(/** @scrutinizer ignore-type */ $overWeightItemsWeight, $underWeightItemsWeight);
Loading history...
Bug introduced by
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 ignore-type  annotation

186
        $oldVariance = self::calculateVariance($overWeightItemsWeight, /** @scrutinizer ignore-type */ $underWeightItemsWeight);
Loading history...
187
        $newVariance = self::calculateVariance($overWeightItemsWeight - $overWeightItem->getWeight(), $underWeightItemsWeight + $overWeightItem->getWeight());
188
189 8
        return $newVariance < $oldVariance;
190
    }
191 8
192
    private static function calculateVariance(int $boxAWeight, int $boxBWeight): float
193
    {
194
        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
195
    }
196
}
197