Passed
Push — master ( f6d69b...61d457 )
by Doug
03:39
created

OrientatedItemFactory::getBestOrientation()   C

Complexity

Conditions 12
Paths 2

Size

Total Lines 61
Code Lines 32

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 32
CRAP Score 12.004

Importance

Changes 0
Metric Value
cc 12
eloc 32
nc 2
nop 8
dl 0
loc 61
ccs 32
cts 33
cp 0.9697
crap 12.004
rs 6.9666
c 0
b 0
f 0

How to fix   Long Method    Complexity    Many Parameters   

Long Method

Small methods make your code easier to understand, in particular if combined with a good name. Besides, if your method is small, finding a good name is usually much easier.

For example, if you find yourself adding comments to a method's body, this is usually a good sign to extract the commented part to a new method, and use the comment as a starting point when coming up with a good name for this new method.

Commonly applied refactorings include:

Many Parameters

Methods with many parameters are not only hard to understand, but their parameters also often become inconsistent when you need more, or different data.

There are several approaches to avoid long parameter lists:

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 Psr\Log\LoggerAwareInterface;
12
use Psr\Log\LoggerAwareTrait;
13
use function array_filter;
14
use function count;
15
use function min;
16
use function reset;
17
use function sort;
18
use function usort;
19
20
/**
21
 * Figure out orientations for an item and a given set of dimensions.
22
 *
23
 * @author Doug Wright
24
 * @internal
25
 */
26
class OrientatedItemFactory implements LoggerAwareInterface
27
{
28
    use LoggerAwareTrait;
29
30
    /** @var Box */
31
    protected $box;
32
33
    /**
34
     * @var OrientatedItem[]
35
     */
36
    protected static $emptyBoxCache = [];
37
38 22
    public function __construct(Box $box)
39
    {
40 22
        $this->box = $box;
41 22
    }
42
43
    /**
44
     * Get the best orientation for an item.
45
     *
46
     * @param Item                $item
47
     * @param OrientatedItem|null $prevItem
48
     * @param ItemList            $nextItems
49
     * @param bool                $isLastItem
50
     * @param int                 $widthLeft
51
     * @param int                 $lengthLeft
52
     * @param int                 $depthLeft
53
     * @param int                 $rowLength
54
     *
55
     * @return OrientatedItem|null
56
     */
57 21
    public function getBestOrientation(
58
        Item $item,
59
        ?OrientatedItem $prevItem,
60
        ItemList $nextItems,
61
        bool $isLastItem,
62
        int $widthLeft,
63
        int $lengthLeft,
64
        int $depthLeft,
65
        int $rowLength
66
    ): ?OrientatedItem {
67 21
        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
68 21
        $usableOrientations = $this->getUsableOrientations($item, $possibleOrientations, $isLastItem);
69
70 21
        if (empty($usableOrientations)) {
71 20
            return null;
72
        }
73
74
        usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength) {
75 9
            $orientationAWidthLeft = $widthLeft - $a->getWidth();
76 9
            $orientationALengthLeft = $lengthLeft - $a->getLength();
77 9
            $orientationADepthLeft = $depthLeft - $a->getDepth();
78 9
            $orientationBWidthLeft = $widthLeft - $b->getWidth();
79 9
            $orientationBLengthLeft = $lengthLeft - $b->getLength();
80 9
            $orientationBDepthLeft = $depthLeft - $b->getDepth();
81
82 9
            $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
83 9
            $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
84
85 9
            if ($orientationAMinGap === 0) { // prefer A if it leaves no gap
86 4
                return -1;
87
            }
88 6
            if ($orientationBMinGap === 0) { // prefer B if it leaves no gap
89 2
                return 1;
90
            }
91
92
            // prefer leaving room for next item in current row
93 5
            if ($nextItems->count()) {
94 4
                $nextItemFitA = count($this->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft));
95 4
                $nextItemFitB = count($this->getPossibleOrientations($nextItems->top(), $b, $orientationBWidthLeft, $lengthLeft, $depthLeft));
96 4
                if ($nextItemFitA && !$nextItemFitB) {
97
                    return -1;
98
                }
99 4
                if ($nextItemFitB && !$nextItemFitA) {
100 2
                    return 1;
101
                }
102
103
                // if not an easy either/or, do a partial lookahead
104 2
                $additionalPackedA = $this->calculateAdditionalItemsPackedWithThisOrientation($a, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
105 2
                $additionalPackedB = $this->calculateAdditionalItemsPackedWithThisOrientation($b, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
106 2
                if ($additionalPackedA !== $additionalPackedB) {
107 1
                    return $additionalPackedB <=> $additionalPackedA;
108
                }
109
            }
110
            // otherwise prefer leaving minimum possible gap, or the greatest footprint
111 2
            return $orientationADepthLeft <=> $orientationBDepthLeft ?: $orientationAMinGap <=> $orientationBMinGap ?: $a->getSurfaceFootprint() <=> $b->getSurfaceFootprint();
112 21
        });
113
114 21
        $bestFit = reset($usableOrientations);
115 21
        $this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]);
116
117 21
        return $bestFit;
118
    }
119
120
    /**
121
     * Find all possible orientations for an item.
122
     *
123
     * @param Item                $item
124
     * @param OrientatedItem|null $prevItem
125
     * @param int                 $widthLeft
126
     * @param int                 $lengthLeft
127
     * @param int                 $depthLeft
128
     *
129
     * @return OrientatedItem[]
130
     */
131 21
    public function getPossibleOrientations(
132
        Item $item,
133
        ?OrientatedItem $prevItem,
134
        int $widthLeft,
135
        int $lengthLeft,
136
        int $depthLeft
137
    ): array {
138 21
        $orientations = [];
139
140
        //Special case items that are the same as what we just packed - keep orientation
141 21
        if ($prevItem && $this->isSameDimensions($prevItem->getItem(), $item)) {
142 16
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
143
        } else {
144
            //simple 2D rotation
145 21
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
146 21
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
147
148
            //add 3D rotation if we're allowed
149 21
            if (!$item->getKeepFlat()) {
150 13
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
151 13
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
152 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
153 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
154
            }
155
        }
156
157 21
        $orientations = array_unique($orientations);
158
159
        //remove any that simply don't fit
160
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
161 21
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
162 21
        });
163
    }
164
165
    /**
166
     * @param  Item             $item
167
     * @return OrientatedItem[]
168
     */
169 22
    public function getPossibleOrientationsInEmptyBox(Item $item): array
170
    {
171 22
        $cacheKey = $item->getWidth() .
172 22
            '|' .
173 22
            $item->getLength() .
174 22
            '|' .
175 22
            $item->getDepth() .
176 22
            '|' .
177 22
            ($item->getKeepFlat() ? '2D' : '3D') .
178 22
            '|' .
179 22
            $this->box->getInnerWidth() .
180 22
            '|' .
181 22
            $this->box->getInnerLength() .
182 22
            '|' .
183 22
            $this->box->getInnerDepth();
184
185 22
        if (isset(static::$emptyBoxCache[$cacheKey])) {
186 22
            $orientations = static::$emptyBoxCache[$cacheKey];
187
        } else {
188 20
            $orientations = $this->getPossibleOrientations(
189 20
                $item,
190 20
                null,
191 20
                $this->box->getInnerWidth(),
192 20
                $this->box->getInnerLength(),
193 20
                $this->box->getInnerDepth()
194
            );
195 20
            static::$emptyBoxCache[$cacheKey] = $orientations;
196
        }
197
198 22
        return $orientations;
1 ignored issue
show
Bug Best Practice introduced by
The expression return $orientations could return the type DVDoug\BoxPacker\OrientatedItem which is incompatible with the type-hinted return array. Consider adding an additional type-check to rule them out.
Loading history...
199
    }
200
201
    /**
202
     * @param Item             $item
203
     * @param OrientatedItem[] $possibleOrientations
204
     * @param bool             $isLastItem
205
     *
206
     * @return OrientatedItem[]
207
     */
208 21
    protected function getUsableOrientations(
209
        Item $item,
210
        $possibleOrientations,
211
        bool $isLastItem
212
    ): array {
213 21
        $orientationsToUse = $stableOrientations = $unstableOrientations = [];
214
215
        // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
216 21
        foreach ($possibleOrientations as $orientation) {
217 21
            if ($orientation->isStable()) {
218 21
                $stableOrientations[] = $orientation;
219
            } else {
220 21
                $unstableOrientations[] = $orientation;
221
            }
222
        }
223
224
        /*
225
         * We prefer to use stable orientations only, but allow unstable ones if either
226
         * the item is the last one left to pack OR
227
         * the item doesn't fit in the box any other way
228
         */
229 21
        if (count($stableOrientations) > 0) {
230 21
            $orientationsToUse = $stableOrientations;
231 20
        } elseif (count($unstableOrientations) > 0) {
232
            $stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);
233
234
            if ($isLastItem || count($stableOrientationsInEmptyBox) === 0) {
235
                $orientationsToUse = $unstableOrientations;
236
            }
237
        }
238
239 21
        return $orientationsToUse;
240
    }
241
242
    /**
243
     * Return the orientations for this item if it were to be placed into the box with nothing else.
244
     *
245
     * @param  Item  $item
246
     * @return array
247
     */
248
    protected function getStableOrientationsInEmptyBox(Item $item): array
249
    {
250
        $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);
251
252
        return array_filter(
253
            $orientationsInEmptyBox,
254
            function (OrientatedItem $orientation) {
255
                return $orientation->isStable();
256
            }
257
        );
258
    }
259
260
    /**
261
     * Compare two items to see if they have same dimensions.
262
     *
263
     * @param Item $itemA
264
     * @param Item $itemB
265
     *
266
     * @return bool
267
     */
268 19
    protected function isSameDimensions(Item $itemA, Item $itemB): bool
269
    {
270 19
        $itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
271 19
        $itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
272 19
        sort($itemADimensions);
273 19
        sort($itemBDimensions);
274
275 19
        return $itemADimensions === $itemBDimensions;
276
    }
277
278
    /**
279
     * Approximation of a forward-looking packing.
280
     *
281
     * Not an actual packing, that has additional logic regarding constraints and stackability, this focuses
282
     * purely on fit.
283
     *
284
     * @param  OrientatedItem $prevItem
285
     * @param  ItemList       $nextItems
286
     * @param  int            $originalWidthLeft
287
     * @param  int            $originalLengthLeft
288
     * @param  int            $depthLeft
289
     * @param  int            $currentRowLengthBeforePacking
290
     * @return int
291
     */
292 2
    protected function calculateAdditionalItemsPackedWithThisOrientation(
293
        OrientatedItem $prevItem,
294
        ItemList $nextItems,
295
        int $originalWidthLeft,
296
        int $originalLengthLeft,
297
        int $depthLeft,
298
        int $currentRowLengthBeforePacking
299
    ): int {
300 2
        $packedCount = 0;
301
302 2
        $currentRowLength = max($prevItem->getLength(), $currentRowLengthBeforePacking);
303
304 2
        $itemsToPack = $nextItems->topN(8); // cap lookahead as this gets recursive and slow
305
306 2
        $tempBox = new WorkingVolume($originalWidthLeft - $prevItem->getWidth(), $currentRowLength, $depthLeft, PHP_INT_MAX);
307 2
        $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
308 2
        $remainingRowPacked = $tempPacker->pack();
309
        /** @var PackedItem $packedItem */
310 2
        foreach ($remainingRowPacked->getItems() as $packedItem) {
311 2
            $itemsToPack->remove($packedItem->getItem());
312
        }
313
314 2
        $tempBox = new WorkingVolume($originalWidthLeft, $originalLengthLeft - $currentRowLength, $depthLeft, PHP_INT_MAX);
315 2
        $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
316 2
        $nextRowsPacked = $tempPacker->pack();
317
        /** @var PackedItem $packedItem */
318 2
        foreach ($nextRowsPacked->getItems() as $packedItem) {
319 1
            $itemsToPack->remove($packedItem->getItem());
320
        }
321
322 2
        $this->logger->debug('Lookahead with orientation', ['packedCount' => $packedCount, 'orientatedItem' => $prevItem]);
323
324 2
        return $nextItems->count() - $itemsToPack->count();
325
    }
326
}
327