Packer::fitsGap() - Code Metrics - Inspection of "Another minor refactor" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( ff9def...abda0a )

by Doug

created 2016-01-24 18:59 UTC

Packer::fitsGap() A

↳ Parent: Packer

Complexity

Conditions	2
Paths	2

Size

Total Lines	4
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	6

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
c	1
b	0
f	0
dl	0
loc	4
ccs	0
cts	0
cp	0
rs	10
cc	2
eloc	3
nc	2
nop	3
crap	6

<?php
/**
 * Box packing (3D bin packing, knapsack problem)
 * @package BoxPacker
 * @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
 * @package BoxPacker
 */
class Packer implements LoggerAwareInterface
{
    use LoggerAwareTrait;

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

    /**
     * Set a list of items all at once
     * @param \Traversable $items
     */
    public function setItems($items)
    {
        if ($items instanceof ItemList) {
            $this->items = clone $items;
        } elseif (is_array($items)) {
            $this->items = new ItemList();
            foreach ($items as $item) {
                $this->items->insert($item);
            }
        } else {
            throw new \RuntimeException('Not a valid list of items');
        }
    }

    /**
     * Add box size
     * @param Box $box
     */
    public function addBox(Box $box)
    {
        $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)
    {
        $this->boxes = clone $boxList;
    }

    /**
     * Pack items into boxes
     *
     * @throws \RuntimeException
     * @return PackedBoxList
     */
    public function pack()
    {
        $packedBoxes = $this->doVolumePacking();

        //If we have multiple boxes, try and optimise/even-out weight distribution
        if ($packedBoxes->count() > 1) {
            $packedBoxes = $this->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 \RuntimeException
     * @return PackedBoxList
     */
    public function doVolumePacking()
    {

        $packedBoxes = new PackedBoxList;

        //Keep going until everything packed
        while ($this->items->count()) {
            $boxesToEvaluate = clone $this->boxes;
            $packedBoxesIteration = new PackedBoxList;

            //Loop through boxes starting with smallest, see what happens
            while (!$boxesToEvaluate->isEmpty()) {
                $box = $boxesToEvaluate->extract();
                $packedBox = $this->packIntoBox($box, clone $this->items);
                if ($packedBox->getItems()->count()) {
                    $packedBoxesIteration->insert($packedBox);

                    //Have we found a single box that contains everything?
                    if ($packedBox->getItems()->count() === $this->items->count()) {
                        break;
                    }
                }
            }

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

            //Find best box of iteration, and remove packed items from unpacked list
            $bestBox = $packedBoxesIteration->top();
            $unPackedItems = $this->items->asArray();
            foreach (clone $bestBox->getItems() as $packedItem) {
                foreach ($unPackedItems as $unpackedKey => $unpackedItem) {
                    if ($packedItem === $unpackedItem) {
                        unset($unPackedItems[$unpackedKey]);
                        break;
                    }
                }
            }
            $unpackedItemList = new ItemList();
            foreach ($unPackedItems as $unpackedItem) {
                $unpackedItemList->insert($unpackedItem);
            }
            $this->items = $unpackedItemList;
            $packedBoxes->insert($bestBox);

        }

        return $packedBoxes;
    }

    /**
     * Given a solution set of packed boxes, repack them to achieve optimum weight distribution
     *
     * @param PackedBoxList $originalBoxes
     * @return PackedBoxList
     */
    public function redistributeWeight(PackedBoxList $originalBoxes)
    {

        $targetWeight = $originalBoxes->getMeanWeight();
        $this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");

        $packedBoxes = new PackedBoxList;

        $overWeightBoxes = [];
        $underWeightBoxes = [];
        foreach (clone $originalBoxes as $packedBox) {
            $boxWeight = $packedBox->getWeight();
            if ($boxWeight > $targetWeight) {
                $overWeightBoxes[] = $packedBox;
            } elseif ($boxWeight < $targetWeight) {
                $underWeightBoxes[] = $packedBox;
            } else {
                $packedBoxes->insert($packedBox); //target weight, so we'll keep these
            }
        }

        do { //Keep moving items from most overweight box to most underweight box
            $tryRepack = false;
            $this->logger->log(LogLevel::DEBUG, 'boxes under/over target: ' . count($underWeightBoxes) . '/' . count($overWeightBoxes));

            foreach ($underWeightBoxes as $u => $underWeightBox) {
                $this->logger->log(LogLevel::DEBUG, 'Underweight Box ' . $u);
                foreach ($overWeightBoxes as $o => $overWeightBox) {
                    $this->logger->log(LogLevel::DEBUG, 'Overweight Box ' . $o);
                    $overWeightBoxItems = $overWeightBox->getItems()->asArray();

                    //For each item in the heavier box, try and move it to the lighter one
                    foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) {
                        $this->logger->log(LogLevel::DEBUG, 'Overweight Item ' . $oi);
                        if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $targetWeight) {
                            $this->logger->log(LogLevel::DEBUG, 'Skipping item for hindering weight distribution');
                            continue; //skip if moving this item would hinder rather than help weight distribution
                        }

                        $newItemsForLighterBox = clone $underWeightBox->getItems();
                        $newItemsForLighterBox->insert($overWeightBoxItem);

                        $newLighterBoxPacker = new Packer(); //we may need a bigger box
                        $newLighterBoxPacker->setBoxes($this->boxes);
                        $newLighterBoxPacker->setItems($newItemsForLighterBox);
                        $this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK LIGHTER BOX]");
                        $newLighterBox = $newLighterBoxPacker->doVolumePacking()->extract();

                        if ($newLighterBox->getItems()->count() === $newItemsForLighterBox->count()) { //new item fits
                            $this->logger->log(LogLevel::DEBUG, 'New item fits');
                            unset($overWeightBoxItems[$oi]); //now packed in different box

                            $newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box
                            $newHeavierBoxPacker->setBoxes($this->boxes);
                            $newHeavierBoxPacker->setItems($overWeightBoxItems);

                            $this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK HEAVIER BOX]");
                            $newHeavierBoxes = $newHeavierBoxPacker->doVolumePacking();
                            if (count($newHeavierBoxes) > 1) { //found an edge case in packing algorithm that *increased* box count
                                $this->logger->log(LogLevel::INFO, "[REDISTRIBUTING WEIGHT] Abandoning redistribution, because new packing is less efficient than original");
                                return $originalBoxes;
                            }

                            $overWeightBoxes[$o] = $newHeavierBoxes->extract();
                            $underWeightBoxes[$u] = $newLighterBox;

                            $tryRepack = true; //we did some work, so see if we can do even better
                            usort($overWeightBoxes, [$packedBoxes, 'reverseCompare']);
                            usort($underWeightBoxes, [$packedBoxes, 'reverseCompare']);
                            break 3;
                        }
                    }
                }
            }
        } while ($tryRepack);

        //Combine back into a single list
        $packedBoxes->insertFromArray($overWeightBoxes);
        $packedBoxes->insertFromArray($underWeightBoxes);

        return $packedBoxes;
    }


    /**
     * Pack as many items as possible into specific given box
     * @param Box      $box
     * @param ItemList $items
     * @return PackedBox packed box
     */
    public function packIntoBox(Box $box, ItemList $items)
    {
        $this->logger->log(LogLevel::DEBUG, "[EVALUATING BOX] {$box->getReference()}");

        $packedItems = new ItemList;
        $remainingDepth = $box->getInnerDepth();
        $remainingWeight = $box->getMaxWeight() - $box->getEmptyWeight();
        $remainingWidth = $box->getInnerWidth();
        $remainingLength = $box->getInnerLength();

        $layerWidth = $layerLength = $layerDepth = 0;
        while (!$items->isEmpty()) {

            $itemToPack = $items->top();

            //skip items that are simply too large
            if ($this->isItemTooLargeForBox($itemToPack, $remainingDepth, $remainingWeight)) {
                $items->extract();
                continue;
            }

            $this->logger->log(LogLevel::DEBUG, "evaluating item {$itemToPack->getDescription()}");
            $this->logger->log(LogLevel::DEBUG, "remaining width: {$remainingWidth}, length: {$remainingLength}, depth: {$remainingDepth}");
            $this->logger->log(LogLevel::DEBUG, "layerWidth: {$layerWidth}, layerLength: {$layerLength}, layerDepth: {$layerDepth}");

            $itemWidth = $itemToPack->getWidth();
            $itemLength = $itemToPack->getLength();

            if ($this->fitsGap($itemToPack, $remainingWidth, $remainingLength)) {

                $packedItems->insert($items->extract());
                $remainingWeight -= $itemToPack->getWeight();

                $nextItem = !$items->isEmpty() ? $items->top() : null;
                if ($this->fitsBetterRotated($itemToPack, $nextItem, $remainingWidth, $remainingLength)) {
                    $this->logger->log(LogLevel::DEBUG, "fits (better) unrotated");
                    $remainingLength -= $itemLength;
                    $layerLength += $itemLength;
                    $layerWidth = max($itemWidth, $layerWidth);
                } else {
                    $this->logger->log(LogLevel::DEBUG, "fits (better) rotated");
                    $remainingLength -= $itemWidth;
                    $layerLength += $itemWidth;
                    $layerWidth = max($itemLength, $layerWidth);
                }
                $layerDepth = max($layerDepth, $itemToPack->getDepth()); //greater than 0, items will always be less deep

                //allow items to be stacked in place within the same footprint up to current layerdepth
                $maxStackDepth = $layerDepth - $itemToPack->getDepth();
                while (!$items->isEmpty() && $this->canStackItemInLayer($itemToPack, $items->top(), $maxStackDepth, $remainingWeight)) {
                    $remainingWeight -= $items->top()->getWeight();
                    $maxStackDepth -= $items->top()->getDepth();
                    $packedItems->insert($items->extract());
                }
            } else {
                if ($remainingWidth >= min($itemWidth, $itemLength) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
                    $this->logger->log(LogLevel::DEBUG, "No more fit in lengthwise, resetting for new row");
                    $remainingLength += $layerLength;
                    $remainingWidth -= $layerWidth;
                    $layerWidth = $layerLength = 0;
                    continue;
                } elseif ($remainingLength < min($itemWidth, $itemLength) || $layerDepth == 0) {
                    $this->logger->log(LogLevel::DEBUG, "doesn't fit on layer even when empty");
                    $items->extract();
                    continue;
                }

                $remainingWidth = $layerWidth ? min(floor($layerWidth * 1.1), $box->getInnerWidth()) : $box->getInnerWidth();
                $remainingLength = $layerLength ? min(floor($layerLength * 1.1), $box->getInnerLength()) : $box->getInnerLength();
                $remainingDepth -= $layerDepth;

                $layerWidth = $layerLength = $layerDepth = 0;
                $this->logger->log(LogLevel::DEBUG, "doesn't fit, so starting next vertical layer");
            }
        }
        $this->logger->log(LogLevel::DEBUG, "done with this box");
        return new PackedBox($box, $packedItems, $remainingWidth, $remainingLength, $remainingDepth, $remainingWeight);
    }

    /**
     * @param Item $item
     * @param int $remainingDepth
     * @param int $remainingWeight
     * @return bool
     */
    protected function isItemTooLargeForBox(Item $item, $remainingDepth, $remainingWeight) {
        return $item->getDepth() > $remainingDepth || $item->getWeight() > $remainingWeight;
    }

    /**
     * Figure out space left for next item if we pack this one in it's regular orientation
     * @param Item $item
     * @param int $remainingWidth
     * @param int $remainingLength
     * @return int
     */
    protected function fitsSameGap(Item $item, $remainingWidth, $remainingLength) {
        return min($remainingWidth - $item->getWidth(), $remainingLength - $item->getLength());
    }

    /**
     * Figure out space left for next item if we pack this one rotated by 90deg
     * @param Item $item
     * @param int $remainingWidth
     * @param int $remainingLength
     * @return int
     */
    protected function fitsRotatedGap(Item $item, $remainingWidth, $remainingLength) {
        return min($remainingWidth - $item->getLength(), $remainingLength - $item->getWidth());
    }

    /**
     * @param Item $item
     * @param Item|null $nextItem
     * @param $remainingWidth
     * @param $remainingLength
     * @return bool
     */
    protected function fitsBetterRotated(Item $item, Item $nextItem = null, $remainingWidth, $remainingLength) {

        $fitsSameGap = $this->fitsSameGap($item, $remainingWidth, $remainingLength);
        $fitsRotatedGap = $this->fitsRotatedGap($item, $remainingWidth, $remainingLength);

        return !!($fitsRotatedGap < 0 ||
        ($fitsSameGap >= 0 && $fitsSameGap <= $fitsRotatedGap) ||
        ($item->getWidth() <= $remainingWidth && $nextItem == $item && $remainingLength >= 2 * $item->getLength()));
    }

    /**
     * Does item fit in specified gap
     * @param Item $item
     * @param $remainingWidth
     * @param $remainingLength
     * @return bool
     */
    protected function fitsGap(Item $item, $remainingWidth, $remainingLength) {
        return $this->fitsSameGap($item, $remainingWidth, $remainingLength) >= 0 ||
               $this->fitsRotatedGap($item, $remainingWidth, $remainingLength) >= 0;
    }

    /**
     * Figure out if we can stack the next item vertically on top of this rather than side by side
     * Used when we've packed a tall item, and have just put a shorter one next to it
     * @param Item $item
     * @param Item $nextItem
     * @param $maxStackDepth
     * @param $remainingWeight
     * @return bool
     */
    protected function canStackItemInLayer(Item $item, Item $nextItem, $maxStackDepth, $remainingWeight)
    {
        return $nextItem->getDepth() <= $maxStackDepth &&
               $nextItem->getWeight() <= $remainingWeight &&
               $nextItem->getWidth() <= $item->getWidth() &&
               $nextItem->getLength() <= $item->getLength();
    }

    /**
     * @param $layerWidth
     * @param $layerLength
     * @param $layerDepth
     * @return bool
     */
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
    }

    /**
     * Pack as many items as possible into specific given box
     * @deprecated
     * @param Box      $box
     * @param ItemList $items
     * @return ItemList items packed into box
     */
    public function packBox(Box $box, ItemList $items)
    {
        $packedBox = $this->packIntoBox($box, $items);
        return $packedBox->getItems();
    }
}


1		<?php
2		/**
3		* Box packing (3D bin packing, knapsack problem)
4		* @package BoxPacker
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		* @author Doug Wright
17		* @package BoxPacker
18		*/
19		class Packer implements LoggerAwareInterface
20		{
21		use LoggerAwareTrait;
22
23		/**
24		* List of items to be packed
25		* @var ItemList
26		*/
27		protected $items;
28
29		/**
30		* List of box sizes available to pack items into
31		* @var BoxList
32		*/
33		protected $boxes;
34
35		/**
36		* Constructor
37	4582	*/
38	4582	public function __construct()
39	4582	{
40		$this->items = new ItemList();
41	4582	$this->boxes = new BoxList();
42	4582
43		$this->logger = new NullLogger();
44		}
45
46		/**
47		* Add item to be packed
48		* @param Item $item
49	4572	* @param int $qty
50	4572	*/
51	4572	public function addItem(Item $item, $qty = 1)
52	4572	{
53	4572	for ($i = 0; $i < $qty; $i++) {
54	4572	$this->items->insert($item);
55		}
56		$this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}");
57		}
58
59		/**
60	1323	* Set a list of items all at once
61	1233	* @param \Traversable $items
62	1233	*/
63	1233	public function setItems($items)
64	1209	{
65	1209	if ($items instanceof ItemList) {
66	1209	$this->items = clone $items;
67	1209	} elseif (is_array($items)) {
68	1323	$this->items = new ItemList();
69	1209	foreach ($items as $item) {
70		$this->items->insert($item);
71		}
72		} else {
73	1233	throw new \RuntimeException('Not a valid list of items');
74		}
75		}
76
77		/**
78		* Add box size
79	4572	* @param Box $box
80	4572	*/
81	4572	public function addBox(Box $box)
82	4572	{
83		$this->boxes->insert($box);
84		$this->logger->log(LogLevel::INFO, "added box {$box->getReference()}");
85		}
86
87		/**
88	1233	* Add a pre-prepared set of boxes all at once
89	1233	* @param BoxList $boxList
90	1233	*/
91		public function setBoxes(BoxList $boxList)
92		{
93		$this->boxes = clone $boxList;
94		}
95
96		/**
97		* Pack items into boxes
98	4572	*
99	4572	* @throws \RuntimeException
100		* @return PackedBoxList
101		*/
102	4570	public function pack()
103	1322	{
104	1322	$packedBoxes = $this->doVolumePacking();
105
106	4570	//If we have multiple boxes, try and optimise/even-out weight distribution
107	4570	if ($packedBoxes->count() > 1) {
108		$packedBoxes = $this->redistributeWeight($packedBoxes);
109		}
110
111		$this->logger->log(LogLevel::INFO, "packing completed, {$packedBoxes->count()} boxes");
112		return $packedBoxes;
113		}
114
115		/**
116	4573	* Pack items into boxes using the principle of largest volume item first
117		*
118	4573	* @throws \RuntimeException
119		* @return PackedBoxList
120		*/
121	4573	public function doVolumePacking()
122	4573	{
123	4573
124		$packedBoxes = new PackedBoxList;
125
126	4573	//Keep going until everything packed
127	4572	while ($this->items->count()) {
128	4572	$boxesToEvaluate = clone $this->boxes;
129	4572	$packedBoxesIteration = new PackedBoxList;
130	4572
131		//Loop through boxes starting with smallest, see what happens
132		while (!$boxesToEvaluate->isEmpty()) {
133	4572	$box = $boxesToEvaluate->extract();
134	4571	$packedBox = $this->packIntoBox($box, clone $this->items);
135		if ($packedBox->getItems()->count()) {
136	3397	$packedBoxesIteration->insert($packedBox);
137	4556
138		//Have we found a single box that contains everything?
139		if ($packedBox->getItems()->count() === $this->items->count()) {
140	4573	break;
141	2	}
142		}
143		}
144
145	4572	//Check iteration was productive
146	4572	if ($packedBoxesIteration->isEmpty()) {
147	4572	throw new \RuntimeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box');
148	4572	}
149	4572
150	4572	//Find best box of iteration, and remove packed items from unpacked list
151	4572	$bestBox = $packedBoxesIteration->top();
152		$unPackedItems = $this->items->asArray();
153	4572	foreach (clone $bestBox->getItems() as $packedItem) {
154	4572	foreach ($unPackedItems as $unpackedKey => $unpackedItem) {
155	4572	if ($packedItem === $unpackedItem) {
156	4572	unset($unPackedItems[$unpackedKey]);
157	1323	break;
158	4572	}
159	4572	}
160	4572	}
161		$unpackedItemList = new ItemList();
162	4572	foreach ($unPackedItems as $unpackedItem) {
163		$unpackedItemList->insert($unpackedItem);
164	4571	}
165		$this->items = $unpackedItemList;
166		$packedBoxes->insert($bestBox);
167
168		}
169
170		return $packedBoxes;
171		}
172
173	1323	/**
174		* Given a solution set of packed boxes, repack them to achieve optimum weight distribution
175	1323	*
176	1323	* @param PackedBoxList $originalBoxes
177		* @return PackedBoxList
178	1323	*/
179		public function redistributeWeight(PackedBoxList $originalBoxes)
180	1323	{
181	1323
182	1323	$targetWeight = $originalBoxes->getMeanWeight();
183	1323	$this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");
184	1323
185	1312	$packedBoxes = new PackedBoxList;
186	1312
187	1323	$overWeightBoxes = [];
188	1312	$underWeightBoxes = [];
189	1312	foreach (clone $originalBoxes as $packedBox) {
190		$boxWeight = $packedBox->getWeight();
191	11	if ($boxWeight > $targetWeight) {
192		$overWeightBoxes[] = $packedBox;
193	1323	} elseif ($boxWeight < $targetWeight) {
194		$underWeightBoxes[] = $packedBox;
195		} else {
196	1323	$packedBoxes->insert($packedBox); //target weight, so we'll keep these
197	1323	}
198		}
199	1323
200	1312	do { //Keep moving items from most overweight box to most underweight box
201	1312	$tryRepack = false;
202	1312	$this->logger->log(LogLevel::DEBUG, 'boxes under/over target: ' . count($underWeightBoxes) . '/' . count($overWeightBoxes));
203	1312
204		foreach ($underWeightBoxes as $u => $underWeightBox) {
205		$this->logger->log(LogLevel::DEBUG, 'Underweight Box ' . $u);
206	1312	foreach ($overWeightBoxes as $o => $overWeightBox) {
207	1312	$this->logger->log(LogLevel::DEBUG, 'Overweight Box ' . $o);
208	1312	$overWeightBoxItems = $overWeightBox->getItems()->asArray();
209	1130
210	1130	//For each item in the heavier box, try and move it to the lighter one
211		foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) {
212		$this->logger->log(LogLevel::DEBUG, 'Overweight Item ' . $oi);
213	1233	if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $targetWeight) {
214	1233	$this->logger->log(LogLevel::DEBUG, 'Skipping item for hindering weight distribution');
215		continue; //skip if moving this item would hinder rather than help weight distribution
216	1233	}
217	1233
218	1233	$newItemsForLighterBox = clone $underWeightBox->getItems();
219	1233	$newItemsForLighterBox->insert($overWeightBoxItem);
220	1233
221		$newLighterBoxPacker = new Packer(); //we may need a bigger box
222	1233	$newLighterBoxPacker->setBoxes($this->boxes);
223	1209	$newLighterBoxPacker->setItems($newItemsForLighterBox);
224	1209	$this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK LIGHTER BOX]");
225		$newLighterBox = $newLighterBoxPacker->doVolumePacking()->extract();
226	1209
227	1209	if ($newLighterBox->getItems()->count() === $newItemsForLighterBox->count()) { //new item fits
228	1209	$this->logger->log(LogLevel::DEBUG, 'New item fits');
229		unset($overWeightBoxItems[$oi]); //now packed in different box
230	1209
231	1209	$newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box
232	1209	$newHeavierBoxPacker->setBoxes($this->boxes);
233	4	$newHeavierBoxPacker->setItems($overWeightBoxItems);
234	4
235		$this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK HEAVIER BOX]");
236		$newHeavierBoxes = $newHeavierBoxPacker->doVolumePacking();
237	1207	if (count($newHeavierBoxes) > 1) { //found an edge case in packing algorithm that increased box count
238	1207	$this->logger->log(LogLevel::INFO, "[REDISTRIBUTING WEIGHT] Abandoning redistribution, because new packing is less efficient than original");
239		return $originalBoxes;
240	1207	}
241	1207
242	1207	$overWeightBoxes[$o] = $newHeavierBoxes->extract();
243	1207	$underWeightBoxes[$u] = $newLighterBox;
244
245	1308	$tryRepack = true; //we did some work, so see if we can do even better
246	1308	usort($overWeightBoxes, [$packedBoxes, 'reverseCompare']);
247	1321	usort($underWeightBoxes, [$packedBoxes, 'reverseCompare']);
248	1321	break 3;
249		}
250		}
251	1319	}
252	1319	}
253		} while ($tryRepack);
254	1319
255		//Combine back into a single list
256		$packedBoxes->insertFromArray($overWeightBoxes);
257		$packedBoxes->insertFromArray($underWeightBoxes);
258
259		return $packedBoxes;
260		}
261
262
263		/**
264	4581	* Pack as many items as possible into specific given box
265	4581	* @param Box $box
266		* @param ItemList $items
267	4581	* @return PackedBox packed box
268	4581	*/
269	4581	public function packIntoBox(Box $box, ItemList $items)
270	4581	{
271	4581	$this->logger->log(LogLevel::DEBUG, "[EVALUATING BOX] {$box->getReference()}");
272
273	4581	$packedItems = new ItemList;
274	4581	$remainingDepth = $box->getInnerDepth();
275		$remainingWeight = $box->getMaxWeight() - $box->getEmptyWeight();
276	4581	$remainingWidth = $box->getInnerWidth();
277		$remainingLength = $box->getInnerLength();
278	4581
279	3473	$layerWidth = $layerLength = $layerDepth = 0;
280	3473	while (!$items->isEmpty()) {
281
282		$itemToPack = $items->top();
283	4581
284	4581	//skip items that are simply too large
285	4581	if ($this->isItemTooLargeForBox($itemToPack, $remainingDepth, $remainingWeight)) {
286		$items->extract();
287	4581	continue;
288	4581	}
289
290	4581	$this->logger->log(LogLevel::DEBUG, "evaluating item {$itemToPack->getDescription()}");
291	4581	$this->logger->log(LogLevel::DEBUG, "remaining width: {$remainingWidth}, length: {$remainingLength}, depth: {$remainingDepth}");
292		$this->logger->log(LogLevel::DEBUG, "layerWidth: {$layerWidth}, layerLength: {$layerLength}, layerDepth: {$layerDepth}");
293	4581
294		$itemWidth = $itemToPack->getWidth();
295	4581	$itemLength = $itemToPack->getLength();
296	4581
297		if ($this->fitsGap($itemToPack, $remainingWidth, $remainingLength)) {
298	4581
299	4572	$packedItems->insert($items->extract());
300	4581	$remainingWeight -= $itemToPack->getWeight();
301	3158
302	3158	$nextItem = !$items->isEmpty() ? $items->top() : null;
303	3158	if ($this->fitsBetterRotated($itemToPack, $nextItem, $remainingWidth, $remainingLength)) {
304	3158	$this->logger->log(LogLevel::DEBUG, "fits (better) unrotated");
305	3158	$remainingLength -= $itemLength;
306		$layerLength += $itemLength;
307	4536	$layerWidth = max($itemWidth, $layerWidth);
308	4536	} else {
309	4536	$this->logger->log(LogLevel::DEBUG, "fits (better) rotated");
310	4536	$remainingLength -= $itemWidth;
311		$layerLength += $itemWidth;
312	4581	$layerWidth = max($itemLength, $layerWidth);
313		}
314		$layerDepth = max($layerDepth, $itemToPack->getDepth()); //greater than 0, items will always be less deep
315	4581
316	4581	//allow items to be stacked in place within the same footprint up to current layerdepth
317	4550	$maxStackDepth = $layerDepth - $itemToPack->getDepth();
318	4550	while (!$items->isEmpty() && $this->canStackItemInLayer($itemToPack, $items->top(), $maxStackDepth, $remainingWeight)) {
319	4550	$remainingWeight -= $items->top()->getWeight();
320	4550	$maxStackDepth -= $items->top()->getDepth();
321	4550	$packedItems->insert($items->extract());
322	285	}
323	285	} else {
324	285	if ($remainingWidth >= min($itemWidth, $itemLength) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
325	285	$this->logger->log(LogLevel::DEBUG, "No more fit in lengthwise, resetting for new row");
326		$remainingLength += $layerLength;
327	4550	$remainingWidth -= $layerWidth;
328		$layerWidth = $layerLength = 0;
329	285	continue;
330	4581	} elseif ($remainingLength < min($itemWidth, $itemLength) \|\| $layerDepth == 0) {
331		$this->logger->log(LogLevel::DEBUG, "doesn't fit on layer even when empty");
332	4562	$items->extract();
333	4502	continue;
334	4502	}
335	4502
336	4502	$remainingWidth = $layerWidth ? min(floor($layerWidth * 1.1), $box->getInnerWidth()) : $box->getInnerWidth();
337	4502	$remainingLength = $layerLength ? min(floor($layerLength * 1.1), $box->getInnerLength()) : $box->getInnerLength();
338		$remainingDepth -= $layerDepth;
339
340	4549	$layerWidth = $layerLength = $layerDepth = 0;
341	4153	$this->logger->log(LogLevel::DEBUG, "doesn't fit, so starting next vertical layer");
342	4153	}
343	4153	}
344		$this->logger->log(LogLevel::DEBUG, "done with this box");
345		return new PackedBox($box, $packedItems, $remainingWidth, $remainingLength, $remainingDepth, $remainingWeight);
346	4487	}
347	4487
348	4487	/**
349		* @param Item $item
350	4487	* @param int $remainingDepth
351	4487	* @param int $remainingWeight
352		* @return bool
353	4581	*/
354	4581	protected function isItemTooLargeForBox(Item $item, $remainingDepth, $remainingWeight) {
355	4581	return $item->getDepth() > $remainingDepth \|\| $item->getWeight() > $remainingWeight;
356		}
357
358		/**
359		* Figure out space left for next item if we pack this one in it's regular orientation
360		* @param Item $item
361		* @param int $remainingWidth
362		* @param int $remainingLength
363		* @return int
364		*/
365		protected function fitsSameGap(Item $item, $remainingWidth, $remainingLength) {
366		return min($remainingWidth - $item->getWidth(), $remainingLength - $item->getLength());
367		}
368
369		/**
370		* Figure out space left for next item if we pack this one rotated by 90deg
371		* @param Item $item
372		* @param int $remainingWidth
373		* @param int $remainingLength
374		* @return int
375		*/
376		protected function fitsRotatedGap(Item $item, $remainingWidth, $remainingLength) {
377		return min($remainingWidth - $item->getLength(), $remainingLength - $item->getWidth());
378		}
379
380		/**
381		* @param Item $item
382		* @param Item\|null $nextItem
383		* @param $remainingWidth
384		* @param $remainingLength
385		* @return bool
386		*/
387		protected function fitsBetterRotated(Item $item, Item $nextItem = null, $remainingWidth, $remainingLength) {
388
389		$fitsSameGap = $this->fitsSameGap($item, $remainingWidth, $remainingLength);
390		$fitsRotatedGap = $this->fitsRotatedGap($item, $remainingWidth, $remainingLength);
391
392		return !!($fitsRotatedGap < 0 \|\|
393		($fitsSameGap >= 0 && $fitsSameGap <= $fitsRotatedGap) \|\|
394		($item->getWidth() <= $remainingWidth && $nextItem == $item && $remainingLength >= 2 * $item->getLength()));
395		}
396
397		/**
398		* Does item fit in specified gap
399		* @param Item $item
400		* @param $remainingWidth
401		* @param $remainingLength
402		* @return bool
403		*/
404		protected function fitsGap(Item $item, $remainingWidth, $remainingLength) {
405		return $this->fitsSameGap($item, $remainingWidth, $remainingLength) >= 0 \|\|
406		$this->fitsRotatedGap($item, $remainingWidth, $remainingLength) >= 0;
407		}
408
409		/**
410		* Figure out if we can stack the next item vertically on top of this rather than side by side
411		* Used when we've packed a tall item, and have just put a shorter one next to it
412		* @param Item $item
413		* @param Item $nextItem
414		* @param $maxStackDepth
415		* @param $remainingWeight
416		* @return bool
417		*/
418		protected function canStackItemInLayer(Item $item, Item $nextItem, $maxStackDepth, $remainingWeight)
419		{
420		return $nextItem->getDepth() <= $maxStackDepth &&
421		$nextItem->getWeight() <= $remainingWeight &&
422		$nextItem->getWidth() <= $item->getWidth() &&
423		$nextItem->getLength() <= $item->getLength();
424		}
425
426		/**
427		* @param $layerWidth
428		* @param $layerLength
429		* @param $layerDepth
430		* @return bool
431		*/
432		protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
433		return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
434		}
435
436		/**
437		* Pack as many items as possible into specific given box
438		* @deprecated
439		* @param Box $box
440		* @param ItemList $items
441		* @return ItemList items packed into box
442		*/
443		public function packBox(Box $box, ItemList $items)
444		{
445		$packedBox = $this->packIntoBox($box, $items);
446		return $packedBox->getItems();
447		}
448		}
449

dvdoug / BoxPacker

Push — master ( ff9def...abda0a )

Packer::fitsGap() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like