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