OrientatedItemFactory::calculateAdditionalItemsPackedWithThisOrientation() - Code Metrics - Inspection of "Allow core packing tests to cover helper objects t..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( b3e52b...de1ca6 )

by Doug

created 2019-09-01 18:30 UTC

calculateAdditionalItemsPackedWithThisOrientation() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	3
Paths	4

Size

Total Lines	35
Code Lines	17

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	18
CRAP Score	3

Importance

Changes	2
Bugs	0	Features	0

Metric	Value
cc	3
eloc	17
c	2
b	0
f	0
nc	4
nop	6
dl	0
loc	35
ccs	18
cts	18
cp	1
crap	3
rs	9.7

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

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

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

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

    /**
     * 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
     * @param int                 $rowLength
     * @param int                 $x
     * @param int                 $y
     * @param int                 $z
     * @param PackedItemList      $prevPackedItemList
     *
     * @return OrientatedItem|null
     */
    public function getBestOrientation(
        Item $item,
        ?OrientatedItem $prevItem,
        ItemList $nextItems,
        bool $isLastItem,
        int $widthLeft,
        int $lengthLeft,
        int $depthLeft,
        int $rowLength,
        int $x,
        int $y,
        int $z,
        PackedItemList $prevPackedItemList
    ): ?OrientatedItem {
        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
        $usableOrientations = $this->getUsableOrientations($item, $possibleOrientations, $isLastItem);

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

        usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList) {
            $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) { // 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, $x, $y, $z, $prevPackedItemList));
                $nextItemFitB = count($this->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);
                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
     * @param int                 $x
     * @param int                 $y
     * @param int                 $z
     * @param PackedItemList      $prevPackedItemList
     *
     * @return OrientatedItem[]
     */
    public function getPossibleOrientations(
        Item $item,
        ?OrientatedItem $prevItem,
        int $widthLeft,
        int $lengthLeft,
        int $depthLeft,
        int $x,
        int $y,
        int $z,
        PackedItemList $prevPackedItemList
    ): array {
        $orientations = $orientationsDimensions = [];

        $isSame = false;
        if ($prevItem) {
            $itemADimensions = [$item->getWidth(), $item->getLength(), $item->getDepth()];
            $itemBDimensions = [$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()];
            sort($itemADimensions);
            sort($itemBDimensions);
            $isSame = ($itemADimensions === $itemBDimensions);
        }

        //Special case items that are the same as what we just packed - keep orientation
        if ($isSame && $prevItem) {
            $orientationsDimensions[] = [$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()];
        } else {
            //simple 2D rotation
            $orientationsDimensions[] = [$item->getWidth(), $item->getLength(), $item->getDepth()];
            $orientationsDimensions[] = [$item->getLength(), $item->getWidth(), $item->getDepth()];

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

        //remove any that simply don't fit
        $orientationsDimensions = array_unique($orientationsDimensions, SORT_REGULAR);
        $orientationsDimensions = array_filter($orientationsDimensions, static function (array $i) use ($widthLeft, $lengthLeft, $depthLeft) {
            return $i[0] <= $widthLeft && $i[1] <= $lengthLeft && $i[2] <= $depthLeft;
        });

        foreach ($orientationsDimensions as $dimensions) {
            $orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]);
        }

        if ($item instanceof ConstrainedPlacementItem) {
            $box = $this->box;
            $orientations = array_filter($orientations, static function (OrientatedItem $i) use ($box, $x, $y, $z, $prevPackedItemList) {
                /** @var ConstrainedPlacementItem $constrainedItem */
                $constrainedItem = $i->getItem();

                return $constrainedItem->canBePacked($box, $prevPackedItemList, $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());
            });
        }

        return $orientations;
    }

    /**
     * @param  Item             $item
     * @return OrientatedItem[]
     */
    public function getPossibleOrientationsInEmptyBox(Item $item): array
    {
        $cacheKey = $item->getWidth() .
            '|' .
            $item->getLength() .
            '|' .
            $item->getDepth() .
            '|' .
            ($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(
                $item,
                null,
                $this->box->getInnerWidth(),
                $this->box->getInnerLength(),
                $this->box->getInnerDepth(),
                0,
                0,
                0,
                new PackedItemList()
            );
            static::$emptyBoxCache[$cacheKey] = $orientations;
        }

        return $orientations;

    }

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

    /**
     * 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
     * @param  int            $currentRowLengthBeforePacking
     * @return int
     */
    protected function calculateAdditionalItemsPackedWithThisOrientation(
        OrientatedItem $prevItem,
        ItemList $nextItems,
        int $originalWidthLeft,
        int $originalLengthLeft,
        int $depthLeft,
        int $currentRowLengthBeforePacking
    ): int {
        $packedCount = 0;

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

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

        $tempBox = new WorkingVolume($originalWidthLeft - $prevItem->getWidth(), $currentRowLength, $depthLeft, PHP_INT_MAX);
        $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
        $tempPacker->setLookAheadMode(true);
        $remainingRowPacked = $tempPacker->pack();
        /** @var PackedItem $packedItem */
        foreach ($remainingRowPacked->getItems() as $packedItem) {
            $itemsToPack->remove($packedItem->getItem());
        }

        $tempBox = new WorkingVolume($originalWidthLeft, $originalLengthLeft - $currentRowLength, $depthLeft, PHP_INT_MAX);
        $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
        $tempPacker->setLookAheadMode(true);
        $nextRowsPacked = $tempPacker->pack();
        /** @var PackedItem $packedItem */
        foreach ($nextRowsPacked->getItems() as $packedItem) {
            $itemsToPack->remove($packedItem->getItem());
        }

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

        return $nextItems->count() - $itemsToPack->count();
    }
}


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 Psr\Log\NullLogger;
14		use function array_filter;
15		use function count;
16		use function min;
17		use function reset;
18		use function sort;
19		use function usort;
20
21		/**
22		* Figure out orientations for an item and a given set of dimensions.
23		*
24		* @author Doug Wright
25		* @internal
26		*/
27		class OrientatedItemFactory implements LoggerAwareInterface
28		{
29		use LoggerAwareTrait;
30
31		/** @var Box */
32		protected $box;
33
34		/**
35		* @var OrientatedItem[]
36		*/
37		protected static $emptyBoxCache = [];
38
39	48	public function __construct(Box $box)
40		{
41	48	$this->box = $box;
42	48	$this->logger = new NullLogger();
43	48	}
44
45		/**
46		* Get the best orientation for an item.
47		*
48		* @param Item $item
49		* @param OrientatedItem\|null $prevItem
50		* @param ItemList $nextItems
51		* @param bool $isLastItem
52		* @param int $widthLeft
53		* @param int $lengthLeft
54		* @param int $depthLeft
55		* @param int $rowLength
56		* @param int $x
57		* @param int $y
58		* @param int $z
59		* @param PackedItemList $prevPackedItemList
60		*
61		* @return OrientatedItem\|null
62		*/
63	48	public function getBestOrientation(
64		Item $item,
65		?OrientatedItem $prevItem,
66		ItemList $nextItems,
67		bool $isLastItem,
68		int $widthLeft,
69		int $lengthLeft,
70		int $depthLeft,
71		int $rowLength,
72		int $x,
73		int $y,
74		int $z,
75		PackedItemList $prevPackedItemList
76		): ?OrientatedItem {
77	48	$possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
78	48	$usableOrientations = $this->getUsableOrientations($item, $possibleOrientations, $isLastItem);
79
80	48	if (empty($usableOrientations)) {
81	46	return null;
82		}
83
84		usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList) {
85	25	$orientationAWidthLeft = $widthLeft - $a->getWidth();
86	25	$orientationALengthLeft = $lengthLeft - $a->getLength();
87	25	$orientationADepthLeft = $depthLeft - $a->getDepth();
88	25	$orientationBWidthLeft = $widthLeft - $b->getWidth();
89	25	$orientationBLengthLeft = $lengthLeft - $b->getLength();
90	25	$orientationBDepthLeft = $depthLeft - $b->getDepth();
91
92	25	$orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
93	25	$orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
94
95	25	if ($orientationAMinGap === 0) { // prefer A if it leaves no gap
96	12	return -1;
97		}
98	22	if ($orientationBMinGap === 0) { // prefer B if it leaves no gap
99	13	return 1;
100		}
101
102		// prefer leaving room for next item in current row
103	21	if ($nextItems->count()) {
104	18	$nextItemFitA = count($this->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList));
105	18	$nextItemFitB = count($this->getPossibleOrientations($nextItems->top(), $b, $orientationBWidthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList));
106	18	if ($nextItemFitA && !$nextItemFitB) {
107	7	return -1;
108		}
109	16	if ($nextItemFitB && !$nextItemFitA) {
110	5	return 1;
111		}
112
113		// if not an easy either/or, do a partial lookahead
114	14	$additionalPackedA = $this->calculateAdditionalItemsPackedWithThisOrientation($a, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
115	14	$additionalPackedB = $this->calculateAdditionalItemsPackedWithThisOrientation($b, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
116	14	if ($additionalPackedA !== $additionalPackedB) {
117	5	return $additionalPackedB <=> $additionalPackedA;
118		}
119		}
120		// otherwise prefer leaving minimum possible gap, or the greatest footprint
121	17	return $orientationADepthLeft <=> $orientationBDepthLeft ?: $orientationAMinGap <=> $orientationBMinGap ?: $a->getSurfaceFootprint() <=> $b->getSurfaceFootprint();
122	47	});
123
124	47	$bestFit = reset($usableOrientations);
125	47	$this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]);
126
127	47	return $bestFit;
128		}
129
130		/**
131		* Find all possible orientations for an item.
132		*
133		* @param Item $item
134		* @param OrientatedItem\|null $prevItem
135		* @param int $widthLeft
136		* @param int $lengthLeft
137		* @param int $depthLeft
138		* @param int $x
139		* @param int $y
140		* @param int $z
141		* @param PackedItemList $prevPackedItemList
142		*
143		* @return OrientatedItem[]
144		*/
145	48	public function getPossibleOrientations(
146		Item $item,
147		?OrientatedItem $prevItem,
148		int $widthLeft,
149		int $lengthLeft,
150		int $depthLeft,
151		int $x,
152		int $y,
153		int $z,
154		PackedItemList $prevPackedItemList
155		): array {
156	48	$orientations = $orientationsDimensions = [];
157
158	48	$isSame = false;
159	48	if ($prevItem) {
160	45	$itemADimensions = [$item->getWidth(), $item->getLength(), $item->getDepth()];
161	45	$itemBDimensions = [$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()];
162	45	sort($itemADimensions);
163	45	sort($itemBDimensions);
164	45	$isSame = ($itemADimensions === $itemBDimensions);
165		}
166
167		//Special case items that are the same as what we just packed - keep orientation
168	48	if ($isSame && $prevItem) {
169	38	$orientationsDimensions[] = [$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()];
170		} else {
171		//simple 2D rotation
172	48	$orientationsDimensions[] = [$item->getWidth(), $item->getLength(), $item->getDepth()];
173	48	$orientationsDimensions[] = [$item->getLength(), $item->getWidth(), $item->getDepth()];
174
175		//add 3D rotation if we're allowed
176	48	if (!$item->getKeepFlat()) {
177	29	$orientationsDimensions[] = [$item->getWidth(), $item->getDepth(), $item->getLength()];
178	29	$orientationsDimensions[] = [$item->getLength(), $item->getDepth(), $item->getWidth()];
179	29	$orientationsDimensions[] = [$item->getDepth(), $item->getWidth(), $item->getLength()];
180	29	$orientationsDimensions[] = [$item->getDepth(), $item->getLength(), $item->getWidth()];
181		}
182		}
183
184		//remove any that simply don't fit
185	48	$orientationsDimensions = array_unique($orientationsDimensions, SORT_REGULAR);
186		$orientationsDimensions = array_filter($orientationsDimensions, static function (array $i) use ($widthLeft, $lengthLeft, $depthLeft) {
187	48	return $i[0] <= $widthLeft && $i[1] <= $lengthLeft && $i[2] <= $depthLeft;
188	48	});
189
190	48	foreach ($orientationsDimensions as $dimensions) {
191	47	$orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]);
192		}
193
194	48	if ($item instanceof ConstrainedPlacementItem) {
195	2	$box = $this->box;
196		$orientations = array_filter($orientations, static function (OrientatedItem $i) use ($box, $x, $y, $z, $prevPackedItemList) {
197		/** @var ConstrainedPlacementItem $constrainedItem */
198	2	$constrainedItem = $i->getItem();
199
200	2	return $constrainedItem->canBePacked($box, $prevPackedItemList, $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());
201	2	});
202		}
203
204	48	return $orientations;
205		}
206
207		/**
208		* @param Item $item
209		* @return OrientatedItem[]
210		*/
211	5	public function getPossibleOrientationsInEmptyBox(Item $item): array
212		{
213	5	$cacheKey = $item->getWidth() .
214	5	'\|' .
215	5	$item->getLength() .
216	5	'\|' .
217	5	$item->getDepth() .
218	5	'\|' .
219	5	($item->getKeepFlat() ? '2D' : '3D') .
220	5	'\|' .
221	5	$this->box->getInnerWidth() .
222	5	'\|' .
223	5	$this->box->getInnerLength() .
224	5	'\|' .
225	5	$this->box->getInnerDepth();
226
227	5	if (isset(static::$emptyBoxCache[$cacheKey])) {
228	4	$orientations = static::$emptyBoxCache[$cacheKey];
229		} else {
230	5	$orientations = $this->getPossibleOrientations(
231	5	$item,
232	5	null,
233	5	$this->box->getInnerWidth(),
234	5	$this->box->getInnerLength(),
235	5	$this->box->getInnerDepth(),
236	5	0,
237	5	0,
238	5	0,
239	5	new PackedItemList()
240		);
241	5	static::$emptyBoxCache[$cacheKey] = $orientations;
242		}
243
244	5	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...
245		}
246
247		/**
248		* @param Item $item
249		* @param OrientatedItem[] $possibleOrientations
250		* @param bool $isLastItem
251		*
252		* @return OrientatedItem[]
253		*/
254	48	protected function getUsableOrientations(
255		Item $item,
256		$possibleOrientations,
257		bool $isLastItem
258		): array {
259	48	$orientationsToUse = $stableOrientations = $unstableOrientations = [];
260
261		// Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
262	48	foreach ($possibleOrientations as $orientation) {
263	47	if ($orientation->isStable()) {
264	45	$stableOrientations[] = $orientation;
265		} else {
266	47	$unstableOrientations[] = $orientation;
267		}
268		}
269
270		/*
271		* We prefer to use stable orientations only, but allow unstable ones if either
272		* the item is the last one left to pack OR
273		* the item doesn't fit in the box any other way
274		*/
275	48	if (count($stableOrientations) > 0) {
276	45	$orientationsToUse = $stableOrientations;
277	46	} elseif (count($unstableOrientations) > 0) {
278	5	$stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);
279
280	5	if ($isLastItem \|\| count($stableOrientationsInEmptyBox) === 0) {
281	3	$orientationsToUse = $unstableOrientations;
282		}
283		}
284
285	48	return $orientationsToUse;
286		}
287
288		/**
289		* Return the orientations for this item if it were to be placed into the box with nothing else.
290		*
291		* @param Item $item
292		* @return array
293		*/
294	5	protected function getStableOrientationsInEmptyBox(Item $item): array
295		{
296	5	$orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);
297
298	5	return array_filter(
299	5	$orientationsInEmptyBox,
300		function (OrientatedItem $orientation) {
301	5	return $orientation->isStable();
302	5	}
303		);
304		}
305
306		/**
307		* Compare two items to see if they have same dimensions.
308		*
309		* @param Item $itemA
310		* @param Item $itemB
311		*
312		* @return bool
313		*/
314	17	public function isSameDimensions(Item $itemA, Item $itemB): bool
315		{
316	17	$itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
317	17	$itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
318	17	sort($itemADimensions);
319	17	sort($itemBDimensions);
320
321	17	return $itemADimensions === $itemBDimensions;
322		}
323
324		/**
325		* Approximation of a forward-looking packing.
326		*
327		* Not an actual packing, that has additional logic regarding constraints and stackability, this focuses
328		* purely on fit.
329		*
330		* @param OrientatedItem $prevItem
331		* @param ItemList $nextItems
332		* @param int $originalWidthLeft
333		* @param int $originalLengthLeft
334		* @param int $depthLeft
335		* @param int $currentRowLengthBeforePacking
336		* @return int
337		*/
338	14	protected function calculateAdditionalItemsPackedWithThisOrientation(
339		OrientatedItem $prevItem,
340		ItemList $nextItems,
341		int $originalWidthLeft,
342		int $originalLengthLeft,
343		int $depthLeft,
344		int $currentRowLengthBeforePacking
345		): int {
346	14	$packedCount = 0;
347
348	14	$currentRowLength = max($prevItem->getLength(), $currentRowLengthBeforePacking);
349
350	14	$itemsToPack = $nextItems->topN(8); // cap lookahead as this gets recursive and slow
351
352	14	$tempBox = new WorkingVolume($originalWidthLeft - $prevItem->getWidth(), $currentRowLength, $depthLeft, PHP_INT_MAX);
353	14	$tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
354	14	$tempPacker->setLookAheadMode(true);
355	14	$remainingRowPacked = $tempPacker->pack();
356		/** @var PackedItem $packedItem */
357	14	foreach ($remainingRowPacked->getItems() as $packedItem) {
358	14	$itemsToPack->remove($packedItem->getItem());
359		}
360
361	14	$tempBox = new WorkingVolume($originalWidthLeft, $originalLengthLeft - $currentRowLength, $depthLeft, PHP_INT_MAX);
362	14	$tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
363	14	$tempPacker->setLookAheadMode(true);
364	14	$nextRowsPacked = $tempPacker->pack();
365		/** @var PackedItem $packedItem */
366	14	foreach ($nextRowsPacked->getItems() as $packedItem) {
367	10	$itemsToPack->remove($packedItem->getItem());
368		}
369
370	14	$this->logger->debug('Lookahead with orientation', ['packedCount' => $packedCount, 'orientatedItem' => $prevItem]);
371
372	14	return $nextItems->count() - $itemsToPack->count();
373		}
374		}
375

dvdoug / BoxPacker

Push — master ( b3e52b...de1ca6 )

calculateAdditionalItemsPackedWithThisOrientation() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like