Completed
Push — master ( 18f60e...12452e )
by Doug
02:50 queued 01:17
created

OrientatedItemFactory   A

Complexity

Total Complexity 29

Size/Duplication

Total Lines 233
Duplicated Lines 0 %

Test Coverage

Coverage 89.25%

Importance

Changes 0
Metric Value
wmc 29
eloc 93
dl 0
loc 233
ccs 83
cts 93
cp 0.8925
rs 10
c 0
b 0
f 0

7 Methods

Rating   Name   Duplication   Size   Complexity  
A __construct() 0 4 1
A getPossibleOrientations() 0 30 6
A getStableOrientationsInEmptyBox() 0 8 1
A isSameDimensions() 0 8 1
B getUsableOrientations() 0 31 7
A getPossibleOrientationsInEmptyBox() 0 30 3
B getBestOrientation() 0 47 10
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
 */
25
class OrientatedItemFactory implements LoggerAwareInterface
26
{
27
    use LoggerAwareTrait;
28
29
    /** @var Item */
30
    protected $item;
31
32
    /** @var Box */
33
    protected $box;
34
35
    /**
36
     * @var OrientatedItem[]
37
     */
38
    protected static $emptyBoxCache = [];
39
40 22
    public function __construct(Item $item, Box $box)
41
    {
42 22
        $this->item = $item;
43 22
        $this->box = $box;
44 22
    }
45
46
    /**
47
     * Get the best orientation for an item.
48
     *
49
     * @param OrientatedItem|null $prevItem
50
     * @param Item|null           $nextItem
51
     * @param bool                $isLastItem
52
     * @param int                 $widthLeft
53
     * @param int                 $lengthLeft
54
     * @param int                 $depthLeft
55
     *
56
     * @return OrientatedItem|null
57
     */
58 21
    public function getBestOrientation(
59
        ?OrientatedItem $prevItem,
60
        ?Item $nextItem,
61
        bool $isLastItem,
62
        int $widthLeft,
63
        int $lengthLeft,
64
        int $depthLeft
65
    ): ?OrientatedItem {
66 21
        $possibleOrientations = $this->getPossibleOrientations($this->item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
67 21
        $usableOrientations = $this->getUsableOrientations($possibleOrientations, $isLastItem);
68
69 21
        if (empty($usableOrientations)) {
70 20
            return null;
71
        }
72
73
        usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItem) {
74 21
            $orientationAWidthLeft = $widthLeft - $a->getWidth();
75 21
            $orientationALengthLeft = $lengthLeft - $a->getLength();
76 21
            $orientationBWidthLeft = $widthLeft - $b->getWidth();
77 21
            $orientationBLengthLeft = $lengthLeft - $b->getLength();
78
79 21
            $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
80 21
            $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
81
82 21
            if ($orientationAMinGap === 0) { // prefer A if it leaves no gap
83 7
                return -1;
84 17
            } elseif ($orientationBMinGap === 0) { // prefer B if it leaves no gap
85 1
                return 1;
86
            } else { // prefer leaving room for next item in current row
87 16
                if ($nextItem) {
88 15
                    $nextItemFitA = count($this->getPossibleOrientations($nextItem, $a, $orientationAWidthLeft, $orientationALengthLeft, $depthLeft));
89 15
                    $nextItemFitB = count($this->getPossibleOrientations($nextItem, $b, $orientationBWidthLeft, $orientationBLengthLeft, $depthLeft));
90 15
                    if ($nextItemFitA && !$nextItemFitB) {
91
                        return -1;
92 15
                    } elseif ($nextItemFitB && !$nextItemFitA) {
93 1
                        return 1;
94
                    }
95
                }
96
                // otherwise prefer leaving minimum possible gap, or the greatest footprint
97 15
                return $orientationAMinGap <=> $orientationBMinGap ?: $a->getSurfaceFootprint() <=> $b->getSurfaceFootprint();
98
            }
99 21
        });
100
101 21
        $bestFit = reset($usableOrientations);
102 21
        $this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]);
103
104 21
        return $bestFit;
105
    }
106
107
    /**
108
     * Find all possible orientations for an item.
109
     *
110
     * @param Item                $item
111
     * @param OrientatedItem|null $prevItem
112
     * @param int                 $widthLeft
113
     * @param int                 $lengthLeft
114
     * @param int                 $depthLeft
115
     *
116
     * @return OrientatedItem[]
117
     */
118 21
    public function getPossibleOrientations(
119
        Item $item,
120
        ?OrientatedItem $prevItem,
121
        int $widthLeft,
122
        int $lengthLeft,
123
        int $depthLeft
124
    ): array {
125 21
        $orientations = [];
126
127
        //Special case items that are the same as what we just packed - keep orientation
128 21
        if ($prevItem && $this->isSameDimensions($prevItem->getItem(), $item)) {
129 16
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
130
        } else {
131
132
            //simple 2D rotation
133 21
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
134 21
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
135
136
            //add 3D rotation if we're allowed
137 21
            if (!$item->getKeepFlat()) {
138 13
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
139 13
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
140 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
141 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
142
            }
143
        }
144
145
        //remove any that simply don't fit
146
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
147 21
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
148 21
        });
149
    }
150
151
    /**
152
     * @return OrientatedItem[]
153
     */
154 22
    public function getPossibleOrientationsInEmptyBox(): array
155
    {
156 22
        $cacheKey = $this->item->getWidth().
157 22
            '|'.
158 22
            $this->item->getLength().
159 22
            '|'.
160 22
            $this->item->getDepth().
161 22
            '|'.
162 22
            ($this->item->getKeepFlat() ? '2D' : '3D').
163 22
            '|'.
164 22
            $this->box->getInnerWidth().
165 22
            '|'.
166 22
            $this->box->getInnerLength().
167 22
            '|'.
168 22
            $this->box->getInnerDepth();
169
170 22
        if (isset(static::$emptyBoxCache[$cacheKey])) {
171 22
            $orientations = static::$emptyBoxCache[$cacheKey];
172
        } else {
173 20
            $orientations = $this->getPossibleOrientations(
174 20
                $this->item,
175 20
                null,
176 20
                $this->box->getInnerWidth(),
177 20
                $this->box->getInnerLength(),
178 20
                $this->box->getInnerDepth()
179
            );
180 20
            static::$emptyBoxCache[$cacheKey] = $orientations;
181
        }
182
183 22
        return $orientations;
0 ignored issues
show
Bug Best Practice introduced by Doug Wright
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...
184
    }
185
186
    /**
187
     * @param OrientatedItem[] $possibleOrientations
188
     * @param bool             $isLastItem
189
     *
190
     * @return OrientatedItem[]
191
     */
192 21
    protected function getUsableOrientations(
193
        $possibleOrientations,
194
        bool $isLastItem
195
    ): array {
196 21
        $orientationsToUse = $stableOrientations = $unstableOrientations = [];
197
198
        // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
199 21
        foreach ($possibleOrientations as $orientation) {
200 21
            if ($orientation->isStable()) {
201 21
                $stableOrientations[] = $orientation;
202
            } else {
203 21
                $unstableOrientations[] = $orientation;
204
            }
205
        }
206
207
        /*
208
         * We prefer to use stable orientations only, but allow unstable ones if either
209
         * the item is the last one left to pack OR
210
         * the item doesn't fit in the box any other way
211
         */
212 21
        if (count($stableOrientations) > 0) {
213 21
            $orientationsToUse = $stableOrientations;
214 20
        } elseif (count($unstableOrientations) > 0) {
215
            $stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox();
216
217
            if ($isLastItem || count($stableOrientationsInEmptyBox) == 0) {
218
                $orientationsToUse = $unstableOrientations;
219
            }
220
        }
221
222 21
        return $orientationsToUse;
223
    }
224
225
    /**
226
     * Return the orientations for this item if it were to be placed into the box with nothing else.
227
     *
228
     * @return array
229
     */
230
    protected function getStableOrientationsInEmptyBox(): array
231
    {
232
        $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox();
233
234
        return array_filter(
235
            $orientationsInEmptyBox,
236
            function (OrientatedItem $orientation) {
237
                return $orientation->isStable();
238
            }
239
        );
240
    }
241
242
    /**
243
     * Compare two items to see if they have same dimensions.
244
     *
245
     * @param Item $itemA
246
     * @param Item $itemB
247
     *
248
     * @return bool
249
     */
250 19
    protected function isSameDimensions(Item $itemA, Item $itemB): bool
251
    {
252 19
        $itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
253 19
        $itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
254 19
        sort($itemADimensions);
255 19
        sort($itemBDimensions);
256
257 19
        return $itemADimensions === $itemBDimensions;
258
    }
259
}
260