Passed
Pull Request — master (#335)
by
unknown
05:51 queued 04:02
created

Packer::getUnpackedItems()   A

Complexity

Conditions 1
Paths 1

Size

Total Lines 3
Code Lines 1

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 2
CRAP Score 1

Importance

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