OrientatedItemFactory::calculateAdditionalItemsPackedWithThisOrientation() - Code Metrics - Inspection of "Backport changes from 3.x-dev" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 1.x-dev ( b2df86...afef98 )

by Doug

created 2018-11-10 23:36 UTC

calculateAdditionalItemsPackedWithThisOrientation() B

↳ Parent: OrientatedItemFactory

Complexity

Conditions	7
Paths	9

Size

Total Lines	40
Code Lines	24

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	24
CRAP Score	7

Importance

Changes

Metric	Value
cc	7
eloc	24
nc	9
nop	5
dl	0
loc	40
ccs	24
cts	24
cp	1
crap	7
rs	8.6026
c	0
b	0
f	0

<?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
 * @internal
 */
class OrientatedItemFactory implements LoggerAwareInterface
{
    use LoggerAwareTrait;

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

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

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

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

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

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

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

            if ($orientationAMinGap === 0 && ($orientationBMinGap !== 0 || PHP_MAJOR_VERSION > 5)) { // prefer A if it leaves no gap
                return -1;
            }
            if ($orientationBMinGap === 0) { // prefer B if it leaves no gap
                return 1;
            }

            // prefer leaving room for next item in current row
            if ($nextItems->count()) {
                $nextItemFitA = count($this->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft));
                $nextItemFitB = count($this->getPossibleOrientations($nextItems->top(), $b, $orientationBWidthLeft, $lengthLeft, $depthLeft));
                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);
                $additionalPackedB = $this->calculateAdditionalItemsPackedWithThisOrientation($b, $nextItems, $widthLeft, $lengthLeft, $depthLeft);
                if ($additionalPackedA !== $additionalPackedB) {
                    return $additionalPackedB - $additionalPackedA;
                }
            }
            // otherwise prefer leaving minimum possible gap, or the greatest footprint
            return ($orientationADepthLeft - $orientationBDepthLeft) ?: ($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());
        }

        //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;
        });
    }

    /**
     * @param  Item             $item
     * @return OrientatedItem[]
     */
    public function getPossibleOrientationsInEmptyBox(Item $item)
    {
        $cacheKey = $item->getWidth() .
            '|' .
            $item->getLength() .
            '|' .
            $item->getDepth() .
            '|' .
            $this->box->getInnerWidth() .
            '|' .
            $this->box->getInnerLength() .
            '|' .
            $this->box->getInnerDepth();

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

        return $orientations;

    }

    /**
     * @param Item             $item
     * @param OrientatedItem[] $possibleOrientations
     * @param bool             $isLastItem
     *
     * @return OrientatedItem[]
     */
    protected function getUsableOrientations(
        Item $item,
        $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($item);

            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.
     *
     * @param  Item  $item
     * @return array
     */
    protected function getStableOrientationsInEmptyBox(Item $item)
    {
        $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);

        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;
    }

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

        // first try packing into current row
        $currentRowWorkingSetItems = clone $nextItems;
        $nextRowWorkingSetItems = new ItemList();
        $widthLeft = $originalWidthLeft - $prevItem->getWidth();
        $lengthLeft = $originalLengthLeft;
        while (count($currentRowWorkingSetItems) > 0 && $widthLeft > 0) {
            $itemToPack = $currentRowWorkingSetItems->extract();
            $orientatedItem = $this->getBestOrientation($itemToPack, $prevItem, $currentRowWorkingSetItems, !count($currentRowWorkingSetItems), $widthLeft, $lengthLeft, $depthLeft);
            if ($orientatedItem instanceof OrientatedItem) {
                ++$packedCount;
                $widthLeft -= $orientatedItem->getWidth();
                $prevItem = $orientatedItem;
            } else {
                $nextRowWorkingSetItems->insert($itemToPack);
            }
        }

        // then see what happens if we try in the next row
        $widthLeft = $originalWidthLeft;
        $lengthLeft = $originalLengthLeft - $prevItem->getLength();
        while (count($nextRowWorkingSetItems) > 0 && $widthLeft > 0) {
            $itemToPack = $nextRowWorkingSetItems->extract();
            $orientatedItem = $this->getBestOrientation($itemToPack, $prevItem, $nextRowWorkingSetItems, !count($nextRowWorkingSetItems), $widthLeft, $lengthLeft, $depthLeft);
            if ($orientatedItem instanceof OrientatedItem) {
                ++$packedCount;
                $widthLeft -= $orientatedItem->getWidth();
                $prevItem = $orientatedItem;
            }
        }

        return $packedCount; // this isn't scientific, but is a reasonable proxy for success from an actual forward packing
    }
}


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		* @internal
18		*/
19		class OrientatedItemFactory implements LoggerAwareInterface
20		{
21		use LoggerAwareTrait;
22
23		/** @var Box */
24		protected $box;
25
26		/**
27		* @var OrientatedItem[]
28		*/
29		protected static $emptyBoxCache = [];
30
31	19	public function __construct(Box $box)
32		{
33	19	$this->box = $box;
34	19	}
35
36		/**
37		* Get the best orientation for an item.
38		*
39		* @param Item $item
40		* @param OrientatedItem\|null $prevItem
41		* @param ItemList $nextItems
42		* @param bool $isLastItem
43		* @param int $widthLeft
44		* @param int $lengthLeft
45		* @param int $depthLeft
46		*
47		* @return OrientatedItem\|null
48		*/
49	19	public function getBestOrientation(
50		Item $item,
51		OrientatedItem $prevItem = null,
52		ItemList $nextItems,
53		$isLastItem,
54		$widthLeft,
55		$lengthLeft,
56		$depthLeft
57		) {
58	19	$possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
59	19	$usableOrientations = $this->getUsableOrientations($item, $possibleOrientations, $isLastItem);
60
61	19	if (empty($usableOrientations)) {
62	19	return null;
63		}
64
65		usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItems) {
66	19	$orientationAWidthLeft = $widthLeft - $a->getWidth();
67	19	$orientationALengthLeft = $lengthLeft - $a->getLength();
68	19	$orientationADepthLeft = $depthLeft - $a->getDepth();
69	19	$orientationBWidthLeft = $widthLeft - $b->getWidth();
70	19	$orientationBLengthLeft = $lengthLeft - $b->getLength();
71	19	$orientationBDepthLeft = $depthLeft - $b->getDepth();
72
73	19	$orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
74	19	$orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
75
76	19	if ($orientationAMinGap === 0 && ($orientationBMinGap !== 0 \|\| PHP_MAJOR_VERSION > 5)) { // prefer A if it leaves no gap
77	7	return -1;
78		}
79	15	if ($orientationBMinGap === 0) { // prefer B if it leaves no gap
80	1	return 1;
81		}
82
83		// prefer leaving room for next item in current row
84	14	if ($nextItems->count()) {
85	14	$nextItemFitA = count($this->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft));
86	14	$nextItemFitB = count($this->getPossibleOrientations($nextItems->top(), $b, $orientationBWidthLeft, $lengthLeft, $depthLeft));
87	14	if ($nextItemFitA && !$nextItemFitB) {
88		return -1;
89		}
90	14	if ($nextItemFitB && !$nextItemFitA) {
91	2	return 1;
92		}
93
94		// if not an easy either/or, do a partial lookahead
95	12	$additionalPackedA = $this->calculateAdditionalItemsPackedWithThisOrientation($a, $nextItems, $widthLeft, $lengthLeft, $depthLeft);
96	12	$additionalPackedB = $this->calculateAdditionalItemsPackedWithThisOrientation($b, $nextItems, $widthLeft, $lengthLeft, $depthLeft);
97	12	if ($additionalPackedA !== $additionalPackedB) {
98	2	return $additionalPackedB - $additionalPackedA;
99		}
100		}
101		// otherwise prefer leaving minimum possible gap, or the greatest footprint
102	11	return ($orientationADepthLeft - $orientationBDepthLeft) ?: ($orientationAMinGap - $orientationBMinGap) ?: ($a->getSurfaceFootprint() - $b->getSurfaceFootprint());
103	19	});
104
105	19	$bestFit = reset($usableOrientations);
106	19	$this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]);
107
108	19	return $bestFit;
109		}
110
111		/**
112		* Find all possible orientations for an item.
113		*
114		* @param Item $item
115		* @param OrientatedItem\|null $prevItem
116		* @param int $widthLeft
117		* @param int $lengthLeft
118		* @param int $depthLeft
119		*
120		* @return OrientatedItem[]
121		*/
122	19	public function getPossibleOrientations(
123		Item $item,
124		OrientatedItem $prevItem = null,
125		$widthLeft,
126		$lengthLeft,
127		$depthLeft
128		) {
129	19	$orientations = [];
130
131		//Special case items that are the same as what we just packed - keep orientation
132	19	if ($prevItem && $this->isSameDimensions($prevItem->getItem(), $item)) {
133	15	$orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
134		} else {
135		//simple 2D rotation
136	19	$orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
137	19	$orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
138		}
139
140		//remove any that simply don't fit
141		return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
142	19	return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
143	19	});
144		}
145
146		/**
147		* @param Item $item
148		* @return OrientatedItem[]
149		*/
150	19	public function getPossibleOrientationsInEmptyBox(Item $item)
151		{
152	19	$cacheKey = $item->getWidth() .
153	19	'\|' .
154	19	$item->getLength() .
155	19	'\|' .
156	19	$item->getDepth() .
157	19	'\|' .
158	19	$this->box->getInnerWidth() .
159	19	'\|' .
160	19	$this->box->getInnerLength() .
161	19	'\|' .
162	19	$this->box->getInnerDepth();
163
164	19	if (isset(static::$emptyBoxCache[$cacheKey])) {
165	16	$orientations = static::$emptyBoxCache[$cacheKey];
166		} else {
167	17	$orientations = $this->getPossibleOrientations(
168	17	$item,
169	17	null,
170	17	$this->box->getInnerWidth(),
171	17	$this->box->getInnerLength(),
172	17	$this->box->getInnerDepth()
173		);
174	17	static::$emptyBoxCache[$cacheKey] = $orientations;
175		}
176
177	19	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...
178		}
179
180		/**
181		* @param Item $item
182		* @param OrientatedItem[] $possibleOrientations
183		* @param bool $isLastItem
184		*
185		* @return OrientatedItem[]
186		*/
187	19	protected function getUsableOrientations(
188		Item $item,
189		$possibleOrientations,
190		$isLastItem
191		) {
192	19	$orientationsToUse = $stableOrientations = $unstableOrientations = [];
193
194		// Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
195	19	foreach ($possibleOrientations as $orientation) {
196	19	if ($orientation->isStable()) {
197	19	$stableOrientations[] = $orientation;
198		} else {
199	19	$unstableOrientations[] = $orientation;
200		}
201		}
202
203		/*
204		* We prefer to use stable orientations only, but allow unstable ones if either
205		* the item is the last one left to pack OR
206		* the item doesn't fit in the box any other way
207		*/
208	19	if (count($stableOrientations) > 0) {
209	19	$orientationsToUse = $stableOrientations;
210	19	} elseif (count($unstableOrientations) > 0) {
211		$stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);
212
213		if ($isLastItem \|\| count($stableOrientationsInEmptyBox) === 0) {
214		$orientationsToUse = $unstableOrientations;
215		}
216		}
217
218	19	return $orientationsToUse;
219		}
220
221		/**
222		* Return the orientations for this item if it were to be placed into the box with nothing else.
223		*
224		* @param Item $item
225		* @return array
226		*/
227		protected function getStableOrientationsInEmptyBox(Item $item)
228		{
229		$orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);
230
231		return array_filter(
232		$orientationsInEmptyBox,
233		function (OrientatedItem $orientation) {
234		return $orientation->isStable();
235		}
236		);
237		}
238
239		/**
240		* Compare two items to see if they have same dimensions.
241		*
242		* @param Item $itemA
243		* @param Item $itemB
244		*
245		* @return bool
246		*/
247	18	protected function isSameDimensions(Item $itemA, Item $itemB)
248		{
249	18	$itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
250	18	$itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
251	18	sort($itemADimensions);
252	18	sort($itemBDimensions);
253
254	18	return $itemADimensions === $itemBDimensions;
255		}
256
257		/**
258		* Approximation of a forward-looking packing.
259		*
260		* Not an actual packing, that has additional logic regarding constraints and stackability, this focuses
261		* purely on fit.
262		*
263		* @param OrientatedItem $prevItem
264		* @param ItemList $nextItems
265		* @param int $originalWidthLeft
266		* @param int $originalLengthLeft
267		* @param int $depthLeft
268		* @return int
269		*/
270	12	protected function calculateAdditionalItemsPackedWithThisOrientation(
271		OrientatedItem $prevItem,
272		ItemList $nextItems,
273		$originalWidthLeft,
274		$originalLengthLeft,
275		$depthLeft
276		) {
277	12	$packedCount = 0;
278
279		// first try packing into current row
280	12	$currentRowWorkingSetItems = clone $nextItems;
281	12	$nextRowWorkingSetItems = new ItemList();
282	12	$widthLeft = $originalWidthLeft - $prevItem->getWidth();
283	12	$lengthLeft = $originalLengthLeft;
284	12	while (count($currentRowWorkingSetItems) > 0 && $widthLeft > 0) {
285	12	$itemToPack = $currentRowWorkingSetItems->extract();
286	12	$orientatedItem = $this->getBestOrientation($itemToPack, $prevItem, $currentRowWorkingSetItems, !count($currentRowWorkingSetItems), $widthLeft, $lengthLeft, $depthLeft);
287	12	if ($orientatedItem instanceof OrientatedItem) {
288	6	++$packedCount;
289	6	$widthLeft -= $orientatedItem->getWidth();
290	6	$prevItem = $orientatedItem;
291		} else {
292	8	$nextRowWorkingSetItems->insert($itemToPack);
293		}
294		}
295
296		// then see what happens if we try in the next row
297	12	$widthLeft = $originalWidthLeft;
298	12	$lengthLeft = $originalLengthLeft - $prevItem->getLength();
299	12	while (count($nextRowWorkingSetItems) > 0 && $widthLeft > 0) {
300	8	$itemToPack = $nextRowWorkingSetItems->extract();
301	8	$orientatedItem = $this->getBestOrientation($itemToPack, $prevItem, $nextRowWorkingSetItems, !count($nextRowWorkingSetItems), $widthLeft, $lengthLeft, $depthLeft);
302	8	if ($orientatedItem instanceof OrientatedItem) {
303	1	++$packedCount;
304	1	$widthLeft -= $orientatedItem->getWidth();
305	1	$prevItem = $orientatedItem;
306		}
307		}
308
309	12	return $packedCount; // this isn't scientific, but is a reasonable proxy for success from an actual forward packing
310		}
311		}
312

dvdoug / BoxPacker

Push — 1.x-dev ( b2df86...afef98 )

calculateAdditionalItemsPackedWithThisOrientation() B

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like