OrientatedItemFactory::getPossibleOrientationsInEmptyBox() - Code Metrics - Inspection of "Add ConstrainedPlacementItem Fixes #165" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 5d8812...a1d92b )

by Doug

created 2019-07-08 17:09 UTC

getPossibleOrientationsInEmptyBox() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	3
Paths	4

Size

Total Lines	34
Code Lines	25

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	28
CRAP Score	3

Importance

Changes	3
Bugs	3	Features	0

Metric	Value
cc	3
eloc	25
c	3
b	3
f	0
nc	4
nop	1
dl	0
loc	34
ccs	28
cts	28
cp	1
crap	3
rs	9.52

<?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
 * @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
     * @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 = [];

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

        $orientations = array_unique($orientations);

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

        if ($item instanceof ConstrainedPlacementItem) {
            $box = $this->box;
            $orientations = array_filter($orientations, 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
     */
    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;
    }

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

dvdoug / BoxPacker

Push — master ( 5d8812...a1d92b )

getPossibleOrientationsInEmptyBox() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like