OrientatedItemSorter::__invoke() - Code Metrics - Inspection of "Backport 2.x" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 1.x ( 457fa0...308477 )

by Doug

created 2020-08-15 23:43 UTC

OrientatedItemSorter::__invoke() B

↳ Parent: OrientatedItemSorter

Complexity

Conditions	6
Paths	5

Size

Total Lines	35
Code Lines	21

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	21
CRAP Score	6.0033

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	6
eloc	21
c	1
b	0
f	0
nc	5
nop	2
dl	0
loc	35
ccs	21
cts	22
cp	0.9545
crap	6.0033
rs	8.9617

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

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

/**
 * Figure out best choice of orientations for an item and a given context.
 *
 * @author Doug Wright
 * @internal
 */
class OrientatedItemSorter implements LoggerAwareInterface
{
    use LoggerAwareTrait;

    /**
     * @var int[]
     */
    protected static $lookaheadCache = [];

    /**
     * @var OrientatedItemFactory
     */
    private $orientatedItemFactory;

    /**
     * @var bool
     */
    private $singlePassMode;

    /**
     * @var int
     */
    private $widthLeft;

    /**
     * @var int
     */
    private $lengthLeft;

    /**
     * @var int
     */
    private $depthLeft;

    /**
     * @var int
     */
    private $rowLength;

    /**
     * @var int
     */
    private $x;

    /**
     * @var int
     */
    private $y;

    /**
     * @var int
     */
    private $z;

    /**
     * @var ItemList
     */
    private $nextItems;

    /**
     * @var PackedItemList
     */
    private $prevPackedItemList;

    public function __construct(OrientatedItemFactory $factory, $singlePassMode, $widthLeft, $lengthLeft, $depthLeft, ItemList $nextItems, $rowLength, $x, $y, $z, PackedItemList $prevPackedItemList)
    {
        $this->orientatedItemFactory = $factory;
        $this->singlePassMode = $singlePassMode;
        $this->widthLeft = $widthLeft;
        $this->lengthLeft = $lengthLeft;
        $this->depthLeft = $depthLeft;
        $this->nextItems = $nextItems;
        $this->rowLength = $rowLength;
        $this->x = $x;
        $this->y = $y;
        $this->z = $z;
        $this->prevPackedItemList = $prevPackedItemList;
    }

    public function __invoke(OrientatedItem $a, OrientatedItem $b)
    {
        //Prefer exact fits in width/length/depth order
        $orientationAWidthLeft = $this->widthLeft - $a->getWidth();
        $orientationBWidthLeft = $this->widthLeft - $b->getWidth();
        $widthDecider = $this->exactFitDecider($orientationAWidthLeft, $orientationBWidthLeft);
        if ($widthDecider !== 0) {
            return $widthDecider;
        }

        $orientationALengthLeft = $this->lengthLeft - $a->getLength();
        $orientationBLengthLeft = $this->lengthLeft - $b->getLength();
        $lengthDecider = $this->exactFitDecider($orientationALengthLeft, $orientationBLengthLeft);
        if ($lengthDecider !== 0) {
            return $lengthDecider;
        }

        $orientationADepthLeft = $this->depthLeft - $a->getDepth();
        $orientationBDepthLeft = $this->depthLeft - $b->getDepth();
        $depthDecider = $this->exactFitDecider($orientationADepthLeft, $orientationBDepthLeft);
        if ($depthDecider !== 0) {
            return $depthDecider;
        }

        // prefer leaving room for next item(s)
        $followingItemDecider = $this->lookAheadDecider($this->nextItems, $a, $b, $orientationAWidthLeft, $orientationBWidthLeft, $this->widthLeft, $this->lengthLeft, $this->depthLeft, $this->rowLength, $this->x, $this->y, $this->z, $this->prevPackedItemList);
        if ($followingItemDecider !== 0) {
            return $followingItemDecider;
        }

        // otherwise prefer leaving minimum possible gap, or the greatest footprint
        $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
        $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);

        return ($orientationAMinGap - $orientationBMinGap) ?: ($a->getSurfaceFootprint() - $b->getSurfaceFootprint());
    }

    private function lookAheadDecider(ItemList $nextItems, OrientatedItem $a, OrientatedItem $b, $orientationAWidthLeft, $orientationBWidthLeft, $widthLeft, $lengthLeft, $depthLeft, $rowLength, $x, $y, $z, PackedItemList $prevPackedItemList)
    {
        if ($nextItems->count() === 0) {
            return 0;
        }

        $nextItemFitA = $this->orientatedItemFactory->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
        $nextItemFitB = $this->orientatedItemFactory->getPossibleOrientations($nextItems->top(), $b, $orientationBWidthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
        if ($nextItemFitA && !$nextItemFitB) {

            return -1;
        }
        if ($nextItemFitB && !$nextItemFitA) {

            return 1;
        }

        // if not an easy either/or, do a partial lookahead
        $additionalPackedA = $this->calculateAdditionalItemsPackedWithThisOrientation($a, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
        $additionalPackedB = $this->calculateAdditionalItemsPackedWithThisOrientation($b, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);

        return ($additionalPackedB - $additionalPackedA) ?: 0;
    }

    /**
     * Approximation of a forward-looking packing.
     *
     * Not an actual packing, that has additional logic regarding constraints and stackability, this focuses
     * purely on fit.
     */
    protected function calculateAdditionalItemsPackedWithThisOrientation(
        OrientatedItem $prevItem,
        ItemList $nextItems,
        $originalWidthLeft,
        $originalLengthLeft,
        $depthLeft,
        $currentRowLengthBeforePacking
    ) {
        if ($this->singlePassMode) {
            return 0;
        }

        $currentRowLength = max($prevItem->getLength(), $currentRowLengthBeforePacking);

        $itemsToPack = $nextItems->topN(8); // cap lookahead as this gets recursive and slow

        $cacheKey = $originalWidthLeft .
            '|' .
            $originalLengthLeft .
            '|' .
            $prevItem->getWidth() .
            '|' .
            $prevItem->getLength() .
            '|' .
            $currentRowLength .
            '|'
            . $depthLeft;

        foreach (clone $itemsToPack as $itemToPack) {
            $cacheKey .= '|' .
                $itemToPack->getWidth() .
                '|' .
                $itemToPack->getLength() .
                '|' .
                $itemToPack->getDepth() .
                '|' .
                $itemToPack->getWeight();
        }

        if (!isset(static::$lookaheadCache[$cacheKey])) {
            $tempBox = new WorkingVolume($originalWidthLeft - $prevItem->getWidth(), $currentRowLength, $depthLeft, PHP_INT_MAX);
            $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
            $tempPacker->setSinglePassMode(true);
            $remainingRowPacked = $tempPacker->pack();

            $itemsToPack->removePackedItems($remainingRowPacked->getPackedItems());

            $tempBox = new WorkingVolume($originalWidthLeft, $originalLengthLeft - $currentRowLength, $depthLeft, PHP_INT_MAX);
            $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
            $tempPacker->setSinglePassMode(true);
            $nextRowsPacked = $tempPacker->pack();

            $itemsToPack->removePackedItems($nextRowsPacked->getPackedItems());

            $packedCount = $nextItems->count() - $itemsToPack->count();
            $this->logger->debug('Lookahead with orientation', ['packedCount' => $packedCount, 'orientatedItem' => $prevItem]);

            static::$lookaheadCache[$cacheKey] = $packedCount;
        }

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

    private function exactFitDecider($dimensionALeft, $dimensionBLeft)
    {
        if ($dimensionALeft === 0 && $dimensionBLeft > 0) {
            return -1;
        }

        if ($dimensionALeft > 0 && $dimensionBLeft === 0) {
            return 1;
        }

        return 0;
    }
}


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
12		/**
13		* Figure out best choice of orientations for an item and a given context.
14		*
15		* @author Doug Wright
16		* @internal
17		*/
18		class OrientatedItemSorter implements LoggerAwareInterface
19		{
20		use LoggerAwareTrait;
21
22		/**
23		* @var int[]
24		*/
25		protected static $lookaheadCache = [];
26
27		/**
28		* @var OrientatedItemFactory
29		*/
30		private $orientatedItemFactory;
31
32		/**
33		* @var bool
34		*/
35		private $singlePassMode;
36
37		/**
38		* @var int
39		*/
40		private $widthLeft;
41
42		/**
43		* @var int
44		*/
45		private $lengthLeft;
46
47		/**
48		* @var int
49		*/
50		private $depthLeft;
51
52		/**
53		* @var int
54		*/
55		private $rowLength;
56
57		/**
58		* @var int
59		*/
60		private $x;
61
62		/**
63		* @var int
64		*/
65		private $y;
66
67		/**
68		* @var int
69		*/
70		private $z;
71
72		/**
73		* @var ItemList
74		*/
75		private $nextItems;
76
77		/**
78		* @var PackedItemList
79		*/
80		private $prevPackedItemList;
81
82	42	public function __construct(OrientatedItemFactory $factory, $singlePassMode, $widthLeft, $lengthLeft, $depthLeft, ItemList $nextItems, $rowLength, $x, $y, $z, PackedItemList $prevPackedItemList)
83		{
84	42	$this->orientatedItemFactory = $factory;
85	42	$this->singlePassMode = $singlePassMode;
86	42	$this->widthLeft = $widthLeft;
87	42	$this->lengthLeft = $lengthLeft;
88	42	$this->depthLeft = $depthLeft;
89	42	$this->nextItems = $nextItems;
90	42	$this->rowLength = $rowLength;
91	42	$this->x = $x;
92	42	$this->y = $y;
93	42	$this->z = $z;
94	42	$this->prevPackedItemList = $prevPackedItemList;
95	42	}
96
97	39	public function __invoke(OrientatedItem $a, OrientatedItem $b)
98		{
99		//Prefer exact fits in width/length/depth order
100	39	$orientationAWidthLeft = $this->widthLeft - $a->getWidth();
101	39	$orientationBWidthLeft = $this->widthLeft - $b->getWidth();
102	39	$widthDecider = $this->exactFitDecider($orientationAWidthLeft, $orientationBWidthLeft);
103	39	if ($widthDecider !== 0) {
104	3	return $widthDecider;
105		}
106
107	36	$orientationALengthLeft = $this->lengthLeft - $a->getLength();
108	36	$orientationBLengthLeft = $this->lengthLeft - $b->getLength();
109	36	$lengthDecider = $this->exactFitDecider($orientationALengthLeft, $orientationBLengthLeft);
110	36	if ($lengthDecider !== 0) {
111	10	return $lengthDecider;
112		}
113
114	36	$orientationADepthLeft = $this->depthLeft - $a->getDepth();
115	36	$orientationBDepthLeft = $this->depthLeft - $b->getDepth();
116	36	$depthDecider = $this->exactFitDecider($orientationADepthLeft, $orientationBDepthLeft);
117	36	if ($depthDecider !== 0) {
118		return $depthDecider;
119		}
120
121		// prefer leaving room for next item(s)
122	36	$followingItemDecider = $this->lookAheadDecider($this->nextItems, $a, $b, $orientationAWidthLeft, $orientationBWidthLeft, $this->widthLeft, $this->lengthLeft, $this->depthLeft, $this->rowLength, $this->x, $this->y, $this->z, $this->prevPackedItemList);
123	36	if ($followingItemDecider !== 0) {
124	12	return $followingItemDecider;
125		}
126
127		// otherwise prefer leaving minimum possible gap, or the greatest footprint
128	31	$orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
129	31	$orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
130
131	31	return ($orientationAMinGap - $orientationBMinGap) ?: ($a->getSurfaceFootprint() - $b->getSurfaceFootprint());
132		}
133
134	36	private function lookAheadDecider(ItemList $nextItems, OrientatedItem $a, OrientatedItem $b, $orientationAWidthLeft, $orientationBWidthLeft, $widthLeft, $lengthLeft, $depthLeft, $rowLength, $x, $y, $z, PackedItemList $prevPackedItemList)
135		{
136	36	if ($nextItems->count() === 0) {
137	19	return 0;
138		}
139
140	35	$nextItemFitA = $this->orientatedItemFactory->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
141	35	$nextItemFitB = $this->orientatedItemFactory->getPossibleOrientations($nextItems->top(), $b, $orientationBWidthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
142	35	if ($nextItemFitA && !$nextItemFitB) {
		0 ignored issues – show introduced 2020-04-23 22:35 UTC by Report Bug Copy Issue Report `$nextItemFitB` is a non-empty array, thus `! $nextItemFitB` is always `false`. Loading history... Bug Best Practice introduced 2020-04-23 22:35 UTC by Report Bug Copy Issue Report The expression `$nextItemFitB` of type `DVDoug\BoxPacker\OrientatedItem[]` is implicitly converted to a boolean; are you sure this is intended? If so, consider using `empty($expr)` instead to make it clear that you intend to check for an array without elements. This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent. Consider making the comparison explicit by using `empty(..)` or `! empty(...)` instead. Loading history... Bug Best Practice introduced 2020-04-23 22:35 UTC by Report Bug Copy Issue Report The expression `$nextItemFitA` of type `DVDoug\BoxPacker\OrientatedItem[]` is implicitly converted to a boolean; are you sure this is intended? If so, consider using `! empty($expr)` instead to make it clear that you intend to check for an array without elements. This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent. Consider making the comparison explicit by using `empty(..)` or `! empty(...)` instead. Loading history...
143	3	return -1;
144		}
145	35	if ($nextItemFitB && !$nextItemFitA) {
		0 ignored issues – show introduced 2020-04-23 22:35 UTC by Report Bug Copy Issue Report `$nextItemFitA` is a non-empty array, thus `! $nextItemFitA` is always `false`. Loading history... Bug Best Practice introduced 2020-04-23 22:35 UTC by Report Bug Copy Issue Report The expression `$nextItemFitA` of type `DVDoug\BoxPacker\OrientatedItem[]` is implicitly converted to a boolean; are you sure this is intended? If so, consider using `empty($expr)` instead to make it clear that you intend to check for an array without elements. This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent. Consider making the comparison explicit by using `empty(..)` or `! empty(...)` instead. Loading history... Bug Best Practice introduced 2020-04-23 22:35 UTC by Report Bug Copy Issue Report The expression `$nextItemFitB` of type `DVDoug\BoxPacker\OrientatedItem[]` is implicitly converted to a boolean; are you sure this is intended? If so, consider using `! empty($expr)` instead to make it clear that you intend to check for an array without elements. This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent. Consider making the comparison explicit by using `empty(..)` or `! empty(...)` instead. Loading history...
146	6	return 1;
147		}
148
149		// if not an easy either/or, do a partial lookahead
150	32	$additionalPackedA = $this->calculateAdditionalItemsPackedWithThisOrientation($a, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
151	32	$additionalPackedB = $this->calculateAdditionalItemsPackedWithThisOrientation($b, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
152
153	32	return ($additionalPackedB - $additionalPackedA) ?: 0;
154		}
155
156		/**
157		* Approximation of a forward-looking packing.
158		*
159		* Not an actual packing, that has additional logic regarding constraints and stackability, this focuses
160		* purely on fit.
161		*/
162	32	protected function calculateAdditionalItemsPackedWithThisOrientation(
163		OrientatedItem $prevItem,
164		ItemList $nextItems,
165		$originalWidthLeft,
166		$originalLengthLeft,
167		$depthLeft,
168		$currentRowLengthBeforePacking
169		) {
170	32	if ($this->singlePassMode) {
171	13	return 0;
172		}
173
174	32	$currentRowLength = max($prevItem->getLength(), $currentRowLengthBeforePacking);
175
176	32	$itemsToPack = $nextItems->topN(8); // cap lookahead as this gets recursive and slow
177
178		$cacheKey = $originalWidthLeft .
179	32	'\|' .
180	32	$originalLengthLeft .
181	32	'\|' .
182	32	$prevItem->getWidth() .
183	32	'\|' .
184	32	$prevItem->getLength() .
185	32	'\|' .
186	32	$currentRowLength .
187	32	'\|'
188	32	. $depthLeft;
189
190	32	foreach (clone $itemsToPack as $itemToPack) {
191		$cacheKey .= '\|' .
192	32	$itemToPack->getWidth() .
193	32	'\|' .
194	32	$itemToPack->getLength() .
195	32	'\|' .
196	32	$itemToPack->getDepth() .
197	32	'\|' .
198	32	$itemToPack->getWeight();
199		}
200
201	32	if (!isset(static::$lookaheadCache[$cacheKey])) {
202	30	$tempBox = new WorkingVolume($originalWidthLeft - $prevItem->getWidth(), $currentRowLength, $depthLeft, PHP_INT_MAX);
203	30	$tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
204	30	$tempPacker->setSinglePassMode(true);
205	30	$remainingRowPacked = $tempPacker->pack();
206
207	30	$itemsToPack->removePackedItems($remainingRowPacked->getPackedItems());
208
209	30	$tempBox = new WorkingVolume($originalWidthLeft, $originalLengthLeft - $currentRowLength, $depthLeft, PHP_INT_MAX);
210	30	$tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
211	30	$tempPacker->setSinglePassMode(true);
212	30	$nextRowsPacked = $tempPacker->pack();
213
214	30	$itemsToPack->removePackedItems($nextRowsPacked->getPackedItems());
215
216	30	$packedCount = $nextItems->count() - $itemsToPack->count();
217	30	$this->logger->debug('Lookahead with orientation', ['packedCount' => $packedCount, 'orientatedItem' => $prevItem]);
218
219	30	static::$lookaheadCache[$cacheKey] = $packedCount;
220		}
221
222	32	return static::$lookaheadCache[$cacheKey];
223		}
224
225	39	private function exactFitDecider($dimensionALeft, $dimensionBLeft)
226		{
227	39	if ($dimensionALeft === 0 && $dimensionBLeft > 0) {
228	7	return -1;
229		}
230
231	37	if ($dimensionALeft > 0 && $dimensionBLeft === 0) {
232	6	return 1;
233		}
234
235	36	return 0;
236		}
237		}
238

dvdoug / BoxPacker

Push — 1.x ( 457fa0...308477 )

OrientatedItemSorter::__invoke() B

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like