Packer::pack() - Code Metrics - Inspection of "Merge branch '3.x'" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 5719ef...74c658 )

by Doug

created 2021-03-14 21:45 UTC

Packer::pack() A

↳ Parent: Packer

Complexity

Conditions	3
Paths	2

Size

Total Lines	15
Code Lines	8

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	9
CRAP Score	3

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	3
eloc	8
c	1
b	0
f	0
nc	2
nop	0
dl	0
loc	15
ccs	9
cts	9
cp	1
crap	3
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 DVDoug\BoxPacker\Exception\ItemTooLargeException;
use DVDoug\BoxPacker\Exception\NoBoxesAvailableException;
use const PHP_INT_MAX;
use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\LogLevel;
use Psr\Log\NullLogger;
use function spl_object_id;
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 array<int, int>
     */
    protected $boxesQtyAvailable = [];

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

        $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>|ItemList $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[spl_object_id($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[spl_object_id($bestBox->getBox())];
        }

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

dvdoug / BoxPacker

Push — master ( 5719ef...74c658 )

Packer::pack() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like