These results are based on our legacy PHP analysis, consider migrating to our new PHP analysis engine instead. Learn more
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 | * Constructor |
||
60 | */ |
||
61 | 26 | public function __construct(Box $box, ItemList $items) |
|
62 | { |
||
63 | 26 | $this->logger = new NullLogger(); |
|
64 | |||
65 | 26 | $this->box = $box; |
|
66 | 26 | $this->items = $items; |
|
67 | |||
68 | 26 | $this->depthLeft = $this->box->getInnerDepth(); |
|
69 | 26 | $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight(); |
|
70 | 26 | $this->widthLeft = $this->box->getInnerWidth(); |
|
71 | 26 | $this->lengthLeft = $this->box->getInnerLength(); |
|
72 | 26 | } |
|
73 | |||
74 | /** |
||
75 | * Pack as many items as possible into specific given box |
||
76 | * @return PackedBox packed box |
||
77 | */ |
||
78 | 26 | public function pack() |
|
79 | { |
||
80 | 26 | $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}"); |
|
81 | |||
82 | 26 | $packedItems = new ItemList; |
|
83 | |||
84 | 26 | $layerWidth = $layerLength = $layerDepth = 0; |
|
85 | |||
86 | 26 | $prevItem = null; |
|
87 | |||
88 | 26 | while (!$this->items->isEmpty()) { |
|
89 | |||
90 | 26 | $itemToPack = $this->items->extract(); |
|
91 | |||
92 | //skip items that are simply too heavy |
||
93 | 26 | if ($itemToPack->getWeight() > $this->remainingWeight) { |
|
94 | 4 | continue; |
|
95 | } |
||
96 | |||
97 | 26 | $this->logger->debug("evaluating item {$itemToPack->getDescription()}"); |
|
98 | 26 | $this->logger->debug("remaining width: {$this->widthLeft}, length: {$this->lengthLeft}, depth: {$this->depthLeft}"); |
|
99 | 26 | $this->logger->debug("layerWidth: {$layerWidth}, layerLength: {$layerLength}, layerDepth: {$layerDepth}"); |
|
100 | |||
101 | 26 | $nextItem = !$this->items->isEmpty() ? $this->items->top() : null; |
|
102 | 26 | $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft); |
|
103 | |||
104 | 26 | if ($orientatedItem) { |
|
105 | |||
106 | 26 | $packedItems->insert($orientatedItem->getItem()); |
|
107 | 26 | $this->remainingWeight -= $itemToPack->getWeight(); |
|
108 | |||
109 | 26 | $this->lengthLeft -= $orientatedItem->getLength(); |
|
110 | 26 | $layerLength += $orientatedItem->getLength(); |
|
111 | 26 | $layerWidth = max($orientatedItem->getWidth(), $layerWidth); |
|
112 | |||
113 | 26 | $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep |
|
114 | |||
115 | //allow items to be stacked in place within the same footprint up to current layerdepth |
||
116 | 26 | $stackableDepth = $layerDepth - $orientatedItem->getDepth(); |
|
117 | 26 | $this->tryAndStackItemsIntoSpace($packedItems, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth); |
|
118 | |||
119 | 26 | $prevItem = $orientatedItem; |
|
120 | 26 | } else { |
|
121 | |||
122 | 23 | $prevItem = null; |
|
123 | |||
124 | 23 | if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) { |
|
125 | 22 | $this->logger->debug("No more fit in lengthwise, resetting for new row"); |
|
126 | 22 | $this->lengthLeft += $layerLength; |
|
127 | 22 | $this->widthLeft -= $layerWidth; |
|
128 | 22 | $layerWidth = $layerLength = 0; |
|
129 | 22 | $this->items->insert($itemToPack); |
|
130 | 22 | continue; |
|
131 | 18 | } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) { |
|
132 | 7 | $this->logger->debug("doesn't fit on layer even when empty"); |
|
133 | 7 | continue; |
|
134 | } |
||
135 | |||
136 | 17 | $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth(); |
|
137 | 17 | $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength(); |
|
138 | 17 | $this->depthLeft -= $layerDepth; |
|
139 | |||
140 | 17 | $layerWidth = $layerLength = $layerDepth = 0; |
|
141 | 17 | $this->logger->debug("doesn't fit, so starting next vertical layer"); |
|
142 | 17 | $this->items->insert($itemToPack); |
|
143 | } |
||
144 | 26 | } |
|
145 | 26 | $this->logger->debug("done with this box"); |
|
146 | 26 | return new PackedBox($this->box, $packedItems, $this->widthLeft, $this->lengthLeft, $this->depthLeft, $this->remainingWeight); |
|
147 | } |
||
148 | |||
149 | /** |
||
150 | * Get the best orientation for an item |
||
151 | * @param Item $item |
||
152 | * @param OrientatedItem|null $prevItem |
||
153 | * @param Item|null $nextItem |
||
154 | * @param int $widthLeft |
||
155 | * @param int $lengthLeft |
||
156 | * @param int $depthLeft |
||
157 | * @return OrientatedItem|false |
||
158 | */ |
||
159 | 26 | protected function findBestOrientation(Item $item, OrientatedItem $prevItem = null, Item $nextItem = null, $widthLeft, $lengthLeft, $depthLeft) { |
|
160 | |||
161 | 26 | $orientations = $this->findPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft); |
|
162 | |||
163 | 26 | if (empty($orientations)) { |
|
164 | 24 | return false; |
|
165 | } |
||
166 | |||
167 | // special casing based on next item |
||
168 | 26 | if (isset($orientations[0]) && $nextItem == $item && $lengthLeft >= 2 * $item->getLength()) { |
|
169 | 5 | $this->logger->debug("not rotating based on next item"); |
|
170 | 5 | return $orientations[0]; // XXX this is tied to the ordering from ->findPossibleOrientations() |
|
171 | } |
||
172 | |||
173 | 26 | $orientationFits = []; |
|
174 | |||
175 | /** @var OrientatedItem $orientation */ |
||
176 | 26 | foreach ($orientations as $o => $orientation) { |
|
177 | 26 | $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft - $orientation->getLength()); |
|
178 | 26 | $orientationFits[$o] = $orientationFit; |
|
179 | 26 | } |
|
180 | |||
181 | 26 | if (!empty($orientationFits)) { |
|
182 | 26 | asort($orientationFits); |
|
183 | 26 | reset($orientationFits); |
|
184 | 26 | $bestFit = key($orientationFits); |
|
185 | 26 | $this->logger->debug("Using orientation #{$bestFit}"); |
|
186 | 26 | return $orientations[$bestFit]; |
|
187 | } else { |
||
188 | return false; |
||
189 | } |
||
190 | } |
||
191 | |||
192 | /** |
||
193 | * Find all possible orientations for an item |
||
194 | * @param Item $item |
||
195 | * @param OrientatedItem|null $prevItem |
||
196 | * @param int $widthLeft |
||
197 | * @param int $lengthLeft |
||
198 | * @param int $depthLeft |
||
199 | * @return OrientatedItem[] |
||
200 | */ |
||
201 | 26 | protected function findPossibleOrientations(Item $item, OrientatedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) { |
|
202 | |||
203 | 26 | $orientations = []; |
|
204 | |||
205 | //Special case items that are the same as what we just packed - keep orientation |
||
206 | 26 | if ($prevItem && $prevItem->getItem() == $item) { |
|
207 | 9 | $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()); |
|
208 | 9 | } else { |
|
209 | |||
210 | //simple 2D rotation |
||
211 | 26 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth()); |
|
212 | 26 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth()); |
|
213 | |||
214 | //add 3D rotation if we're allowed |
||
215 | 26 | if (!$item->getKeepFlat()) { |
|
216 | 10 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength()); |
|
217 | 10 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth()); |
|
218 | 10 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength()); |
|
219 | 10 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth()); |
|
220 | 10 | } |
|
221 | } |
||
222 | |||
223 | //remove any that simply don't fit |
||
224 | 26 | return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) { |
|
225 | 26 | return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft; |
|
226 | 26 | }); |
|
227 | |||
228 | } |
||
229 | |||
230 | /** |
||
231 | * Figure out if we can stack the next item vertically on top of this rather than side by side |
||
232 | * Used when we've packed a tall item, and have just put a shorter one next to it |
||
233 | * @param ItemList $packedItems |
||
234 | * @param int $maxWidth |
||
235 | * @param int $maxLength |
||
236 | * @param int $maxDepth |
||
237 | * @return bool |
||
0 ignored issues
–
show
|
|||
238 | */ |
||
239 | 26 | protected function tryAndStackItemsIntoSpace(ItemList $packedItems, $maxWidth, $maxLength, $maxDepth) |
|
240 | { |
||
241 | 26 | while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) { |
|
242 | 24 | $stackedItem = $this->findBestOrientation($this->items->top(), null, null, $maxWidth, $maxLength, $maxDepth); |
|
243 | 24 | if ($stackedItem) { |
|
244 | 1 | $this->remainingWeight -= $this->items->top()->getWeight(); |
|
245 | 1 | $maxDepth -= $stackedItem->getDepth(); |
|
246 | 1 | $packedItems->insert($this->items->extract()); |
|
247 | 1 | } else { |
|
248 | 24 | break; |
|
249 | } |
||
250 | 1 | } |
|
251 | 26 | } |
|
252 | |||
253 | /** |
||
254 | * @param int $layerWidth |
||
255 | * @param int $layerLength |
||
256 | * @param int $layerDepth |
||
257 | * @return bool |
||
258 | */ |
||
259 | 23 | protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) { |
|
260 | 23 | return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0; |
|
261 | } |
||
262 | } |
||
263 |
This check compares the return type specified in the
@return
annotation of a function or method doc comment with the types returned by the function and raises an issue if they mismatch.