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 Psr\Log\LoggerAwareInterface; |
||
12 | use Psr\Log\LoggerInterface; |
||
13 | use Psr\Log\NullLogger; |
||
14 | |||
15 | use function array_merge; |
||
16 | use function iterator_to_array; |
||
17 | use function max; |
||
18 | use function sort; |
||
19 | |||
20 | /** |
||
21 | * Layer packer. |
||
22 | * @internal |
||
23 | */ |
||
24 | class LayerPacker implements LoggerAwareInterface |
||
25 | { |
||
26 | private LoggerInterface $logger; |
||
27 | |||
28 | private bool $singlePassMode = false; |
||
29 | |||
30 | private readonly OrientatedItemFactory $orientatedItemFactory; |
||
31 | |||
32 | private bool $beStrictAboutItemOrdering = false; |
||
33 | |||
34 | private bool $isBoxRotated = false; |
||
35 | |||
36 | 99 | public function __construct(private readonly Box $box) |
|
37 | { |
||
38 | 99 | $this->logger = new NullLogger(); |
|
39 | |||
40 | 99 | $this->orientatedItemFactory = new OrientatedItemFactory($this->box); |
|
0 ignored issues
–
show
Bug
introduced
by
Loading history...
|
|||
41 | 99 | $this->orientatedItemFactory->setLogger($this->logger); |
|
42 | } |
||
43 | |||
44 | /** |
||
45 | * Sets a logger. |
||
46 | */ |
||
47 | 99 | public function setLogger(LoggerInterface $logger): void |
|
48 | { |
||
49 | 99 | $this->logger = $logger; |
|
50 | 99 | $this->orientatedItemFactory->setLogger($logger); |
|
51 | } |
||
52 | |||
53 | 19 | public function setSinglePassMode(bool $singlePassMode): void |
|
54 | { |
||
55 | 19 | $this->singlePassMode = $singlePassMode; |
|
56 | 19 | $this->orientatedItemFactory->setSinglePassMode($singlePassMode); |
|
57 | } |
||
58 | |||
59 | 99 | public function setBoxIsRotated(bool $boxIsRotated): void |
|
60 | { |
||
61 | 99 | $this->isBoxRotated = $boxIsRotated; |
|
62 | 99 | $this->orientatedItemFactory->setBoxIsRotated($boxIsRotated); |
|
63 | } |
||
64 | |||
65 | 40 | public function beStrictAboutItemOrdering(bool $beStrict): void |
|
66 | { |
||
67 | 40 | $this->beStrictAboutItemOrdering = $beStrict; |
|
68 | } |
||
69 | |||
70 | /** |
||
71 | * Pack items into an individual vertical layer. |
||
72 | */ |
||
73 | 99 | public function packLayer(ItemList &$items, PackedItemList $packedItemList, int $startX, int $startY, int $startZ, int $widthForLayer, int $lengthForLayer, int $depthForLayer, int $guidelineLayerDepth, bool $considerStability, ?OrientatedItem $firstItem): PackedLayer |
|
74 | { |
||
75 | 99 | $layer = new PackedLayer(); |
|
76 | 99 | $x = $startX; |
|
77 | 99 | $y = $startY; |
|
78 | 99 | $z = $startZ; |
|
79 | 99 | $rowLength = 0; |
|
80 | 99 | $prevItem = null; |
|
81 | 99 | $skippedItems = []; |
|
82 | 99 | $remainingWeightAllowed = $this->box->getMaxWeight() - $this->box->getEmptyWeight() - $packedItemList->getWeight(); |
|
83 | |||
84 | 99 | while ($items->count() > 0) { |
|
85 | 99 | $itemToPack = $items->extract(); |
|
86 | |||
87 | // skip items that will never fit e.g. too heavy |
||
88 | 99 | if ($itemToPack->getWeight() > $remainingWeightAllowed) { |
|
89 | 18 | continue; |
|
90 | } |
||
91 | |||
92 | 97 | if ($firstItem instanceof OrientatedItem && $firstItem->item === $itemToPack) { |
|
93 | 90 | $orientatedItem = $firstItem; |
|
94 | 90 | $firstItem = null; |
|
95 | } else { |
||
96 | 92 | $orientatedItem = $this->orientatedItemFactory->getBestOrientation($itemToPack, $prevItem, $items, $widthForLayer - $x, $lengthForLayer - $y, $depthForLayer, $rowLength, $x, $y, $z, $packedItemList, $considerStability); |
|
97 | } |
||
98 | |||
99 | 97 | if ($orientatedItem instanceof OrientatedItem) { |
|
100 | 96 | $packedItem = PackedItem::fromOrientatedItem($orientatedItem, $x, $y, $z); |
|
101 | 96 | $layer->insert($packedItem); |
|
102 | 96 | $packedItemList->insert($packedItem); |
|
103 | |||
104 | 96 | $rowLength = max($rowLength, $packedItem->length); |
|
105 | 96 | $prevItem = $orientatedItem; |
|
106 | |||
107 | // Figure out if we can stack items on top of this rather than side by side |
||
108 | // e.g. when we've packed a tall item, and have just put a shorter one next to it. |
||
109 | 96 | $stackableDepth = ($guidelineLayerDepth ?: $layer->getDepth()) - $packedItem->depth; |
|
110 | 96 | if ($stackableDepth > 0) { |
|
111 | 31 | $stackedLayer = $this->packLayer($items, $packedItemList, $x, $y, $z + $packedItem->depth, $x + $packedItem->width, $y + $packedItem->length, $stackableDepth, $stackableDepth, $considerStability, null); |
|
112 | 31 | $layer->merge($stackedLayer); |
|
113 | } |
||
114 | |||
115 | 96 | $x += $packedItem->width; |
|
116 | 96 | $remainingWeightAllowed = $this->box->getMaxWeight() - $this->box->getEmptyWeight() - $packedItemList->getWeight(); // remember may have packed additional items |
|
117 | |||
118 | // might be space available lengthwise across the width of this item, up to the current layer length |
||
119 | 96 | $layer->merge($this->packLayer($items, $packedItemList, $x - $packedItem->width, $y + $packedItem->length, $z, $x, $y + $rowLength, $depthForLayer, $layer->getDepth(), $considerStability, null)); |
|
120 | |||
121 | 96 | if ($items->count() === 0 && $skippedItems) { |
|
0 ignored issues
–
show
The expression
$skippedItems 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
Loading history...
|
|||
122 | 22 | $items = ItemList::fromArray(array_merge($skippedItems, iterator_to_array($items)), true); |
|
123 | 22 | $skippedItems = []; |
|
124 | } |
||
125 | |||
126 | 96 | continue; |
|
127 | } |
||
128 | |||
129 | 92 | if (!$this->beStrictAboutItemOrdering && $items->count() > 0) { // skip for now, move on to the next item |
|
130 | 79 | $this->logger->debug("doesn't fit, skipping for now"); |
|
131 | 79 | $skippedItems[] = $itemToPack; |
|
132 | // abandon here if next item is the same, no point trying to keep going. Last time is not skipped, need that to trigger appropriate reset logic |
||
133 | 79 | while ($items->count() > 1 && self::isSameDimensions($itemToPack, $items->top())) { |
|
134 | 39 | $skippedItems[] = $items->extract(); |
|
135 | } |
||
136 | 79 | continue; |
|
137 | } |
||
138 | |||
139 | 92 | if ($x > $startX) { |
|
140 | 87 | $this->logger->debug('No more fit in width wise, resetting for new row'); |
|
141 | 87 | $y += $rowLength; |
|
142 | 87 | $x = $startX; |
|
143 | 87 | $rowLength = 0; |
|
144 | 87 | $skippedItems[] = $itemToPack; |
|
145 | 87 | $items = ItemList::fromArray(array_merge($skippedItems, iterator_to_array($items)), true); |
|
146 | 87 | $skippedItems = []; |
|
147 | 87 | $prevItem = null; |
|
148 | 87 | continue; |
|
149 | } |
||
150 | |||
151 | 92 | $this->logger->debug('no items fit, so starting next vertical layer'); |
|
152 | 92 | $skippedItems[] = $itemToPack; |
|
153 | |||
154 | 92 | $items = ItemList::fromArray(array_merge($skippedItems, iterator_to_array($items)), true); |
|
155 | |||
156 | 92 | return $layer; |
|
157 | } |
||
158 | |||
159 | 96 | return $layer; |
|
160 | } |
||
161 | |||
162 | /** |
||
163 | * Compare two items to see if they have same dimensions. |
||
164 | */ |
||
165 | 53 | private static function isSameDimensions(Item $itemA, Item $itemB): bool |
|
166 | { |
||
167 | 53 | if ($itemA === $itemB) { |
|
168 | 34 | return true; |
|
169 | } |
||
170 | 31 | $itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()]; |
|
171 | 31 | $itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()]; |
|
172 | 31 | sort($itemADimensions); |
|
173 | 31 | sort($itemBDimensions); |
|
174 | |||
175 | 31 | return $itemADimensions === $itemBDimensions; |
|
176 | } |
||
177 | } |
||
178 |