|
1
|
|
|
<?php |
|
2
|
|
|
/** |
|
3
|
|
|
* Box packing (3D bin packing, knapsack problem). |
|
4
|
|
|
* |
|
5
|
|
|
* @author Doug Wright |
|
6
|
|
|
*/ |
|
7
|
|
|
|
|
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
|
|
|
* |
|
18
|
|
|
* @author Doug Wright |
|
19
|
|
|
*/ |
|
20
|
|
|
class WeightRedistributor implements LoggerAwareInterface |
|
21
|
|
|
{ |
|
22
|
|
|
use LoggerAwareTrait; |
|
23
|
|
|
|
|
24
|
|
|
/** |
|
25
|
|
|
* List of box sizes available to pack items into. |
|
26
|
|
|
* |
|
27
|
|
|
* @var BoxList |
|
28
|
|
|
*/ |
|
29
|
|
|
protected $boxes; |
|
30
|
|
|
|
|
31
|
|
|
/** |
|
32
|
|
|
* Constructor. |
|
33
|
|
|
* |
|
34
|
|
|
* @param BoxList $boxList |
|
35
|
|
|
*/ |
|
36
|
1 |
|
public function __construct(BoxList $boxList) |
|
37
|
|
|
{ |
|
38
|
1 |
|
$this->boxes = clone $boxList; |
|
39
|
1 |
|
$this->logger = new NullLogger(); |
|
40
|
1 |
|
} |
|
41
|
|
|
|
|
42
|
|
|
/** |
|
43
|
|
|
* Given a solution set of packed boxes, repack them to achieve optimum weight distribution. |
|
44
|
|
|
* |
|
45
|
|
|
* @param PackedBoxList $originalBoxes |
|
46
|
|
|
* |
|
47
|
|
|
* @return PackedBoxList |
|
48
|
|
|
*/ |
|
49
|
1 |
|
public function redistributeWeight(PackedBoxList $originalBoxes) |
|
50
|
|
|
{ |
|
51
|
1 |
|
$targetWeight = $originalBoxes->getMeanWeight(); |
|
52
|
1 |
|
$this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}"); |
|
53
|
|
|
|
|
54
|
1 |
|
$packedBoxes = new PackedBoxList(); |
|
55
|
|
|
|
|
56
|
1 |
|
$overWeightBoxes = []; |
|
57
|
1 |
|
$underWeightBoxes = []; |
|
58
|
1 |
|
foreach (clone $originalBoxes as $packedBox) { |
|
59
|
1 |
|
$boxWeight = $packedBox->getWeight(); |
|
60
|
1 |
|
if ($boxWeight > $targetWeight) { |
|
61
|
1 |
|
$overWeightBoxes[] = $packedBox; |
|
62
|
1 |
|
} elseif ($boxWeight < $targetWeight) { |
|
63
|
1 |
|
$underWeightBoxes[] = $packedBox; |
|
64
|
|
|
} else { |
|
65
|
1 |
|
$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
|
1 |
|
$tryRepack = false; |
|
71
|
1 |
|
$this->logger->log(LogLevel::DEBUG, 'boxes under/over target: '.count($underWeightBoxes).'/'.count($overWeightBoxes)); |
|
72
|
|
|
|
|
73
|
1 |
|
usort($overWeightBoxes, [$this, 'sortMoreSpaceFirst']); |
|
74
|
1 |
|
usort($underWeightBoxes, [$this, 'sortMoreSpaceFirst']); |
|
75
|
|
|
|
|
76
|
1 |
|
foreach ($underWeightBoxes as $u => $underWeightBox) { |
|
77
|
1 |
|
$this->logger->log(LogLevel::DEBUG, 'Underweight Box '.$u); |
|
78
|
1 |
|
foreach ($overWeightBoxes as $o => $overWeightBox) { |
|
79
|
1 |
|
$this->logger->log(LogLevel::DEBUG, 'Overweight Box '.$o); |
|
80
|
1 |
|
$overWeightBoxItems = $overWeightBox->getItems()->asArray(); |
|
81
|
|
|
|
|
82
|
|
|
//For each item in the heavier box, try and move it to the lighter one |
|
83
|
|
|
/** @var Item $overWeightBoxItem */ |
|
84
|
1 |
|
foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) { |
|
85
|
1 |
|
$this->logger->log(LogLevel::DEBUG, 'Overweight Item '.$oi); |
|
86
|
1 |
|
if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $targetWeight) { |
|
87
|
1 |
|
$this->logger->log(LogLevel::DEBUG, 'Skipping item for hindering weight distribution'); |
|
88
|
1 |
|
continue; //skip if moving this item would hinder rather than help weight distribution |
|
89
|
|
|
} |
|
90
|
|
|
|
|
91
|
|
|
$newItemsForLighterBox = $underWeightBox->getItems()->asArray(); |
|
92
|
|
|
$newItemsForLighterBox[] = $overWeightBoxItem; |
|
93
|
|
|
|
|
94
|
|
|
$newLighterBoxPacker = new Packer(); //we may need a bigger box |
|
95
|
|
|
$newLighterBoxPacker->setBoxes($this->boxes); |
|
96
|
|
|
$newLighterBoxPacker->setItems($newItemsForLighterBox); |
|
97
|
|
|
$this->logger->log(LogLevel::INFO, '[ATTEMPTING TO PACK LIGHTER BOX]'); |
|
98
|
|
|
$newLighterBox = $newLighterBoxPacker->doVolumePacking()->top(); |
|
99
|
|
|
|
|
100
|
|
|
if ($newLighterBox->getItems()->count() === count($newItemsForLighterBox)) { //new item fits |
|
101
|
|
|
$this->logger->log(LogLevel::DEBUG, 'New item fits'); |
|
102
|
|
|
unset($overWeightBoxItems[$oi]); //now packed in different box |
|
103
|
|
|
|
|
104
|
|
|
if (count($overWeightBoxItems) > 0) { |
|
105
|
|
|
$newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box |
|
106
|
|
|
$newHeavierBoxPacker->setBoxes($this->boxes); |
|
107
|
|
|
$newHeavierBoxPacker->setItems($overWeightBoxItems); |
|
108
|
|
|
|
|
109
|
|
|
$this->logger->log(LogLevel::INFO, '[ATTEMPTING TO PACK HEAVIER BOX]'); |
|
110
|
|
|
$newHeavierBoxes = $newHeavierBoxPacker->doVolumePacking(); |
|
111
|
|
|
if ($newHeavierBoxes->count() |
|
112
|
|
|
> 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
|
|
|
$overWeightBoxes[$o] = $newHeavierBoxes->top(); |
|
122
|
|
|
} else { |
|
123
|
|
|
unset($overWeightBoxes[$o]); |
|
124
|
|
|
} |
|
125
|
|
|
$underWeightBoxes[$u] = $newLighterBox; |
|
126
|
|
|
|
|
127
|
|
|
$tryRepack = true; //we did some work, so see if we can do even better |
|
128
|
1 |
|
break 3; |
|
129
|
|
|
} |
|
130
|
|
|
} |
|
131
|
|
|
} |
|
132
|
|
|
} |
|
133
|
1 |
|
} while ($tryRepack); |
|
134
|
|
|
|
|
135
|
|
|
//Combine back into a single list |
|
136
|
1 |
|
$packedBoxes->insertFromArray($overWeightBoxes); |
|
137
|
1 |
|
$packedBoxes->insertFromArray($underWeightBoxes); |
|
138
|
|
|
|
|
139
|
1 |
|
return $packedBoxes; |
|
140
|
|
|
} |
|
141
|
|
|
|
|
142
|
|
|
/** |
|
143
|
|
|
* @param PackedBox $boxA |
|
144
|
|
|
* @param PackedBox $boxB |
|
145
|
|
|
* |
|
146
|
|
|
* @return int |
|
147
|
|
|
*/ |
|
148
|
1 |
View Code Duplication |
private function sortMoreSpaceFirst(PackedBox $boxA, PackedBox $boxB) |
|
|
|
|
|
|
149
|
|
|
{ |
|
150
|
1 |
|
$choice = $boxB->getItems()->count() - $boxA->getItems()->count(); |
|
151
|
1 |
|
if ($choice === 0) { |
|
152
|
1 |
|
$choice = $boxA->getInnerVolume() - $boxB->getInnerVolume(); |
|
153
|
|
|
} |
|
154
|
1 |
|
if ($choice === 0) { |
|
155
|
1 |
|
$choice = $boxB->getWeight() - $boxA->getWeight(); |
|
156
|
|
|
} |
|
157
|
|
|
|
|
158
|
1 |
|
return $choice; |
|
159
|
|
|
} |
|
160
|
|
|
} |
|
161
|
|
|
|
dvdoug /
BoxPacker
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.
You can also find more detailed suggestions in the “Code” section of your repository.