VolumePacker::packAcrossWidthOnly() - Code Metrics - Inspection of "Merge branch '3.x'" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 0042a3...0bad10 )

by Doug

created 2021-03-08 21:04 UTC

VolumePacker::packAcrossWidthOnly() A

↳ Parent: VolumePacker

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	2
CRAP Score	1

Importance

Changes

Metric	Value
cc	1
eloc	1
c	0
b	0
f	0
nc	1
nop	0
dl	0
loc	3
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 function array_map;
use function count;
use function max;
use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerInterface;
use Psr\Log\NullLogger;

/**
 * Actual packer.
 *
 * @author Doug Wright
 */
class VolumePacker implements LoggerAwareInterface
{
    /**
     * The logger instance.
     *
     * @var LoggerInterface
     */
    protected $logger;

    /**
     * Box to pack items into.
     *
     * @var Box
     */
    protected $box;

    /**
     * List of items to be packed.
     *
     * @var ItemList
     */
    protected $items;

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

    /**
     * Whether the packer should only try packing along the width.
     *
     * @var bool
     */
    protected $packAcrossWidthOnly = false;

    /**
     * @var LayerPacker
     */
    private $layerPacker;

    /**
     * @var bool
     */
    private $hasConstrainedItems;

    /**
     * @var bool
     */
    private $hasNoRotationItems;

    /**
     * Constructor.
     */
    public function __construct(Box $box, ItemList $items)
    {
        $this->box = $box;
        $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;
    }

    /**
     * @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->getItems()->count() === $this->items->count()) {
                return $boxPermutation;
            }

            $boxPermutations[] = $boxPermutation;
        }

        usort($boxPermutations, static function (PackedBox $a, PackedBox $b) {
            return $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]);

        /** @var PackedLayer[] $layers */
        $layers = [];
        $items = clone $this->items;

        while ($items->count() > 0) {
            $layerStartDepth = static::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, $layers, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, 0, true);
            if (count($preliminaryLayer->getItems()) === 0) {
                break;
            }

            if ($preliminaryLayer->getDepth() === $preliminaryLayer->getItems()[0]->getDepth()) { // 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, $layers, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, $preliminaryLayer->getDepth(), 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 function (PackedLayer $layer) {
                return $layer->getEndX();
            }, $layers));
            $layers[] = $this->layerPacker->packLayer($items, $this->getPackedItemList($layers), $layers, 0, $boxWidth - $maxLayerWidth, $boxLength, $this->box->getInnerDepth(), $this->box->getInnerDepth(), false);

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

dvdoug / BoxPacker

Push — master ( 0042a3...0bad10 )

VolumePacker::packAcrossWidthOnly() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like