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\NullLogger; |
12
|
|
|
|
13
|
|
|
/** |
14
|
|
|
* Actual packer |
15
|
|
|
* @author Doug Wright |
16
|
|
|
* @package BoxPacker |
17
|
|
|
*/ |
18
|
|
|
class VolumePacker implements LoggerAwareInterface |
19
|
|
|
{ |
20
|
|
|
use LoggerAwareTrait; |
21
|
|
|
|
22
|
|
|
/** |
23
|
|
|
* Box to pack items into |
24
|
|
|
* @var Box |
25
|
|
|
*/ |
26
|
|
|
protected $box; |
27
|
|
|
|
28
|
|
|
/** |
29
|
|
|
* List of items to be packed |
30
|
|
|
* @var ItemList |
31
|
|
|
*/ |
32
|
|
|
protected $items; |
33
|
|
|
|
34
|
|
|
/** |
35
|
|
|
* Remaining width of the box to pack items into |
36
|
|
|
* @var int |
37
|
|
|
*/ |
38
|
|
|
protected $widthLeft; |
39
|
|
|
|
40
|
|
|
/** |
41
|
|
|
* Remaining length of the box to pack items into |
42
|
|
|
* @var int |
43
|
|
|
*/ |
44
|
|
|
protected $lengthLeft; |
45
|
|
|
|
46
|
|
|
/** |
47
|
|
|
* Remaining depth of the box to pack items into |
48
|
|
|
* @var int |
49
|
|
|
*/ |
50
|
|
|
protected $depthLeft; |
51
|
|
|
|
52
|
|
|
/** |
53
|
|
|
* Remaining weight capacity of the box |
54
|
|
|
* @var int |
55
|
|
|
*/ |
56
|
|
|
protected $remainingWeight; |
57
|
|
|
|
58
|
|
|
/** |
59
|
|
|
* Used width inside box for packing items |
60
|
|
|
* @var int |
61
|
|
|
*/ |
62
|
|
|
protected $usedWidth = 0; |
63
|
|
|
|
64
|
|
|
/** |
65
|
|
|
* Used length inside box for packing items |
66
|
|
|
* @var int |
67
|
|
|
*/ |
68
|
|
|
protected $usedLength = 0; |
69
|
|
|
|
70
|
|
|
/** |
71
|
|
|
* Used depth inside box for packing items |
72
|
|
|
* @var int |
73
|
|
|
*/ |
74
|
|
|
protected $usedDepth = 0; |
75
|
|
|
|
76
|
|
|
/** |
77
|
|
|
* @var int |
78
|
|
|
*/ |
79
|
|
|
protected $layerWidth = 0; |
80
|
|
|
|
81
|
|
|
/** |
82
|
|
|
* @var int |
83
|
|
|
*/ |
84
|
|
|
protected $layerLength = 0; |
85
|
|
|
|
86
|
|
|
/** |
87
|
|
|
* @var int |
88
|
|
|
*/ |
89
|
|
|
protected $layerDepth = 0; |
90
|
|
|
|
91
|
|
|
/** |
92
|
|
|
* Constructor |
93
|
|
|
* |
94
|
|
|
* @param Box $box |
95
|
|
|
* @param ItemList $items |
96
|
|
|
*/ |
97
|
33 |
|
public function __construct(Box $box, ItemList $items) |
98
|
|
|
{ |
99
|
33 |
|
$this->logger = new NullLogger(); |
100
|
|
|
|
101
|
33 |
|
$this->box = $box; |
102
|
33 |
|
$this->items = $items; |
103
|
|
|
|
104
|
33 |
|
$this->depthLeft = $this->box->getInnerDepth(); |
105
|
33 |
|
$this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight(); |
106
|
33 |
|
$this->widthLeft = $this->box->getInnerWidth(); |
107
|
33 |
|
$this->lengthLeft = $this->box->getInnerLength(); |
108
|
|
|
} |
109
|
|
|
|
110
|
|
|
/** |
111
|
|
|
* Pack as many items as possible into specific given box |
112
|
|
|
* @return PackedBox packed box |
113
|
|
|
*/ |
114
|
33 |
|
public function pack() |
115
|
|
|
{ |
116
|
33 |
|
$this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}"); |
117
|
|
|
|
118
|
33 |
|
$packedItems = new ItemList; |
119
|
|
|
|
120
|
33 |
|
$this->layerWidth = $this->layerLength = $this->layerDepth = 0; |
121
|
|
|
|
122
|
33 |
|
$prevItem = null; |
123
|
|
|
|
124
|
33 |
|
while (!$this->items->isEmpty()) { |
125
|
|
|
|
126
|
33 |
|
$itemToPack = $this->items->extract(); |
127
|
|
|
|
128
|
|
|
//skip items that are simply too heavy |
129
|
33 |
|
if (!$this->checkNonDimensionalConstraints($itemToPack, $packedItems)) { |
130
|
5 |
|
continue; |
131
|
|
|
} |
132
|
|
|
|
133
|
33 |
|
$nextItem = !$this->items->isEmpty() ? $this->items->top() : null; |
134
|
33 |
|
$orientatedItem = $this->getOrientationForItem($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft); |
135
|
|
|
|
136
|
33 |
|
if ($orientatedItem) { |
137
|
|
|
|
138
|
33 |
|
$packedItems->insert($orientatedItem->getItem()); |
139
|
33 |
|
$this->remainingWeight -= $orientatedItem->getItem()->getWeight(); |
140
|
|
|
|
141
|
33 |
|
$this->lengthLeft -= $orientatedItem->getLength(); |
142
|
33 |
|
$this->layerLength += $orientatedItem->getLength(); |
143
|
33 |
|
$this->layerWidth = max($orientatedItem->getWidth(), $this->layerWidth); |
144
|
|
|
|
145
|
33 |
|
$this->layerDepth = max($this->layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep |
146
|
|
|
|
147
|
33 |
|
$this->usedLength = max($this->usedLength, $this->layerLength); |
148
|
33 |
|
$this->usedWidth = max($this->usedWidth, $this->layerWidth); |
149
|
|
|
|
150
|
|
|
//allow items to be stacked in place within the same footprint up to current layerdepth |
151
|
33 |
|
$stackableDepth = $this->layerDepth - $orientatedItem->getDepth(); |
152
|
33 |
|
$this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth); |
153
|
|
|
|
154
|
33 |
|
$prevItem = $orientatedItem; |
155
|
|
|
|
156
|
33 |
|
if ($this->items->isEmpty()) { |
157
|
33 |
|
$this->usedDepth += $this->layerDepth; |
158
|
|
|
} |
159
|
|
|
} else { |
160
|
|
|
|
161
|
25 |
|
$prevItem = null; |
162
|
|
|
|
163
|
25 |
|
if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted()) { |
164
|
24 |
|
$this->logger->debug("No more fit in lengthwise, resetting for new row"); |
165
|
24 |
|
$this->lengthLeft += $this->layerLength; |
166
|
24 |
|
$this->widthLeft -= $this->layerWidth; |
167
|
24 |
|
$this->layerWidth = $this->layerLength = 0; |
168
|
24 |
|
$this->items->insert($itemToPack); |
169
|
24 |
|
continue; |
170
|
19 |
|
} elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $this->layerDepth == 0) { |
171
|
8 |
|
$this->logger->debug("doesn't fit on layer even when empty"); |
172
|
8 |
|
$this->usedDepth += $this->layerDepth; |
173
|
8 |
|
continue; |
174
|
|
|
} |
175
|
|
|
|
176
|
17 |
|
$this->widthLeft = $this->layerWidth ? min(floor($this->layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth(); |
177
|
17 |
|
$this->lengthLeft = $this->layerLength ? min(floor($this->layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength(); |
178
|
17 |
|
$this->depthLeft -= $this->layerDepth; |
179
|
17 |
|
$this->usedDepth += $this->layerDepth; |
180
|
|
|
|
181
|
17 |
|
$this->layerWidth = $this->layerLength = $this->layerDepth = 0; |
182
|
17 |
|
$this->logger->debug("doesn't fit, so starting next vertical layer"); |
183
|
17 |
|
$this->items->insert($itemToPack); |
184
|
|
|
} |
185
|
|
|
} |
186
|
33 |
|
$this->logger->debug("done with this box"); |
187
|
33 |
|
return new PackedBox( |
188
|
33 |
|
$this->box, |
189
|
|
|
$packedItems, |
190
|
33 |
|
$this->widthLeft, |
191
|
33 |
|
$this->lengthLeft, |
192
|
33 |
|
$this->depthLeft, |
193
|
33 |
|
$this->remainingWeight, |
194
|
33 |
|
$this->usedWidth, |
195
|
33 |
|
$this->usedLength, |
196
|
33 |
|
$this->usedDepth); |
197
|
|
|
} |
198
|
|
|
|
199
|
|
|
/** |
200
|
|
|
* @param Item $itemToPack |
201
|
|
|
* @param OrientatedItem|null $prevItem |
202
|
|
|
* @param Item|null $nextItem |
203
|
|
|
* @param int $maxWidth |
204
|
|
|
* @param int $maxLength |
205
|
|
|
* @param int $maxDepth |
206
|
|
|
* |
207
|
|
|
* @return OrientatedItem|false |
208
|
|
|
*/ |
209
|
33 |
|
protected function getOrientationForItem( |
210
|
|
|
Item $itemToPack, |
211
|
|
|
OrientatedItem $prevItem = null, |
212
|
|
|
Item $nextItem = null, |
213
|
|
|
$maxWidth, $maxLength, |
214
|
|
|
$maxDepth |
215
|
|
|
) { |
216
|
33 |
|
$this->logger->debug( |
217
|
33 |
|
"evaluating item {$itemToPack->getDescription()} for fit", |
218
|
|
|
[ |
219
|
33 |
|
'item' => $itemToPack, |
220
|
|
|
'space' => [ |
221
|
33 |
|
'maxWidth' => $maxWidth, |
222
|
33 |
|
'maxLength' => $maxLength, |
223
|
33 |
|
'maxDepth' => $maxDepth, |
224
|
33 |
|
'layerWidth' => $this->layerWidth, |
225
|
33 |
|
'layerLength' => $this->layerLength, |
226
|
33 |
|
'layerDepth' => $this->layerDepth |
227
|
|
|
] |
228
|
|
|
] |
229
|
|
|
); |
230
|
|
|
|
231
|
33 |
|
$orientatedItemFactory = new OrientatedItemFactory(); |
232
|
33 |
|
$orientatedItemFactory->setLogger($this->logger); |
233
|
33 |
|
$orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevItem, $nextItem, $maxWidth, $maxLength, $maxDepth); |
234
|
|
|
|
235
|
33 |
|
return $orientatedItem; |
236
|
|
|
} |
237
|
|
|
|
238
|
|
|
/** |
239
|
|
|
* Figure out if we can stack the next item vertically on top of this rather than side by side |
240
|
|
|
* Used when we've packed a tall item, and have just put a shorter one next to it |
241
|
|
|
* |
242
|
|
|
* @param ItemList $packedItems |
243
|
|
|
* @param OrientatedItem $prevItem |
|
|
|
|
244
|
|
|
* @param Item $nextItem |
|
|
|
|
245
|
|
|
* @param int $maxWidth |
246
|
|
|
* @param int $maxLength |
247
|
|
|
* @param int $maxDepth |
248
|
|
|
*/ |
249
|
33 |
|
protected function tryAndStackItemsIntoSpace( |
250
|
|
|
ItemList $packedItems, |
251
|
|
|
OrientatedItem $prevItem = null, |
252
|
|
|
Item $nextItem = null, |
253
|
|
|
$maxWidth, |
254
|
|
|
$maxLength, |
255
|
|
|
$maxDepth |
256
|
|
|
) { |
257
|
33 |
|
while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) { |
258
|
31 |
|
$stackedItem = $this->getOrientationForItem( |
259
|
31 |
|
$this->items->top(), |
260
|
|
|
$prevItem, |
261
|
|
|
$nextItem, |
262
|
|
|
$maxWidth, |
263
|
|
|
$maxLength, |
264
|
|
|
$maxDepth |
265
|
|
|
); |
266
|
31 |
|
if ($stackedItem) { |
267
|
3 |
|
$this->remainingWeight -= $this->items->top()->getWeight(); |
268
|
3 |
|
$maxDepth -= $stackedItem->getDepth(); |
269
|
3 |
|
$packedItems->insert($this->items->extract()); |
270
|
|
|
} else { |
271
|
31 |
|
break; |
272
|
|
|
} |
273
|
|
|
} |
274
|
|
|
} |
275
|
|
|
|
276
|
|
|
/** |
277
|
|
|
* @return bool |
278
|
|
|
*/ |
279
|
25 |
|
protected function isLayerStarted() |
280
|
|
|
{ |
281
|
25 |
|
return $this->layerWidth > 0 && $this->layerLength > 0 && $this->layerDepth > 0; |
282
|
|
|
} |
283
|
|
|
|
284
|
|
|
/** |
285
|
|
|
* As well as purely dimensional constraints, there are other constraints that need to be met |
286
|
|
|
* e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box) |
287
|
|
|
* |
288
|
|
|
* @param Item $itemToPack |
289
|
|
|
* @param ItemList $packedItems |
290
|
|
|
* |
291
|
|
|
* @return bool |
292
|
|
|
*/ |
293
|
33 |
|
protected function checkNonDimensionalConstraints(Item $itemToPack, ItemList $packedItems) |
294
|
|
|
{ |
295
|
33 |
|
$weightOK = $itemToPack->getWeight() <= $this->remainingWeight; |
296
|
|
|
|
297
|
33 |
|
if ($itemToPack instanceof ConstrainedItem) { |
298
|
1 |
|
return $weightOK && $itemToPack->canBePackedInBox(clone $packedItems, $this->box); |
299
|
|
|
} |
300
|
|
|
|
301
|
32 |
|
return $weightOK; |
302
|
|
|
} |
303
|
|
|
} |
304
|
|
|
|
This check looks for
@param
annotations where the type inferred by our type inference engine differs from the declared type.It makes a suggestion as to what type it considers more descriptive.
Most often this is a case of a parameter that can be null in addition to its declared types.