Completed
Push — master ( 17ecec...f96e7f )
by Doug
51:32 queued 50:04
created

Packer::findBestBoxFromIteration()   A

Complexity

Conditions 1
Paths 1

Size

Total Lines 5
Code Lines 3

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 3
CRAP Score 1

Importance

Changes 0
Metric Value
dl 0
loc 5
ccs 3
cts 3
cp 1
rs 9.4285
c 0
b 0
f 0
cc 1
eloc 3
nc 1
nop 1
crap 1
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 function array_unshift;
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
 * @author Doug Wright
19
 * @package BoxPacker
20
 */
21
class Packer implements LoggerAwareInterface
22
{
23
    use LoggerAwareTrait;
24
25
    /**
26
     * Number of boxes at which balancing weight is deemed not worth it
27
     * @var int
28
     */
29
    protected $maxBoxesToBalanceWeight = 12;
30
31
    /**
32
     * List of items to be packed
33
     * @var ItemList
34
     */
35
    protected $items;
36
37
    /**
38
     * List of box sizes available to pack items into
39
     * @var BoxList
40
     */
41
    protected $boxes;
42
43
    /**
44
     * Constructor
45
     */
46 27
    public function __construct()
47
    {
48 27
        $this->items = new ItemList();
49 27
        $this->boxes = new BoxList();
50
51 27
        $this->logger = new NullLogger();
52
    }
53
54
    /**
55
     * Add item to be packed
56
     * @param Item $item
57
     * @param int  $qty
58
     */
59 26
    public function addItem(Item $item, int $qty = 1): void
60
    {
61 26
        for ($i = 0; $i < $qty; $i++) {
62 26
            $this->items->insert($item);
63
        }
64 26
        $this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}");
65
    }
66
67
    /**
68
     * Set a list of items all at once
69
     * @param \Traversable|array $items
70
     */
71 2
    public function setItems($items): void
72
    {
73 2
        if ($items instanceof ItemList) {
74
            $this->items = clone $items;
75
        } else {
76 2
            $this->items = new ItemList();
77 2
            foreach ($items as $item) {
78 2
                $this->items->insert($item);
79
            }
80
        }
81 2
    }
82
83
    /**
84
     * Add box size
85
     * @param Box $box
86
     */
87 25
    public function addBox(Box $box): void
88
    {
89 25
        $this->boxes->insert($box);
90 25
        $this->logger->log(LogLevel::INFO, "added box {$box->getReference()}");
91
    }
92
93
    /**
94
     * Add a pre-prepared set of boxes all at once
95
     * @param BoxList $boxList
96
     */
97 2
    public function setBoxes(BoxList $boxList): void
98
    {
99 2
        $this->boxes = $boxList;
100
    }
101
102
    /**
103
     * Number of boxes at which balancing weight is deemed not worth the extra computation time
104
     * @return int
105
     */
106 1
    public function getMaxBoxesToBalanceWeight(): int
107
    {
108 1
        return $this->maxBoxesToBalanceWeight;
109
    }
110
111
    /**
112
     * Number of boxes at which balancing weight is deemed not worth the extra computation time
113
     * @param int $maxBoxesToBalanceWeight
114
     */
115 2
    public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight)
116
    {
117 2
        $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
118
    }
119
120
    /**
121
     * Pack items into boxes
122
     *
123
     * @return PackedBoxList
124
     */
125 26
    public function pack(): PackedBoxList
126
    {
127 26
        $packedBoxes = $this->doVolumePacking();
128
129
        //If we have multiple boxes, try and optimise/even-out weight distribution
130 24
        if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
131 6
            $redistributor = new WeightRedistributor($this->boxes);
132 6
            $redistributor->setLogger($this->logger);
133 6
            $packedBoxes = $redistributor->redistributeWeight($packedBoxes);
134
        }
135
136 24
        $this->logger->log(LogLevel::INFO, "packing completed, {$packedBoxes->count()} boxes");
137 24
        return $packedBoxes;
138
    }
139
140
    /**
141
     * Pack items into boxes using the principle of largest volume item first
142
     *
143
     * @throws ItemTooLargeException
144
     * @return PackedBoxList
145
     */
146 26
    public function doVolumePacking(): PackedBoxList
147
    {
148
149 26
        $packedBoxes = new PackedBoxList;
150
151
        //Keep going until everything packed
152 26
        while ($this->items->count()) {
153 26
            $packedBoxesIteration = [];
154
155
            //Loop through boxes starting with smallest, see what happens
156 26
            foreach ($this->boxes as $box) {
157 25
                $volumePacker = new VolumePacker($box, clone $this->items);
158 25
                $volumePacker->setLogger($this->logger);
159 25
                $packedBox = $volumePacker->pack();
160 25
                if ($packedBox->getItems()->count()) {
161 25
                    $packedBoxesIteration[] = $packedBox;
162
163
                    //Have we found a single box that contains everything?
164 25
                    if ($packedBox->getItems()->count() === $this->items->count()) {
165
                        break;
166
                    }
167
                }
168
            }
169
170
            //Check iteration was productive
171 26
            if (!$packedBoxesIteration) {
0 ignored issues
show
Bug Best Practice introduced by
The expression $packedBoxesIteration of type array is implicitly converted to a boolean; are you sure this is intended? If so, consider using empty($expr) instead to make it clear that you intend to check for an array without elements.

This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent.

Consider making the comparison explicit by using empty(..) or ! empty(...) instead.

Loading history...
172 2
                throw new ItemTooLargeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box', $this->items->top());
173
            }
174
175
            //Find best box of iteration, and remove packed items from unpacked list
176 25
            $bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
177 25
            $unPackedItems = iterator_to_array($this->items, false);
178 25
            foreach ($bestBox->getItems() as $packedItem) {
179 25
                foreach ($unPackedItems as $unpackedKey => $unpackedItem) {
180 25
                    if ($packedItem->getItem() === $unpackedItem) {
181 25
                        unset($unPackedItems[$unpackedKey]);
182 25
                        break;
183
                    }
184
                }
185
            }
186 25
            $unpackedItemList = new ItemList();
187 25
            foreach ($unPackedItems as $unpackedItem) {
188 8
                $unpackedItemList->insert($unpackedItem);
189
            }
190 25
            $this->items = $unpackedItemList;
191 25
            $packedBoxes->insert($bestBox);
192
193
        }
194
195 24
        return $packedBoxes;
196
    }
197
198
    /**
199
     * @param PackedBox[] $packedBoxes
200
     *
201
     * @return PackedBox
202
     */
203 25
    private function findBestBoxFromIteration($packedBoxes): PackedBox
204
    {
205 25
        usort($packedBoxes, [$this, 'compare']);
206 25
        return array_shift($packedBoxes);
207
    }
208
209
    /**
210
     * @param PackedBox $boxA
211
     * @param PackedBox $boxB
212
     *
213
     * @return int
214
     */
215 3 View Code Duplication
    private static function compare(PackedBox $boxA, PackedBox $boxB): int
0 ignored issues
show
Duplication introduced by
This method seems to be duplicated in your project.

Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.

You can also find more detailed suggestions in the “Code” section of your repository.

Loading history...
216
    {
217 3
        $choice = $boxB->getItems()->count() <=> $boxA->getItems()->count();
218 3
        if ($choice === 0) {
219
            $choice = $boxA->getInnerVolume() <=> $boxB->getInnerVolume();
220
        }
221 3
        if ($choice === 0) {
222
            $choice = $boxA->getWeight() <=> $boxB->getWeight();
223
        }
224 3
        return $choice;
225
    }
226
}
227