Passed
Pull Request — master (#308)
by
unknown
05:50 queued 03:55
created

Packer::packAllPermutations()   C

Complexity

Conditions 13
Paths 89

Size

Total Lines 60
Code Lines 38

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 0
CRAP Score 182

Importance

Changes 0
Metric Value
cc 13
eloc 38
c 0
b 0
f 0
nc 89
nop 0
dl 0
loc 60
ccs 0
cts 38
cp 0
crap 182
rs 6.6166

How to fix   Long Method    Complexity   

Long Method

Small methods make your code easier to understand, in particular if combined with a good name. Besides, if your method is small, finding a good name is usually much easier.

For example, if you find yourself adding comments to a method's body, this is usually a good sign to extract the commented part to a new method, and use the comment as a starting point when coming up with a good name for this new method.

Commonly applied refactorings include:

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 function array_merge;
12
use function array_pop;
13
use function count;
14
15
use DVDoug\BoxPacker\Exception\NoBoxesAvailableException;
16
17
use const PHP_INT_MAX;
18
19
use Psr\Log\LoggerAwareInterface;
20
use Psr\Log\LoggerInterface;
21
use Psr\Log\LogLevel;
22
use Psr\Log\NullLogger;
23
24
use function usort;
25
26
use WeakMap;
27
28
/**
29
 * Actual packer.
30
 */
31
class Packer implements LoggerAwareInterface
32
{
33
    private LoggerInterface $logger;
34
35
    protected int $maxBoxesToBalanceWeight = 12;
36
37
    protected ItemList $items;
38
39
    protected BoxList $boxes;
40
41
    /** @var WeakMap<Box, int> */
42
    protected WeakMap $boxQuantitiesAvailable;
43
44
    protected PackedBoxSorter $packedBoxSorter;
45
46
    protected bool $throwOnUnpackableItem = true;
47
48
    private bool $beStrictAboutItemOrdering = false;
49
50 24
    public function __construct()
51
    {
52 24
        $this->items = new ItemList();
53 24
        $this->boxes = new BoxList();
54 24
        $this->packedBoxSorter = new DefaultPackedBoxSorter();
55 24
        $this->boxQuantitiesAvailable = new WeakMap();
56
57 24
        $this->logger = new NullLogger();
58
    }
59
60
    public function setLogger(LoggerInterface $logger): void
61
    {
62
        $this->logger = $logger;
63
    }
64
65
    /**
66
     * Add item to be packed.
67
     */
68
    public function addItem(Item $item, int $qty = 1): void
69
    {
70
        $this->items->insert($item, $qty);
71
        $this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}", ['item' => $item]);
72
    }
73
74
    /**
75
     * Set a list of items all at once.
76
     * @param iterable<Item>|ItemList $items
77
     */
78 24
    public function setItems(iterable $items): void
79
    {
80 24
        if ($items instanceof ItemList) {
81 24
            $this->items = clone $items;
82
        } else {
83
            $this->items = new ItemList();
84
            foreach ($items as $item) {
85
                $this->items->insert($item);
86
            }
87
        }
88
    }
89
90
    /**
91
     * Add box size.
92
     */
93
    public function addBox(Box $box): void
94
    {
95
        $this->boxes->insert($box);
96
        $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
97
        $this->logger->log(LogLevel::INFO, "added box {$box->getReference()}", ['box' => $box]);
98
    }
99
100
    /**
101
     * Add a pre-prepared set of boxes all at once.
102
     */
103 24
    public function setBoxes(BoxList $boxList): void
104
    {
105 24
        $this->boxes = $boxList;
106 24
        foreach ($this->boxes as $box) {
107 24
            $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
108
        }
109
    }
110
111
    /**
112
     * Set the quantity of this box type available.
113
     */
114 24
    public function setBoxQuantity(Box $box, int $qty): void
115
    {
116 24
        $this->boxQuantitiesAvailable[$box] = $qty;
117
    }
118
119
    /**
120
     * Number of boxes at which balancing weight is deemed not worth the extra computation time.
121
     */
122
    public function getMaxBoxesToBalanceWeight(): int
123
    {
124
        return $this->maxBoxesToBalanceWeight;
125
    }
126
127
    /**
128
     * Number of boxes at which balancing weight is deemed not worth the extra computation time.
129
     */
130
    public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight): void
131
    {
132
        $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
133
    }
134
135
    public function setPackedBoxSorter(PackedBoxSorter $packedBoxSorter): void
136
    {
137
        $this->packedBoxSorter = $packedBoxSorter;
138
    }
139
140 4
    public function throwOnUnpackableItem(bool $throwOnUnpackableItem): void
141
    {
142 4
        $this->throwOnUnpackableItem = $throwOnUnpackableItem;
143
    }
144
145
    public function beStrictAboutItemOrdering(bool $beStrict): void
146
    {
147
        $this->beStrictAboutItemOrdering = $beStrict;
148
    }
149
150
    /**
151
     * Return the items that haven't been packed.
152
     */
153 4
    public function getUnpackedItems(): ItemList
154
    {
155 4
        return $this->items;
156
    }
157
158
    /**
159
     * Pack items into boxes using built-in heuristics for the best solution.
160
     */
161 24
    public function pack(): PackedBoxList
162
    {
163 24
        $this->logger->log(LogLevel::INFO, '[PACKING STARTED]');
164
165 24
        $packedBoxes = $this->doBasicPacking();
166
167
        // If we have multiple boxes, try and optimise/even-out weight distribution
168 24
        if (!$this->beStrictAboutItemOrdering && $packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
169 4
            $redistributor = new WeightRedistributor($this->boxes, $this->packedBoxSorter, $this->boxQuantitiesAvailable);
170 4
            $redistributor->setLogger($this->logger);
171 4
            $packedBoxes = $redistributor->redistributeWeight($packedBoxes);
172
        }
173
174 24
        $this->logger->log(LogLevel::INFO, "[PACKING COMPLETED], {$packedBoxes->count()} boxes");
175
176 24
        return $packedBoxes;
177
    }
178
179
    /**
180
     * @internal
181
     */
182 24
    public function doBasicPacking(bool $enforceSingleBox = false): PackedBoxList
183
    {
184 24
        $packedBoxes = new PackedBoxList($this->packedBoxSorter);
185
186
        // Keep going until everything packed
187 24
        while ($this->items->count()) {
188 24
            $packedBoxesIteration = [];
189
190
            // Loop through boxes starting with smallest, see what happens
191 24
            foreach ($this->getBoxList($enforceSingleBox) as $box) {
192 24
                $volumePacker = new VolumePacker($box, $this->items);
193 24
                $volumePacker->setLogger($this->logger);
194 24
                $volumePacker->beStrictAboutItemOrdering($this->beStrictAboutItemOrdering);
195 24
                $packedBox = $volumePacker->pack();
196 24
                if ($packedBox->getItems()->count()) {
197 22
                    $packedBoxesIteration[] = $packedBox;
198
199
                    // Have we found a single box that contains everything?
200 22
                    if ($packedBox->getItems()->count() === $this->items->count()) {
201 20
                        $this->logger->log(LogLevel::DEBUG, "Single box found for remaining {$this->items->count()} items");
202 20
                        break;
203
                    }
204
                }
205
            }
206
207 24
            if (count($packedBoxesIteration) > 0) {
208
                // Find best box of iteration, and remove packed items from unpacked list
209 22
                usort($packedBoxesIteration, [$this->packedBoxSorter, 'compare']);
210 22
                $bestBox = $packedBoxesIteration[0];
211
212 22
                $this->items->removePackedItems($bestBox->getItems());
213
214 22
                $packedBoxes->insert($bestBox);
215 22
                --$this->boxQuantitiesAvailable[$bestBox->getBox()];
216 4
            } elseif ($this->throwOnUnpackableItem) {
217
                throw new NoBoxesAvailableException("No boxes could be found for item '{$this->items->top()->getDescription()}'", $this->items);
218
            } else {
219 4
                $this->logger->log(LogLevel::INFO, "{$this->items->count()} unpackable items found");
220 4
                break;
221
            }
222
        }
223
224 24
        return $packedBoxes;
225
    }
226
227
    /**
228
     * Pack items into boxes returning "all" possible box combination permutations.
229
     * Use with caution (will be slow) with a large number of box types!
230
     *
231
     * @return PackedBoxList[]
232
     */
233
    public function packAllPermutations(): array
234
    {
235
        $this->logger->log(LogLevel::INFO, '[PACKING STARTED (all permutations)]');
236
237
        $boxQuantitiesAvailable = clone $this->boxQuantitiesAvailable;
238
239
        $wipPermutations = [['permutation' => new PackedBoxList($this->packedBoxSorter), 'itemsLeft' => $this->items]];
240
        $completedPermutations = [];
241
242
        // Keep going until everything packed
243
        while ($wipPermutations) {
0 ignored issues
show
Bug Best Practice introduced by
The expression $wipPermutations of type array<integer,array<stri...xPacker\PackedBoxList>> 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...
244
            $wipPermutation = array_pop($wipPermutations);
245
            $remainingBoxQuantities = clone $boxQuantitiesAvailable;
246
            foreach ($wipPermutation['permutation'] as $packedBox) {
247
                --$remainingBoxQuantities[$packedBox->getBox()];
248
            }
249
            if ($wipPermutation['itemsLeft']->count() === 0) {
250
                $completedPermutations[] = $wipPermutation['permutation'];
251
                continue;
252
            }
253
254
            $additionalPermutationsForThisPermutation = [];
255
            foreach ($this->boxes as $box) {
256
                if ($remainingBoxQuantities[$box] > 0) {
257
                    $volumePacker = new VolumePacker($box, $wipPermutation['itemsLeft']);
258
                    $volumePacker->setLogger($this->logger);
259
                    $packedBox = $volumePacker->pack();
260
                    if ($packedBox->getItems()->count()) {
261
                        $additionalPermutationsForThisPermutation[] = $packedBox;
262
                    }
263
                }
264
            }
265
266
            if (count($additionalPermutationsForThisPermutation) > 0) {
267
                foreach ($additionalPermutationsForThisPermutation as $additionalPermutationForThisPermutation) {
268
                    $newPermutation = clone $wipPermutation['permutation'];
269
                    $newPermutation->insert($additionalPermutationForThisPermutation);
270
                    $itemsRemainingOnPermutation = clone $wipPermutation['itemsLeft'];
271
                    $itemsRemainingOnPermutation->removePackedItems($additionalPermutationForThisPermutation->getItems());
272
                    $wipPermutations[] = ['permutation' => $newPermutation, 'itemsLeft' => $itemsRemainingOnPermutation];
273
                }
274
            } elseif ($this->throwOnUnpackableItem) {
275
                throw new NoBoxesAvailableException("No boxes could be found for item '{$wipPermutation['itemsLeft']->top()->getDescription()}'", $wipPermutation['itemsLeft']);
276
            } else {
277
                $this->logger->log(LogLevel::INFO, "{$this->items->count()} unpackable items found");
278
                if ($wipPermutation['permutation']->count() > 0) { // don't treat initial empty permutation as completed
279
                    $completedPermutations[] = $wipPermutation['permutation'];
280
                }
281
            }
282
        }
283
284
        $this->logger->log(LogLevel::INFO, '[PACKING COMPLETED], ' . count($completedPermutations) . ' permutations');
285
286
        foreach ($completedPermutations as $completedPermutation) {
287
            foreach ($completedPermutation as $packedBox) {
288
                $this->items->removePackedItems($packedBox->getItems());
289
            }
290
        }
291
292
        return $completedPermutations;
293
    }
294
295
    /**
296
     * Get a "smart" ordering of the boxes to try packing items into. The initial BoxList is already sorted in order
297
     * so that the smallest boxes are evaluated first, but this means that time is spent on boxes that cannot possibly
298
     * hold the entire set of items due to volume limitations. These should be evaluated first.
299
     *
300
     * @return iterable<Box>
301
     */
302 24
    protected function getBoxList(bool $enforceSingleBox = false): iterable
303
    {
304 24
        $this->logger->log(LogLevel::INFO, 'Determining box search pattern', ['enforceSingleBox' => $enforceSingleBox]);
305 24
        $itemVolume = 0;
306 24
        foreach ($this->items as $item) {
307 24
            $itemVolume += $item->getWidth() * $item->getLength() * $item->getDepth();
308
        }
309 24
        $this->logger->log(LogLevel::DEBUG, 'Item volume', ['itemVolume' => $itemVolume]);
310
311 24
        $preferredBoxes = [];
312 24
        $otherBoxes = [];
313 24
        foreach ($this->boxes as $box) {
314 24
            if ($this->boxQuantitiesAvailable[$box] > 0) {
315 24
                if ($box->getInnerWidth() * $box->getInnerLength() * $box->getInnerDepth() >= $itemVolume) {
316 24
                    $preferredBoxes[] = $box;
317 14
                } elseif (!$enforceSingleBox) {
318 14
                    $otherBoxes[] = $box;
319
                }
320
            }
321
        }
322
323 24
        $this->logger->log(LogLevel::INFO, 'Box search pattern complete', ['preferredBoxCount' => count($preferredBoxes), 'otherBoxCount' => count($otherBoxes)]);
324
325 24
        return array_merge($preferredBoxes, $otherBoxes);
326
    }
327
}
328