Completed
Push — master ( 22d589...9fb66e )
by Doug
01:13
created

getPossibleOrientationsInEmptyBox()   B

Complexity

Conditions 3
Paths 4

Size

Total Lines 30
Code Lines 25

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 24
CRAP Score 3

Importance

Changes 0
Metric Value
dl 0
loc 30
ccs 24
cts 24
cp 1
rs 8.8571
c 0
b 0
f 0
cc 3
eloc 25
nc 4
nop 2
crap 3
1
<?php
2
/**
3
 * Box packing (3D bin packing, knapsack problem)
4
 * @package BoxPacker
5
 * @author Doug Wright
6
 */
7
declare(strict_types=1);
8
namespace DVDoug\BoxPacker;
9
10
use Psr\Log\LoggerAwareInterface;
11
use Psr\Log\LoggerAwareTrait;
12
13
/**
14
 * Figure out orientations for an item and a given set of dimensions
15
 * @author Doug Wright
16
 * @package BoxPacker
17
 */
18
class OrientatedItemFactory implements LoggerAwareInterface
19
{
20
    use LoggerAwareTrait;
21
22
    /**
23
     * @var OrientatedItem[]
24
     */
25
    protected static $emptyBoxCache = [];
26
27
    /**
28
     * Get the best orientation for an item
29
     * @param Box $box
30
     * @param Item $item
31
     * @param ?PackedItem $prevItem
0 ignored issues
show
Documentation introduced by
The doc-type ?PackedItem could not be parsed: Unknown type name "?PackedItem" at position 0. (view supported doc-types)

This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.

Loading history...
32
     * @param bool $isLastItem
33
     * @param int $widthLeft
34
     * @param int $lengthLeft
35
     * @param int $depthLeft
36
     * @return ?OrientatedItem
0 ignored issues
show
Documentation introduced by
The doc-type ?OrientatedItem could not be parsed: Unknown type name "?OrientatedItem" at position 0. (view supported doc-types)

This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.

Loading history...
37
     */
38 36
    public function getBestOrientation(
0 ignored issues
show
Documentation introduced by
The return type could not be reliably inferred; please add a @return annotation.

Our type inference engine in quite powerful, but sometimes the code does not provide enough clues to go by. In these cases we request you to add a @return annotation as described here.

Loading history...
39
        Box $box,
40
        Item $item,
41
        ?PackedItem $prevItem,
42
        bool $isLastItem,
43
        int $widthLeft,
44
        int $lengthLeft,
45
        int $depthLeft
46
    ): ?OrientatedItem {
47
48 36
        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
49 36
        $usableOrientations = $this->getUsableOrientations($possibleOrientations, $box, $item, $isLastItem);
50
51 36
        if (empty($usableOrientations)) {
52 32
            return null;
53
        }
54
55 36
        usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft) {
56 34
            $orientationAWidthLeft = $widthLeft - $a->getWidth();
57 34
            $orientationALengthLeft = $lengthLeft - $a->getLength();
58 34
            $orientationBWidthLeft = $widthLeft - $b->getWidth();
59 34
            $orientationBLengthLeft = $lengthLeft - $b->getLength();
60
61 34
            $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
62 34
            $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
63
64 34
            if ($orientationAMinGap === 0) {
65 13
                return -1;
66 25
            } elseif ($orientationBMinGap === 0) {
67 2
                return 1;
68
            } else {
69 24
                return min($orientationAWidthLeft, $orientationALengthLeft) <=> min($orientationBWidthLeft, $orientationBLengthLeft);
70
            }
71 36
        });
72
73 36
        $bestFit = reset($usableOrientations);
74 36
        $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]);
75 36
        return $bestFit;
76
    }
77
78
    /**
79
     * Find all possible orientations for an item
80
     * @param Item $item
81
     * @param ?PackedItem $prevItem
0 ignored issues
show
Documentation introduced by
The doc-type ?PackedItem could not be parsed: Unknown type name "?PackedItem" at position 0. (view supported doc-types)

This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.

Loading history...
82
     * @param int $widthLeft
83
     * @param int $lengthLeft
84
     * @param int $depthLeft
85
     * @return OrientatedItem[]
86
     */
87 36
    public function getPossibleOrientations(
88
        Item $item,
89
        ?PackedItem $prevItem,
90
        int $widthLeft,
91
        int $lengthLeft,
92
        int $depthLeft
93
    ): array {
94
95 36
        $orientations = [];
96
97
        //Special case items that are the same as what we just packed - keep orientation
98
        /** @noinspection PhpNonStrictObjectEqualityInspection */
99 36
        if ($prevItem && $prevItem->getItem() == $item) {
100 13
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
101
        } else {
102
103
            //simple 2D rotation
104 36
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
105 36
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
106
107
            //add 3D rotation if we're allowed
108 36
            if (!$item->getKeepFlat()) {
109 15
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
110 15
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
111 15
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
112 15
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
113
            }
114
        }
115
116
        //remove any that simply don't fit
117 36
        return array_filter($orientations, function(OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
118 36
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
119 36
        });
120
    }
121
122
    /**
123
     * @param Item $item
124
     * @param Box  $box
125
     * @return OrientatedItem[]
126
     */
127 36
    public function getPossibleOrientationsInEmptyBox(Item $item, Box $box): array
128
    {
129 36
        $cacheKey = $item->getWidth() .
130 36
            '|' .
131 36
            $item->getLength() .
132 36
            '|' .
133 36
            $item->getDepth() .
134 36
            '|' .
135 36
            ($item->getKeepFlat() ? '2D' : '3D') .
136 36
            '|' .
137 36
            $box->getInnerWidth() .
138 36
            '|' .
139 36
            $box->getInnerLength() .
140 36
            '|' .
141 36
            $box->getInnerDepth();
142
143 36
        if (isset(static::$emptyBoxCache[$cacheKey])) {
144 31
            $orientations = static::$emptyBoxCache[$cacheKey];
145
        } else {
146 32
            $orientations = $this->getPossibleOrientations(
147 32
                $item,
148 32
                null,
149 32
                $box->getInnerWidth(),
150 32
                $box->getInnerLength(),
151 32
                $box->getInnerDepth()
152
            );
153 32
            static::$emptyBoxCache[$cacheKey] = $orientations;
154
        }
155 36
        return $orientations;
156
    }
157
158
    /**
159
     * @param OrientatedItem[] $possibleOrientations
160
     * @param Box              $box
161
     * @param Item             $item
162
     * @param bool             $isLastItem
163
     *
164
     * @return OrientatedItem[]
165
     */
166 36
    protected function getUsableOrientations(
167
        $possibleOrientations,
168
        Box $box,
169
        Item $item,
170
        bool $isLastItem
171
    ): array {
172
        /*
173
         * Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
174
         */
175 36
        $stableOrientations = [];
176 36
        $unstableOrientations = [];
177
178 36
        foreach ($possibleOrientations as $o => $orientation) {
179 36
            if ($orientation->isStable()) {
180 31
                $stableOrientations[] = $orientation;
181
            } else {
182 8
                $unstableOrientations[] = $orientation;
183
            }
184
        }
185
186 36
        $orientationsToUse = [];
187
188
        /*
189
         * We prefer to use stable orientations only, but allow unstable ones if either
190
         * the item is the last one left to pack OR
191
         * the item doesn't fit in the box any other way
192
         */
193 36
        if (count($stableOrientations) > 0) {
194 31
            $orientationsToUse = $stableOrientations;
195 35
        } else if (count($unstableOrientations) > 0) {
196 6
            $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item, $box);
197
198 6
            $stableOrientationsInEmptyBox = array_filter(
199 6
                $orientationsInEmptyBox,
200 6
                function(OrientatedItem $orientation) {
201 6
                    return $orientation->isStable();
202 6
                }
203
            );
204
205 6
            if ($isLastItem || count($stableOrientationsInEmptyBox) == 0) {
206 6
                $orientationsToUse = $unstableOrientations;
207
            }
208
        }
209
210 36
        return $orientationsToUse;
211
    }
212
}
213
214