VolumePacker::getPackedItemList() - Code Metrics - Inspection of "Bump the babylon group in /visualiser with 2 updat..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Pull Request — master (#549)

unknown

created 2023-08-18 02:59 UTC

VolumePacker::getPackedItemList() A

↳ Parent: VolumePacker

Complexity

Conditions	3
Paths	3

Size

Total Lines	10
Code Lines	5

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	6
CRAP Score	3

Importance

Changes	4
Bugs	0	Features	0

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

<?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\LoggerInterface;
use Psr\Log\NullLogger;

use function array_map;
use function count;
use function max;
use function reset;
use function usort;

/**
 * Actual packer.
 */
class VolumePacker implements LoggerAwareInterface
{
    protected LoggerInterface $logger;

    protected ItemList $items;

    protected bool $singlePassMode = false;

    protected bool $packAcrossWidthOnly = false;

    private readonly LayerPacker $layerPacker;

    protected bool $beStrictAboutItemOrdering = false;

    private readonly bool $hasConstrainedItems;

    private readonly bool $hasNoRotationItems;

    public function __construct(protected Box $box, ItemList $items)
    {
        $this->items = clone $items;

        $this->logger = new NullLogger();

        $this->hasConstrainedItems = $items->hasConstrainedItems();

        $this->hasNoRotationItems = $items->hasNoRotationItems();


        $this->layerPacker = new LayerPacker($this->box);

        $this->layerPacker->setLogger($this->logger);
    }

    /**
     * Sets a logger.
     */
    public function setLogger(LoggerInterface $logger): void
    {
        $this->logger = $logger;
        $this->layerPacker->setLogger($logger);
    }

    public function packAcrossWidthOnly(): void
    {
        $this->packAcrossWidthOnly = true;
    }

    public function beStrictAboutItemOrdering(bool $beStrict): void
    {
        $this->beStrictAboutItemOrdering = $beStrict;
        $this->layerPacker->beStrictAboutItemOrdering($beStrict);
    }

    /**
     * @internal
     */
    public function setSinglePassMode(bool $singlePassMode): void
    {
        $this->singlePassMode = $singlePassMode;
        if ($singlePassMode) {
            $this->packAcrossWidthOnly = true;
        }
        $this->layerPacker->setSinglePassMode($singlePassMode);
    }

    /**
     * Pack as many items as possible into specific given box.
     *
     * @return PackedBox packed box
     */
    public function pack(): PackedBox
    {
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}", ['box' => $this->box]);

        $rotationsToTest = [false];
        if (!$this->packAcrossWidthOnly && !$this->hasNoRotationItems) {
            $rotationsToTest[] = true;
        }

        $boxPermutations = [];
        foreach ($rotationsToTest as $rotation) {
            if ($rotation) {
                $boxWidth = $this->box->getInnerLength();
                $boxLength = $this->box->getInnerWidth();
            } else {
                $boxWidth = $this->box->getInnerWidth();
                $boxLength = $this->box->getInnerLength();
            }

            $boxPermutation = $this->packRotation($boxWidth, $boxLength);
            if ($boxPermutation->items->count() === $this->items->count()) {
                return $boxPermutation;
            }

            $boxPermutations[] = $boxPermutation;
        }

        usort($boxPermutations, static fn (PackedBox $a, PackedBox $b) => $b->getVolumeUtilisation() <=> $a->getVolumeUtilisation());

        return reset($boxPermutations);
    }

    /**
     * Pack as many items as possible into specific given box.
     *
     * @return PackedBox packed box
     */
    private function packRotation(int $boxWidth, int $boxLength): PackedBox
    {
        $this->logger->debug("[EVALUATING ROTATION] {$this->box->getReference()}", ['width' => $boxWidth, 'length' => $boxLength]);
        $this->layerPacker->setBoxIsRotated($this->box->getInnerWidth() !== $boxWidth);

        $layers = [];
        $items = clone $this->items;

        while ($items->count() > 0) {
            $layerStartDepth = self::getCurrentPackedDepth($layers);
            $packedItemList = $this->getPackedItemList($layers);

            // do a preliminary layer pack to get the depth used
            $preliminaryItems = clone $items;
            $preliminaryLayer = $this->layerPacker->packLayer($preliminaryItems, clone $packedItemList, 0, 0, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, 0, true);
            if (count($preliminaryLayer->getItems()) === 0) {
                break;
            }

            $preliminaryLayerDepth = $preliminaryLayer->getDepth();
            if ($preliminaryLayerDepth === $preliminaryLayer->getItems()[0]->depth) { // preliminary === final
                $layers[] = $preliminaryLayer;
                $items = $preliminaryItems;
            } else { // redo with now-known-depth so that we can stack to that height from the first item
                $layers[] = $this->layerPacker->packLayer($items, $packedItemList, 0, 0, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, $preliminaryLayerDepth, true);
            }
        }

        if (!$this->singlePassMode && $layers) {
            $layers = $this->stabiliseLayers($layers);

            // having packed layers, there may be tall, narrow gaps at the ends that can be utilised
            $maxLayerWidth = max(array_map(static fn (PackedLayer $layer) => $layer->getEndX(), $layers));
            $layers[] = $this->layerPacker->packLayer($items, $this->getPackedItemList($layers), $maxLayerWidth, 0, 0, $boxWidth, $boxLength, $this->box->getInnerDepth(), $this->box->getInnerDepth(), false);

            $maxLayerLength = max(array_map(static fn (PackedLayer $layer) => $layer->getEndY(), $layers));
            $layers[] = $this->layerPacker->packLayer($items, $this->getPackedItemList($layers), 0, $maxLayerLength, 0, $boxWidth, $boxLength, $this->box->getInnerDepth(), $this->box->getInnerDepth(), false);
        }

        $layers = $this->correctLayerRotation($layers, $boxWidth);

        return new PackedBox($this->box, $this->getPackedItemList($layers));
    }

    /**
     * During packing, it is quite possible that layers have been created that aren't physically stable
     * i.e. they overhang the ones below.
     *
     * This function reorders them so that the ones with the greatest surface area are placed at the bottom
     *
     * @param  PackedLayer[] $oldLayers
     * @return PackedLayer[]
     */
    private function stabiliseLayers(array $oldLayers): array
    {
        if ($this->hasConstrainedItems || $this->beStrictAboutItemOrdering) { // constraints include position, so cannot change
            return $oldLayers;
        }

        $stabiliser = new LayerStabiliser();

        return $stabiliser->stabilise($oldLayers);
    }

    /**
     * Swap back width/length of the packed items to match orientation of the box if needed.
     *
     * @param PackedLayer[] $oldLayers
     *
     * @return PackedLayer[]
     */
    private function correctLayerRotation(array $oldLayers, int $boxWidth): array
    {
        if ($this->box->getInnerWidth() === $boxWidth) {
            return $oldLayers;
        }

        $newLayers = [];
        foreach ($oldLayers as $originalLayer) {
            $newLayer = new PackedLayer();
            foreach ($originalLayer->getItems() as $item) {
                $packedItem = new PackedItem($item->item, $item->y, $item->x, $item->z, $item->length, $item->width, $item->depth);
                $newLayer->insert($packedItem);
            }
            $newLayers[] = $newLayer;
        }

        return $newLayers;
    }

    /**
     * Generate a single list of items packed.
     * @param PackedLayer[] $layers
     */
    private function getPackedItemList(array $layers): PackedItemList
    {
        $packedItemList = new PackedItemList();
        foreach ($layers as $layer) {
            foreach ($layer->getItems() as $packedItem) {
                $packedItemList->insert($packedItem);
            }
        }

        return $packedItemList;
    }

    /**
     * Return the current packed depth.
     *
     * @param PackedLayer[] $layers
     */
    private static function getCurrentPackedDepth(array $layers): int
    {
        $depth = 0;
        foreach ($layers as $layer) {
            $depth += $layer->getDepth();
        }

        return $depth;
    }
}


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\LoggerInterface;
13		use Psr\Log\NullLogger;
14
15		use function array_map;
16		use function count;
17		use function max;
18		use function reset;
19		use function usort;
20
21		/**
22		* Actual packer.
23		*/
24		class VolumePacker implements LoggerAwareInterface
25		{
26		protected LoggerInterface $logger;
27
28		protected ItemList $items;
29
30		protected bool $singlePassMode = false;
31
32		protected bool $packAcrossWidthOnly = false;
33
34		private readonly LayerPacker $layerPacker;
35
36		protected bool $beStrictAboutItemOrdering = false;
37
38		private readonly bool $hasConstrainedItems;
39
40		private readonly bool $hasNoRotationItems;
41
42	84	public function __construct(protected Box $box, ItemList $items)
43		{
44	84	$this->items = clone $items;
45
46	84	$this->logger = new NullLogger();
47
48	84	$this->hasConstrainedItems = $items->hasConstrainedItems();
		0 ignored issues – show Bug introduced 2022-12-05 18:54 UTC by Report Bug Copy Issue Report The property `hasConstrainedItems` is declared read-only in `DVDoug\BoxPacker\VolumePacker`. Loading history...
49	84	$this->hasNoRotationItems = $items->hasNoRotationItems();
		0 ignored issues – show Bug introduced 2022-12-05 18:54 UTC by Report Bug Copy Issue Report The property `hasNoRotationItems` is declared read-only in `DVDoug\BoxPacker\VolumePacker`. Loading history...
50
51	84	$this->layerPacker = new LayerPacker($this->box);
		0 ignored issues – show Bug introduced 2022-12-05 18:54 UTC by Report Bug Copy Issue Report The property `layerPacker` is declared read-only in `DVDoug\BoxPacker\VolumePacker`. Loading history...
52	84	$this->layerPacker->setLogger($this->logger);
53		}
54
55		/**
56		* Sets a logger.
57		*/
58	24	public function setLogger(LoggerInterface $logger): void
59		{
60	24	$this->logger = $logger;
61	24	$this->layerPacker->setLogger($logger);
62		}
63
64		public function packAcrossWidthOnly(): void
65		{
66		$this->packAcrossWidthOnly = true;
67		}
68
69	24	public function beStrictAboutItemOrdering(bool $beStrict): void
70		{
71	24	$this->beStrictAboutItemOrdering = $beStrict;
72	24	$this->layerPacker->beStrictAboutItemOrdering($beStrict);
73		}
74
75		/**
76		* @internal
77		*/
78	4	public function setSinglePassMode(bool $singlePassMode): void
79		{
80	4	$this->singlePassMode = $singlePassMode;
81	4	if ($singlePassMode) {
82	4	$this->packAcrossWidthOnly = true;
83		}
84	4	$this->layerPacker->setSinglePassMode($singlePassMode);
85		}
86
87		/**
88		* Pack as many items as possible into specific given box.
89		*
90		* @return PackedBox packed box
91		*/
92	84	public function pack(): PackedBox
93		{
94	84	$this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}", ['box' => $this->box]);
95
96	84	$rotationsToTest = [false];
97	84	if (!$this->packAcrossWidthOnly && !$this->hasNoRotationItems) {
98	84	$rotationsToTest[] = true;
99		}
100
101	84	$boxPermutations = [];
102	84	foreach ($rotationsToTest as $rotation) {
103	84	if ($rotation) {
104	16	$boxWidth = $this->box->getInnerLength();
105	16	$boxLength = $this->box->getInnerWidth();
106		} else {
107	84	$boxWidth = $this->box->getInnerWidth();
108	84	$boxLength = $this->box->getInnerLength();
109		}
110
111	84	$boxPermutation = $this->packRotation($boxWidth, $boxLength);
112	84	if ($boxPermutation->items->count() === $this->items->count()) {
113	72	return $boxPermutation;
114		}
115
116	18	$boxPermutations[] = $boxPermutation;
117		}
118
119	18	usort($boxPermutations, static fn (PackedBox $a, PackedBox $b) => $b->getVolumeUtilisation() <=> $a->getVolumeUtilisation());
120
121	18	return reset($boxPermutations);
122		}
123
124		/**
125		* Pack as many items as possible into specific given box.
126		*
127		* @return PackedBox packed box
128		*/
129	84	private function packRotation(int $boxWidth, int $boxLength): PackedBox
130		{
131	84	$this->logger->debug("[EVALUATING ROTATION] {$this->box->getReference()}", ['width' => $boxWidth, 'length' => $boxLength]);
132	84	$this->layerPacker->setBoxIsRotated($this->box->getInnerWidth() !== $boxWidth);
133
134	84	$layers = [];
135	84	$items = clone $this->items;
136
137	84	while ($items->count() > 0) {
138	84	$layerStartDepth = self::getCurrentPackedDepth($layers);
139	84	$packedItemList = $this->getPackedItemList($layers);
140
141		// do a preliminary layer pack to get the depth used
142	84	$preliminaryItems = clone $items;
143	84	$preliminaryLayer = $this->layerPacker->packLayer($preliminaryItems, clone $packedItemList, 0, 0, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, 0, true);
144	84	if (count($preliminaryLayer->getItems()) === 0) {
145	14	break;
146		}
147
148	82	$preliminaryLayerDepth = $preliminaryLayer->getDepth();
149	82	if ($preliminaryLayerDepth === $preliminaryLayer->getItems()[0]->depth) { // preliminary === final
150	80	$layers[] = $preliminaryLayer;
151	80	$items = $preliminaryItems;
152		} else { // redo with now-known-depth so that we can stack to that height from the first item
153	4	$layers[] = $this->layerPacker->packLayer($items, $packedItemList, 0, 0, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, $preliminaryLayerDepth, true);
154		}
155		}
156
157	84	if (!$this->singlePassMode && $layers) {
158	82	$layers = $this->stabiliseLayers($layers);
159
160		// having packed layers, there may be tall, narrow gaps at the ends that can be utilised
161	82	$maxLayerWidth = max(array_map(static fn (PackedLayer $layer) => $layer->getEndX(), $layers));
162	82	$layers[] = $this->layerPacker->packLayer($items, $this->getPackedItemList($layers), $maxLayerWidth, 0, 0, $boxWidth, $boxLength, $this->box->getInnerDepth(), $this->box->getInnerDepth(), false);
163
164	82	$maxLayerLength = max(array_map(static fn (PackedLayer $layer) => $layer->getEndY(), $layers));
165	82	$layers[] = $this->layerPacker->packLayer($items, $this->getPackedItemList($layers), 0, $maxLayerLength, 0, $boxWidth, $boxLength, $this->box->getInnerDepth(), $this->box->getInnerDepth(), false);
166		}
167
168	84	$layers = $this->correctLayerRotation($layers, $boxWidth);
169
170	84	return new PackedBox($this->box, $this->getPackedItemList($layers));
171		}
172
173		/**
174		* During packing, it is quite possible that layers have been created that aren't physically stable
175		* i.e. they overhang the ones below.
176		*
177		* This function reorders them so that the ones with the greatest surface area are placed at the bottom
178		*
179		* @param PackedLayer[] $oldLayers
180		* @return PackedLayer[]
181		*/
182	82	private function stabiliseLayers(array $oldLayers): array
183		{
184	82	if ($this->hasConstrainedItems \|\| $this->beStrictAboutItemOrdering) { // constraints include position, so cannot change
185		return $oldLayers;
186		}
187
188	82	$stabiliser = new LayerStabiliser();
189
190	82	return $stabiliser->stabilise($oldLayers);
191		}
192
193		/**
194		* Swap back width/length of the packed items to match orientation of the box if needed.
195		*
196		* @param PackedLayer[] $oldLayers
197		*
198		* @return PackedLayer[]
199		*/
200	84	private function correctLayerRotation(array $oldLayers, int $boxWidth): array
201		{
202	84	if ($this->box->getInnerWidth() === $boxWidth) {
203	84	return $oldLayers;
204		}
205
206		$newLayers = [];
207		foreach ($oldLayers as $originalLayer) {
208		$newLayer = new PackedLayer();
209		foreach ($originalLayer->getItems() as $item) {
210		$packedItem = new PackedItem($item->item, $item->y, $item->x, $item->z, $item->length, $item->width, $item->depth);
211		$newLayer->insert($packedItem);
212		}
213		$newLayers[] = $newLayer;
214		}
215
216		return $newLayers;
217		}
218
219		/**
220		* Generate a single list of items packed.
221		* @param PackedLayer[] $layers
222		*/
223	84	private function getPackedItemList(array $layers): PackedItemList
224		{
225	84	$packedItemList = new PackedItemList();
226	84	foreach ($layers as $layer) {
227	82	foreach ($layer->getItems() as $packedItem) {
228	82	$packedItemList->insert($packedItem);
229		}
230		}
231
232	84	return $packedItemList;
233		}
234
235		/**
236		* Return the current packed depth.
237		*
238		* @param PackedLayer[] $layers
239		*/
240	84	private static function getCurrentPackedDepth(array $layers): int
241		{
242	84	$depth = 0;
243	84	foreach ($layers as $layer) {
244	54	$depth += $layer->getDepth();
245		}
246
247	84	return $depth;
248		}
249		}
250

dvdoug / BoxPacker

Pull Request — master (#549)

VolumePacker::getPackedItemList() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like