DVDoug\BoxPacker\OrientatedItemFactory

Complexity

Total Complexity

59

Size/Duplication

Total Lines	371
Duplicated Lines	0 %

Test Coverage

Coverage

100%

Importance

Changes	23
Bugs	3	Features	0

10 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	4	1
A	setSinglePassMode()	0	3	1
A	getBestOrientation()	0	55	5
C	getPossibleOrientations()	0	50	14
A	getStableOrientationsInEmptyBox()	0	8	1
B	calculateAdditionalItemsPackedWithThisOrientation()	0	68	7
B	lookAheadDecider()	0	20	7
C	exactFitDecider()	0	30	13
B	getUsableOrientations()	0	30	7
A	getPossibleOrientationsInEmptyBox()	0	34	3

<?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 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;

    /**
     * Whether the packer is in single-pass mode.
     *
     * @var bool
     */
    protected $singlePassMode = false;

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

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

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

    public function setSinglePassMode(bool $singlePassMode): void
    {
        $this->singlePassMode = $singlePassMode;
    }

    /**
     * Get the best orientation for an item.
     */
    public function getBestOrientation(
        Item $item,
        ?OrientatedItem $prevItem,
        ItemList $nextItems,
        int $widthLeft,
        int $lengthLeft,
        int $depthLeft,
        int $rowLength,
        int $x,
        int $y,
        int $z,
        PackedItemList $prevPackedItemList
    ): ?OrientatedItem {
        $this->logger->debug(
            "evaluating item {$item->getDescription()} for fit",
            [
                'item' => $item,
                'space' => [
                    'widthLeft' => $widthLeft,
                    'lengthLeft' => $lengthLeft,
                    'depthLeft' => $depthLeft,
                ],
            ]
        );

        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
        $usableOrientations = $this->getUsableOrientations($item, $possibleOrientations);

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

        usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList) {
            //Prefer exact fits in width/length/depth order
            $exactFitDecider = $this->exactFitDecider($a, $b, $widthLeft, $lengthLeft, $depthLeft);
            if ($exactFitDecider !== 0) {
                return $exactFitDecider;
            }

            // prefer leaving room for next item(s)
            $followingItemDecider = $this->lookAheadDecider($nextItems, $a, $b, $widthLeft, $lengthLeft, $depthLeft, $rowLength, $x, $y, $z, $prevPackedItemList);
            if ($followingItemDecider !== 0) {
                return $followingItemDecider;
            }

            // otherwise prefer leaving minimum possible gap, or the greatest footprint
            $orientationAMinGap = min($widthLeft - $a->getWidth(), $lengthLeft - $a->getLength());
            $orientationBMinGap = min($widthLeft - $b->getWidth(), $lengthLeft - $b->getLength());

            return $orientationAMinGap <=> $orientationBMinGap ?: $a->getSurfaceFootprint() <=> $b->getSurfaceFootprint();
        });

        $this->logger->debug('Selected best fit orientation', ['orientation' => $usableOrientations[0]]);

        return $usableOrientations[0];
    }

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

        //Special case items that are the same as what we just packed - keep orientation
        if ($prevItem && $item === $prevItem->getItem() && $prevItem->getWidth() <= $widthLeft && $prevItem->getLength() <= $lengthLeft && $prevItem->getDepth() <= $depthLeft) {
            $orientations[] = $prevItem; // reuse the existing object for a small speed boost
        } else {
            //Might be different a item but having same dimensions - apply same rule
            if ($prevItem && $prevItem->isSameDimensions($item)) {
                $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
            foreach ($orientationsDimensions as $dimensions) {
                if ($dimensions[0] <= $widthLeft && $dimensions[1] <= $lengthLeft && $dimensions[2] <= $depthLeft) {
                    $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) {
                return $i->getItem()->canBePacked($box, $prevPackedItemList, $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());

The method canBePacked() does not exist on DVDoug\BoxPacker\Item. It seems like you code against a sub-type of DVDoug\BoxPacker\Item such as DVDoug\BoxPacker\ConstrainedPlacementItem or DVDoug\BoxPacker\Test\ConstrainedPlacementByCountTestItem or DVDoug\BoxPacker\Test\ConstrainedPlacementNoStackingTestItem.

            });
        }

        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;

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.

    }

    /**
     * @param OrientatedItem[] $possibleOrientations
     *
     * @return OrientatedItem[]
     */
    protected function getUsableOrientations(
        Item $item,
        array $possibleOrientations
    ): 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() || $this->box->getInnerDepth() === $orientation->getDepth()) {
                $stableOrientations[] = $orientation;
            } else {
                $unstableOrientations[] = $orientation;
            }
        }

        /*
         * We prefer to use stable orientations only, but allow unstable ones if
         * 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 (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();
            }
        );
    }

    /**
     * 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 {
        if ($this->singlePassMode) {
            return 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, $itemsToPack);
            $tempPacker->setSinglePassMode(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, $itemsToPack);
            $tempPacker->setSinglePassMode(true);
            $nextRowsPacked = $tempPacker->pack();
            /** @var PackedItem $packedItem */
            foreach ($nextRowsPacked->getItems() as $packedItem) {
                $itemsToPack->remove($packedItem->getItem());
            }

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

            static::$lookaheadCache[$cacheKey] = $packedCount;
        }

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

    private function exactFitDecider(OrientatedItem $a, OrientatedItem $b, int $widthLeft, int $lengthLeft, int $depthLeft): int
    {
        $orientationAWidthLeft = $widthLeft - $a->getWidth();
        $orientationBWidthLeft = $widthLeft - $b->getWidth();
        if ($orientationAWidthLeft === 0 && $orientationBWidthLeft > 0) {
            return -1;
        }
        if ($orientationBWidthLeft === 0 && $orientationAWidthLeft > 0) {
            return 1;
        }

        $orientationALengthLeft = $lengthLeft - $a->getLength();
        $orientationBLengthLeft = $lengthLeft - $b->getLength();
        if ($orientationALengthLeft === 0 && $orientationBLengthLeft > 0) {
            return -1;
        }
        if ($orientationBLengthLeft === 0 && $orientationALengthLeft > 0) {
            return 1;
        }

        $orientationADepthLeft = $depthLeft - $a->getDepth();
        $orientationBDepthLeft = $depthLeft - $b->getDepth();
        if ($orientationADepthLeft === 0 && $orientationBDepthLeft > 0) {
            return -1;
        }
        if ($orientationBDepthLeft === 0 && $orientationADepthLeft > 0) {
            return 1;
        }

        return 0;
    }

    private function lookAheadDecider(ItemList $nextItems, OrientatedItem $a, OrientatedItem $b, int $widthLeft, int $lengthLeft, int $depthLeft, int $rowLength, int $x, int $y, int $z, PackedItemList $prevPackedItemList): int
    {
        if ($nextItems->count() === 0) {
            return 0;
        }

        $nextItemFitA = $this->getPossibleOrientations($nextItems->top(), $a, $widthLeft - $a->getWidth(), $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
        $nextItemFitB = $this->getPossibleOrientations($nextItems->top(), $b, $widthLeft - $b->getWidth(), $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);

        return $additionalPackedB <=> $additionalPackedA ?: 0;
    }
}