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