VolumePacker::getRemainingWeightAllowed() - Code Metrics - Inspection of "Split the lookahead part of the sort routine in a..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 34b8f8...cb2e0a )

by Doug

created 2020-04-12 19:31 UTC

VolumePacker::getRemainingWeightAllowed() A

↳ Parent: Project

Complexity

Conditions	2
Paths	2

Size

Total Lines	8
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	5
CRAP Score	2

Importance

Changes	2
Bugs	0	Features	0

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

<?php
/**
 * Box packing (3D bin packing, knapsack problem).
 *
 * @author Doug Wright
 */
declare(strict_types=1);

namespace DVDoug\BoxPacker;

use function count;
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;

    /**
     * @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);
    }

    /**
     * @internal
     */
    public function setSinglePassMode(bool $singlePassMode): void
    {
        $this->singlePassMode = $singlePassMode;
        $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->singlePassMode) {
            $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);
            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());
            }
        }

        if ($this->box->getInnerWidth() !== $boxWidth) {
            $layers = static::rotateLayersNinetyDegrees($layers);
        }

        if (!$this->singlePassMode && !$this->hasConstrainedItems) {
            $layers = static::stabiliseLayers($layers);
        }

        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[] $layers
     */
    private static function stabiliseLayers(array $layers): array
    {
        $stabiliser = new LayerStabiliser();

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

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

dvdoug / BoxPacker

Push — master ( 34b8f8...cb2e0a )

VolumePacker::getRemainingWeightAllowed() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like