WeightRedistributor::redistributeWeight() - Code Metrics - Inspection of "Future proof changes to ItemList implementation by..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — data_structures ( b3e6cb )

by Doug

created 2017-10-23 17:51 UTC

WeightRedistributor::redistributeWeight() C

↳ Parent: WeightRedistributor

Complexity

Conditions	12
Paths	32

Size

Total Lines	93
Code Lines	61

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	93
rs	5.034
c	0
b	0
f	0
cc	12
eloc	61
nc	32
nop	1

How to fix Long Method Complexity

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

    use LoggerAwareTrait;

    /**
     * List of box sizes available to pack items into
     * @var BoxList
     */
    protected $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}");

        $packedBoxes = new PackedBoxList;

        $overWeightBoxes = [];
        $underWeightBoxes = [];
        foreach ($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));

            usort($overWeightBoxes, [$this, 'sortMoreSpaceFirst']);
            usort($underWeightBoxes, [$this, 'sortMoreSpaceFirst']);

            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()->asItemArray();

                    //For each item in the heavier box, try and move it to the lighter one
                    /** @var Item $overWeightBoxItem */
                    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 = $underWeightBox->getItems()->asItemArray();
                        $newItemsForLighterBox[] = $overWeightBoxItem;

                        $newLighterBoxPacker = new Packer(); //we may need a bigger box
                        $newLighterBoxPacker->setBoxes($this->boxes);
                        $newLighterBoxPacker->setItems($newItemsForLighterBox);
function acceptsInteger($int) { }

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

// Instead of
acceptsInteger($x);

// we recommend to use
acceptsInteger((integer) $x);
                        $this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK LIGHTER BOX]");
                        $newLighterBox = $newLighterBoxPacker->doVolumePacking()->top();

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

                            if (count($overWeightBoxItems) > 0) {
                                $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 ($newHeavierBoxes->count()
                                    > 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->top();
                            } else {
                                unset($overWeightBoxes[$o]);
                            }
                            $underWeightBoxes[$u] = $newLighterBox;

                            $tryRepack = true; //we did some work, so see if we can do even better
                            break 3;
                        }
                    }
                }
            }
        } while ($tryRepack);

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

        return $packedBoxes;
    }

    /**
     * @param PackedBox $boxA
     * @param PackedBox $boxB
     *
     * @return int
     */
    private function sortMoreSpaceFirst(PackedBox $boxA, PackedBox $boxB): int
    {
        $choice = $boxB->getItems()->count() - $boxA->getItems()->count();
        if ($choice === 0) {
            $choice = $boxA->getInnerVolume() - $boxB->getInnerVolume();
        }
        if ($choice === 0) {
            $choice = $boxB->getWeight() - $boxA->getWeight();
        }
        return $choice;
    }
}


1			<?php
2			/**
3			* Box packing (3D bin packing, knapsack problem)
4			* @package BoxPacker
5			* @author Doug Wright
6			*/
7			declare(strict_types=1);
8			namespace DVDoug\BoxPacker;
9
10			use Psr\Log\LoggerAwareInterface;
11			use Psr\Log\LoggerAwareTrait;
12			use Psr\Log\LogLevel;
13			use Psr\Log\NullLogger;
14
15			/**
16			* Actual packer
17			* @author Doug Wright
18			* @package BoxPacker
19			*/
20			class WeightRedistributor implements LoggerAwareInterface
21			{
22
23			use LoggerAwareTrait;
24
25			/**
26			* List of box sizes available to pack items into
27			* @var BoxList
28			*/
29			protected $boxes;
30
31			/**
32			* Constructor
33			*
34			* @param BoxList $boxList
35			*/
36			public function __construct(BoxList $boxList)
37			{
38			$this->boxes = $boxList;
39			$this->logger = new NullLogger();
40			}
41
42			/**
43			* Given a solution set of packed boxes, repack them to achieve optimum weight distribution
44			*
45			* @param PackedBoxList $originalBoxes
46			* @return PackedBoxList
47			*/
48			public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList
49			{
50
51			$targetWeight = $originalBoxes->getMeanWeight();
52			$this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");
53
54			$packedBoxes = new PackedBoxList;
55
56			$overWeightBoxes = [];
57			$underWeightBoxes = [];
58			foreach ($originalBoxes as $packedBox) {
59			$boxWeight = $packedBox->getWeight();
60			if ($boxWeight > $targetWeight) {
61			$overWeightBoxes[] = $packedBox;
62			} elseif ($boxWeight < $targetWeight) {
63			$underWeightBoxes[] = $packedBox;
64			} else {
65			$packedBoxes->insert($packedBox); //target weight, so we'll keep these
66			}
67			}
68
69			do { //Keep moving items from most overweight box to most underweight box
70			$tryRepack = false;
71			$this->logger->log(LogLevel::DEBUG, 'boxes under/over target: ' . count($underWeightBoxes) . '/' . count($overWeightBoxes));
72
73			usort($overWeightBoxes, [$this, 'sortMoreSpaceFirst']);
74			usort($underWeightBoxes, [$this, 'sortMoreSpaceFirst']);
75
76			foreach ($underWeightBoxes as $u => $underWeightBox) {
77			$this->logger->log(LogLevel::DEBUG, 'Underweight Box ' . $u);
78			foreach ($overWeightBoxes as $o => $overWeightBox) {
79			$this->logger->log(LogLevel::DEBUG, 'Overweight Box ' . $o);
80			$overWeightBoxItems = $overWeightBox->getItems()->asItemArray();
81
82			//For each item in the heavier box, try and move it to the lighter one
83			/** @var Item $overWeightBoxItem */
84			foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) {
85			$this->logger->log(LogLevel::DEBUG, 'Overweight Item ' . $oi);
86			if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $targetWeight) {
87			$this->logger->log(LogLevel::DEBUG, 'Skipping item for hindering weight distribution');
88			continue; //skip if moving this item would hinder rather than help weight distribution
89			}
90
91			$newItemsForLighterBox = $underWeightBox->getItems()->asItemArray();
92			$newItemsForLighterBox[] = $overWeightBoxItem;
93
94			$newLighterBoxPacker = new Packer(); //we may need a bigger box
95			$newLighterBoxPacker->setBoxes($this->boxes);
96			$newLighterBoxPacker->setItems($newItemsForLighterBox);
			0 ignored issues – show Documentation introduced 2017-08-27 21:21 UTC by Report Bug Copy Issue Report `$newItemsForLighterBox` is of type `array<integer,?>`, 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...
97			$this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK LIGHTER BOX]");
98			$newLighterBox = $newLighterBoxPacker->doVolumePacking()->top();
99
100			if ($newLighterBox->getItems()->count() === count($newItemsForLighterBox)) { //new item fits
101			$this->logger->log(LogLevel::DEBUG, 'New item fits');
102			unset($overWeightBoxItems[$oi]); //now packed in different box
103
104			if (count($overWeightBoxItems) > 0) {
105			$newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box
106			$newHeavierBoxPacker->setBoxes($this->boxes);
107			$newHeavierBoxPacker->setItems($overWeightBoxItems);
108
109			$this->logger->log(LogLevel::INFO, "[ATTEMPTING TO PACK HEAVIER BOX]");
110			$newHeavierBoxes = $newHeavierBoxPacker->doVolumePacking();
111			if ($newHeavierBoxes->count()
112			> 1) { //found an edge case in packing algorithm that increased box count
113			$this->logger->log(
114			LogLevel::INFO,
115			"[REDISTRIBUTING WEIGHT] Abandoning redistribution, because new packing is less efficient than original"
116			);
117
118			return $originalBoxes;
119			}
120
121			$overWeightBoxes[$o] = $newHeavierBoxes->top();
122			} else {
123			unset($overWeightBoxes[$o]);
124			}
125			$underWeightBoxes[$u] = $newLighterBox;
126
127			$tryRepack = true; //we did some work, so see if we can do even better
128			break 3;
129			}
130			}
131			}
132			}
133			} while ($tryRepack);
134
135			//Combine back into a single list
136			$packedBoxes->insertFromArray($overWeightBoxes);
137			$packedBoxes->insertFromArray($underWeightBoxes);
138
139			return $packedBoxes;
140			}
141
142			/**
143			* @param PackedBox $boxA
144			* @param PackedBox $boxB
145			*
146			* @return int
147			*/
148			private function sortMoreSpaceFirst(PackedBox $boxA, PackedBox $boxB): int
149			{
150			$choice = $boxB->getItems()->count() - $boxA->getItems()->count();
151			if ($choice === 0) {
152			$choice = $boxA->getInnerVolume() - $boxB->getInnerVolume();
153			}
154			if ($choice === 0) {
155			$choice = $boxB->getWeight() - $boxA->getWeight();
156			}
157			return $choice;
158			}
159			}
160

dvdoug / BoxPacker

Push — data_structures ( b3e6cb )

WeightRedistributor::redistributeWeight() C

Complexity

Size

Duplication

Importance

How to fix Long Method Complexity

Long Method

Duplication Side-by-Side

Filter issues like