Packer::setMaxBoxesToBalanceWeight() - Code Metrics - Inspection of "Bump to a version of PHP-CS-Fixer that works on PH..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 3.x ( 0d7474...922c95 )

by Doug

created 2021-01-25 20:12 UTC

Packer::setMaxBoxesToBalanceWeight() A

↳ Parent: Packer

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	2

Importance

Changes

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

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

namespace DVDoug\BoxPacker;

use function array_merge;
use function count;
use const PHP_INT_MAX;
use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\LogLevel;
use Psr\Log\NullLogger;
use SplObjectStorage;
use function usort;

/**
 * Actual packer.
 *
 * @author Doug Wright
 */
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;

    /**
     * Quantities available of each box type.
     *
     * @var SplObjectStorage
     */
    protected $boxesQtyAvailable;

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

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

    /**
     * Add item to be packed.
     */
    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()}", ['item' => $item]);
    }

    /**
     * Set a list of items all at once.
     * @param iterable|Item[] $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.
     */
    public function addBox(Box $box): void
    {
        $this->boxes->insert($box);
        $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
        $this->logger->log(LogLevel::INFO, "added box {$box->getReference()}", ['box' => $box]);
    }

    /**
     * Add a pre-prepared set of boxes all at once.
     */
    public function setBoxes(BoxList $boxList): void
    {
        $this->boxes = $boxList;
        foreach ($this->boxes as $box) {
            $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
        }
    }

    /**
     * Set the quantity of this box type available.
     */
    public function setBoxQuantity(Box $box, int $qty): void
    {
        $this->boxesQtyAvailable[$box] = $qty;
    }

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

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

    /**
     * Pack items into boxes.
     */
    public function pack(): PackedBoxList
    {
        $this->sanityPrecheck();
        $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, $this->boxesQtyAvailable);
            $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 NoBoxesAvailableException
     */
    public function doVolumePacking(bool $singlePassMode = false, bool $enforceSingleBox = false): 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->getBoxList($enforceSingleBox) as $box) {
                $volumePacker = new VolumePacker($box, $this->items);
                $volumePacker->setLogger($this->logger);
                $volumePacker->setSinglePassMode($singlePassMode);
                $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;
                    }
                }
            }

            try {
                //Find best box of iteration, and remove packed items from unpacked list
                $bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
            } catch (NoBoxesAvailableException $e) {
                if ($enforceSingleBox) {
                    return new PackedBoxList();
                }
                throw $e;
            }

            $this->items->removePackedItems($bestBox->getItems());

            $packedBoxes->insert($bestBox);
            $this->boxesQtyAvailable[$bestBox->getBox()] = $this->boxesQtyAvailable[$bestBox->getBox()] - 1;
        }

        return $packedBoxes;
    }

    /**
     * Get a "smart" ordering of the boxes to try packing items into. The initial BoxList is already sorted in order
     * so that the smallest boxes are evaluated first, but this means that time is spent on boxes that cannot possibly
     * hold the entire set of items due to volume limitations. These should be evaluated first.
     */
    protected function getBoxList(bool $enforceSingleBox = false): iterable
    {
        $itemVolume = 0;
        foreach ($this->items as $item) {
            $itemVolume += $item->getWidth() * $item->getLength() * $item->getDepth();
        }

        $preferredBoxes = [];
        $otherBoxes = [];
        foreach ($this->boxes as $box) {
            if ($this->boxesQtyAvailable[$box] > 0) {
                if ($box->getInnerWidth() * $box->getInnerLength() * $box->getInnerDepth() >= $itemVolume) {
                    $preferredBoxes[] = $box;
                } elseif (!$enforceSingleBox) {
                    $otherBoxes[] = $box;
                }
            }
        }

        return array_merge($preferredBoxes, $otherBoxes);
    }

    /**
     * @param PackedBox[] $packedBoxes
     */
    protected function findBestBoxFromIteration(array $packedBoxes): PackedBox
    {
        if (count($packedBoxes) === 0) {
            throw new NoBoxesAvailableException("No boxes could be found for item '{$this->items->top()->getDescription()}'", $this->items->top());
        }

        usort($packedBoxes, [$this, 'compare']);

        return $packedBoxes[0];
    }

    private function sanityPrecheck(): void
    {
        /** @var Item $item */
        foreach ($this->items as $item) {
            $possibleFits = 0;

            /** @var Box $box */
            foreach ($this->boxes as $box) {
                if ($item->getWeight() <= ($box->getMaxWeight() - $box->getEmptyWeight())) {
                    $possibleFits += count((new OrientatedItemFactory($box))->getPossibleOrientationsInEmptyBox($item));
                }
            }

            if ($possibleFits === 0) {
                throw new ItemTooLargeException("Item '{$item->getDescription()}' is too large to fit into any box", $item);
            }
        }
    }

    private static function compare(PackedBox $boxA, PackedBox $boxB): int
    {
        $choice = $boxB->getItems()->count() <=> $boxA->getItems()->count();

        if ($choice === 0) {
            $choice = $boxB->getVolumeUtilisation() <=> $boxA->getVolumeUtilisation();
        }
        if ($choice === 0) {
            $choice = $boxB->getUsedVolume() <=> $boxA->getUsedVolume();
        }

        return $choice;
    }
}


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_merge;
12		use function count;
13		use const PHP_INT_MAX;
14		use Psr\Log\LoggerAwareInterface;
15		use Psr\Log\LoggerAwareTrait;
16		use Psr\Log\LogLevel;
17		use Psr\Log\NullLogger;
18		use SplObjectStorage;
19		use function usort;
20
21		/**
22		* Actual packer.
23		*
24		* @author Doug Wright
25		*/
26		class Packer implements LoggerAwareInterface
27		{
28		use LoggerAwareTrait;
29
30		/**
31		* Number of boxes at which balancing weight is deemed not worth it.
32		*
33		* @var int
34		*/
35		protected $maxBoxesToBalanceWeight = 12;
36
37		/**
38		* List of items to be packed.
39		*
40		* @var ItemList
41		*/
42		protected $items;
43
44		/**
45		* List of box sizes available to pack items into.
46		*
47		* @var BoxList
48		*/
49		protected $boxes;
50
51		/**
52		* Quantities available of each box type.
53		*
54		* @var SplObjectStorage
55		*/
56		protected $boxesQtyAvailable;
57
58		/**
59		* Constructor.
60		*/
61	19	public function __construct()
62		{
63	19	$this->items = new ItemList();
64	19	$this->boxes = new BoxList();
65	19	$this->boxesQtyAvailable = new SplObjectStorage();
66
67	19	$this->logger = new NullLogger();
68	19	}
69
70		/**
71		* Add item to be packed.
72		*/
73		public function addItem(Item $item, int $qty = 1): void
74		{
75		for ($i = 0; $i < $qty; ++$i) {
76		$this->items->insert($item);
77		}
78		$this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}", ['item' => $item]);
79		}
80
81		/**
82		* Set a list of items all at once.
83		* @param iterable\|Item[] $items
84		*/
85	19	public function setItems(iterable $items): void
86		{
87	19	if ($items instanceof ItemList) {
88	19	$this->items = clone $items;
89		} else {
90		$this->items = new ItemList();
91		foreach ($items as $item) {
92		$this->items->insert($item);
93		}
94		}
95	19	}
96
97		/**
98		* Add box size.
99		*/
100		public function addBox(Box $box): void
101		{
102		$this->boxes->insert($box);
103		$this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
104		$this->logger->log(LogLevel::INFO, "added box {$box->getReference()}", ['box' => $box]);
105		}
106
107		/**
108		* Add a pre-prepared set of boxes all at once.
109		*/
110	19	public function setBoxes(BoxList $boxList): void
111		{
112	19	$this->boxes = $boxList;
113	19	foreach ($this->boxes as $box) {
114	19	$this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
115		}
116	19	}
117
118		/**
119		* Set the quantity of this box type available.
120		*/
121	19	public function setBoxQuantity(Box $box, int $qty): void
122		{
123	19	$this->boxesQtyAvailable[$box] = $qty;
124	19	}
125
126		/**
127		* Number of boxes at which balancing weight is deemed not worth the extra computation time.
128		*/
129		public function getMaxBoxesToBalanceWeight(): int
130		{
131		return $this->maxBoxesToBalanceWeight;
132		}
133
134		/**
135		* Number of boxes at which balancing weight is deemed not worth the extra computation time.
136		*/
137		public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight): void
138		{
139		$this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
140		}
141
142		/**
143		* Pack items into boxes.
144		*/
145	19	public function pack(): PackedBoxList
146		{
147	19	$this->sanityPrecheck();
148	19	$packedBoxes = $this->doVolumePacking();
149
150		//If we have multiple boxes, try and optimise/even-out weight distribution
151	19	if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
152	3	$redistributor = new WeightRedistributor($this->boxes, $this->boxesQtyAvailable);
153	3	$redistributor->setLogger($this->logger);
154	3	$packedBoxes = $redistributor->redistributeWeight($packedBoxes);
155		}
156
157	19	$this->logger->log(LogLevel::INFO, "[PACKING COMPLETED], {$packedBoxes->count()} boxes");
158
159	19	return $packedBoxes;
160		}
161
162		/**
163		* Pack items into boxes using the principle of largest volume item first.
164		*
165		* @throws NoBoxesAvailableException
166		*/
167	19	public function doVolumePacking(bool $singlePassMode = false, bool $enforceSingleBox = false): PackedBoxList
168		{
169	19	$packedBoxes = new PackedBoxList();
170
171		//Keep going until everything packed
172	19	while ($this->items->count()) {
173	17	$packedBoxesIteration = [];
174
175		//Loop through boxes starting with smallest, see what happens
176	17	foreach ($this->getBoxList($enforceSingleBox) as $box) {
177	17	$volumePacker = new VolumePacker($box, $this->items);
178	17	$volumePacker->setLogger($this->logger);
179	17	$volumePacker->setSinglePassMode($singlePassMode);
180	17	$packedBox = $volumePacker->pack();
181	17	if ($packedBox->getItems()->count()) {
182	17	$packedBoxesIteration[] = $packedBox;
183
184		//Have we found a single box that contains everything?
185	17	if ($packedBox->getItems()->count() === $this->items->count()) {
186	17	break;
187		}
188		}
189		}
190
191		try {
192		//Find best box of iteration, and remove packed items from unpacked list
193	17	$bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
194		} catch (NoBoxesAvailableException $e) {
195		if ($enforceSingleBox) {
196		return new PackedBoxList();
197		}
198		throw $e;
199		}
200
201	17	$this->items->removePackedItems($bestBox->getItems());
202
203	17	$packedBoxes->insert($bestBox);
204	17	$this->boxesQtyAvailable[$bestBox->getBox()] = $this->boxesQtyAvailable[$bestBox->getBox()] - 1;
205		}
206
207	19	return $packedBoxes;
208		}
209
210		/**
211		* Get a "smart" ordering of the boxes to try packing items into. The initial BoxList is already sorted in order
212		* so that the smallest boxes are evaluated first, but this means that time is spent on boxes that cannot possibly
213		* hold the entire set of items due to volume limitations. These should be evaluated first.
214		*/
215	17	protected function getBoxList(bool $enforceSingleBox = false): iterable
216		{
217	17	$itemVolume = 0;
218	17	foreach ($this->items as $item) {
219	17	$itemVolume += $item->getWidth() * $item->getLength() * $item->getDepth();
220		}
221
222	17	$preferredBoxes = [];
223	17	$otherBoxes = [];
224	17	foreach ($this->boxes as $box) {
225	17	if ($this->boxesQtyAvailable[$box] > 0) {
226	17	if ($box->getInnerWidth() * $box->getInnerLength() * $box->getInnerDepth() >= $itemVolume) {
227	17	$preferredBoxes[] = $box;
228	9	} elseif (!$enforceSingleBox) {
229	9	$otherBoxes[] = $box;
230		}
231		}
232		}
233
234	17	return array_merge($preferredBoxes, $otherBoxes);
235		}
236
237		/**
238		* @param PackedBox[] $packedBoxes
239		*/
240	17	protected function findBestBoxFromIteration(array $packedBoxes): PackedBox
241		{
242	17	if (count($packedBoxes) === 0) {
243		throw new NoBoxesAvailableException("No boxes could be found for item '{$this->items->top()->getDescription()}'", $this->items->top());
244		}
245
246	17	usort($packedBoxes, [$this, 'compare']);
247
248	17	return $packedBoxes[0];
249		}
250
251	19	private function sanityPrecheck(): void
252		{
253		/** @var Item $item */
254	19	foreach ($this->items as $item) {
255	19	$possibleFits = 0;
256
257		/** @var Box $box */
258	19	foreach ($this->boxes as $box) {
259	19	if ($item->getWeight() <= ($box->getMaxWeight() - $box->getEmptyWeight())) {
260	19	$possibleFits += count((new OrientatedItemFactory($box))->getPossibleOrientationsInEmptyBox($item));
261		}
262		}
263
264	19	if ($possibleFits === 0) {
265	4	throw new ItemTooLargeException("Item '{$item->getDescription()}' is too large to fit into any box", $item);
266		}
267		}
268	19	}
269
270	3	private static function compare(PackedBox $boxA, PackedBox $boxB): int
271		{
272	3	$choice = $boxB->getItems()->count() <=> $boxA->getItems()->count();
273
274	3	if ($choice === 0) {
275		$choice = $boxB->getVolumeUtilisation() <=> $boxA->getVolumeUtilisation();
276		}
277	3	if ($choice === 0) {
278		$choice = $boxB->getUsedVolume() <=> $boxA->getUsedVolume();
279		}
280
281	3	return $choice;
282		}
283		}
284

dvdoug / BoxPacker

Push — 3.x ( 0d7474...922c95 )

Packer::setMaxBoxesToBalanceWeight() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like