Packer::addItem() - Code Metrics - Inspection of "#169 Teach Packer and WeightDistributor about the..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — limited_supply_boxes ( 273b14 )

by Doug

created 2020-01-18 20:58 UTC

Packer::addItem() A

↳ Parent: Packer

Complexity

Conditions	2
Paths	2

Size

Total Lines	6
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	4
CRAP Score	2

Importance

Changes

Metric	Value
cc	2
eloc	3
nc	2
nop	2
dl	0
loc	6
ccs	4
cts	4
cp	1
crap	2
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 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
     */
    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.
     */
    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
    {
        $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();

        $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) {
                if ($this->boxesQtyAvailable[spl_object_id($box)] > 0) {
                    $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);
            --$this->boxesQtyAvailable[spl_object_id($bestBox->getBox())];
        }

        return $packedBoxes;
    }

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

dvdoug / BoxPacker

Push — limited_supply_boxes ( 273b14 )

Packer::addItem() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like