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

Completed

Push — 1.x-dev ( f03c49...17b59f )

by Doug

created 2019-12-21 18:27 UTC

getPossibleOrientationsInEmptyBox() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	2
Paths	2

Size

Total Lines	32
Code Lines	23

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	26
CRAP Score	2

Importance

Changes	3
Bugs	3	Features	0

Metric	Value
cc	2
eloc	23
c	3
b	3
f	0
nc	2
nop	1
dl	0
loc	32
ccs	26
cts	26
cp	1
crap	2
rs	9.552

<?php
/**
 * Box packing (3D bin packing, knapsack problem).
 *
 * @author Doug Wright
 */
namespace DVDoug\BoxPacker;

use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\NullLogger;

/**
 * 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.
     *
     * @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 = null,
        ItemList $nextItems,
        $isLastItem,
        $widthLeft,
        $lengthLeft,
        $depthLeft,
        $rowLength,
        $x,
        $y,
        $z,
        PackedItemList $prevPackedItemList
    ) {
        $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 && ($orientationBMinGap !== 0 || PHP_MAJOR_VERSION > 5)) { // prefer A if it leaves no gap
                return -1;
            }
            if ($orientationBMinGap === 0) { // prefer B if it leaves no gap
                return 1;
            }

            // prefer leaving room for next item in current row
            if ($nextItems->count()) {
                $nextItemFitA = count($this->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft, $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 -1;
                }
                if ($additionalPackedA < $additionalPackedB) {
                    return 1;
                }
                if ($additionalPackedA === 0) {
                    return PHP_MAJOR_VERSION > 5 ? -1 : 1;
                }
            }
            // 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 = null,
        $widthLeft,
        $lengthLeft,
        $depthLeft,
        $x,
        $y,
        $z,
        PackedItemList $prevPackedItemList
    ) {
        $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()];
        }

        //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)
    {
        $cacheKey = $item->getWidth() .
            '|' .
            $item->getLength() .
            '|' .
            $item->getDepth() .
            '|' .
            $this->box->getInnerWidth() .
            '|' .
            $this->box->getInnerLength() .
            '|' .
            $this->box->getInnerDepth();

        if (isset(static::$emptyBoxCache[$cacheKey])) {
            $orientations = static::$emptyBoxCache[$cacheKey];
        } else {
            $orientations = $this->getPossibleOrientations(
                $item,
                null,
                $this->box->getInnerWidth(),
                $this->box->getInnerLength(),
                $this->box->getInnerDepth(),
                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,
        $isLastItem
    ) {
        $orientationsToUse = $stableOrientations = $unstableOrientations = [];

        // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
        foreach ($possibleOrientations as $orientation) {
            if ($orientation->isStable()) {
                $stableOrientations[] = $orientation;
            } else {
                $unstableOrientations[] = $orientation;
            }
        }

        /*
         * We prefer to use stable orientations only, but allow unstable ones if either
         * the item is the last one left to pack OR
         * the item doesn't fit in the box any other way
         */
        if (count($stableOrientations) > 0) {
            $orientationsToUse = $stableOrientations;
        } elseif (count($unstableOrientations) > 0) {
            $stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);

            if ($isLastItem || count($stableOrientationsInEmptyBox) === 0) {
                $orientationsToUse = $unstableOrientations;
            }
        }

        return $orientationsToUse;
    }

    /**
     * Return the orientations for this item if it were to be placed into the box with nothing else.
     *
     * @param  Item  $item
     * @return array
     */
    protected function getStableOrientationsInEmptyBox(Item $item)
    {
        $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);

        return array_filter(
            $orientationsInEmptyBox,
            function (OrientatedItem $orientation) {
                return $orientation->isStable();
            }
        );
    }

    /**
     * Compare two items to see if they have same dimensions.
     *
     * @param Item $itemA
     * @param Item $itemB
     *
     * @return bool
     */
    public function isSameDimensions(Item $itemA, Item $itemB)
    {
        $itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
        $itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
        sort($itemADimensions);
        sort($itemBDimensions);

        return $itemADimensions === $itemBDimensions;
    }

    /**
     * Approximation of a forward-looking packing.
     *
     * Not an actual packing, that has additional logic regarding constraints and stackability, this focuses
     * purely on fit.
     *
     * @param  OrientatedItem $prevItem
     * @param  ItemList       $nextItems
     * @param  int            $originalWidthLeft
     * @param  int            $originalLengthLeft
     * @param  int            $depthLeft
     * @param  int            $currentRowLengthBeforePacking
     * @return int
     */
    protected function calculateAdditionalItemsPackedWithThisOrientation(
        OrientatedItem $prevItem,
        ItemList $nextItems,
        $originalWidthLeft,
        $originalLengthLeft,
        $depthLeft,
        $currentRowLengthBeforePacking
    ) {
        $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 (clone $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);
            }

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

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

dvdoug / BoxPacker

Push — 1.x-dev ( f03c49...17b59f )

getPossibleOrientationsInEmptyBox() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like