VolumePacker::pack() - Code Metrics - Inspection of "Feature/pack solid items into flatbags" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Pull Request — master (#353)

unknown

created 2022-10-15 16:04 UTC

VolumePacker::pack() B

↳ Parent: VolumePacker

Complexity

Conditions	9
Paths	13

Size

Total Lines	46
Code Lines	30

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	24
CRAP Score	9

Importance

Changes	14
Bugs	0	Features	0

Metric	Value
cc	9
eloc	30
c	14
b	0
f	0
nc	13
nop	0
dl	0
loc	46
ccs	24
cts	24
cp	1
crap	9
rs	8.0555

<?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 Box $box;

    protected ItemList $items;

    protected bool $singlePassMode = false;

    protected bool $packAcrossWidthOnly = false;

    private LayerPacker $layerPacker;

    protected bool $beStrictAboutItemOrdering = false;

    private bool $hasConstrainedItems = false;

    private bool $hasNoRotationItems = false;

    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;
    }

    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]);

        if($this->box->getType() !== 'FlatBag'){
            $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;
            }
        }else{
            $bagInitWidth = $this->box->getOuterWidth();
            for($i = 1; $i <= 50; $i++){
                $boxWidth = (int)round($bagInitWidth/100*(100-$i));
                $boxLength = (int)round($bagInitWidth/100*$i);
                $boxDepth = (int)round($this->box->getOuterDepth() - $boxLength);
                $this->box->setFlatBagDimensions($boxWidth, $boxLength, $boxDepth);
                $boxPermutation = $this->packRotation($boxWidth, $boxLength);
                if ($boxPermutation->getItems()->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]);

        $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;
            }

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

dvdoug / BoxPacker

Pull Request — master (#353)

VolumePacker::pack() B

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like