WeightRedistributor::didRepackActuallyHelp() - Code Metrics - Inspection of "Rework weight redistribution to not be a single hu..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — weight_redistributor ( 060e5b...8de9a1 )

by Doug

created 2018-01-07 14:34 UTC

WeightRedistributor::didRepackActuallyHelp() A

↳ Parent: WeightRedistributor

Complexity

Conditions	1
Paths	1

Size

Total Lines	10
Code Lines	6

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	2

Importance

Changes

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

<?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 WeightRedistributor implements LoggerAwareInterface
{
    use LoggerAwareTrait;

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

    /**
     * Constructor.
     *
     * @param BoxList $boxList
     */
    public function __construct(BoxList $boxList)
    {
        $this->boxes = $boxList;
        $this->logger = new NullLogger();
    }

    /**
     * Given a solution set of packed boxes, repack them to achieve optimum weight distribution.
     *
     * @param PackedBoxList $originalBoxes
     *
     * @return PackedBoxList
     */
    public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList
    {
        $targetWeight = $originalBoxes->getMeanWeight();
        $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, function (PackedBox $boxA, PackedBox $boxB) {
            return $boxB->getWeight() <=> $boxA->getWeight();
        });

        try {
            do {
                $iterationSuccessful = false;

                foreach ($boxes as $a => &$boxA) {
                    foreach ($boxes as $b => &$boxB) {
                        if ($b <= $a) {
                            continue; //same box, or already seen in the loop
                        }

                        if ($boxA->getWeight() === $boxB->getWeight()) {
                            continue; //same box, or already seen in the loop
                        }

                        $iterationSuccessful = $this->equaliseWeight($boxA, $boxB, $targetWeight);
                        if ($boxA === null) {
                            unset($boxes[$a]);
                        }
                        if ($boxB === null) {
                            unset($boxes[$b]);
                        }
                        if ($iterationSuccessful) {
                            break 2;
                        }
                    }
                }
            } while ($iterationSuccessful);
        } catch (IncreasedBoxCountException $e) {
            assert(false); // if development, don't want to silently bypass
            return $originalBoxes;
        }

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

        return $packedBoxes;
    }

    /**
     * Attempt to equalise weight distribution between 2 boxes.
     *
     * @param PackedBox $boxA
     * @param PackedBox $boxB
     * @param float     $targetWeight
     *
     * @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() + $boxB->getWeight() > $targetWeight) {
                continue; // moving this item would harm more than help
            }

            $newLighterBoxes = $this->doVolumeRepack(array_merge($underWeightBoxItems, [$overWeightItem]));
function acceptsInteger($int) { }

$x = '123'; // string "123"

// Instead of
acceptsInteger($x);

// we recommend to use
acceptsInteger((integer) $x);
            if (count($newLighterBoxes) !== 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;

                return true;
            } else {
                unset($overWeightBoxItems[$key]);
                $newHeavierBoxes = $this->doVolumeRepack($overWeightBoxItems);
function acceptsInteger($int) { }

$x = '123'; // string "123"

// Instead of
acceptsInteger($x);

// we recommend to use
acceptsInteger((integer) $x);
                if (count($newHeavierBoxes) !== 1) {
                    throw new IncreasedBoxCountException('Edge case, additional box was needed');
                }

                if ($this->didRepackActuallyHelp($boxA, $boxB, $newHeavierBoxes->top(), $newLighterBoxes->top())) {
                    $boxB = $newLighterBoxes->top();
                    $boxA = $newHeavierBoxes->top();
                    $anyIterationSuccessful = true;
                }
            }
        }

        return $anyIterationSuccessful;
    }

    /**
     * Do a volume repack of a set of items.
     *
     * @param iterable $items
     *
     * @return PackedBoxList
     */
    private function doVolumeRepack(iterable $items): PackedBoxList
    {
        $packer = new Packer();
        $packer->setBoxes($this->boxes); // use the full set of boxes to allow smaller/larger for full efficiency
        $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.
     *
     * @param PackedBox $oldBoxA
     * @param PackedBox $oldBoxB
     * @param PackedBox $newBoxA
     * @param PackedBox $newBoxB
     *
     * @return bool
     */
    private 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 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 WeightRedistributor implements LoggerAwareInterface
22		{
23		use LoggerAwareTrait;
24
25		/**
26		* List of box sizes available to pack items into.
27		*
28		* @var BoxList
29		*/
30		private $boxes;
31
32		/**
33		* Constructor.
34		*
35		* @param BoxList $boxList
36		*/
37	1	public function __construct(BoxList $boxList)
38		{
39	1	$this->boxes = $boxList;
40	1	$this->logger = new NullLogger();
41	1	}
42
43		/**
44		* Given a solution set of packed boxes, repack them to achieve optimum weight distribution.
45		*
46		* @param PackedBoxList $originalBoxes
47		*
48		* @return PackedBoxList
49		*/
50	1	public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList
51		{
52	1	$targetWeight = $originalBoxes->getMeanWeight();
53	1	$this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");
54
55		/** @var PackedBox[] $boxes */
56	1	$boxes = iterator_to_array($originalBoxes);
57
58	1	usort($boxes, function (PackedBox $boxA, PackedBox $boxB) {
59	1	return $boxB->getWeight() <=> $boxA->getWeight();
60	1	});
61
62		try {
63		do {
64	1	$iterationSuccessful = false;
65
66	1	foreach ($boxes as $a => &$boxA) {
67	1	foreach ($boxes as $b => &$boxB) {
68	1	if ($b <= $a) {
69	1	continue; //same box, or already seen in the loop
70		}
71
72	1	if ($boxA->getWeight() === $boxB->getWeight()) {
73	1	continue; //same box, or already seen in the loop
74		}
75
76	1	$iterationSuccessful = $this->equaliseWeight($boxA, $boxB, $targetWeight);
77	1	if ($boxA === null) {
78		unset($boxes[$a]);
79		}
80	1	if ($boxB === null) {
81		unset($boxes[$b]);
82		}
83	1	if ($iterationSuccessful) {
84	1	break 2;
85		}
86		}
87		}
88	1	} while ($iterationSuccessful);
89		} catch (IncreasedBoxCountException $e) {
90		assert(false); // if development, don't want to silently bypass
91		return $originalBoxes;
92		}
93
94		//Combine back into a single list
95	1	$packedBoxes = new PackedBoxList();
96	1	$packedBoxes->insertFromArray($boxes);
97
98	1	return $packedBoxes;
99		}
100
101		/**
102		* Attempt to equalise weight distribution between 2 boxes.
103		*
104		* @param PackedBox $boxA
105		* @param PackedBox $boxB
106		* @param float $targetWeight
107		*
108		* @return bool was the weight rebalanced?
109		*/
110	1	private function equaliseWeight(PackedBox &$boxA, PackedBox &$boxB, float $targetWeight): bool
111		{
112	1	$anyIterationSuccessful = false;
113
114	1	if ($boxA->getWeight() > $boxB->getWeight()) {
115	1	$overWeightBox = $boxA;
116	1	$underWeightBox = $boxB;
117		} else {
118		$overWeightBox = $boxB;
119		$underWeightBox = $boxA;
120		}
121
122	1	$overWeightBoxItems = $overWeightBox->getItems()->asItemArray();
123	1	$underWeightBoxItems = $underWeightBox->getItems()->asItemArray();
124
125	1	foreach ($overWeightBoxItems as $key => $overWeightItem) {
126	1	if ($overWeightItem->getWeight() + $boxB->getWeight() > $targetWeight) {
127	1	continue; // moving this item would harm more than help
128		}
129
130		$newLighterBoxes = $this->doVolumeRepack(array_merge($underWeightBoxItems, [$overWeightItem]));
		0 ignored issues – show Documentation introduced 2018-01-07 14:36 UTC by Report Bug Copy Issue Report `array_merge($underWeight...array($overWeightItem))` is of type `array<integer,object<DVD...ug\\BoxPacker\\Item>"}>`, but the function expects a `object<DVDoug\BoxPacker\iterable>`. It seems like the type of the argument is not accepted by the function/method which you are calling. In some cases, in particular if PHP’s automatic type-juggling kicks in this might be fine. In other cases, however this might be a bug. We suggest to add an explicit type cast like in the following example: function acceptsInteger($int) { } $x = '123'; // string "123" // Instead of acceptsInteger($x); // we recommend to use acceptsInteger((integer) $x); Loading history...
131		if (count($newLighterBoxes) !== 1) {
132		continue; //only want to move this item if it still fits in a single box
133		}
134
135		$underWeightBoxItems[] = $overWeightItem;
136
137		if (count($overWeightBoxItems) === 1) { //sometimes a repack can be efficient enough to eliminate a box
138		$boxB = $newLighterBoxes->top();
139		$boxA = null;
140
141		return true;
142		} else {
143		unset($overWeightBoxItems[$key]);
144		$newHeavierBoxes = $this->doVolumeRepack($overWeightBoxItems);
		0 ignored issues – show Documentation introduced 2018-01-07 14:36 UTC by Report Bug Copy Issue Report `$overWeightBoxItems` is of type `array<integer,object<DVDoug\BoxPacker\Item>>`, but the function expects a `object<DVDoug\BoxPacker\iterable>`. It seems like the type of the argument is not accepted by the function/method which you are calling. In some cases, in particular if PHP’s automatic type-juggling kicks in this might be fine. In other cases, however this might be a bug. We suggest to add an explicit type cast like in the following example: function acceptsInteger($int) { } $x = '123'; // string "123" // Instead of acceptsInteger($x); // we recommend to use acceptsInteger((integer) $x); Loading history...
145		if (count($newHeavierBoxes) !== 1) {
146		throw new IncreasedBoxCountException('Edge case, additional box was needed');
147		}
148
149		if ($this->didRepackActuallyHelp($boxA, $boxB, $newHeavierBoxes->top(), $newLighterBoxes->top())) {
150		$boxB = $newLighterBoxes->top();
151		$boxA = $newHeavierBoxes->top();
152		$anyIterationSuccessful = true;
153		}
154		}
155		}
156
157	1	return $anyIterationSuccessful;
158		}
159
160		/**
161		* Do a volume repack of a set of items.
162		*
163		* @param iterable $items
164		*
165		* @return PackedBoxList
166		*/
167		private function doVolumeRepack(iterable $items): PackedBoxList
168		{
169		$packer = new Packer();
170		$packer->setBoxes($this->boxes); // use the full set of boxes to allow smaller/larger for full efficiency
171		$packer->setItems($items);
172
173		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		* @param PackedBox $oldBoxA
182		* @param PackedBox $oldBoxB
183		* @param PackedBox $newBoxA
184		* @param PackedBox $newBoxB
185		*
186		* @return bool
187		*/
188		private function didRepackActuallyHelp(PackedBox $oldBoxA, PackedBox $oldBoxB, PackedBox $newBoxA, PackedBox $newBoxB): bool
189		{
190		$oldList = new PackedBoxList();
191		$oldList->insertFromArray([$oldBoxA, $oldBoxB]);
192
193		$newList = new PackedBoxList();
194		$newList->insertFromArray([$newBoxA, $newBoxB]);
195
196		return $newList->getWeightVariance() < $oldList->getWeightVariance();
197		}
198		}
199

dvdoug / BoxPacker

Push — weight_redistributor ( 060e5b...8de9a1 )

WeightRedistributor::didRepackActuallyHelp() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like