OrientatedItemFactory::getBestOrientation() - Code Metrics - Inspection of "Bump @babylonjs/gui from 5.9.0 to 5.16.0 in /docs/..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Pull Request — master (#308)

unknown

created 2022-07-22 02:42 UTC

OrientatedItemFactory::getBestOrientation() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	3
Paths	4

Size

Total Lines	39
Code Lines	15

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	3

Importance

Changes	14
Bugs	3	Features	0

Metric	Value
cc	3
eloc	15
c	14
b	3
f	0
nc	4
nop	12
dl	0
loc	39
ccs	13
cts	13
cp	1
crap	3
rs	9.7666

How to fix Many Parameters

<?php
/**
 * Box packing (3D bin packing, knapsack problem).
 *
 * @author Doug Wright
 */
declare(strict_types=1);

namespace DVDoug\BoxPacker;

use function array_filter;
use function count;

use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerInterface;
use Psr\Log\NullLogger;

use function usort;

/**
 * Figure out orientations for an item and a given set of dimensions.
 * @internal
 */
class OrientatedItemFactory implements LoggerAwareInterface
{
    protected LoggerInterface $logger;

    protected Box $box;

    protected bool $singlePassMode = false;

    /** @var array<string, bool> */
    protected static array $emptyBoxStableItemOrientationCache = [];

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

    public function setLogger(LoggerInterface $logger): void
    {
        $this->logger = $logger;
    }

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

    /**
     * Get the best orientation for an item.
     */
    public function getBestOrientation(
        Item $item,
        ?OrientatedItem $prevItem,
        ItemList $nextItems,
        int $widthLeft,
        int $lengthLeft,
        int $depthLeft,
        int $rowLength,
        int $x,
        int $y,
        int $z,
        PackedItemList $prevPackedItemList,
        bool $considerStability
    ): ?OrientatedItem {
        $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 = $considerStability ? $this->getUsableOrientations($item, $possibleOrientations) : $possibleOrientations;

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

        $sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList, $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.
     *
     * @return OrientatedItem[]
     */
    public function getPossibleOrientations(
        Item $item,
        ?OrientatedItem $prevItem,
        int $widthLeft,
        int $lengthLeft,
        int $depthLeft,
        int $x,
        int $y,
        int $z,
        PackedItemList $prevPackedItemList
    ): array {
        $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 && !$this->box instanceof WorkingVolume) {
            $orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList): bool {
                /** @var ConstrainedPlacementItem $constrainedItem */
                $constrainedItem = $i->getItem();

                return $constrainedItem->canBePacked(new PackedBox($this->box, $prevPackedItemList), $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());
            });
        }

        return $orientations;
    }

    /**
     * @param  OrientatedItem[] $possibleOrientations
     * @return OrientatedItem[]
     */
    protected function getUsableOrientations(
        Item $item,
        array $possibleOrientations
    ): array {
        $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) {
            return $stableOrientations;
        }

        if ((count($unstableOrientations) > 0) && !$this->hasStableOrientationsInEmptyBox($item)) {
            return $unstableOrientations;
        }

        return [];
    }

    /**
     * Return the orientations for this item if it were to be placed into the box with nothing else.
     */
    protected function hasStableOrientationsInEmptyBox(Item $item): bool
    {
        $cacheKey = $item->getWidth() .
            '|' .
            $item->getLength() .
            '|' .
            $item->getDepth() .
            '|' .
            $item->getAllowedRotation()->name .

            '|' .
            $this->box->getInnerWidth() .
            '|' .
            $this->box->getInnerLength() .
            '|' .
            $this->box->getInnerDepth();

        if (isset(static::$emptyBoxStableItemOrientationCache[$cacheKey])) {
            return static::$emptyBoxStableItemOrientationCache[$cacheKey];
        }

        $orientations = $this->getPossibleOrientations(
            $item,
            null,
            $this->box->getInnerWidth(),
            $this->box->getInnerLength(),
            $this->box->getInnerDepth(),
            0,
            0,
            0,
            new PackedItemList()
        );

        $stableOrientations = array_filter(
            $orientations,
            static fn (OrientatedItem $orientation) => $orientation->isStable()
        );
        static::$emptyBoxStableItemOrientationCache[$cacheKey] = count($stableOrientations) > 0;

        return static::$emptyBoxStableItemOrientationCache[$cacheKey];
    }

    /**
     * @return array<array<int>>
     */
    private function generatePermutations(Item $item, ?OrientatedItem $prevItem): array
    {
        // Special case items that are the same as what we just packed - keep orientation
        if ($prevItem && $prevItem->isSameDimensions($item)) {
            return [[$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()]];
        }

        $permutations = [];
        $w = $item->getWidth();
        $l = $item->getLength();
        $d = $item->getDepth();

        $permutations[$w . '|' . $l . '|' . $d] = [$w, $l, $d];

        if ($item->getAllowedRotation() !== Rotation::Never) { // simple 2D rotation
            $permutations[$l . '|' . $w . '|' . $d] = [$l, $w, $d];
        }

        if ($item->getAllowedRotation() === Rotation::BestFit) { // add 3D rotation if we're allowed
            $permutations[$w . '|' . $d . '|' . $l] = [$w, $d, $l];
            $permutations[$l . '|' . $d . '|' . $w] = [$l, $d, $w];
            $permutations[$d . '|' . $w . '|' . $l] = [$d, $w, $l];
            $permutations[$d . '|' . $l . '|' . $w] = [$d, $l, $w];
        }

        return $permutations;
    }
}


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 function array_filter;
12		use function count;
13
14		use Psr\Log\LoggerAwareInterface;
15		use Psr\Log\LoggerInterface;
16		use Psr\Log\NullLogger;
17
18		use function usort;
19
20		/**
21		* Figure out orientations for an item and a given set of dimensions.
22		* @internal
23		*/
24		class OrientatedItemFactory implements LoggerAwareInterface
25		{
26		protected LoggerInterface $logger;
27
28		protected Box $box;
29
30		protected bool $singlePassMode = false;
31
32		/** @var array<string, bool> */
33		protected static array $emptyBoxStableItemOrientationCache = [];
34
35	84	public function __construct(Box $box)
36		{
37	84	$this->box = $box;
38	84	$this->logger = new NullLogger();
39		}
40
41	84	public function setLogger(LoggerInterface $logger): void
42		{
43	84	$this->logger = $logger;
44		}
45
46	4	public function setSinglePassMode(bool $singlePassMode): void
47		{
48	4	$this->singlePassMode = $singlePassMode;
49		}
50
51		/**
52		* Get the best orientation for an item.
53		*/
54	84	public function getBestOrientation(
55		Item $item,
56		?OrientatedItem $prevItem,
57		ItemList $nextItems,
58		int $widthLeft,
59		int $lengthLeft,
60		int $depthLeft,
61		int $rowLength,
62		int $x,
63		int $y,
64		int $z,
65		PackedItemList $prevPackedItemList,
66		bool $considerStability
67		): ?OrientatedItem {
68	84	$this->logger->debug(
69	84	"evaluating item {$item->getDescription()} for fit",
70		[
71	84	'item' => $item,
72		'space' => [
73	84	'widthLeft' => $widthLeft,
74		'lengthLeft' => $lengthLeft,
75		'depthLeft' => $depthLeft,
76		],
77		]
78		);
79
80	84	$possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
81	84	$usableOrientations = $considerStability ? $this->getUsableOrientations($item, $possibleOrientations) : $possibleOrientations;
82
83	84	if (empty($usableOrientations)) {
84	76	return null;
85		}
86
87	82	$sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList, $this->logger);
88	82	usort($usableOrientations, $sorter);
89
90	82	$this->logger->debug('Selected best fit orientation', ['orientation' => $usableOrientations[0]]);
91
92	82	return $usableOrientations[0];
93		}
94
95		/**
96		* Find all possible orientations for an item.
97		*
98		* @return OrientatedItem[]
99		*/
100	84	public function getPossibleOrientations(
101		Item $item,
102		?OrientatedItem $prevItem,
103		int $widthLeft,
104		int $lengthLeft,
105		int $depthLeft,
106		int $x,
107		int $y,
108		int $z,
109		PackedItemList $prevPackedItemList
110		): array {
111	84	$permutations = $this->generatePermutations($item, $prevItem);
112
113		// remove any that simply don't fit
114	84	$orientations = [];
115	84	foreach ($permutations as $dimensions) {
116	84	if ($dimensions[0] <= $widthLeft && $dimensions[1] <= $lengthLeft && $dimensions[2] <= $depthLeft) {
117	82	$orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]);
118		}
119		}
120
121	84	if ($item instanceof ConstrainedPlacementItem && !$this->box instanceof WorkingVolume) {
122		$orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList): bool {
123		/** @var ConstrainedPlacementItem $constrainedItem */
124		$constrainedItem = $i->getItem();
125
126		return $constrainedItem->canBePacked(new PackedBox($this->box, $prevPackedItemList), $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());
127		});
128		}
129
130	84	return $orientations;
131		}
132
133		/**
134		* @param OrientatedItem[] $possibleOrientations
135		* @return OrientatedItem[]
136		*/
137	84	protected function getUsableOrientations(
138		Item $item,
139		array $possibleOrientations
140		): array {
141	84	$stableOrientations = $unstableOrientations = [];
142
143		// Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
144	84	foreach ($possibleOrientations as $orientation) {
145	82	if ($orientation->isStable() \|\| $this->box->getInnerDepth() === $orientation->getDepth()) {
146	82	$stableOrientations[] = $orientation;
147		} else {
148		$unstableOrientations[] = $orientation;
149		}
150		}
151
152		/*
153		* We prefer to use stable orientations only, but allow unstable ones if
154		* the item doesn't fit in the box any other way
155		*/
156	84	if (count($stableOrientations) > 0) {
157	82	return $stableOrientations;
158		}
159
160	76	if ((count($unstableOrientations) > 0) && !$this->hasStableOrientationsInEmptyBox($item)) {
161		return $unstableOrientations;
162		}
163
164	76	return [];
165		}
166
167		/**
168		* Return the orientations for this item if it were to be placed into the box with nothing else.
169		*/
170		protected function hasStableOrientationsInEmptyBox(Item $item): bool
171		{
172		$cacheKey = $item->getWidth() .
173		'\|' .
174		$item->getLength() .
175		'\|' .
176		$item->getDepth() .
177		'\|' .
178		$item->getAllowedRotation()->name .
		0 ignored issues – show Bug introduced 2022-07-01 03:02 UTC by Report Bug Copy Issue Report The property `name` does not seem to exist on `DVDoug\BoxPacker\Rotation`. Loading history...
179		'\|' .
180		$this->box->getInnerWidth() .
181		'\|' .
182		$this->box->getInnerLength() .
183		'\|' .
184		$this->box->getInnerDepth();
185
186		if (isset(static::$emptyBoxStableItemOrientationCache[$cacheKey])) {
187		return static::$emptyBoxStableItemOrientationCache[$cacheKey];
188		}
189
190		$orientations = $this->getPossibleOrientations(
191		$item,
192		null,
193		$this->box->getInnerWidth(),
194		$this->box->getInnerLength(),
195		$this->box->getInnerDepth(),
196		0,
197		0,
198		0,
199		new PackedItemList()
200		);
201
202		$stableOrientations = array_filter(
203		$orientations,
204		static fn (OrientatedItem $orientation) => $orientation->isStable()
205		);
206		static::$emptyBoxStableItemOrientationCache[$cacheKey] = count($stableOrientations) > 0;
207
208		return static::$emptyBoxStableItemOrientationCache[$cacheKey];
209		}
210
211		/**
212		* @return array<array<int>>
213		*/
214	84	private function generatePermutations(Item $item, ?OrientatedItem $prevItem): array
215		{
216		// Special case items that are the same as what we just packed - keep orientation
217	84	if ($prevItem && $prevItem->isSameDimensions($item)) {
218	62	return [[$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()]];
219		}
220
221	84	$permutations = [];
222	84	$w = $item->getWidth();
223	84	$l = $item->getLength();
224	84	$d = $item->getDepth();
225
226	84	$permutations[$w . '\|' . $l . '\|' . $d] = [$w, $l, $d];
227
228	84	if ($item->getAllowedRotation() !== Rotation::Never) { // simple 2D rotation
229	84	$permutations[$l . '\|' . $w . '\|' . $d] = [$l, $w, $d];
230		}
231
232	84	if ($item->getAllowedRotation() === Rotation::BestFit) { // add 3D rotation if we're allowed
233	52	$permutations[$w . '\|' . $d . '\|' . $l] = [$w, $d, $l];
234	52	$permutations[$l . '\|' . $d . '\|' . $w] = [$l, $d, $w];
235	52	$permutations[$d . '\|' . $w . '\|' . $l] = [$d, $w, $l];
236	52	$permutations[$d . '\|' . $l . '\|' . $w] = [$d, $l, $w];
237		}
238
239	84	return $permutations;
240		}
241		}
242

dvdoug / BoxPacker

Pull Request — master (#308)

OrientatedItemFactory::getBestOrientation() A

Complexity

Size

Duplication

Code Coverage

Importance

How to fix Many Parameters

Many Parameters

Duplication Side-by-Side

Filter issues like