WeightRedistributor::equaliseWeight() - Code Metrics - Inspection of "Add testcase for a bit of weight redistribution wi..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — limited_supply_boxes ( 794880...0d0189 )

by Doug

created 2020-01-18 22:24 UTC

WeightRedistributor::equaliseWeight() B

↳ Parent: WeightRedistributor

Complexity

Conditions	8
Paths	14

Size

Total Lines	55
Code Lines	35

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	34
CRAP Score	8.0014

Importance

Changes	3
Bugs	1	Features	0

Metric	Value
cc	8
eloc	35
c	3
b	1
f	0
nc	14
nop	3
dl	0
loc	55
ccs	34
cts	35
cp	0.9714
crap	8.0014
rs	8.1155

How to fix Long Method

<?php
/**
 * Box packing (3D bin packing, knapsack problem).
 *
 * @author Doug Wright
 */
declare(strict_types=1);

namespace DVDoug\BoxPacker;

use function array_filter;
use function array_merge;
use function count;
use function iterator_to_array;
use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\LogLevel;
use Psr\Log\NullLogger;
use SplObjectStorage;
use function usort;

/**
 * Actual packer.
 *
 * @author Doug Wright
 * @internal
 */
class WeightRedistributor implements LoggerAwareInterface
{
    use LoggerAwareTrait;

    /**
     * List of box sizes available to pack items into.
     *
     * @var BoxList
     */
    private $boxes;

    /**
     * Quantities available of each box type.
     *
     * @var SplObjectStorage
     */
    private $boxesQtyAvailable;

    /**
     * Constructor.
     */
    public function __construct(BoxList $boxList, SplObjectStorage $boxQuantitiesAvailable)
    {
        $this->boxes = $boxList;
        $this->boxesQtyAvailable = $boxQuantitiesAvailable;
        $this->logger = new NullLogger();
    }

    /**
     * Given a solution set of packed boxes, repack them to achieve optimum weight distribution.
     */
    public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList
    {
        $targetWeight = $originalBoxes->getMeanItemWeight();
        $this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");

        /** @var PackedBox[] $boxes */
        $boxes = iterator_to_array($originalBoxes);

        usort($boxes, static function (PackedBox $boxA, PackedBox $boxB) {
            return $boxB->getWeight() <=> $boxA->getWeight();
        });

        do {
            $iterationSuccessful = false;

            foreach ($boxes as $a => &$boxA) {
                foreach ($boxes as $b => &$boxB) {
                    if ($b <= $a || $boxA->getWeight() === $boxB->getWeight()) {
                        continue; //no need to evaluate
                    }

                    $iterationSuccessful = $this->equaliseWeight($boxA, $boxB, $targetWeight);
                    if ($iterationSuccessful) {
                        $boxes = array_filter($boxes, static function (?PackedBox $box) { //remove any now-empty boxes from the list
                            return $box instanceof PackedBox;
                        });
                        break 2;
                    }
                }
            }
        } while ($iterationSuccessful);

        //Combine back into a single list
        $packedBoxes = new PackedBoxList();
        $packedBoxes->insertFromArray($boxes);

        return $packedBoxes;
    }

    /**
     * Attempt to equalise weight distribution between 2 boxes.
     *
     * @return bool was the weight rebalanced?
     */
    private function equaliseWeight(PackedBox &$boxA, PackedBox &$boxB, float $targetWeight): bool
    {
        $anyIterationSuccessful = false;

        if ($boxA->getWeight() > $boxB->getWeight()) {
            $overWeightBox = $boxA;
            $underWeightBox = $boxB;
        } else {
            $overWeightBox = $boxB;
            $underWeightBox = $boxA;
        }

        $overWeightBoxItems = $overWeightBox->getItems()->asItemArray();
        $underWeightBoxItems = $underWeightBox->getItems()->asItemArray();

        foreach ($overWeightBoxItems as $key => $overWeightItem) {
            if ($overWeightItem->getWeight() + $underWeightBox->getItemWeight() > $targetWeight) {
                continue; // moving this item would harm more than help
            }

            $newLighterBoxes = $this->doVolumeRepack(array_merge($underWeightBoxItems, [$overWeightItem]), $underWeightBox->getBox());
            if ($newLighterBoxes->count() !== 1) {
                continue; //only want to move this item if it still fits in a single box
            }

            $underWeightBoxItems[] = $overWeightItem;

            if (count($overWeightBoxItems) === 1) { //sometimes a repack can be efficient enough to eliminate a box
                $boxB = $newLighterBoxes->top();
                $boxA = null;
                $this->boxesQtyAvailable[$boxB->getBox()] = $this->boxesQtyAvailable[$boxB->getBox()] - 1;
                $this->boxesQtyAvailable[$overWeightBox->getBox()] = $this->boxesQtyAvailable[$overWeightBox->getBox()] + 1;

                return true;
            }

            unset($overWeightBoxItems[$key]);
            $newHeavierBoxes = $this->doVolumeRepack($overWeightBoxItems, $overWeightBox->getBox());
            if (count($newHeavierBoxes) !== 1) {
                continue; //this should never happen, if we can pack n+1 into the box, we should be able to pack n
            }

            if (static::didRepackActuallyHelp($boxA, $boxB, $newHeavierBoxes->top(), $newLighterBoxes->top())) {
                $this->boxesQtyAvailable[$boxA->getBox()] = $this->boxesQtyAvailable[$boxA->getBox()] + 1;
                $this->boxesQtyAvailable[$boxB->getBox()] = $this->boxesQtyAvailable[$boxB->getBox()] + 1;
                $this->boxesQtyAvailable[$newHeavierBoxes->top()->getBox()] = $this->boxesQtyAvailable[$newHeavierBoxes->top()->getBox()] - 1;
                $this->boxesQtyAvailable[$newLighterBoxes->top()->getBox()] = $this->boxesQtyAvailable[$newLighterBoxes->top()->getBox()] - 1;
                $underWeightBox = $boxB = $newLighterBoxes->top();
                $boxA = $newHeavierBoxes->top();

                $anyIterationSuccessful = true;
            }
        }

        return $anyIterationSuccessful;
    }

    /**
     * Do a volume repack of a set of items.
     */
    private function doVolumeRepack(iterable $items, Box $currentBox): PackedBoxList
    {
        $packer = new Packer();
        $packer->setBoxes($this->boxes); // use the full set of boxes to allow smaller/larger for full efficiency
        foreach ($this->boxes as $box) {
            $packer->setBoxQuantity($box, $this->boxesQtyAvailable[$box]);
        }
        $packer->setBoxQuantity($currentBox, max(PHP_INT_MAX, $this->boxesQtyAvailable[$currentBox] + 1));
        $packer->setItems($items);

        return $packer->doVolumePacking();
    }

    /**
     * Not every attempted repack is actually helpful - sometimes moving an item between two otherwise identical
     * boxes, or sometimes the box used for the now lighter set of items actually weighs more when empty causing
     * an increase in total weight.
     */
    private static function didRepackActuallyHelp(PackedBox $oldBoxA, PackedBox $oldBoxB, PackedBox $newBoxA, PackedBox $newBoxB): bool
    {
        $oldList = new PackedBoxList();
        $oldList->insertFromArray([$oldBoxA, $oldBoxB]);

        $newList = new PackedBoxList();
        $newList->insertFromArray([$newBoxA, $newBoxB]);

        return $newList->getWeightVariance() < $oldList->getWeightVariance();
    }
}


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_filter;
12		use function array_merge;
13		use function count;
14		use function iterator_to_array;
15		use Psr\Log\LoggerAwareInterface;
16		use Psr\Log\LoggerAwareTrait;
17		use Psr\Log\LogLevel;
18		use Psr\Log\NullLogger;
19		use SplObjectStorage;
20		use function usort;
21
22		/**
23		* Actual packer.
24		*
25		* @author Doug Wright
26		* @internal
27		*/
28		class WeightRedistributor implements LoggerAwareInterface
29		{
30		use LoggerAwareTrait;
31
32		/**
33		* List of box sizes available to pack items into.
34		*
35		* @var BoxList
36		*/
37		private $boxes;
38
39		/**
40		* Quantities available of each box type.
41		*
42		* @var SplObjectStorage
43		*/
44		private $boxesQtyAvailable;
45
46		/**
47		* Constructor.
48		*/
49	14	public function __construct(BoxList $boxList, SplObjectStorage $boxQuantitiesAvailable)
50		{
51	14	$this->boxes = $boxList;
52	14	$this->boxesQtyAvailable = $boxQuantitiesAvailable;
53	14	$this->logger = new NullLogger();
54	14	}
55
56		/**
57		* Given a solution set of packed boxes, repack them to achieve optimum weight distribution.
58		*/
59	14	public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList
60		{
61	14	$targetWeight = $originalBoxes->getMeanItemWeight();
62	14	$this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");
63
64		/** @var PackedBox[] $boxes */
65	14	$boxes = iterator_to_array($originalBoxes);
66
67		usort($boxes, static function (PackedBox $boxA, PackedBox $boxB) {
68	14	return $boxB->getWeight() <=> $boxA->getWeight();
69	14	});
70
71		do {
72	14	$iterationSuccessful = false;
73
74	14	foreach ($boxes as $a => &$boxA) {
75	14	foreach ($boxes as $b => &$boxB) {
76	14	if ($b <= $a \|\| $boxA->getWeight() === $boxB->getWeight()) {
77	14	continue; //no need to evaluate
78		}
79
80	10	$iterationSuccessful = $this->equaliseWeight($boxA, $boxB, $targetWeight);
81	10	if ($iterationSuccessful) {
82		$boxes = array_filter($boxes, static function (?PackedBox $box) { //remove any now-empty boxes from the list
83	7	return $box instanceof PackedBox;
84	7	});
85	14	break 2;
86		}
87		}
88		}
89	14	} while ($iterationSuccessful);
90
91		//Combine back into a single list
92	14	$packedBoxes = new PackedBoxList();
93	14	$packedBoxes->insertFromArray($boxes);
94
95	14	return $packedBoxes;
96		}
97
98		/**
99		* Attempt to equalise weight distribution between 2 boxes.
100		*
101		* @return bool was the weight rebalanced?
102		*/
103	10	private function equaliseWeight(PackedBox &$boxA, PackedBox &$boxB, float $targetWeight): bool
104		{
105	10	$anyIterationSuccessful = false;
106
107	10	if ($boxA->getWeight() > $boxB->getWeight()) {
108	10	$overWeightBox = $boxA;
109	10	$underWeightBox = $boxB;
110		} else {
111	2	$overWeightBox = $boxB;
112	2	$underWeightBox = $boxA;
113		}
114
115	10	$overWeightBoxItems = $overWeightBox->getItems()->asItemArray();
116	10	$underWeightBoxItems = $underWeightBox->getItems()->asItemArray();
117
118	10	foreach ($overWeightBoxItems as $key => $overWeightItem) {
119	10	if ($overWeightItem->getWeight() + $underWeightBox->getItemWeight() > $targetWeight) {
120	9	continue; // moving this item would harm more than help
121		}
122
123	8	$newLighterBoxes = $this->doVolumeRepack(array_merge($underWeightBoxItems, [$overWeightItem]), $underWeightBox->getBox());
124	8	if ($newLighterBoxes->count() !== 1) {
125	3	continue; //only want to move this item if it still fits in a single box
126		}
127
128	7	$underWeightBoxItems[] = $overWeightItem;
129
130	7	if (count($overWeightBoxItems) === 1) { //sometimes a repack can be efficient enough to eliminate a box
131	1	$boxB = $newLighterBoxes->top();
132	1	$boxA = null;
133	1	$this->boxesQtyAvailable[$boxB->getBox()] = $this->boxesQtyAvailable[$boxB->getBox()] - 1;
134	1	$this->boxesQtyAvailable[$overWeightBox->getBox()] = $this->boxesQtyAvailable[$overWeightBox->getBox()] + 1;
135
136	1	return true;
137		}
138
139	7	unset($overWeightBoxItems[$key]);
140	7	$newHeavierBoxes = $this->doVolumeRepack($overWeightBoxItems, $overWeightBox->getBox());
141	7	if (count($newHeavierBoxes) !== 1) {
142		continue; //this should never happen, if we can pack n+1 into the box, we should be able to pack n
143		}
144
145	7	if (static::didRepackActuallyHelp($boxA, $boxB, $newHeavierBoxes->top(), $newLighterBoxes->top())) {
146	7	$this->boxesQtyAvailable[$boxA->getBox()] = $this->boxesQtyAvailable[$boxA->getBox()] + 1;
147	7	$this->boxesQtyAvailable[$boxB->getBox()] = $this->boxesQtyAvailable[$boxB->getBox()] + 1;
148	7	$this->boxesQtyAvailable[$newHeavierBoxes->top()->getBox()] = $this->boxesQtyAvailable[$newHeavierBoxes->top()->getBox()] - 1;
149	7	$this->boxesQtyAvailable[$newLighterBoxes->top()->getBox()] = $this->boxesQtyAvailable[$newLighterBoxes->top()->getBox()] - 1;
150	7	$underWeightBox = $boxB = $newLighterBoxes->top();
151	7	$boxA = $newHeavierBoxes->top();
152
153	7	$anyIterationSuccessful = true;
154		}
155		}
156
157	10	return $anyIterationSuccessful;
158		}
159
160		/**
161		* Do a volume repack of a set of items.
162		*/
163	8	private function doVolumeRepack(iterable $items, Box $currentBox): PackedBoxList
164		{
165	8	$packer = new Packer();
166	8	$packer->setBoxes($this->boxes); // use the full set of boxes to allow smaller/larger for full efficiency
167	8	foreach ($this->boxes as $box) {
168	8	$packer->setBoxQuantity($box, $this->boxesQtyAvailable[$box]);
169		}
170	8	$packer->setBoxQuantity($currentBox, max(PHP_INT_MAX, $this->boxesQtyAvailable[$currentBox] + 1));
171	8	$packer->setItems($items);
172
173	8	return $packer->doVolumePacking();
174		}
175
176		/**
177		* Not every attempted repack is actually helpful - sometimes moving an item between two otherwise identical
178		* boxes, or sometimes the box used for the now lighter set of items actually weighs more when empty causing
179		* an increase in total weight.
180		*/
181	7	private static function didRepackActuallyHelp(PackedBox $oldBoxA, PackedBox $oldBoxB, PackedBox $newBoxA, PackedBox $newBoxB): bool
182		{
183	7	$oldList = new PackedBoxList();
184	7	$oldList->insertFromArray([$oldBoxA, $oldBoxB]);
185
186	7	$newList = new PackedBoxList();
187	7	$newList->insertFromArray([$newBoxA, $newBoxB]);
188
189	7	return $newList->getWeightVariance() < $oldList->getWeightVariance();
190		}
191		}
192

dvdoug / BoxPacker

Push — limited_supply_boxes ( 794880...0d0189 )

WeightRedistributor::equaliseWeight() B

Complexity

Size

Duplication

Code Coverage

Importance

How to fix Long Method

Long Method

Duplication Side-by-Side

Filter issues like