Packer::findBestBoxFromIteration() - Code Metrics - Inspection of "Backport 3.x" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Test Failed

Push — 2.x-dev ( 5e90af...eccc16 )

by Doug

created 2020-04-23 22:32 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	4
CRAP Score	2.032

Importance

Changes

Metric	Value
cc	2
eloc	4
c	0
b	0
f	0
nc	2
nop	1
dl	0
loc	9
ccs	4
cts	5
cp	0.8
crap	2.032
rs	10

<?php
/**
 * Box packing (3D bin packing, knapsack problem).
 *
 * @author Doug Wright
 */
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, $qty = 1)
    {
        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($items)
    {
        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)
    {
        $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.
     *
     * @param BoxList $boxList
     */
    public function setBoxes(BoxList $boxList)
    {
        $this->boxes = clone $boxList;
    }

    /**
     * Number of boxes at which balancing weight is deemed not worth the extra computation time.
     *
     * @return int
     */
    public function getMaxBoxesToBalanceWeight()
    {
        return $this->maxBoxesToBalanceWeight;
    }

    /**
     * Number of boxes at which balancing weight is deemed not worth the extra computation time.
     *
     * @param int $maxBoxesToBalanceWeight
     */
    public function setMaxBoxesToBalanceWeight($maxBoxesToBalanceWeight)
    {
        $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
    }

    /**
     * Pack items into boxes.
     *
     * @return PackedBoxList
     */
    public function pack()
    {
        $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);
            $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
     *
     * @return PackedBoxList
     */
    public function doVolumePacking($singlePassMode = false, $enforceSingleBox = false)
    {
        $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($enforceSingleBox) as $box) {
                $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;
                    }
                }
            }

            try {
                //Find best box of iteration, and remove packed items from unpacked list
                $bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
            } catch (NoBoxesAvailableException $e) {
                if ($enforceSingleBox) {
                    return new PackedBoxList();
                }
                throw $e;
            }

            $this->items->removePackedItems($bestBox->getPackedItems());

            $packedBoxes->insert($bestBox);
        }

        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($enforceSingleBox = false)
    {
        $itemVolume = 0;
        foreach (clone $this->items as $item) {
            $itemVolume += $item->getWidth() * $item->getLength() * $item->getDepth();
        }

        $preferredBoxes = [];
        $otherBoxes = [];
        foreach (clone $this->boxes as $box) {
            if ($box->getInnerWidth() * $box->getInnerLength() * $box->getInnerDepth() >= $itemVolume) {
                $preferredBoxes[] = $box;
            } elseif (!$enforceSingleBox) {
                $otherBoxes[] = $box;
            }
        }

        return array_merge($preferredBoxes, $otherBoxes);
    }

    /**
     * @param PackedBox[] $packedBoxes
     */
    protected function findBestBoxFromIteration(array $packedBoxes)
    {
        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()
    {
        /** @var Item $item */
        foreach (clone $this->items as $item) {
            $possibleFits = 0;

            /** @var Box $box */
            foreach (clone $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)
    {
        $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 = PHP_MAJOR_VERSION > 5 ? -1 : 1;
        }

        return $choice;
    }
}


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

dvdoug / BoxPacker

Push — 2.x-dev ( 5e90af...eccc16 )

Packer::findBestBoxFromIteration() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like