Packer::setItems() - Code Metrics - Inspection of "Enable JIT on CI" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — test_jit ( c34f6e...87859e )

by Doug

created 2020-04-11 21:59 UTC

Packer::setItems() A

↳ Parent: Packer

Complexity

Conditions	3
Paths	3

Size

Total Lines	8
Code Lines	6

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	6
CRAP Score	3

Importance

Changes

Metric	Value
cc	3
eloc	6
nc	3
nop	1
dl	0
loc	8
ccs	6
cts	6
cp	1
crap	3
rs	10
c	0
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\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.
     */
    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): 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() as $box) {
                if ($this->boxesQtyAvailable[$box] > 0) {
                    $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;
                        }
                    }
                }
            }

            //Find best box of iteration, and remove packed items from unpacked list
            $bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);

            /** @var PackedItem $packedItem */
            foreach ($bestBox->getItems() as $packedItem) {
                $this->items->remove($packedItem->getItem());
            }

            $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(): iterable
    {
        $itemVolume = 0;
        /** @var Item $item */
        foreach ($this->items as $item) {
            $itemVolume += $item->getWidth() * $item->getLength() * $item->getDepth();
        }

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

dvdoug / BoxPacker

Push — test_jit ( c34f6e...87859e )

Packer::setItems() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like