Packer::getMaxBoxesToBalanceWeight() - Code Metrics - Inspection of "Add #187 testcase for benchmarking on Travis" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — issue_187 ( fb1b49 )

by Doug

created 2020-01-15 23:10 UTC

Packer::getMaxBoxesToBalanceWeight() A

↳ Parent: Packer

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	2
CRAP Score	1

Importance

Changes

Metric	Value
cc	1
eloc	1
nc	1
nop	0
dl	0
loc	3
ccs	2
cts	2
cp	1
crap	1
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 array_shift;
use function count;
use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\LogLevel;
use Psr\Log\NullLogger;
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;

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

    /**
     * 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
    {
        $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
     */
    public function doVolumePacking(): PackedBoxList
    {
        $packedBoxes = new PackedBoxList();

        $this->sanityPrecheck();

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

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

        return $packedBoxes;
    }

    /**
     * @param PackedBox[] $packedBoxes
     */
    protected function findBestBoxFromIteration(array $packedBoxes): PackedBox
    {
        //Check iteration was productive
        if (count($packedBoxes) === 0) {
            throw new ItemTooLargeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box', $this->items->top());
        }

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

        return array_shift($packedBoxes);
    }

    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();
        }
        if ($choice === 0) {
            $choice = $boxA->getWeight() <=> $boxB->getWeight();
        }

        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_shift;
12		use function count;
13		use Psr\Log\LoggerAwareInterface;
14		use Psr\Log\LoggerAwareTrait;
15		use Psr\Log\LogLevel;
16		use Psr\Log\NullLogger;
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		* Constructor.
51		*/
52	26	public function __construct()
53		{
54	26	$this->items = new ItemList();
55	26	$this->boxes = new BoxList();
56
57	26	$this->logger = new NullLogger();
58	26	}
59
60		/**
61		* Add item to be packed.
62		*/
63	18	public function addItem(Item $item, int $qty = 1): void
64		{
65	18	for ($i = 0; $i < $qty; ++$i) {
66	18	$this->items->insert($item);
67		}
68	18	$this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}", ['item' => $item]);
69	18	}
70
71		/**
72		* Set a list of items all at once.
73		*/
74	12	public function setItems(iterable $items): void
75		{
76	12	if ($items instanceof ItemList) {
77	8	$this->items = clone $items;
78		} else {
79	4	$this->items = new ItemList();
80	4	foreach ($items as $item) {
81	4	$this->items->insert($item);
82		}
83		}
84	12	}
85
86		/**
87		* Add box size.
88		*/
89	17	public function addBox(Box $box): void
90		{
91	17	$this->boxes->insert($box);
92	17	$this->logger->log(LogLevel::INFO, "added box {$box->getReference()}", ['box' => $box]);
93	17	}
94
95		/**
96		* Add a pre-prepared set of boxes all at once.
97		*/
98	11	public function setBoxes(BoxList $boxList): void
99		{
100	11	$this->boxes = $boxList;
101	11	}
102
103		/**
104		* Number of boxes at which balancing weight is deemed not worth the extra computation time.
105		*/
106	1	public function getMaxBoxesToBalanceWeight(): int
107		{
108	1	return $this->maxBoxesToBalanceWeight;
109		}
110
111		/**
112		* Number of boxes at which balancing weight is deemed not worth the extra computation time.
113		*/
114	2	public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight): void
115		{
116	2	$this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
117	2	}
118
119		/**
120		* Pack items into boxes.
121		*/
122	25	public function pack(): PackedBoxList
123		{
124	25	$packedBoxes = $this->doVolumePacking();
125
126		//If we have multiple boxes, try and optimise/even-out weight distribution
127	23	if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
128	9	$redistributor = new WeightRedistributor($this->boxes);
129	9	$redistributor->setLogger($this->logger);
130	9	$packedBoxes = $redistributor->redistributeWeight($packedBoxes);
131		}
132
133	23	$this->logger->log(LogLevel::INFO, "[PACKING COMPLETED], {$packedBoxes->count()} boxes");
134
135	23	return $packedBoxes;
136		}
137
138		/**
139		* Pack items into boxes using the principle of largest volume item first.
140		*
141		* @throws ItemTooLargeException
142		*/
143	25	public function doVolumePacking(): PackedBoxList
144		{
145	25	$packedBoxes = new PackedBoxList();
146
147	25	$this->sanityPrecheck();
148
149		//Keep going until everything packed
150	23	while ($this->items->count()) {
151	22	$packedBoxesIteration = [];
152
153		//Loop through boxes starting with smallest, see what happens
154	22	foreach ($this->boxes as $box) {
155	22	$volumePacker = new VolumePacker($box, clone $this->items);
156	22	$volumePacker->setLogger($this->logger);
157	22	$packedBox = $volumePacker->pack();
158	22	if ($packedBox->getItems()->count()) {
159	22	$packedBoxesIteration[] = $packedBox;
160
161		//Have we found a single box that contains everything?
162	22	if ($packedBox->getItems()->count() === $this->items->count()) {
163	22	break;
164		}
165		}
166		}
167
168		//Find best box of iteration, and remove packed items from unpacked list
169	22	$bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
170
171		/** @var PackedItem $packedItem */
172	22	foreach ($bestBox->getItems() as $packedItem) {
173	22	$this->items->remove($packedItem->getItem());
174		}
175
176	22	$packedBoxes->insert($bestBox);
177		}
178
179	23	return $packedBoxes;
180		}
181
182		/**
183		* @param PackedBox[] $packedBoxes
184		*/
185	22	protected function findBestBoxFromIteration(array $packedBoxes): PackedBox
186		{
187		//Check iteration was productive
188	22	if (count($packedBoxes) === 0) {
189		throw new ItemTooLargeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box', $this->items->top());
190		}
191
192	22	usort($packedBoxes, [$this, 'compare']);
193
194	22	return array_shift($packedBoxes);
195		}
196
197	25	private function sanityPrecheck(): void
198		{
199		/** @var Item $item */
200	25	foreach ($this->items as $item) {
201	25	$possibleFits = 0;
202
203		/** @var Box $box */
204	25	foreach ($this->boxes as $box) {
205	24	if ($item->getWeight() <= ($box->getMaxWeight() - $box->getEmptyWeight())) {
206	24	$possibleFits += count((new OrientatedItemFactory($box))->getPossibleOrientationsInEmptyBox($item));
207		}
208		}
209
210	25	if ($possibleFits === 0) {
211	5	throw new ItemTooLargeException('Item ' . $item->getDescription() . ' is too large to fit into any box', $item);
212		}
213		}
214	23	}
215
216	6	private static function compare(PackedBox $boxA, PackedBox $boxB): int
217		{
218	6	$choice = $boxB->getItems()->count() <=> $boxA->getItems()->count();
219
220	6	if ($choice === 0) {
221	4	$choice = $boxB->getVolumeUtilisation() <=> $boxA->getVolumeUtilisation();
222		}
223	6	if ($choice === 0) {
224	2	$choice = $boxB->getUsedVolume() <=> $boxA->getUsedVolume();
225		}
226	6	if ($choice === 0) {
227	1	$choice = $boxA->getWeight() <=> $boxB->getWeight();
228		}
229
230	6	return $choice;
231		}
232		}
233

dvdoug / BoxPacker

Push — issue_187 ( fb1b49 )

Packer::getMaxBoxesToBalanceWeight() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like