Packer::pack() - Code Metrics - Inspection of "Add bulk insert capability to ItemList" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — weight_redistributor ( af2cc6...92270a )

by Doug

created 2018-01-07 17:54 UTC

Packer::pack() A

↳ Parent: Packer

Complexity

Conditions	3
Paths	2

Size

Total Lines	14
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	8
CRAP Score	3

Importance

Changes

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

/**
 * 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.
     *
     * @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()}");
    }

    /**
     * Set a list of items all at once.
     *
     * @param iterable $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->logger->log(LogLevel::INFO, "added box {$box->getReference()}");
    }

    /**
     * Add a pre-prepared set of boxes all at once.
     *
     * @param BoxList $boxList
     */
    public function setBoxes(BoxList $boxList): void
    {
        $this->boxes = $boxList;
    }

    /**
     * Number of boxes at which balancing weight is deemed not worth the extra computation time.
     *
     * @return int
     */
    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)
    {
        $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
    }

    /**
     * Pack items into boxes.
     *
     * @return PackedBoxList
     */
    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
     *
     * @return PackedBoxList
     */
    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) {
                $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;
                    }
                }
            }

            //Check iteration was productive
            if (!$packedBoxesIteration) {
                throw new ItemTooLargeException('Item '.$this->items->top()->getDescription().' is too large to fit into any box', $this->items->top());
            }

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

            foreach ($bestBox->getItems() as $packedItem) {
                foreach ($unPackedItems as $unpackedKey => $unpackedItem) {
                    if ($packedItem->getItem() === $unpackedItem) {
                        unset($unPackedItems[$unpackedKey]);
                        break;
                    }
                }
            }
            $this->items = new ItemList();
            $this->items->insertFromArray($unPackedItems);

            $packedBoxes->insert($bestBox);
        }

        return $packedBoxes;
    }

    /**
     * @param PackedBox[] $packedBoxes
     *
     * @return PackedBox
     */
    private function findBestBoxFromIteration($packedBoxes): PackedBox
    {
        usort($packedBoxes, [$this, 'compare']);

        return array_shift($packedBoxes);
    }

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

dvdoug / BoxPacker

Push — weight_redistributor ( af2cc6...92270a )

Packer::pack() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like