VolumePacker::beStrictAboutItemOrdering() - Code Metrics - Inspection of "Add a flag to enforce strict item ordering. Fixes..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 3.x ( 071761...f78397 )

by Doug

created 2021-11-26 19:30 UTC

VolumePacker::beStrictAboutItemOrdering() A

↳ Parent: VolumePacker

Complexity

Conditions	1
Paths	1

Size

Total Lines	4
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	3
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	3
cts	3
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;
use function reset;
use function usort;

/**
 * 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 bool
     */
    protected $beStrictAboutItemOrdering = false;

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

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

    /**
     * Constructor.
     */
    public function __construct(Box $box, ItemList $items)
    {
        $this->box = $box;
        $this->items = clone $items;

        $this->logger = new NullLogger();

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

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

dvdoug / BoxPacker

Push — 3.x ( 071761...f78397 )

VolumePacker::beStrictAboutItemOrdering() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like