WeightRedistributor::equaliseWeight()   B
last analyzed

Complexity

Conditions 8
Paths 14

Size

Total Lines 48
Code Lines 30

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 23
CRAP Score 8.5668

Importance

Changes 0
Metric Value
cc 8
eloc 30
c 0
b 0
f 0
nc 14
nop 3
dl 0
loc 48
ccs 23
cts 29
cp 0.7931
crap 8.5668
rs 8.1954
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\LoggerAwareTrait;
13
use Psr\Log\LogLevel;
14
use Psr\Log\NullLogger;
15
use function array_filter;
16
use function array_merge;
17
use function count;
18
use function iterator_to_array;
19
use function usort;
20
21
/**
22
 * Actual packer.
23
 *
24
 * @author Doug Wright
25
 * @internal
26
 */
27
class WeightRedistributor implements LoggerAwareInterface
28
{
29
    use LoggerAwareTrait;
30
31
    /**
32
     * List of box sizes available to pack items into.
33
     *
34
     * @var BoxList
35
     */
36
    private $boxes;
37
38
    /**
39
     * Constructor.
40
     *
41
     * @param BoxList $boxList
42
     */
43 8
    public function __construct(BoxList $boxList)
44
    {
45 8
        $this->boxes = $boxList;
46 8
        $this->logger = new NullLogger();
47 8
    }
48
49
    /**
50
     * Given a solution set of packed boxes, repack them to achieve optimum weight distribution.
51
     *
52
     * @param PackedBoxList $originalBoxes
53
     *
54
     * @return PackedBoxList
55
     */
56 8
    public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList
57
    {
58 8
        $targetWeight = $originalBoxes->getMeanWeight();
59 8
        $this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");
60
61
        /** @var PackedBox[] $boxes */
62 8
        $boxes = iterator_to_array($originalBoxes);
63
64
        usort($boxes, function (PackedBox $boxA, PackedBox $boxB) {
65 8
            return $boxB->getWeight() <=> $boxA->getWeight();
66 8
        });
67
68
        do {
69 8
            $iterationSuccessful = false;
70
71 8
            foreach ($boxes as $a => &$boxA) {
72 8
                foreach ($boxes as $b => &$boxB) {
73 8
                    if ($b <= $a || $boxA->getWeight() === $boxB->getWeight()) {
74 8
                        continue; //no need to evaluate
75
                    }
76
77 5
                    $iterationSuccessful = $this->equaliseWeight($boxA, $boxB, $targetWeight);
78 5
                    if ($iterationSuccessful) {
79
                        $boxes = array_filter($boxes, function (?PackedBox $box) { //remove any now-empty boxes from the list
80 3
                            return $box instanceof PackedBox;
81 3
                        });
82 8
                        break 2;
83
                    }
84
                }
85
            }
86 8
        } while ($iterationSuccessful);
87
88
        //Combine back into a single list
89 8
        $packedBoxes = new PackedBoxList();
90 8
        $packedBoxes->insertFromArray($boxes);
91
92 8
        return $packedBoxes;
93
    }
94
95
    /**
96
     * Attempt to equalise weight distribution between 2 boxes.
97
     *
98
     * @param PackedBox $boxA
99
     * @param PackedBox $boxB
100
     * @param float     $targetWeight
101
     *
102
     * @return bool was the weight rebalanced?
103
     */
104 5
    private function equaliseWeight(PackedBox &$boxA, PackedBox &$boxB, float $targetWeight): bool
105
    {
106 5
        $anyIterationSuccessful = false;
107
108 5
        if ($boxA->getWeight() > $boxB->getWeight()) {
109 5
            $overWeightBox = $boxA;
110 5
            $underWeightBox = $boxB;
111
        } else {
112
            $overWeightBox = $boxB;
113
            $underWeightBox = $boxA;
114
        }
115
116 5
        $overWeightBoxItems = $overWeightBox->getItems()->asItemArray();
117 5
        $underWeightBoxItems = $underWeightBox->getItems()->asItemArray();
118
119 5
        foreach ($overWeightBoxItems as $key => $overWeightItem) {
120 5
            if ($overWeightItem->getWeight() + $boxB->getWeight() > $targetWeight) {
121 4
                continue; // moving this item would harm more than help
122
            }
123
124 4
            $newLighterBoxes = $this->doVolumeRepack(array_merge($underWeightBoxItems, [$overWeightItem]));
125 4
            if ($newLighterBoxes->count() !== 1) {
126 1
                continue; //only want to move this item if it still fits in a single box
127
            }
128
129 3
            $underWeightBoxItems[] = $overWeightItem;
130
131 3
            if (count($overWeightBoxItems) === 1) { //sometimes a repack can be efficient enough to eliminate a box
132
                $boxB = $newLighterBoxes->top();
133
                $boxA = null;
134
135
                return true;
136
            } else {
137 3
                unset($overWeightBoxItems[$key]);
138 3
                $newHeavierBoxes = $this->doVolumeRepack($overWeightBoxItems);
139 3
                if (count($newHeavierBoxes) !== 1) {
140
                    continue;
141
                }
142
143 3
                if ($this->didRepackActuallyHelp($boxA, $boxB, $newHeavierBoxes->top(), $newLighterBoxes->top())) {
144 3
                    $boxB = $newLighterBoxes->top();
145 3
                    $boxA = $newHeavierBoxes->top();
146 3
                    $anyIterationSuccessful = true;
147
                }
148
            }
149
        }
150
151 5
        return $anyIterationSuccessful;
152
    }
153
154
    /**
155
     * Do a volume repack of a set of items.
156
     *
157
     * @param iterable $items
158
     *
159
     * @return PackedBoxList
160
     */
161 4
    private function doVolumeRepack(iterable $items): PackedBoxList
162
    {
163 4
        $packer = new Packer();
164 4
        $packer->setBoxes($this->boxes); // use the full set of boxes to allow smaller/larger for full efficiency
165 4
        $packer->setItems($items);
166
167 4
        return $packer->doVolumePacking();
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
     *
175
     * @param PackedBox $oldBoxA
176
     * @param PackedBox $oldBoxB
177
     * @param PackedBox $newBoxA
178
     * @param PackedBox $newBoxB
179
     *
180
     * @return bool
181
     */
182 3
    private function didRepackActuallyHelp(PackedBox $oldBoxA, PackedBox $oldBoxB, PackedBox $newBoxA, PackedBox $newBoxB): bool
183
    {
184 3
        $oldList = new PackedBoxList();
185 3
        $oldList->insertFromArray([$oldBoxA, $oldBoxB]);
186
187 3
        $newList = new PackedBoxList();
188 3
        $newList->insertFromArray([$newBoxA, $newBoxB]);
189
190 3
        return $newList->getWeightVariance() < $oldList->getWeightVariance();
191
    }
192
}
193