WeightRedistributor::doVolumeRepack() - Code Metrics - Inspection of "Backport changes from 3.x" - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — 1.x-dev ( f03c49...17b59f )

by Doug

created 2019-12-21 18:27 UTC

WeightRedistributor::doVolumeRepack() A

↳ Parent: WeightRedistributor

Complexity

Conditions	1
Paths	1

Size

Total Lines	7
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	5
CRAP Score	1

Importance

Changes

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

<?php
/**
 * Box packing (3D bin packing, knapsack problem).
 *
 * @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
 * @internal
 */
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 = clone $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)
    {
        $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();
        });

        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, function ($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.
     *
     * @param PackedBox $boxA
     * @param PackedBox $boxB
     * @param float     $targetWeight
     *
     * @return bool was the weight rebalanced?
     */
    private function equaliseWeight(PackedBox &$boxA, PackedBox &$boxB, $targetWeight)
    {
        $anyIterationSuccessful = false;

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

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

        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]));
            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);
                if (count($newHeavierBoxes) !== 1) {
                    continue;
                }

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

dvdoug / BoxPacker

Push — 1.x-dev ( f03c49...17b59f )

WeightRedistributor::doVolumeRepack() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like