OrientatedItemFactory::getBestOrientation() - Code Metrics - Inspection of "More deterministic sorting, PHP5 and 7 were giving..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Test Failed

Push — 2.x-dev ( 9cc753...b24883 )

by Doug

created 2018-09-30 17:34 UTC

OrientatedItemFactory::getBestOrientation() C

↳ Parent: OrientatedItemFactory

Complexity

Conditions	12
Paths	2

Size

Total Lines	47
Code Lines	27

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	25
CRAP Score	12.0585

Importance

Changes

Metric	Value
cc	12
eloc	27
nc	2
nop	6
dl	0
loc	47
ccs	25
cts	27
cp	0.9259
crap	12.0585
rs	6.9666
c	0
b	0
f	0

How to fix Complexity

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

namespace DVDoug\BoxPacker;

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

/**
 * Figure out orientations for an item and a given set of dimensions.
 *
 * @author Doug Wright
 */
class OrientatedItemFactory implements LoggerAwareInterface
{
    use LoggerAwareTrait;

    /** @var Item */
    protected $item;

    /** @var Box */
    protected $box;

    /**
     * @var OrientatedItem[]
     */
    protected static $emptyBoxCache = [];

    public function __construct(Item $item, Box $box)
    {
        $this->item = $item;
        $this->box = $box;
    }

    /**
     * Get the best orientation for an item.
     *
     * @param OrientatedItem|null $prevItem
     * @param Item|null           $nextItem
     * @param bool                $isLastItem
     * @param int                 $widthLeft
     * @param int                 $lengthLeft
     * @param int                 $depthLeft
     *
     * @return OrientatedItem|null
     */
    public function getBestOrientation(
        OrientatedItem $prevItem = null,
        Item $nextItem = null,
        $isLastItem,
        $widthLeft,
        $lengthLeft,
        $depthLeft
    ) {
        $possibleOrientations = $this->getPossibleOrientations($this->item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
        $usableOrientations = $this->getUsableOrientations($possibleOrientations, $isLastItem);

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

        usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItem) {
            $orientationAWidthLeft = $widthLeft - $a->getWidth();
            $orientationALengthLeft = $lengthLeft - $a->getLength();
            $orientationBWidthLeft = $widthLeft - $b->getWidth();
            $orientationBLengthLeft = $lengthLeft - $b->getLength();

            $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
            $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);

            if ($orientationAMinGap === 0 && $orientationBMinGap !== 0) { // prefer A if it leaves no gap
                return -1;
            } elseif ($orientationBMinGap === 0 && $orientationAMinGap !== 0) { // prefer B if it leaves no gap
                return 1;
            } else { // prefer leaving room for next item in current row
                if ($nextItem) {
                    $nextItemFitA = count($this->getPossibleOrientations($nextItem, $a, $orientationAWidthLeft, $orientationALengthLeft, $depthLeft));
                    $nextItemFitB = count($this->getPossibleOrientations($nextItem, $b, $orientationBWidthLeft, $orientationBLengthLeft, $depthLeft));
                    if ($nextItemFitA && !$nextItemFitB) {
                        return -1;
                    } elseif ($nextItemFitB && !$nextItemFitA) {
                        return 1;
                    }
                }
                // otherwise prefer leaving minimum possible gap, or the greatest footprint
                return $orientationAMinGap - $orientationBMinGap ?: $a->getSurfaceFootprint() - $b->getSurfaceFootprint();
            }
        });

        $bestFit = reset($usableOrientations);
        $this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]);

        return $bestFit;
    }

    /**
     * Find all possible orientations for an item.
     *
     * @param Item                $item
     * @param OrientatedItem|null $prevItem
     * @param int                 $widthLeft
     * @param int                 $lengthLeft
     * @param int                 $depthLeft
     *
     * @return OrientatedItem[]
     */
    public function getPossibleOrientations(
        Item $item,
        OrientatedItem $prevItem = null,
        $widthLeft,
        $lengthLeft,
        $depthLeft
    ) {
        $orientations = [];

        //Special case items that are the same as what we just packed - keep orientation
        if ($prevItem && $this->isSameDimensions($prevItem->getItem(), $item)) {
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
        } else {

            //simple 2D rotation
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());

            //add 3D rotation if we're allowed
            if (!$item->getKeepFlat()) {
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
            }
        }

        //remove any that simply don't fit
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
        });
    }

    /**
     * @return OrientatedItem[]
     */
    public function getPossibleOrientationsInEmptyBox()
    {
        $cacheKey = $this->item->getWidth().
            '|'.
            $this->item->getLength().
            '|'.
            $this->item->getDepth().
            '|'.
            ($this->item->getKeepFlat() ? '2D' : '3D').
            '|'.
            $this->box->getInnerWidth().
            '|'.
            $this->box->getInnerLength().
            '|'.
            $this->box->getInnerDepth();

        if (isset(static::$emptyBoxCache[$cacheKey])) {
            $orientations = static::$emptyBoxCache[$cacheKey];
        } else {
            $orientations = $this->getPossibleOrientations(
                $this->item,
                null,
                $this->box->getInnerWidth(),
                $this->box->getInnerLength(),
                $this->box->getInnerDepth()
            );
            static::$emptyBoxCache[$cacheKey] = $orientations;
        }

        return $orientations;

    }

    /**
     * @param OrientatedItem[] $possibleOrientations
     * @param bool             $isLastItem
     *
     * @return OrientatedItem[]
     */
    protected function getUsableOrientations(
        $possibleOrientations,
        $isLastItem
    ) {
        $orientationsToUse = $stableOrientations = $unstableOrientations = [];

        // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
        foreach ($possibleOrientations as $orientation) {
            if ($orientation->isStable()) {
                $stableOrientations[] = $orientation;
            } else {
                $unstableOrientations[] = $orientation;
            }
        }

        /*
         * We prefer to use stable orientations only, but allow unstable ones if either
         * the item is the last one left to pack OR
         * the item doesn't fit in the box any other way
         */
        if (count($stableOrientations) > 0) {
            $orientationsToUse = $stableOrientations;
        } elseif (count($unstableOrientations) > 0) {
            $stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox();

            if ($isLastItem || count($stableOrientationsInEmptyBox) == 0) {
                $orientationsToUse = $unstableOrientations;
            }
        }

        return $orientationsToUse;
    }

    /**
     * Return the orientations for this item if it were to be placed into the box with nothing else.
     *
     * @return array
     */
    protected function getStableOrientationsInEmptyBox()
    {
        $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox();

        return array_filter(
            $orientationsInEmptyBox,
            function (OrientatedItem $orientation) {
                return $orientation->isStable();
            }
        );
    }

    /**
     * Compare two items to see if they have same dimensions.
     *
     * @param Item $itemA
     * @param Item $itemB
     *
     * @return bool
     */
    protected function isSameDimensions(Item $itemA, Item $itemB)
    {
        $itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
        $itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
        sort($itemADimensions);
        sort($itemBDimensions);

        return $itemADimensions === $itemBDimensions;
    }
}


1		<?php
2		/**
3		* Box packing (3D bin packing, knapsack problem).
4		*
5		* @author Doug Wright
6		*/
7
8		namespace DVDoug\BoxPacker;
9
10		use Psr\Log\LoggerAwareInterface;
11		use Psr\Log\LoggerAwareTrait;
12
13		/**
14		* Figure out orientations for an item and a given set of dimensions.
15		*
16		* @author Doug Wright
17		*/
18		class OrientatedItemFactory implements LoggerAwareInterface
19		{
20		use LoggerAwareTrait;
21
22		/** @var Item */
23		protected $item;
24
25		/** @var Box */
26		protected $box;
27
28		/**
29		* @var OrientatedItem[]
30		*/
31		protected static $emptyBoxCache = [];
32
33	20	public function __construct(Item $item, Box $box)
34		{
35	20	$this->item = $item;
36	20	$this->box = $box;
37	20	}
38
39		/**
40		* Get the best orientation for an item.
41		*
42		* @param OrientatedItem\|null $prevItem
43		* @param Item\|null $nextItem
44		* @param bool $isLastItem
45		* @param int $widthLeft
46		* @param int $lengthLeft
47		* @param int $depthLeft
48		*
49		* @return OrientatedItem\|null
50		*/
51	20	public function getBestOrientation(
52		OrientatedItem $prevItem = null,
53		Item $nextItem = null,
54		$isLastItem,
55		$widthLeft,
56		$lengthLeft,
57		$depthLeft
58		) {
59	20	$possibleOrientations = $this->getPossibleOrientations($this->item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
60	20	$usableOrientations = $this->getUsableOrientations($possibleOrientations, $isLastItem);
61
62	20	if (empty($usableOrientations)) {
63	19	return;
64		}
65
66		usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItem) {
67	20	$orientationAWidthLeft = $widthLeft - $a->getWidth();
68	20	$orientationALengthLeft = $lengthLeft - $a->getLength();
69	20	$orientationBWidthLeft = $widthLeft - $b->getWidth();
70	20	$orientationBLengthLeft = $lengthLeft - $b->getLength();
71
72	20	$orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
73	20	$orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
74
75	20	if ($orientationAMinGap === 0 && $orientationBMinGap !== 0) { // prefer A if it leaves no gap
76		return -1;
77	20	} elseif ($orientationBMinGap === 0 && $orientationAMinGap !== 0) { // prefer B if it leaves no gap
78	1	return 1;
79		} else { // prefer leaving room for next item in current row
80	19	if ($nextItem) {
81	18	$nextItemFitA = count($this->getPossibleOrientations($nextItem, $a, $orientationAWidthLeft, $orientationALengthLeft, $depthLeft));
82	18	$nextItemFitB = count($this->getPossibleOrientations($nextItem, $b, $orientationBWidthLeft, $orientationBLengthLeft, $depthLeft));
83	18	if ($nextItemFitA && !$nextItemFitB) {
84		return -1;
85	18	} elseif ($nextItemFitB && !$nextItemFitA) {
86	1	return 1;
87		}
88		}
89		// otherwise prefer leaving minimum possible gap, or the greatest footprint
90	18	return $orientationAMinGap - $orientationBMinGap ?: $a->getSurfaceFootprint() - $b->getSurfaceFootprint();
91		}
92	20	});
93
94	20	$bestFit = reset($usableOrientations);
95	20	$this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]);
96
97	20	return $bestFit;
98		}
99
100		/**
101		* Find all possible orientations for an item.
102		*
103		* @param Item $item
104		* @param OrientatedItem\|null $prevItem
105		* @param int $widthLeft
106		* @param int $lengthLeft
107		* @param int $depthLeft
108		*
109		* @return OrientatedItem[]
110		*/
111	20	public function getPossibleOrientations(
112		Item $item,
113		OrientatedItem $prevItem = null,
114		$widthLeft,
115		$lengthLeft,
116		$depthLeft
117		) {
118	20	$orientations = [];
119
120		//Special case items that are the same as what we just packed - keep orientation
121	20	if ($prevItem && $this->isSameDimensions($prevItem->getItem(), $item)) {
122	16	$orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
123		} else {
124
125		//simple 2D rotation
126	20	$orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
127	20	$orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
128
129		//add 3D rotation if we're allowed
130	20	if (!$item->getKeepFlat()) {
131	12	$orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
132	12	$orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
133	12	$orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
134	12	$orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
135		}
136		}
137
138		//remove any that simply don't fit
139		return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
140	20	return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
141	20	});
142		}
143
144		/**
145		* @return OrientatedItem[]
146		*/
147	20	public function getPossibleOrientationsInEmptyBox()
148		{
149	20	$cacheKey = $this->item->getWidth().
150	20	'\|'.
151	20	$this->item->getLength().
152	20	'\|'.
153	20	$this->item->getDepth().
154	20	'\|'.
155	20	($this->item->getKeepFlat() ? '2D' : '3D').
156	20	'\|'.
157	20	$this->box->getInnerWidth().
158	20	'\|'.
159	20	$this->box->getInnerLength().
160	20	'\|'.
161	20	$this->box->getInnerDepth();
162
163	20	if (isset(static::$emptyBoxCache[$cacheKey])) {
164	17	$orientations = static::$emptyBoxCache[$cacheKey];
165		} else {
166	19	$orientations = $this->getPossibleOrientations(
167	19	$this->item,
168	19	null,
169	19	$this->box->getInnerWidth(),
170	19	$this->box->getInnerLength(),
171	19	$this->box->getInnerDepth()
172		);
173	19	static::$emptyBoxCache[$cacheKey] = $orientations;
174		}
175
176	20	return $orientations;
		0 ignored issues – show Bug Best Practice introduced 2018-02-25 15:17 UTC by Report Bug Copy Issue Report The expression `return $orientations` also could return the type `DVDoug\BoxPacker\OrientatedItem` which is incompatible with the documented return type `DVDoug\BoxPacker\OrientatedItem[]`. Loading history...
177		}
178
179		/**
180		* @param OrientatedItem[] $possibleOrientations
181		* @param bool $isLastItem
182		*
183		* @return OrientatedItem[]
184		*/
185	20	protected function getUsableOrientations(
186		$possibleOrientations,
187		$isLastItem
188		) {
189	20	$orientationsToUse = $stableOrientations = $unstableOrientations = [];
190
191		// Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
192	20	foreach ($possibleOrientations as $orientation) {
193	20	if ($orientation->isStable()) {
194	20	$stableOrientations[] = $orientation;
195		} else {
196	20	$unstableOrientations[] = $orientation;
197		}
198		}
199
200		/*
201		* We prefer to use stable orientations only, but allow unstable ones if either
202		* the item is the last one left to pack OR
203		* the item doesn't fit in the box any other way
204		*/
205	20	if (count($stableOrientations) > 0) {
206	20	$orientationsToUse = $stableOrientations;
207	19	} elseif (count($unstableOrientations) > 0) {
208		$stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox();
209
210		if ($isLastItem \|\| count($stableOrientationsInEmptyBox) == 0) {
211		$orientationsToUse = $unstableOrientations;
212		}
213		}
214
215	20	return $orientationsToUse;
216		}
217
218		/**
219		* Return the orientations for this item if it were to be placed into the box with nothing else.
220		*
221		* @return array
222		*/
223		protected function getStableOrientationsInEmptyBox()
224		{
225		$orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox();
226
227		return array_filter(
228		$orientationsInEmptyBox,
229		function (OrientatedItem $orientation) {
230		return $orientation->isStable();
231		}
232		);
233		}
234
235		/**
236		* Compare two items to see if they have same dimensions.
237		*
238		* @param Item $itemA
239		* @param Item $itemB
240		*
241		* @return bool
242		*/
243	19	protected function isSameDimensions(Item $itemA, Item $itemB)
244		{
245	19	$itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
246	19	$itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
247	19	sort($itemADimensions);
248	19	sort($itemBDimensions);
249
250	19	return $itemADimensions === $itemBDimensions;
251		}
252		}
253

dvdoug / BoxPacker

Push — 2.x-dev ( 9cc753...b24883 )

OrientatedItemFactory::getBestOrientation() C

Complexity

Size

Duplication

Code Coverage

Importance

How to fix Complexity

Long Method

Duplication Side-by-Side

Filter issues like