OrientatedItemFactory::setBoxIsRotated() - Code Metrics - Inspection of "Backport packing improvements" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 3.x ( d739e8...b351ea )

by Doug

created 2023-07-26 16:15 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	1
CRAP Score	1

Importance

Changes

Metric	Value
cc	1
eloc	1
nc	1
nop	1
dl	0
loc	3
ccs	1
cts	1
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 Box $box;

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

    protected bool $boxIsRotated = 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;
    }

    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->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($this->box, $rotatedPrevPackedItemList, $y, $x, $z, $i->getLength(), $i->getWidth(), $i->getDepth());
                } else {
                    return $constrainedItem->canBePacked($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->getKeepFlat() ? '2D' : '3D') .
            '|' .
            $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();

        // simple 2D rotation
        $permutations[$w . '|' . $l . '|' . $d] = [$w, $l, $d];
        $permutations[$l . '|' . $w . '|' . $d] = [$l, $w, $d];

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

dvdoug / BoxPacker

Push — 3.x ( d739e8...b351ea )

OrientatedItemFactory::setBoxIsRotated() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like