Packer::findBestBoxFromIteration() - Code Metrics - Inspection of "WIP: Optimize weight redistributor by using simpli..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Test Failed

Pull Request — master (#198)

unknown

created 2020-04-10 02:44 UTC

Packer::findBestBoxFromIteration() A

↳ Parent: Packer

Complexity

Conditions	2
Paths	2

Size

Total Lines	9
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	5
CRAP Score	2

Importance

Changes	3
Bugs	0	Features	0

Metric	Value
cc	2
eloc	4
nc	2
nop	1
dl	0
loc	9
ccs	5
cts	5
cp	1
crap	2
rs	10
c	3
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.
     *
     * @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()}", ['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.
     *
     * @param Box $box
     */
    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.
     *
     * @param BoxList $boxList
     */
    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.
     *
     * @param Box $box
     * @param int $qty
     */
    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.
     *
     * @param int $maxBoxesToBalanceWeight
     */
    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(): 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) {
                if ($this->boxesQtyAvailable[$box] > 0) {
                    $volumePacker = new VolumePacker($box, $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;
                        }
                    }
                }
            }

            //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;
    }

    /**
     * Pack all items into a single box if possible, otherwise return an empty list
     *
     * @throws NoBoxesAvailableException
     */
    public function doVolumePackingSingleBox(): PackedBoxList
    {
        $packedBoxes = new PackedBoxList();
        $itemsTotalVolume = $this->items->getTotalVolume();

        // Find smallest box that will hold all items
        foreach ($this->boxes as $box) {
            // Skip boxes that are not available
            if ($this->boxesQtyAvailable[$box] < 1) {
                continue;
            }

            // Skip boxes that are obviously too small
            if ($box->getInnerDepth() * $box->getInnerLength() * $box->getInnerWidth() < $itemsTotalVolume) {
                continue;
            }

            // Attempt to pack all items into one box
            $volumePacker = new VolumePacker($box, $this->items);
            $volumePacker->setLogger($this->logger);
            $packedBox = $volumePacker->pack();
            if ($packedBox->getItems()->count() < $this->items->count()) {
                $packedBoxes->insert($packedBox);
                $this->boxesQtyAvailable[$packedBox->getBox()] = $this->boxesQtyAvailable[$packedBox->getBox()] - 1;
                break;
            }
        }

        return $packedBoxes;
    }

    /**
     * @param PackedBox[] $packedBoxes
     * @return PackedBox
     */
    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	27	public function __construct()
60		{
61	27	$this->items = new ItemList();
62	27	$this->boxes = new BoxList();
63	27	$this->boxesQtyAvailable = new SplObjectStorage();
64
65	27	$this->logger = new NullLogger();
66	27	}
67
68		/**
69		* Add item to be packed.
70		*
71		* @param Item $item
72		* @param int $qty
73		*/
74	19	public function addItem(Item $item, int $qty = 1): void
75		{
76	19	for ($i = 0; $i < $qty; ++$i) {
77	19	$this->items->insert($item);
78		}
79	19	$this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}", ['item' => $item]);
80	19	}
81
82		/**
83		* Set a list of items all at once.
84		* @param iterable\|Item[] $items
85		*/
86	12	public function setItems(iterable $items): void
87		{
88	12	if ($items instanceof ItemList) {
89	8	$this->items = clone $items;
90		} else {
91	4	$this->items = new ItemList();
92	4	foreach ($items as $item) {
93	4	$this->items->insert($item);
94		}
95		}
96	12	}
97
98		/**
99		* Add box size.
100		*
101		* @param Box $box
102		*/
103	18	public function addBox(Box $box): void
104		{
105	18	$this->boxes->insert($box);
106	18	$this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
107	18	$this->logger->log(LogLevel::INFO, "added box {$box->getReference()}", ['box' => $box]);
108	18	}
109
110		/**
111		* Add a pre-prepared set of boxes all at once.
112		*
113		* @param BoxList $boxList
114		*/
115	11	public function setBoxes(BoxList $boxList): void
116		{
117	11	$this->boxes = $boxList;
118	11	foreach ($this->boxes as $box) {
119	11	$this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
120		}
121	11	}
122
123		/**
124		* Set the quantity of this box type available.
125		*
126		* @param Box $box
127		* @param int $qty
128		*/
129	25	public function setBoxQuantity(Box $box, int $qty): void
130		{
131	25	$this->boxesQtyAvailable[$box] = $qty;
132	25	}
133
134		/**
135		* Number of boxes at which balancing weight is deemed not worth the extra computation time.
136		*/
137	1	public function getMaxBoxesToBalanceWeight(): int
138		{
139	1	return $this->maxBoxesToBalanceWeight;
140		}
141
142		/**
143		* Number of boxes at which balancing weight is deemed not worth the extra computation time.
144		*
145		* @param int $maxBoxesToBalanceWeight
146		*/
147	1	public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight): void
148		{
149	1	$this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
150	1	}
151
152		/**
153		* Pack items into boxes.
154		*/
155	26	public function pack(): PackedBoxList
156		{
157	26	$this->sanityPrecheck();
158	24	$packedBoxes = $this->doVolumePacking();
159
160		//If we have multiple boxes, try and optimise/even-out weight distribution
161	23	if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
162	10	$redistributor = new WeightRedistributor($this->boxes, $this->boxesQtyAvailable);
163	10	$redistributor->setLogger($this->logger);
164	10	$packedBoxes = $redistributor->redistributeWeight($packedBoxes);
165		}
166
167	23	$this->logger->log(LogLevel::INFO, "[PACKING COMPLETED], {$packedBoxes->count()} boxes");
168
169	23	return $packedBoxes;
170		}
171
172		/**
173		* Pack items into boxes using the principle of largest volume item first.
174		*
175		* @throws NoBoxesAvailableException
176		*/
177	24	public function doVolumePacking(): PackedBoxList
178		{
179	24	$packedBoxes = new PackedBoxList();
180
181		//Keep going until everything packed
182	24	while ($this->items->count()) {
183	23	$packedBoxesIteration = [];
184
185		//Loop through boxes starting with smallest, see what happens
186	23	foreach ($this->boxes as $box) {
187	23	if ($this->boxesQtyAvailable[$box] > 0) {
188	23	$volumePacker = new VolumePacker($box, $this->items);
189	23	$volumePacker->setLogger($this->logger);
190	23	$packedBox = $volumePacker->pack();
191	23	if ($packedBox->getItems()->count()) {
192	23	$packedBoxesIteration[] = $packedBox;
193
194		//Have we found a single box that contains everything?
195	23	if ($packedBox->getItems()->count() === $this->items->count()) {
196	22	break;
197		}
198		}
199		}
200		}
201
202		//Find best box of iteration, and remove packed items from unpacked list
203	23	$bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
204
205		/** @var PackedItem $packedItem */
206	23	foreach ($bestBox->getItems() as $packedItem) {
207	23	$this->items->remove($packedItem->getItem());
208		}
209
210	23	$packedBoxes->insert($bestBox);
211	23	$this->boxesQtyAvailable[$bestBox->getBox()] = $this->boxesQtyAvailable[$bestBox->getBox()] - 1;
212		}
213
214	23	return $packedBoxes;
215		}
216
217		/**
218		* Pack all items into a single box if possible, otherwise return an empty list
219		*
220		* @throws NoBoxesAvailableException
221		*/
222	4	public function doVolumePackingSingleBox(): PackedBoxList
223		{
224	4	$packedBoxes = new PackedBoxList();
225	4	$itemsTotalVolume = $this->items->getTotalVolume();
226
227		// Find smallest box that will hold all items
228	4	foreach ($this->boxes as $box) {
229		// Skip boxes that are not available
230	4	if ($this->boxesQtyAvailable[$box] < 1) {
231		continue;
232		}
233
234		// Skip boxes that are obviously too small
235	4	if ($box->getInnerDepth() * $box->getInnerLength() * $box->getInnerWidth() < $itemsTotalVolume) {
236	2	continue;
237		}
238
239		// Attempt to pack all items into one box
240	2	$volumePacker = new VolumePacker($box, $this->items);
241	2	$volumePacker->setLogger($this->logger);
242	2	$packedBox = $volumePacker->pack();
243	2	if ($packedBox->getItems()->count() < $this->items->count()) {
244	1	$packedBoxes->insert($packedBox);
245	1	$this->boxesQtyAvailable[$packedBox->getBox()] = $this->boxesQtyAvailable[$packedBox->getBox()] - 1;
246	1	break;
247		}
248		}
249
250	4	return $packedBoxes;
251		}
252
253		/**
254		* @param PackedBox[] $packedBoxes
255		* @return PackedBox
256		*/
257	23	protected function findBestBoxFromIteration(array $packedBoxes): PackedBox
258		{
259	23	if (count($packedBoxes) === 0) {
260	1	throw new NoBoxesAvailableException("No boxes could be found for item '{$this->items->top()->getDescription()}'", $this->items->top());
261		}
262
263	23	usort($packedBoxes, [$this, 'compare']);
264
265	23	return $packedBoxes[0];
266		}
267
268	26	private function sanityPrecheck(): void
269		{
270		/** @var Item $item */
271	26	foreach ($this->items as $item) {
272	26	$possibleFits = 0;
273
274		/** @var Box $box */
275	26	foreach ($this->boxes as $box) {
276	25	if ($item->getWeight() <= ($box->getMaxWeight() - $box->getEmptyWeight())) {
277	25	$possibleFits += count((new OrientatedItemFactory($box))->getPossibleOrientationsInEmptyBox($item));
278		}
279		}
280
281	26	if ($possibleFits === 0) {
282	5	throw new ItemTooLargeException("Item '{$item->getDescription()}' is too large to fit into any box", $item);
283		}
284		}
285	24	}
286
287	7	private static function compare(PackedBox $boxA, PackedBox $boxB): int
288		{
289	7	$choice = $boxB->getItems()->count() <=> $boxA->getItems()->count();
290
291	7	if ($choice === 0) {
292	4	$choice = $boxB->getVolumeUtilisation() <=> $boxA->getVolumeUtilisation();
293		}
294	7	if ($choice === 0) {
295	3	$choice = $boxB->getUsedVolume() <=> $boxA->getUsedVolume();
296		}
297
298	7	return $choice;
299		}
300		}
301

dvdoug / BoxPacker

Pull Request — master (#198)

Packer::findBestBoxFromIteration() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like