OrientatedItemFactory::getStableOrientationsInEmptyBox() - Code Metrics - Inspection of "Backport 3.x" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Test Failed

Push — 2.x-dev ( 5e90af...eccc16 )

by Doug

created 2020-04-23 22:32 UTC

getStableOrientationsInEmptyBox() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	1
Paths	1

Size

Total Lines	8
Code Lines	5

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	5
CRAP Score	1

Importance

Changes

Metric	Value
cc	1
eloc	5
c	0
b	0
f	0
nc	1
nop	1
dl	0
loc	8
ccs	5
cts	5
cp	1
crap	1
rs	10

<?php
/**
 * Box packing (3D bin packing, knapsack problem).
 *
 * @author Doug Wright
 */
namespace DVDoug\BoxPacker;

use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\NullLogger;

/**
 * Figure out orientations for an item and a given set of dimensions.
 *
 * @author Doug Wright
 * @internal
 */
class OrientatedItemFactory implements LoggerAwareInterface
{
    use LoggerAwareTrait;

    /** @var Box */
    protected $box;

    /**
     * Whether the packer is in single-pass mode.
     *
     * @var bool
     */
    protected $singlePassMode = false;

    /**
     * @var OrientatedItem[]
     */
    protected static $emptyBoxCache = [];

    public function __construct(Box $box)
    {
        $this->box = $box;
        $this->logger = new NullLogger();
    }

    public function setSinglePassMode($singlePassMode)
    {
        $this->singlePassMode = $singlePassMode;
    }

    /**
     * Get the best orientation for an item.
     *
     * @param Item                $item
     * @param OrientatedItem|null $prevItem
     * @param ItemList            $nextItems
     * @param int                 $widthLeft
     * @param int                 $lengthLeft
     * @param int                 $depthLeft
     * @param int                 $rowLength
     * @param int                 $x
     * @param int                 $y
     * @param int                 $z
     * @param PackedItemList      $prevPackedItemList
     *
     * @return OrientatedItem|null
     */
    public function getBestOrientation(
        Item $item,
        OrientatedItem $prevItem = null,
        ItemList $nextItems,
        $widthLeft,
        $lengthLeft,
        $depthLeft,
        $rowLength,
        $x,
        $y,
        $z,
        PackedItemList $prevPackedItemList
    ) {
        $this->logger->debug(
            "evaluating item {$item->getDescription()} for fit",
            [
                'item' => $item,
                'space' => [
                    'widthLeft' => $widthLeft,
                    'lengthLeft' => $lengthLeft,
                    'depthLeft' => $depthLeft,
                ],
            ]
        );

        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
        $usableOrientations = $this->getUsableOrientations($item, $possibleOrientations);

        if (empty($usableOrientations)) {
            return null;
        }

        $sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList);
        $sorter->setLogger($this->logger);
        usort($usableOrientations, $sorter);

        $this->logger->debug('Selected best fit orientation', ['orientation' => $usableOrientations[0]]);

        return $usableOrientations[0];
    }

    /**
     * Find all possible orientations for an item.
     *
     * @param Item                $item
     * @param OrientatedItem|null $prevItem
     * @param int                 $widthLeft
     * @param int                 $lengthLeft
     * @param int                 $depthLeft
     * @param int                 $x
     * @param int                 $y
     * @param int                 $z
     * @param PackedItemList      $prevPackedItemList
     *
     * @return OrientatedItem[]
     */
    public function getPossibleOrientations(
        Item $item,
        OrientatedItem $prevItem = null,
        $widthLeft,
        $lengthLeft,
        $depthLeft,
        $x,
        $y,
        $z,
        PackedItemList $prevPackedItemList
    ) {
        $permutations = $this->generatePermutations($item, $prevItem);

        //remove any that simply don't fit
        $orientations = [];
        foreach ($permutations as $dimensions) {
            if ($dimensions[0] <= $widthLeft && $dimensions[1] <= $lengthLeft && $dimensions[2] <= $depthLeft) {
                $orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]);
            }
        }

        if ($item instanceof ConstrainedPlacementItem) {
            $orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList) {
                return $i->getItem()->canBePacked($this->box, clone $prevPackedItemList, $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());
            });
        }

        return $orientations;
    }

    /**
     * @param  Item             $item
     * @return OrientatedItem[]
     */
    public function getPossibleOrientationsInEmptyBox(Item $item)
    {
        $cacheKey = $item->getWidth() .
            '|' .
            $item->getLength() .
            '|' .
            $item->getDepth() .
            '|' .
            ($item->getKeepFlat() ? '2D' : '3D') .
            '|' .
            $this->box->getInnerWidth() .
            '|' .
            $this->box->getInnerLength() .
            '|' .
            $this->box->getInnerDepth();

        if (isset(static::$emptyBoxCache[$cacheKey])) {
            $orientations = static::$emptyBoxCache[$cacheKey];
        } else {
            $orientations = $this->getPossibleOrientations(
                $item,
                null,
                $this->box->getInnerWidth(),
                $this->box->getInnerLength(),
                $this->box->getInnerDepth(),
                0,
                0,
                0,
                new PackedItemList()
            );
            static::$emptyBoxCache[$cacheKey] = $orientations;
        }

        return $orientations;

    }

    /**
     * @param Item             $item
     * @param OrientatedItem[] $possibleOrientations
     * @param bool             $isLastItem
     *
     * @return OrientatedItem[]
     */
    protected function getUsableOrientations(
        Item $item,
        array $possibleOrientations
    ) {
        $orientationsToUse = $stableOrientations = $unstableOrientations = [];

        // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
        foreach ($possibleOrientations as $orientation) {
            if ($orientation->isStable() || $this->box->getInnerDepth() === $orientation->getDepth()) {
                $stableOrientations[] = $orientation;
            } else {
                $unstableOrientations[] = $orientation;
            }
        }

        /*
         * We prefer to use stable orientations only, but allow unstable ones if
         * the item doesn't fit in the box any other way
         */
        if (count($stableOrientations) > 0) {
            $orientationsToUse = $stableOrientations;
        } elseif (count($unstableOrientations) > 0) {
            $stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);

            if (count($stableOrientationsInEmptyBox) === 0) {
                $orientationsToUse = $unstableOrientations;
            }
        }

        return $orientationsToUse;
    }

    /**
     * Return the orientations for this item if it were to be placed into the box with nothing else.
     *
     * @param  Item  $item
     * @return array
     */
    protected function getStableOrientationsInEmptyBox(Item $item)
    {
        $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);

        return array_filter(
            $orientationsInEmptyBox,
            function (OrientatedItem $orientation) {
                return $orientation->isStable();
            }
        );
    }

    private function generatePermutations(Item $item, OrientatedItem $prevItem = null)
    {
        $permutations = [];

        //Special case items that are the same as what we just packed - keep orientation
        if ($prevItem && $prevItem->isSameDimensions($item)) {
            $permutations[] = [$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()];
        } else {
            //simple 2D rotation
            $permutations[] = [$item->getWidth(), $item->getLength(), $item->getDepth()];
            $permutations[] = [$item->getLength(), $item->getWidth(), $item->getDepth()];

            //add 3D rotation if we're allowed
            if (!$item->getKeepFlat()) {
                $permutations[] = [$item->getWidth(), $item->getDepth(), $item->getLength()];
                $permutations[] = [$item->getLength(), $item->getDepth(), $item->getWidth()];
                $permutations[] = [$item->getDepth(), $item->getWidth(), $item->getLength()];
                $permutations[] = [$item->getDepth(), $item->getLength(), $item->getWidth()];
            }
        }

        return $permutations;
    }
}


1		<?php
2		/**
3		* Box packing (3D bin packing, knapsack problem).
4		*
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		* Figure out orientations for an item and a given set of dimensions.
15		*
16		* @author Doug Wright
17		* @internal
18		*/
19		class OrientatedItemFactory implements LoggerAwareInterface
20		{
21		use LoggerAwareTrait;
22
23		/** @var Box */
24		protected $box;
25
26		/**
27		* Whether the packer is in single-pass mode.
28		*
29		* @var bool
30		*/
31		protected $singlePassMode = false;
32
33		/**
34		* @var OrientatedItem[]
35		*/
36		protected static $emptyBoxCache = [];
37
38	29	public function __construct(Box $box)
39		{
40	29	$this->box = $box;
41	29	$this->logger = new NullLogger();
42	29	}
43
44	23	public function setSinglePassMode($singlePassMode)
45		{
46	23	$this->singlePassMode = $singlePassMode;
47	23	}
48
49		/**
50		* Get the best orientation for an item.
51		*
52		* @param Item $item
53		* @param OrientatedItem\|null $prevItem
54		* @param ItemList $nextItems
55		* @param int $widthLeft
56		* @param int $lengthLeft
57		* @param int $depthLeft
58		* @param int $rowLength
59		* @param int $x
60		* @param int $y
61		* @param int $z
62		* @param PackedItemList $prevPackedItemList
63		*
64		* @return OrientatedItem\|null
65		*/
66	28	public function getBestOrientation(
67		Item $item,
68		OrientatedItem $prevItem = null,
69		ItemList $nextItems,
70		$widthLeft,
71		$lengthLeft,
72		$depthLeft,
73		$rowLength,
74		$x,
75		$y,
76		$z,
77		PackedItemList $prevPackedItemList
78		) {
79	28	$this->logger->debug(
80	28	"evaluating item {$item->getDescription()} for fit",
81		[
82	28	'item' => $item,
83		'space' => [
84	28	'widthLeft' => $widthLeft,
85	28	'lengthLeft' => $lengthLeft,
86	28	'depthLeft' => $depthLeft,
87		],
88		]
89		);
90
91	28	$possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
92	28	$usableOrientations = $this->getUsableOrientations($item, $possibleOrientations);
93
94	28	if (empty($usableOrientations)) {
95	26	return null;
96		}
97
98	28	$sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList);
99	28	$sorter->setLogger($this->logger);
100	28	usort($usableOrientations, $sorter);
101
102	18	$this->logger->debug('Selected best fit orientation', ['orientation' => $usableOrientations[0]]);
103
104	18	return $usableOrientations[0];
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		* @param int $x
116		* @param int $y
117		* @param int $z
118		* @param PackedItemList $prevPackedItemList
119		*
120		* @return OrientatedItem[]
121		*/
122	29	public function getPossibleOrientations(
123		Item $item,
124		OrientatedItem $prevItem = null,
125		$widthLeft,
126		$lengthLeft,
127		$depthLeft,
128		$x,
129		$y,
130		$z,
131		PackedItemList $prevPackedItemList
132		) {
133	29	$permutations = $this->generatePermutations($item, $prevItem);
134
135		//remove any that simply don't fit
136	29	$orientations = [];
137	29	foreach ($permutations as $dimensions) {
138	29	if ($dimensions[0] <= $widthLeft && $dimensions[1] <= $lengthLeft && $dimensions[2] <= $depthLeft) {
139	28	$orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]);
140		}
141		}
142
143	29	if ($item instanceof ConstrainedPlacementItem) {
144		$orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList) {
145		return $i->getItem()->canBePacked($this->box, clone $prevPackedItemList, $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());
146		});
147		}
148
149	29	return $orientations;
150		}
151
152		/**
153		* @param Item $item
154		* @return OrientatedItem[]
155		*/
156	13	public function getPossibleOrientationsInEmptyBox(Item $item)
157		{
158	13	$cacheKey = $item->getWidth() .
159	13	'\|' .
160	13	$item->getLength() .
161	13	'\|' .
162	13	$item->getDepth() .
163	13	'\|' .
164	13	($item->getKeepFlat() ? '2D' : '3D') .
165	13	'\|' .
166	13	$this->box->getInnerWidth() .
167	13	'\|' .
168	13	$this->box->getInnerLength() .
169	13	'\|' .
170	13	$this->box->getInnerDepth();
171
172	13	if (isset(static::$emptyBoxCache[$cacheKey])) {
173	8	$orientations = static::$emptyBoxCache[$cacheKey];
174		} else {
175	13	$orientations = $this->getPossibleOrientations(
176	13	$item,
177	13	null,
178	13	$this->box->getInnerWidth(),
179	13	$this->box->getInnerLength(),
180	13	$this->box->getInnerDepth(),
181	13	0,
182	13	0,
183	13	0,
184	13	new PackedItemList()
185		);
186	13	static::$emptyBoxCache[$cacheKey] = $orientations;
187		}
188
189	13	return $orientations;
		0 ignored issues – show Bug Best Practice introduced 2018-02-25 15:17 UTC by Report Bug Copy Issue Report The expression `return $orientations` also could return the type `DVDoug\BoxPacker\OrientatedItem` which is incompatible with the documented return type `DVDoug\BoxPacker\OrientatedItem[]`. Loading history...
190		}
191
192		/**
193		* @param Item $item
194		* @param OrientatedItem[] $possibleOrientations
195		* @param bool $isLastItem
196		*
197		* @return OrientatedItem[]
198		*/
199	28	protected function getUsableOrientations(
200		Item $item,
201		array $possibleOrientations
202		) {
203	28	$orientationsToUse = $stableOrientations = $unstableOrientations = [];
204
205		// Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
206	28	foreach ($possibleOrientations as $orientation) {
207	28	if ($orientation->isStable() \|\| $this->box->getInnerDepth() === $orientation->getDepth()) {
208	26	$stableOrientations[] = $orientation;
209		} else {
210	3	$unstableOrientations[] = $orientation;
211		}
212		}
213
214		/*
215		* We prefer to use stable orientations only, but allow unstable ones if
216		* the item doesn't fit in the box any other way
217		*/
218	28	if (count($stableOrientations) > 0) {
219	26	$orientationsToUse = $stableOrientations;
220	26	} elseif (count($unstableOrientations) > 0) {
221	3	$stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);
222
223	3	if (count($stableOrientationsInEmptyBox) === 0) {
224	2	$orientationsToUse = $unstableOrientations;
225		}
226		}
227
228	28	return $orientationsToUse;
229		}
230
231		/**
232		* Return the orientations for this item if it were to be placed into the box with nothing else.
233		*
234		* @param Item $item
235		* @return array
236		*/
237	3	protected function getStableOrientationsInEmptyBox(Item $item)
238		{
239	3	$orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);
240
241	3	return array_filter(
242	3	$orientationsInEmptyBox,
243		function (OrientatedItem $orientation) {
244	3	return $orientation->isStable();
245	3	}
246		);
247		}
248
249	29	private function generatePermutations(Item $item, OrientatedItem $prevItem = null)
250		{
251	29	$permutations = [];
252
253		//Special case items that are the same as what we just packed - keep orientation
254	29	if ($prevItem && $prevItem->isSameDimensions($item)) {
255	16	$permutations[] = [$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()];
256		} else {
257		//simple 2D rotation
258	29	$permutations[] = [$item->getWidth(), $item->getLength(), $item->getDepth()];
259	29	$permutations[] = [$item->getLength(), $item->getWidth(), $item->getDepth()];
260
261		//add 3D rotation if we're allowed
262	29	if (!$item->getKeepFlat()) {
263	17	$permutations[] = [$item->getWidth(), $item->getDepth(), $item->getLength()];
264	17	$permutations[] = [$item->getLength(), $item->getDepth(), $item->getWidth()];
265	17	$permutations[] = [$item->getDepth(), $item->getWidth(), $item->getLength()];
266	17	$permutations[] = [$item->getDepth(), $item->getLength(), $item->getWidth()];
267		}
268		}
269
270	29	return $permutations;
271		}
272		}
273

dvdoug / BoxPacker

Push — 2.x-dev ( 5e90af...eccc16 )

getStableOrientationsInEmptyBox() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like