Completed
Push — master ( 7e0694...82858a )
by Doug
13:02
created

WeightRedistributor::sortBoxes()   A

Complexity

Conditions 4
Paths 4

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 12
Code Lines 9

Code Coverage

Tests 8
CRAP Score 4

Importance

Changes 0
Metric Value
dl 0
loc 12
ccs 8
cts 8
cp 1
rs 9.2
c 0
b 0
f 0
cc 4
eloc 9
nc 4
nop 0
crap 4
1
<?php
2
/**
3
 * Box packing (3D bin packing, knapsack problem)
4
 * @package BoxPacker
5
 * @author Doug Wright
6
 */
7
namespace DVDoug\BoxPacker;
8
9
use Psr\Log\LoggerAwareInterface;
10
use Psr\Log\LoggerAwareTrait;
11
use Psr\Log\LogLevel;
12
use Psr\Log\NullLogger;
13
14
/**
15
 * Actual packer
16
 * @author Doug Wright
17
 * @package BoxPacker
18
 */
19
class WeightRedistributor implements LoggerAwareInterface
20
{
21
22
    use LoggerAwareTrait;
23
24
    /**
25
     * List of box sizes available to pack items into
26
     * @var BoxList
27
     */
28
    protected $boxList;
29
30
    /**
31
     * @var PackedBoxList
32
     */
33
    protected $originalPackedBoxes;
34
35
    /**
36
     * @var PackedBox[]
37
     */
38
    protected $underWeightBoxes = [];
39
40
    /**
41
     * @var PackedBox[]
42
     */
43
    protected $targetWeightBoxes = [];
44
45
    /**
46
     * @var PackedBox[]
47
     */
48
    protected $overWeightBoxes = [];
49
50
    /**
51
     * @var float
52
     */
53
    protected $targetWeight;
54
55
    /**
56
     * Constructor
57
     *
58
     * @param BoxList       $boxList
59
     * @param PackedBoxList $originalPackedBoxes
60
     */
61 4
    public function __construct(BoxList $boxList, PackedBoxList $originalPackedBoxes)
62
    {
63 4
        $this->boxList = clone $boxList;
64 4
        $this->originalPackedBoxes = $originalPackedBoxes;
65 4
        $this->logger = new NullLogger();
66
67 4
        $this->targetWeight = $this->originalPackedBoxes->getMeanWeight();
0 ignored issues
show
Documentation Bug introduced by Doug Wright
It seems like $this->originalPackedBoxes->getMeanWeight() can also be of type integer. However, the property $targetWeight is declared as type double. Maybe add an additional type check?

Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a mixed type is assigned to a property that is type hinted more strictly.

For example, imagine you have a variable $accountId that can either hold an Id object or false (if there is no account id yet). Your code now assigns that value to the id property of an instance of the Account class. This class holds a proper account, so the id value must no longer be false.

Either this assignment is in error or a type check should be added for that assignment.

class Id
{
    public $id;

    public function __construct($id)
    {
        $this->id = $id;
    }

}

class Account
{
    /** @var  Id $id */
    public $id;
}

$account_id = false;

if (starsAreRight()) {
    $account_id = new Id(42);
}

$account = new Account();
if ($account instanceof Id)
{
    $account->id = $account_id;
}
Loading history...
68 4
        $this->sortBoxes();
69
    }
70
71
    /**
72
     * Given a solution set of packed boxes, repack them to achieve optimum weight distribution
73
     *
74
     * @return PackedBoxList
75
     */
76 4
    public function redistributeWeight()
77
    {
78 4
        $this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$this->originalPackedBoxes->getWeightVariance()}, target weight {$this->targetWeight}");
79
80 4
        $packedBoxes = new PackedBoxList;
81
82
        do { //Keep moving items from most overweight box to most underweight box
83 4
            $tryRepack = false;
84 4
            $this->logger->log(LogLevel::DEBUG, 'boxes under/over target: '.count($this->underWeightBoxes).'/'.count($this->overWeightBoxes));
85
86 4
            foreach ($this->underWeightBoxes as $u => $underWeightBox) {
87 3
                $this->logger->log(LogLevel::DEBUG, 'Underweight Box '.$u);
88 3
                foreach ($this->overWeightBoxes as $o => $overWeightBox) {
89 3
                    $this->logger->log(LogLevel::DEBUG, 'Overweight Box '.$o);
90 3
                    $overWeightBoxItems = $overWeightBox->getItems()->asArray();
91
92
                    //For each item in the heavier box, try and move it to the lighter one
93 3
                    foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) {
94 3
                        $this->logger->log(LogLevel::DEBUG, 'Overweight Item '.$oi);
95 3
                        if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $this->targetWeight) {
96 3
                            $this->logger->log(LogLevel::DEBUG, 'Skipping item for hindering weight distribution');
97 3
                            continue; //skip if moving this item would hinder rather than help weight distribution
98
                        }
99
100 2
                        $newItemsForLighterBox = clone $underWeightBox->getItems();
101 2
                        $newItemsForLighterBox->insert($overWeightBoxItem);
102
103 2
                        $newLighterBoxPacker = new Packer(); //we may need a bigger box
104 2
                        $newLighterBoxPacker->setBoxes($this->boxList);
105 2
                        $newLighterBoxPacker->setItems($newItemsForLighterBox);
106 2
                        $this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK LIGHTER BOX]");
107 2
                        $newLighterBox = $newLighterBoxPacker->doVolumePacking()->getIterator()->current();
108
109 2
                        if ($newLighterBox->getItems()->count() === $newItemsForLighterBox->count()) { //new item fits
110 2
                            $this->logger->log(LogLevel::DEBUG, 'New item fits');
111 2
                            unset($overWeightBoxItems[$oi]); //now packed in different box
112
113 2
                            $newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box
114 2
                            $newHeavierBoxPacker->setBoxes($this->boxList);
115 2
                            $newHeavierBoxPacker->setItems($overWeightBoxItems);
116
117 2
                            $this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK HEAVIER BOX]");
118 2
                            $newHeavierBoxes = $newHeavierBoxPacker->doVolumePacking();
119 2
                            if (count($newHeavierBoxes) > 1) { //found an edge case in packing algorithm that *increased* box count
120
                                $this->logger->log(LogLevel::INFO, "[REDISTRIBUTING WEIGHT] Abandoning redistribution, because new packing is less efficient than original");
121
                                return $this->originalPackedBoxes;
122
                            }
123
124 2
                            $this->overWeightBoxes[$o] = $newHeavierBoxes->getIterator()->current();
125 2
                            $this->underWeightBoxes[$u] = $newLighterBox;
126
127 2
                            $tryRepack = true; //we did some work, so see if we can do even better
128 2
                            usort($this->overWeightBoxes, [$packedBoxes, 'reverseCompare']);
129 2
                            usort($this->underWeightBoxes, [$packedBoxes, 'reverseCompare']);
130 3
                            break 3;
131
                        }
132
                    }
133
                }
134
            }
135 4
        } while ($tryRepack);
136
137
        //Combine back into a single list
138 4
        $packedBoxes->insertFromArray($this->overWeightBoxes);
139 4
        $packedBoxes->insertFromArray($this->underWeightBoxes);
140 4
        $packedBoxes->insertFromArray($this->targetWeightBoxes);
141
142 4
        return $packedBoxes;
143
    }
144
145
    /**
146
     * Perform initial classification of boxes into under/over/target weight
147
     */
148 4
    protected function sortBoxes() {
149 4
        foreach (clone $this->originalPackedBoxes as $packedBox) {
150 4
            $boxWeight = $packedBox->getWeight();
151 4
            if ($boxWeight > $this->targetWeight) {
152 3
                $this->overWeightBoxes[] = $packedBox;
153 4
            } elseif ($boxWeight < $this->targetWeight) {
154 3
                $this->underWeightBoxes[] = $packedBox;
155
            } else {
156 4
                $this->targetWeightBoxes[] = $packedBox; //target weight, so we'll keep these
157
            }
158
        }
159
    }
160
}
161