OrientatedItemFactory::setBoxIsRotated() - Code Metrics - Inspection of "Correct rotations before entering callbacks, add a..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 2e0db4...02b4d3 )

by Doug

created 2023-04-23 16:31 UTC

OrientatedItemFactory::setBoxIsRotated() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	2
CRAP Score	1

Importance

Changes

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

<?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,
filter:
    dependency_paths: ["lib/*"]
        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();

                if ($this->boxIsRotated) {
                    $rotatedPrevPackedItemList = new PackedItemList();
                    foreach ($prevPackedItemList as $prevPackedItem) {
                        $rotatedPrevPackedItemList->insert(new PackedItem($prevPackedItem->getItem(), $prevPackedItem->getY(), $prevPackedItem->getX(), $prevPackedItem->getZ(), $prevPackedItem->getLength(), $prevPackedItem->getWidth(), $prevPackedItem->getDepth()));
                    }

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

dvdoug / BoxPacker

Push — master ( 2e0db4...02b4d3 )

OrientatedItemFactory::setBoxIsRotated() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like