VolumePacker::beStrictAboutItemOrdering() - Code Metrics - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

VolumePacker::beStrictAboutItemOrdering() A
last analyzed 2025-02-06 23:05 UTC

↳ Parent: VolumePacker

Complexity

Conditions	1
Paths	1

Size

Total Lines	4
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	2
CRAP Score	1

Importance

Changes

Metric	Value
cc	1
eloc	2
c	0
b	0
f	0
nc	1
nop	1
dl	0
loc	4
ccs	2
cts	2
cp	1
crap	1
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
    {
        $orientatedItemFactory = new OrientatedItemFactory($this->box);
        $orientatedItemFactory->setLogger($this->logger);
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}", ['box' => $this->box]);

        // Sometimes "space available" decisions depend on orientation of the box, so try both ways
        $rotationsToTest = [false];
        if (!$this->packAcrossWidthOnly && !$this->hasNoRotationItems) {
            $rotationsToTest[] = true;
        }

        // The orientation of the first item can have an outsized effect on the rest of the placement, so special-case
        // that and try everything

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

            $specialFirstItemOrientations = [null];
            if (!$this->singlePassMode) {
                $specialFirstItemOrientations = $orientatedItemFactory->getPossibleOrientations($this->items->top(), null, $boxWidth, $boxLength, $this->box->getInnerDepth(), 0, 0, 0, new PackedItemList()) ?: [null];
            }

            foreach ($specialFirstItemOrientations as $firstItemOrientation) {
                $boxPermutation = $this->packRotation($boxWidth, $boxLength, $firstItemOrientation);
                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, ?OrientatedItem $firstItemOrientation): 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);

            if ($packedItemList->count() > 0) {
                $firstItemOrientation = null;
            }

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

        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, null);

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

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

dvdoug / BoxPacker

VolumePacker::beStrictAboutItemOrdering() A last analyzed 2025-02-06 23:05 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

VolumePacker::beStrictAboutItemOrdering() A
last analyzed 2025-02-06 23:05 UTC