OrientatedItemFactory::getPossibleOrientations() - Code Metrics - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

OrientatedItemFactory::getPossibleOrientations() B
last analyzed 2025-02-06 23:05 UTC

↳ Parent: OrientatedItemFactory

Complexity

Conditions	9
Paths	6

Size

Total Lines	40
Code Lines	16

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	16
CRAP Score	9

Importance

Changes	9
Bugs	0	Features	0

Metric	Value
cc	9
eloc	16
c	9
b	0
f	0
nc	6
nop	9
dl	0
loc	40
ccs	16
cts	16
cp	1
crap	9
rs	8.0555

How to fix Many Parameters

<?php

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

namespace DVDoug\BoxPacker;

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

use function array_filter;
use function count;
use function usort;

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

    protected bool $singlePassMode = false;

    protected bool $boxIsRotated = false;

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

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

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

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

    public function setBoxIsRotated(bool $boxIsRotated): void
    {
        $this->boxIsRotated = $boxIsRotated;
    }

    /**
     * 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,
                ],
                'position' => [
                    'x' => $x,
                    'y' => $y,
                    'z' => $z,
                ],
            ]
        );

        $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->item;

                if ($this->boxIsRotated) {
                    $rotatedPrevPackedItemList = new PackedItemList();
                    foreach ($prevPackedItemList as $prevPackedItem) {
                        $rotatedPrevPackedItemList->insert(new PackedItem($prevPackedItem->item, $prevPackedItem->y, $prevPackedItem->x, $prevPackedItem->z, $prevPackedItem->length, $prevPackedItem->width, $prevPackedItem->depth));
                    }

                    return $constrainedItem->canBePacked(new PackedBox($this->box, $rotatedPrevPackedItemList), $y, $x, $z, $i->length, $i->width, $i->depth);
                } else {
                    return $constrainedItem->canBePacked(new PackedBox($this->box, $prevPackedItemList), $x, $y, $z, $i->width, $i->length, $i->depth);
                }
            });
        }

        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->depth) {
                $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->width, $prevItem->length, $prevItem->depth]];
        }

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

dvdoug / BoxPacker

OrientatedItemFactory::getPossibleOrientations() B last analyzed 2025-02-06 23:05 UTC

Complexity

Size

Duplication

Code Coverage

Importance

How to fix Many Parameters

Many Parameters

Duplication Side-by-Side

Filter issues like

OrientatedItemFactory::getPossibleOrientations() B
last analyzed 2025-02-06 23:05 UTC