OrientatedItemFactory::getStableOrientationsInEmptyBox() - Code Metrics - Inspection of "Remove non-benchmark tests" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — issue_187 ( fb1b49...8952f9 )

by Doug

created 2020-01-21 20:33 UTC

getStableOrientationsInEmptyBox() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	1
Paths	1

Size

Total Lines	8
Code Lines	5

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	5
CRAP Score	1

Importance

Changes

Metric	Value
cc	1
eloc	5
c	0
b	0
f	0
nc	1
nop	1
dl	0
loc	8
ccs	5
cts	5
cp	1
crap	1
rs	10

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

namespace DVDoug\BoxPacker;

use function array_filter;
use function count;
use function min;
use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\NullLogger;
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 = [];

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

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

    /**
     * Get the best orientation for an item.
     */
    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.
     *
     * @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;
    }

    /**
     * @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 OrientatedItem[] $possibleOrientations
     *
     * @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.
     */
    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.
     */
    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.
     */
    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

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

        /** @var Item $itemToPack */
        foreach ($itemsToPack as $itemToPack) {
            $cacheKey .= '|' .
                $itemToPack->getWidth() .
                '|' .
                $itemToPack->getLength() .
                '|' .
                $itemToPack->getDepth() .
                '|' .
                $itemToPack->getWeight() .
                '|' .
                ($itemToPack->getKeepFlat() ? '1' : '0');
        }

        if (!isset(static::$lookaheadCache[$cacheKey])) {
            $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]);

            static::$lookaheadCache[$cacheKey] = $nextItems->count() - $itemsToPack->count();
        }

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


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

dvdoug / BoxPacker

Push — issue_187 ( fb1b49...8952f9 )

getStableOrientationsInEmptyBox() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like