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