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

Completed

Push — master ( 18f60e...12452e )

by Doug

created 2018-09-30 20:37 UTC

OrientatedItemFactory::getPossibleOrientations() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	6
Paths	3

Size

Total Lines	30
Code Lines	13

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	12
CRAP Score	6

Importance

Changes

Metric	Value
cc	6
eloc	13
nc	3
nop	5
dl	0
loc	30
ccs	12
cts	12
cp	1
crap	6
rs	9.2222
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\LoggerAwareTrait;
use function array_filter;
use function count;
use function min;
use function reset;
use function sort;
use function usort;

/**
 * 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,
        ?Item $nextItem,
        bool $isLastItem,
        int $widthLeft,
        int $lengthLeft,
        int $depthLeft
    ): ?OrientatedItem {
        $possibleOrientations = $this->getPossibleOrientations($this->item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
        $usableOrientations = $this->getUsableOrientations($possibleOrientations, $isLastItem);

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

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

dvdoug / BoxPacker

Push — master ( 18f60e...12452e )

OrientatedItemFactory::getPossibleOrientations() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like