OrientatedItemFactory::generatePermutations() - Code Metrics - Inspection of "Add option to enforce packing direction within the..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 3.x ( 3ac6d2...8ba8a4 )

by Doug

created 2021-03-08 21:00 UTC

OrientatedItemFactory::generatePermutations() A

↳ Parent: OrientatedItemFactory

Complexity

Conditions	4
Paths	3

Size

Total Lines	22
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	12
CRAP Score	4

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	4
eloc	12
c	1
b	0
f	0
nc	3
nop	2
dl	0
loc	22
ccs	12
cts	12
cp	1
crap	4
rs	9.8666

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

    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,
        bool $considerStability
    ): ?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 = $considerStability ? $this->getUsableOrientations($item, $possibleOrientations) : $possibleOrientations;

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

        $sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList);
        $sorter->setLogger($this->logger);
        usort($usableOrientations, $sorter);

        $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 {
        $permutations = $this->generatePermutations($item, $prevItem);

        //remove any that simply don't fit
        $orientations = [];
        foreach ($permutations 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 && !$this->box instanceof WorkingVolume) {
            $orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList) {
                return $i->getItem()->canBePacked($this->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,
        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();
            }
        );
    }

    private function generatePermutations(Item $item, ?OrientatedItem $prevItem): array
    {
        $permutations = [];

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

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

        return $permutations;
    }
}


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 Psr\Log\LoggerAwareInterface;
14		use Psr\Log\LoggerAwareTrait;
15		use Psr\Log\NullLogger;
16		use function usort;
17
18		/**
19		* Figure out orientations for an item and a given set of dimensions.
20		*
21		* @author Doug Wright
22		* @internal
23		*/
24		class OrientatedItemFactory implements LoggerAwareInterface
25		{
26		use LoggerAwareTrait;
27
28		/** @var Box */
29		protected $box;
30
31		/**
32		* Whether the packer is in single-pass mode.
33		*
34		* @var bool
35		*/
36		protected $singlePassMode = false;
37
38		/**
39		* @var OrientatedItem[]
40		*/
41		protected static $emptyBoxCache = [];
42
43	56	public function __construct(Box $box)
44		{
45	56	$this->box = $box;
46	56	$this->logger = new NullLogger();
47	56	}
48
49	49	public function setSinglePassMode(bool $singlePassMode): void
50		{
51	49	$this->singlePassMode = $singlePassMode;
52	49	}
53
54		/**
55		* Get the best orientation for an item.
56		*/
57	54	public function getBestOrientation(
58		Item $item,
59		?OrientatedItem $prevItem,
60		ItemList $nextItems,
61		int $widthLeft,
62		int $lengthLeft,
63		int $depthLeft,
64		int $rowLength,
65		int $x,
66		int $y,
67		int $z,
68		PackedItemList $prevPackedItemList,
69		bool $considerStability
70		): ?OrientatedItem {
71	54	$this->logger->debug(
72	54	"evaluating item {$item->getDescription()} for fit",
73		[
74	54	'item' => $item,
75		'space' => [
76	54	'widthLeft' => $widthLeft,
77	54	'lengthLeft' => $lengthLeft,
78	54	'depthLeft' => $depthLeft,
79		],
80		]
81		);
82
83	54	$possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
84	54	$usableOrientations = $considerStability ? $this->getUsableOrientations($item, $possibleOrientations) : $possibleOrientations;
85
86	54	if (empty($usableOrientations)) {
87	48	return null;
88		}
89
90	54	$sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList);
91	54	$sorter->setLogger($this->logger);
92	54	usort($usableOrientations, $sorter);
93
94	54	$this->logger->debug('Selected best fit orientation', ['orientation' => $usableOrientations[0]]);
95
96	54	return $usableOrientations[0];
97		}
98
99		/**
100		* Find all possible orientations for an item.
101		*
102		* @return OrientatedItem[]
103		*/
104	55	public function getPossibleOrientations(
105		Item $item,
106		?OrientatedItem $prevItem,
107		int $widthLeft,
108		int $lengthLeft,
109		int $depthLeft,
110		int $x,
111		int $y,
112		int $z,
113		PackedItemList $prevPackedItemList
114		): array {
115	55	$permutations = $this->generatePermutations($item, $prevItem);
116
117		//remove any that simply don't fit
118	55	$orientations = [];
119	55	foreach ($permutations as $dimensions) {
120	55	if ($dimensions[0] <= $widthLeft && $dimensions[1] <= $lengthLeft && $dimensions[2] <= $depthLeft) {
121	54	$orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]);
122		}
123		}
124
125	55	if ($item instanceof ConstrainedPlacementItem && !$this->box instanceof WorkingVolume) {
126		$orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList) {
127	3	return $i->getItem()->canBePacked($this->box, $prevPackedItemList, $x, $y, $z, $i->getWidth(), $i->getLength(), $i->getDepth());
128	3	});
129		}
130
131	55	return $orientations;
132		}
133
134		/**
135		* @return OrientatedItem[]
136		*/
137	30	public function getPossibleOrientationsInEmptyBox(Item $item): array
138		{
139	30	$cacheKey = $item->getWidth() .
140	30	'\|' .
141	30	$item->getLength() .
142	30	'\|' .
143	30	$item->getDepth() .
144	30	'\|' .
145	30	($item->getKeepFlat() ? '2D' : '3D') .
146	30	'\|' .
147	30	$this->box->getInnerWidth() .
148	30	'\|' .
149	30	$this->box->getInnerLength() .
150	30	'\|' .
151	30	$this->box->getInnerDepth();
152
153	30	if (isset(static::$emptyBoxCache[$cacheKey])) {
154	24	$orientations = static::$emptyBoxCache[$cacheKey];
155		} else {
156	26	$orientations = $this->getPossibleOrientations(
157	26	$item,
158	26	null,
159	26	$this->box->getInnerWidth(),
160	26	$this->box->getInnerLength(),
161	26	$this->box->getInnerDepth(),
162	26	0,
163	26	0,
164	26	0,
165	26	new PackedItemList()
166		);
167	26	static::$emptyBoxCache[$cacheKey] = $orientations;
168		}
169
170	30	return $orientations;
171		}
172
173		/**
174		* @param OrientatedItem[] $possibleOrientations
175		* @return OrientatedItem[]
176		*/
177	54	protected function getUsableOrientations(
178		Item $item,
179		array $possibleOrientations
180		): array {
181	54	$orientationsToUse = $stableOrientations = $unstableOrientations = [];
182
183		// Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
184	54	foreach ($possibleOrientations as $orientation) {
185	54	if ($orientation->isStable() \|\| $this->box->getInnerDepth() === $orientation->getDepth()) {
186	52	$stableOrientations[] = $orientation;
187		} else {
188	8	$unstableOrientations[] = $orientation;
189		}
190		}
191
192		/*
193		* We prefer to use stable orientations only, but allow unstable ones if
194		* the item doesn't fit in the box any other way
195		*/
196	54	if (count($stableOrientations) > 0) {
197	52	$orientationsToUse = $stableOrientations;
198	48	} elseif (count($unstableOrientations) > 0) {
199	8	$stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);
200
201	8	if (count($stableOrientationsInEmptyBox) === 0) {
202	7	$orientationsToUse = $unstableOrientations;
203		}
204		}
205
206	54	return $orientationsToUse;
207		}
208
209		/**
210		* Return the orientations for this item if it were to be placed into the box with nothing else.
211		*/
212	8	protected function getStableOrientationsInEmptyBox(Item $item): array
213		{
214	8	$orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);
215
216	8	return array_filter(
217	8	$orientationsInEmptyBox,
218		function (OrientatedItem $orientation) {
219	8	return $orientation->isStable();
220	8	}
221		);
222		}
223
224	55	private function generatePermutations(Item $item, ?OrientatedItem $prevItem): array
225		{
226	55	$permutations = [];
227
228		//Special case items that are the same as what we just packed - keep orientation
229	55	if ($prevItem && $prevItem->isSameDimensions($item)) {
230	44	$permutations[] = [$prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()];
231		} else {
232		//simple 2D rotation
233	55	$permutations[] = [$item->getWidth(), $item->getLength(), $item->getDepth()];
234	55	$permutations[] = [$item->getLength(), $item->getWidth(), $item->getDepth()];
235
236		//add 3D rotation if we're allowed
237	55	if (!$item->getKeepFlat()) {
238	37	$permutations[] = [$item->getWidth(), $item->getDepth(), $item->getLength()];
239	37	$permutations[] = [$item->getLength(), $item->getDepth(), $item->getWidth()];
240	37	$permutations[] = [$item->getDepth(), $item->getWidth(), $item->getLength()];
241	37	$permutations[] = [$item->getDepth(), $item->getLength(), $item->getWidth()];
242		}
243		}
244
245	55	return $permutations;
246		}
247		}
248

dvdoug / BoxPacker

Push — 3.x ( 3ac6d2...8ba8a4 )

OrientatedItemFactory::generatePermutations() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like