Packer::doVolumePacking() - Code Metrics - Inspection of "Future proof changes to ItemList implementation by..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — data_structures ( b3e6cb )

by Doug

created 2017-10-23 17:51 UTC

Packer::doVolumePacking() C

↳ Parent: Packer

Complexity

Conditions	10
Paths	37

Size

Total Lines	51
Code Lines	27

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	51
rs	6
c	0
b	0
f	0
cc	10
eloc	27
nc	37
nop	0

How to fix Long Method Complexity

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

use function array_unshift;
use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\LogLevel;
use Psr\Log\NullLogger;

/**
 * Actual packer
 * @author Doug Wright
 * @package BoxPacker
 */
class Packer implements LoggerAwareInterface
{
    use LoggerAwareTrait;

    /**
     * Number of boxes at which balancing weight is deemed not worth it
     * @var int
     */
    protected $maxBoxesToBalanceWeight = 12;

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

    /**
     * List of box sizes available to pack items into
     * @var BoxList
     */
    protected $boxes;

    /**
     * Constructor
     */
    public function __construct()
    {
        $this->items = new ItemList();
        $this->boxes = new BoxList();

        $this->logger = new NullLogger();
    }

    /**
     * Add item to be packed
     * @param Item $item
     * @param int  $qty
     */
    public function addItem(Item $item, int $qty = 1): void
    {
        for ($i = 0; $i < $qty; $i++) {
            $this->items->insert($item);
        }
        $this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}");
    }

    /**
     * Set a list of items all at once
     * @param iterable $items
     */
    public function setItems(iterable $items): void
    {
        if ($items instanceof ItemList) {
            $this->items = clone $items;
        } else {
            $this->items = new ItemList();
            foreach ($items as $item) {
                $this->items->insert($item);
            }
        }
    }

    /**
     * Add box size
     * @param Box $box
     */
    public function addBox(Box $box): void
    {
        $this->boxes->insert($box);
        $this->logger->log(LogLevel::INFO, "added box {$box->getReference()}");
    }

    /**
     * Add a pre-prepared set of boxes all at once
     * @param BoxList $boxList
     */
    public function setBoxes(BoxList $boxList): void
    {
        $this->boxes = $boxList;
    }

    /**
     * Number of boxes at which balancing weight is deemed not worth the extra computation time
     * @return int
     */
    public function getMaxBoxesToBalanceWeight(): int
    {
        return $this->maxBoxesToBalanceWeight;
    }

    /**
     * Number of boxes at which balancing weight is deemed not worth the extra computation time
     * @param int $maxBoxesToBalanceWeight
     */
    public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight)
    {
        $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
    }

    /**
     * Pack items into boxes
     *
     * @return PackedBoxList
     */
    public function pack(): PackedBoxList
    {
        $packedBoxes = $this->doVolumePacking();

        //If we have multiple boxes, try and optimise/even-out weight distribution
        if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
            $redistributor = new WeightRedistributor($this->boxes);
            $redistributor->setLogger($this->logger);
            $packedBoxes = $redistributor->redistributeWeight($packedBoxes);
        }

        $this->logger->log(LogLevel::INFO, "packing completed, {$packedBoxes->count()} boxes");
        return $packedBoxes;
    }

    /**
     * Pack items into boxes using the principle of largest volume item first
     *
     * @throws ItemTooLargeException
     * @return PackedBoxList
     */
    public function doVolumePacking(): PackedBoxList
    {

        $packedBoxes = new PackedBoxList;

        //Keep going until everything packed
        while ($this->items->count()) {
            $packedBoxesIteration = [];

            //Loop through boxes starting with smallest, see what happens
            foreach ($this->boxes as $box) {
                $volumePacker = new VolumePacker($box, clone $this->items);
                $volumePacker->setLogger($this->logger);
                $packedBox = $volumePacker->pack();
                if ($packedBox->getItems()->count()) {
                    $packedBoxesIteration[] = $packedBox;

                    //Have we found a single box that contains everything?
                    if ($packedBox->getItems()->count() === $this->items->count()) {
                        break;
                    }
                }
            }

            //Check iteration was productive
            if (!$packedBoxesIteration) {

                throw new ItemTooLargeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box', $this->items->top());
            }

            //Find best box of iteration, and remove packed items from unpacked list
            $bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
            $unPackedItems = iterator_to_array($this->items, false);
            foreach ($bestBox->getItems() as $packedItem) {
                foreach ($unPackedItems as $unpackedKey => $unpackedItem) {
                    if ($packedItem->getItem() === $unpackedItem) {
                        unset($unPackedItems[$unpackedKey]);
                        break;
                    }
                }
            }
            $unpackedItemList = new ItemList();
            foreach ($unPackedItems as $unpackedItem) {
                $unpackedItemList->insert($unpackedItem);
            }
            $this->items = $unpackedItemList;
            $packedBoxes->insert($bestBox);

        }

        return $packedBoxes;
    }

    /**
     * @param PackedBox[] $packedBoxes
     *
     * @return PackedBox
     */
    private function findBestBoxFromIteration($packedBoxes): PackedBox
    {
        usort($packedBoxes, [$this, 'compare']);
        return array_shift($packedBoxes);
    }

    /**
     * @param PackedBox $boxA
     * @param PackedBox $boxB
     *
     * @return int
     */
    private static function compare(PackedBox $boxA, PackedBox $boxB): int

    {
        $choice = $boxB->getItems()->count() <=> $boxA->getItems()->count();
        if ($choice === 0) {
            $choice = $boxA->getInnerVolume() <=> $boxB->getInnerVolume();
        }
        if ($choice === 0) {
            $choice = $boxA->getWeight() <=> $boxB->getWeight();
        }
        return $choice;
    }
}


1		<?php
2		/**
3		* Box packing (3D bin packing, knapsack problem)
4		* @package BoxPacker
5		* @author Doug Wright
6		*/
7		declare(strict_types=1);
8		namespace DVDoug\BoxPacker;
9
10		use function array_unshift;
11		use Psr\Log\LoggerAwareInterface;
12		use Psr\Log\LoggerAwareTrait;
13		use Psr\Log\LogLevel;
14		use Psr\Log\NullLogger;
15
16		/**
17		* Actual packer
18		* @author Doug Wright
19		* @package BoxPacker
20		*/
21		class Packer implements LoggerAwareInterface
22		{
23		use LoggerAwareTrait;
24
25		/**
26		* Number of boxes at which balancing weight is deemed not worth it
27		* @var int
28		*/
29		protected $maxBoxesToBalanceWeight = 12;
30
31		/**
32		* List of items to be packed
33		* @var ItemList
34		*/
35		protected $items;
36
37		/**
38		* List of box sizes available to pack items into
39		* @var BoxList
40		*/
41		protected $boxes;
42
43		/**
44		* Constructor
45		*/
46		public function __construct()
47		{
48		$this->items = new ItemList();
49		$this->boxes = new BoxList();
50
51		$this->logger = new NullLogger();
52		}
53
54		/**
55		* Add item to be packed
56		* @param Item $item
57		* @param int $qty
58		*/
59		public function addItem(Item $item, int $qty = 1): void
60		{
61		for ($i = 0; $i < $qty; $i++) {
62		$this->items->insert($item);
63		}
64		$this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}");
65		}
66
67		/**
68		* Set a list of items all at once
69		* @param iterable $items
70		*/
71		public function setItems(iterable $items): void
72		{
73		if ($items instanceof ItemList) {
74		$this->items = clone $items;
75		} else {
76		$this->items = new ItemList();
77		foreach ($items as $item) {
78		$this->items->insert($item);
79		}
80		}
81		}
82
83		/**
84		* Add box size
85		* @param Box $box
86		*/
87		public function addBox(Box $box): void
88		{
89		$this->boxes->insert($box);
90		$this->logger->log(LogLevel::INFO, "added box {$box->getReference()}");
91		}
92
93		/**
94		* Add a pre-prepared set of boxes all at once
95		* @param BoxList $boxList
96		*/
97		public function setBoxes(BoxList $boxList): void
98		{
99		$this->boxes = $boxList;
100		}
101
102		/**
103		* Number of boxes at which balancing weight is deemed not worth the extra computation time
104		* @return int
105		*/
106		public function getMaxBoxesToBalanceWeight(): int
107		{
108		return $this->maxBoxesToBalanceWeight;
109		}
110
111		/**
112		* Number of boxes at which balancing weight is deemed not worth the extra computation time
113		* @param int $maxBoxesToBalanceWeight
114		*/
115		public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight)
116		{
117		$this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
118		}
119
120		/**
121		* Pack items into boxes
122		*
123		* @return PackedBoxList
124		*/
125		public function pack(): PackedBoxList
126		{
127		$packedBoxes = $this->doVolumePacking();
128
129		//If we have multiple boxes, try and optimise/even-out weight distribution
130		if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
131		$redistributor = new WeightRedistributor($this->boxes);
132		$redistributor->setLogger($this->logger);
133		$packedBoxes = $redistributor->redistributeWeight($packedBoxes);
134		}
135
136		$this->logger->log(LogLevel::INFO, "packing completed, {$packedBoxes->count()} boxes");
137		return $packedBoxes;
138		}
139
140		/**
141		* Pack items into boxes using the principle of largest volume item first
142		*
143		* @throws ItemTooLargeException
144		* @return PackedBoxList
145		*/
146		public function doVolumePacking(): PackedBoxList
147		{
148
149		$packedBoxes = new PackedBoxList;
150
151		//Keep going until everything packed
152		while ($this->items->count()) {
153		$packedBoxesIteration = [];
154
155		//Loop through boxes starting with smallest, see what happens
156		foreach ($this->boxes as $box) {
157		$volumePacker = new VolumePacker($box, clone $this->items);
158		$volumePacker->setLogger($this->logger);
159		$packedBox = $volumePacker->pack();
160		if ($packedBox->getItems()->count()) {
161		$packedBoxesIteration[] = $packedBox;
162
163		//Have we found a single box that contains everything?
164		if ($packedBox->getItems()->count() === $this->items->count()) {
165		break;
166		}
167		}
168		}
169
170		//Check iteration was productive
171		if (!$packedBoxesIteration) {
		0 ignored issues – show Bug Best Practice introduced 2017-10-23 18:10 UTC by Report Bug Copy Issue Report The expression `$packedBoxesIteration` of type `array` is implicitly converted to a boolean; are you sure this is intended? If so, consider using `empty($expr)` instead to make it clear that you intend to check for an array without elements. This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent. Consider making the comparison explicit by using `empty(..)` or `! empty(...)` instead. Loading history...
172		throw new ItemTooLargeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box', $this->items->top());
173		}
174
175		//Find best box of iteration, and remove packed items from unpacked list
176		$bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
177		$unPackedItems = iterator_to_array($this->items, false);
178		foreach ($bestBox->getItems() as $packedItem) {
179		foreach ($unPackedItems as $unpackedKey => $unpackedItem) {
180		if ($packedItem->getItem() === $unpackedItem) {
181		unset($unPackedItems[$unpackedKey]);
182		break;
183		}
184		}
185		}
186		$unpackedItemList = new ItemList();
187		foreach ($unPackedItems as $unpackedItem) {
188		$unpackedItemList->insert($unpackedItem);
189		}
190		$this->items = $unpackedItemList;
191		$packedBoxes->insert($bestBox);
192
193		}
194
195		return $packedBoxes;
196		}
197
198		/**
199		* @param PackedBox[] $packedBoxes
200		*
201		* @return PackedBox
202		*/
203		private function findBestBoxFromIteration($packedBoxes): PackedBox
204		{
205		usort($packedBoxes, [$this, 'compare']);
206		return array_shift($packedBoxes);
207		}
208
209		/**
210		* @param PackedBox $boxA
211		* @param PackedBox $boxB
212		*
213		* @return int
214		*/
215	View Code Duplication	private static function compare(PackedBox $boxA, PackedBox $boxB): int
		0 ignored issues – show Duplication introduced 2017-10-23 18:10 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
216		{
217		$choice = $boxB->getItems()->count() <=> $boxA->getItems()->count();
218		if ($choice === 0) {
219		$choice = $boxA->getInnerVolume() <=> $boxB->getInnerVolume();
220		}
221		if ($choice === 0) {
222		$choice = $boxA->getWeight() <=> $boxB->getWeight();
223		}
224		return $choice;
225		}
226		}
227

dvdoug / BoxPacker

Push — data_structures ( b3e6cb )

Packer::doVolumePacking() C

Complexity

Size

Duplication

Importance

How to fix Long Method Complexity

Long Method

Duplication Side-by-Side

Filter issues like