WeightRedistributor::classifyBoxes() - Code Metrics - Inspection of "Extract box classification logic" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — weight_redistributor ( b07968 )

by Doug

created 2017-12-30 17:55 UTC

WeightRedistributor::classifyBoxes() A

↳ Parent: WeightRedistributor

Complexity

Conditions	4
Paths	4

Size

Total Lines	19
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	12
CRAP Score	4

Importance

Changes

Metric	Value
dl	0
loc	19
ccs	12
cts	12
cp	1
rs	9.2
c	0
b	0
f	0
cc	4
eloc	12
nc	4
nop	2
crap	4

<?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
     */
    protected $boxes;

    /**
     * Boxes over the target weight
     * @var PackedBox[]
     */
    protected $overWeightBoxes = [];

    /**
     * Boxes exactly at the target weight
     * @var PackedBox[]
     */
    protected $targetWeightBoxes = [];

    /**
     * Boxes under the target weight
     * @var PackedBox[]
     */
    protected $underWeightBoxes = [];

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

        $this->classifyBoxes($originalBoxes, $targetWeight);

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

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

            foreach ($this->underWeightBoxes as $u => $underWeightBox) {
                $this->logger->log(LogLevel::DEBUG, 'Underweight Box '.$u);
                foreach ($this->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;
                                }

                                $this->overWeightBoxes[$o] = $newHeavierBoxes->top();
                            } else {
                                unset($this->overWeightBoxes[$o]);
                            }
                            $this->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
        $newPackedBoxes = new PackedBoxList();
        $newPackedBoxes->insertFromArray($this->overWeightBoxes);
        $newPackedBoxes->insertFromArray($this->targetWeightBoxes);
        $newPackedBoxes->insertFromArray($this->underWeightBoxes);

        return $newPackedBoxes;
    }

    /**
     * Classify boxes into under/target/overweight
     * @param PackedBoxList $boxes
     * @param float $targetWeight
     */
    protected function classifyBoxes(PackedBoxList $boxes, float $targetWeight): void
    {
        // reset any previous working state
        $this->underWeightBoxes = [];
        $this->targetWeightBoxes = [];
        $this->overWeightBoxes = [];

        /** @var PackedBox $packedBox */
        foreach ($boxes as $packedBox) {
            $boxWeight = $packedBox->getWeight();
            if ($boxWeight > $targetWeight) {
                $this->overWeightBoxes[] = $packedBox;
            } elseif ($boxWeight < $targetWeight) {
                $this->underWeightBoxes[] = $packedBox;
            } else {
                $this->targetWeightBoxes[] = $packedBox;
            }
        }
    }

    /**
     * @param PackedBox $boxA
     * @param PackedBox $boxB
     *
     * @return int
     */
    protected 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		*
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		* @var BoxList
28		*/
29		protected $boxes;
30
31		/**
32		* Boxes over the target weight
33		* @var PackedBox[]
34		*/
35		protected $overWeightBoxes = [];
36
37		/**
38		* Boxes exactly at the target weight
39		* @var PackedBox[]
40		*/
41		protected $targetWeightBoxes = [];
42
43		/**
44		* Boxes under the target weight
45		* @var PackedBox[]
46		*/
47		protected $underWeightBoxes = [];
48
49		/**
50		* Constructor.
51		*
52		* @param BoxList $boxList
53		*/
54	1	public function __construct(BoxList $boxList)
55		{
56	1	$this->boxes = $boxList;
57	1	$this->logger = new NullLogger();
58	1	}
59
60		/**
61		* Given a solution set of packed boxes, repack them to achieve optimum weight distribution.
62		*
63		* @param PackedBoxList $originalBoxes
64		*
65		* @return PackedBoxList
66		*/
67	1	public function redistributeWeight(PackedBoxList $originalBoxes): PackedBoxList
68		{
69	1	$targetWeight = $originalBoxes->getMeanWeight();
70	1	$this->logger->log(LogLevel::DEBUG, "repacking for weight distribution, weight variance {$originalBoxes->getWeightVariance()}, target weight {$targetWeight}");
71
72	1	$this->classifyBoxes($originalBoxes, $targetWeight);
73
74		do { //Keep moving items from most overweight box to most underweight box
75	1	$tryRepack = false;
76	1	$this->logger->log(LogLevel::DEBUG, 'boxes under/over target: '.count($this->underWeightBoxes).'/'.count($this->overWeightBoxes));
77
78	1	usort($this->overWeightBoxes, [$this, 'sortMoreSpaceFirst']);
79	1	usort($this->underWeightBoxes, [$this, 'sortMoreSpaceFirst']);
80
81	1	foreach ($this->underWeightBoxes as $u => $underWeightBox) {
82	1	$this->logger->log(LogLevel::DEBUG, 'Underweight Box '.$u);
83	1	foreach ($this->overWeightBoxes as $o => $overWeightBox) {
84	1	$this->logger->log(LogLevel::DEBUG, 'Overweight Box '.$o);
85	1	$overWeightBoxItems = $overWeightBox->getItems()->asItemArray();
86
87		//For each item in the heavier box, try and move it to the lighter one
88		/** @var Item $overWeightBoxItem */
89	1	foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) {
90	1	$this->logger->log(LogLevel::DEBUG, 'Overweight Item '.$oi);
91	1	if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $targetWeight) {
92	1	$this->logger->log(LogLevel::DEBUG, 'Skipping item for hindering weight distribution');
93	1	continue; //skip if moving this item would hinder rather than help weight distribution
94		}
95
96		$newItemsForLighterBox = $underWeightBox->getItems()->asItemArray();
97		$newItemsForLighterBox[] = $overWeightBoxItem;
98
99		$newLighterBoxPacker = new Packer(); //we may need a bigger box
100		$newLighterBoxPacker->setBoxes($this->boxes);
101		$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...
102		$this->logger->log(LogLevel::INFO, '[ATTEMPTING TO PACK LIGHTER BOX]');
103		$newLighterBox = $newLighterBoxPacker->doVolumePacking()->top();
104
105		if ($newLighterBox->getItems()->count() === count($newItemsForLighterBox)) { //new item fits
106		$this->logger->log(LogLevel::DEBUG, 'New item fits');
107		unset($overWeightBoxItems[$oi]); //now packed in different box
108
109		if (count($overWeightBoxItems) > 0) {
110		$newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box
111		$newHeavierBoxPacker->setBoxes($this->boxes);
112		$newHeavierBoxPacker->setItems($overWeightBoxItems);
113
114		$this->logger->log(LogLevel::INFO, '[ATTEMPTING TO PACK HEAVIER BOX]');
115		$newHeavierBoxes = $newHeavierBoxPacker->doVolumePacking();
116		if ($newHeavierBoxes->count()
117		> 1) { //found an edge case in packing algorithm that increased box count
118		$this->logger->log(
119		LogLevel::INFO,
120		'[REDISTRIBUTING WEIGHT] Abandoning redistribution, because new packing is less efficient than original'
121		);
122
123		return $originalBoxes;
124		}
125
126		$this->overWeightBoxes[$o] = $newHeavierBoxes->top();
127		} else {
128		unset($this->overWeightBoxes[$o]);
129		}
130		$this->underWeightBoxes[$u] = $newLighterBox;
131
132		$tryRepack = true; //we did some work, so see if we can do even better
133	1	break 3;
134		}
135		}
136		}
137		}
138	1	} while ($tryRepack);
139
140		//Combine back into a single list
141	1	$newPackedBoxes = new PackedBoxList();
142	1	$newPackedBoxes->insertFromArray($this->overWeightBoxes);
143	1	$newPackedBoxes->insertFromArray($this->targetWeightBoxes);
144	1	$newPackedBoxes->insertFromArray($this->underWeightBoxes);
145
146	1	return $newPackedBoxes;
147		}
148
149		/**
150		* Classify boxes into under/target/overweight
151		* @param PackedBoxList $boxes
152		* @param float $targetWeight
153		*/
154	1	protected function classifyBoxes(PackedBoxList $boxes, float $targetWeight): void
155		{
156		// reset any previous working state
157	1	$this->underWeightBoxes = [];
158	1	$this->targetWeightBoxes = [];
159	1	$this->overWeightBoxes = [];
160
161		/** @var PackedBox $packedBox */
162	1	foreach ($boxes as $packedBox) {
163	1	$boxWeight = $packedBox->getWeight();
164	1	if ($boxWeight > $targetWeight) {
165	1	$this->overWeightBoxes[] = $packedBox;
166	1	} elseif ($boxWeight < $targetWeight) {
167	1	$this->underWeightBoxes[] = $packedBox;
168		} else {
169	1	$this->targetWeightBoxes[] = $packedBox;
170		}
171		}
172	1	}
173
174		/**
175		* @param PackedBox $boxA
176		* @param PackedBox $boxB
177		*
178		* @return int
179		*/
180	1	protected function sortMoreSpaceFirst(PackedBox $boxA, PackedBox $boxB): int
181		{
182	1	$choice = $boxB->getItems()->count() - $boxA->getItems()->count();
183	1	if ($choice === 0) {
184	1	$choice = $boxA->getInnerVolume() - $boxB->getInnerVolume();
185		}
186	1	if ($choice === 0) {
187	1	$choice = $boxB->getWeight() - $boxA->getWeight();
188		}
189
190	1	return $choice;
191		}
192		}
193

dvdoug / BoxPacker

Push — weight_redistributor ( b07968 )

WeightRedistributor::classifyBoxes() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like