|
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 ArrayIterator; |
|
12
|
|
|
use IteratorAggregate; |
|
13
|
|
|
use Traversable; |
|
14
|
|
|
|
|
15
|
|
|
/** |
|
16
|
|
|
* List of packed boxes. |
|
17
|
|
|
* |
|
18
|
|
|
* @author Doug Wright |
|
19
|
|
|
*/ |
|
20
|
|
|
class PackedBoxList implements IteratorAggregate |
|
21
|
|
|
{ |
|
22
|
|
|
/** |
|
23
|
|
|
* Average (mean) weight of boxes. |
|
24
|
|
|
* |
|
25
|
|
|
* @var float |
|
26
|
|
|
*/ |
|
27
|
|
|
protected $meanWeight; |
|
28
|
|
|
|
|
29
|
|
|
/** |
|
30
|
|
|
* List containing boxes. |
|
31
|
|
|
* |
|
32
|
|
|
* @var Box[] |
|
33
|
|
|
*/ |
|
34
|
|
|
private $list = []; |
|
35
|
|
|
|
|
36
|
|
|
/** |
|
37
|
|
|
* Has this list already been sorted? |
|
38
|
|
|
* |
|
39
|
|
|
* @var bool |
|
40
|
|
|
*/ |
|
41
|
|
|
private $isSorted = false; |
|
42
|
|
|
|
|
43
|
|
|
/** |
|
44
|
|
|
* @return Traversable |
|
45
|
|
|
*/ |
|
46
|
1 |
View Code Duplication |
public function getIterator(): Traversable |
|
|
|
|
|
|
47
|
|
|
{ |
|
48
|
1 |
|
if (!$this->isSorted) { |
|
49
|
1 |
|
usort($this->list, [$this, 'compare']); |
|
50
|
1 |
|
$this->isSorted = true; |
|
51
|
|
|
} |
|
52
|
|
|
|
|
53
|
1 |
|
return new ArrayIterator($this->list); |
|
54
|
|
|
} |
|
55
|
|
|
|
|
56
|
|
|
/** |
|
57
|
|
|
* Number of items in list. |
|
58
|
|
|
* |
|
59
|
|
|
* @return int |
|
60
|
|
|
*/ |
|
61
|
|
|
public function count(): int |
|
62
|
|
|
{ |
|
63
|
|
|
return count($this->list); |
|
64
|
|
|
} |
|
65
|
|
|
|
|
66
|
|
|
/** |
|
67
|
|
|
* @param PackedBox $item |
|
68
|
|
|
*/ |
|
69
|
2 |
|
public function insert(PackedBox $item) |
|
70
|
|
|
{ |
|
71
|
2 |
|
$this->list[] = $item; |
|
72
|
2 |
|
} |
|
73
|
|
|
|
|
74
|
|
|
/** |
|
75
|
|
|
* Do a bulk insert. |
|
76
|
|
|
* |
|
77
|
|
|
* @internal |
|
78
|
|
|
* |
|
79
|
|
|
* @param PackedBox[] $boxes |
|
80
|
|
|
*/ |
|
81
|
|
|
public function insertFromArray(array $boxes): void |
|
82
|
|
|
{ |
|
83
|
|
|
foreach ($boxes as $box) { |
|
84
|
|
|
$this->insert($box); |
|
85
|
|
|
} |
|
86
|
|
|
} |
|
87
|
|
|
|
|
88
|
|
|
/** |
|
89
|
|
|
* @internal |
|
90
|
|
|
* |
|
91
|
|
|
* @return PackedBox |
|
92
|
|
|
*/ |
|
93
|
|
View Code Duplication |
public function top(): PackedBox |
|
|
|
|
|
|
94
|
|
|
{ |
|
95
|
|
|
if (!$this->isSorted) { |
|
96
|
|
|
usort($this->list, [$this, 'compare']); |
|
97
|
|
|
$this->isSorted = true; |
|
98
|
|
|
} |
|
99
|
|
|
|
|
100
|
|
|
return reset($this->list); |
|
101
|
|
|
} |
|
102
|
|
|
|
|
103
|
|
|
/** |
|
104
|
|
|
* @param PackedBox $boxA |
|
105
|
|
|
* @param PackedBox $boxB |
|
106
|
|
|
* |
|
107
|
|
|
* @return int |
|
108
|
|
|
*/ |
|
109
|
|
View Code Duplication |
private function compare(PackedBox $boxA, PackedBox $boxB): int |
|
|
|
|
|
|
110
|
|
|
{ |
|
111
|
|
|
$choice = $boxB->getItems()->count() <=> $boxA->getItems()->count(); |
|
112
|
|
|
if ($choice === 0) { |
|
113
|
|
|
$choice = $boxB->getInnerVolume() <=> $boxA->getInnerVolume(); |
|
114
|
|
|
} |
|
115
|
|
|
if ($choice === 0) { |
|
116
|
|
|
$choice = $boxA->getWeight() <=> $boxB->getWeight(); |
|
117
|
|
|
} |
|
118
|
|
|
|
|
119
|
|
|
return $choice; |
|
120
|
|
|
} |
|
121
|
|
|
|
|
122
|
|
|
/** |
|
123
|
|
|
* Calculate the average (mean) weight of the boxes. |
|
124
|
|
|
* |
|
125
|
|
|
* @return float |
|
126
|
|
|
*/ |
|
127
|
1 |
|
public function getMeanWeight(): float |
|
128
|
|
|
{ |
|
129
|
1 |
|
if (!is_null($this->meanWeight)) { |
|
130
|
|
|
return $this->meanWeight; |
|
131
|
|
|
} |
|
132
|
|
|
|
|
133
|
|
|
/** @var PackedBox $box */ |
|
134
|
1 |
|
foreach ($this->list as $box) { |
|
135
|
1 |
|
$this->meanWeight += $box->getWeight(); |
|
|
|
|
|
|
136
|
|
|
} |
|
137
|
|
|
|
|
138
|
1 |
|
return $this->meanWeight /= count($this->list); |
|
139
|
|
|
} |
|
140
|
|
|
|
|
141
|
|
|
/** |
|
142
|
|
|
* Calculate the variance in weight between these boxes. |
|
143
|
|
|
* |
|
144
|
|
|
* @return float |
|
145
|
|
|
*/ |
|
146
|
1 |
|
public function getWeightVariance(): float |
|
147
|
|
|
{ |
|
148
|
1 |
|
$mean = $this->getMeanWeight(); |
|
149
|
|
|
|
|
150
|
1 |
|
$weightVariance = 0; |
|
151
|
|
|
/** @var PackedBox $box */ |
|
152
|
1 |
|
foreach ($this->list as $box) { |
|
153
|
1 |
|
$weightVariance += ($box->getWeight() - $mean) ** 2; |
|
154
|
|
|
} |
|
155
|
|
|
|
|
156
|
1 |
|
return round($weightVariance / count($this->list), 1); |
|
157
|
|
|
} |
|
158
|
|
|
|
|
159
|
|
|
/** |
|
160
|
|
|
* Get volume utilisation of the set of packed boxes. |
|
161
|
|
|
* |
|
162
|
|
|
* @return float |
|
163
|
|
|
*/ |
|
164
|
1 |
|
public function getVolumeUtilisation(): float |
|
165
|
|
|
{ |
|
166
|
1 |
|
$itemVolume = 0; |
|
167
|
1 |
|
$boxVolume = 0; |
|
168
|
|
|
|
|
169
|
|
|
/** @var PackedBox $box */ |
|
170
|
1 |
|
foreach ($this as $box) { |
|
171
|
1 |
|
$boxVolume += $box->getInnerVolume(); |
|
172
|
|
|
|
|
173
|
|
|
/** @var PackedItem $item */ |
|
174
|
1 |
|
foreach ($box->getItems() as $item) { |
|
175
|
1 |
|
$itemVolume += ($item->getItem()->getWidth() * $item->getItem()->getLength() * $item->getItem()->getDepth()); |
|
176
|
|
|
} |
|
177
|
|
|
} |
|
178
|
|
|
|
|
179
|
1 |
|
return round($itemVolume / $boxVolume * 100, 1); |
|
180
|
|
|
} |
|
181
|
|
|
} |
|
182
|
|
|
|
dvdoug /
BoxPacker
Loading history...
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.