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 ArrayIterator; |
||
12 | use Countable; |
||
13 | use IteratorAggregate; |
||
14 | use Traversable; |
||
15 | |||
16 | use function array_key_last; |
||
17 | use function array_pop; |
||
18 | use function array_reverse; |
||
19 | use function array_slice; |
||
20 | use function count; |
||
21 | use function current; |
||
22 | use function end; |
||
23 | use function key; |
||
24 | use function prev; |
||
25 | use function usort; |
||
26 | |||
27 | /** |
||
28 | * List of items to be packed, ordered by volume. |
||
29 | */ |
||
30 | class ItemList implements Countable, IteratorAggregate |
||
31 | { |
||
32 | /** |
||
33 | * @var Item[] |
||
34 | */ |
||
35 | private array $list = []; |
||
36 | |||
37 | private bool $isSorted = false; |
||
38 | |||
39 | private ?bool $hasConstrainedItems = null; |
||
40 | |||
41 | private ?bool $hasNoRotationItems = null; |
||
42 | |||
43 | 106 | public function __construct(private readonly ItemSorter $sorter = new DefaultItemSorter()) |
|
44 | { |
||
45 | 106 | } |
|
46 | |||
47 | /** |
||
48 | * Do a bulk create. |
||
49 | * |
||
50 | * @param Item[] $items |
||
51 | */ |
||
52 | 92 | public static function fromArray(array $items, bool $preSorted = false): self |
|
53 | { |
||
54 | 92 | $list = new self(); |
|
55 | 92 | $list->list = array_reverse($items); // internal sort is largest at the end |
|
56 | 92 | $list->isSorted = $preSorted; |
|
57 | |||
58 | 92 | return $list; |
|
59 | } |
||
60 | |||
61 | 107 | public function insert(Item $item, int $qty = 1): void |
|
62 | { |
||
63 | 107 | for ($i = 0; $i < $qty; ++$i) { |
|
64 | 107 | $this->list[] = $item; |
|
65 | } |
||
66 | 107 | $this->isSorted = false; |
|
67 | |||
68 | 107 | if (isset($this->hasConstrainedItems)) { // normally lazy evaluated, override if that's already been done |
|
69 | $this->hasConstrainedItems = $this->hasConstrainedItems || $item instanceof ConstrainedPlacementItem; |
||
70 | } |
||
71 | |||
72 | 107 | if (isset($this->hasNoRotationItems)) { // normally lazy evaluated, override if that's already been done |
|
73 | $this->hasNoRotationItems = $this->hasNoRotationItems || $item->getAllowedRotation() === Rotation::Never; |
||
74 | } |
||
75 | } |
||
76 | |||
77 | /** |
||
78 | * Remove item from list. |
||
79 | */ |
||
80 | 1 | public function remove(Item $item): void |
|
81 | { |
||
82 | 1 | if (!$this->isSorted) { |
|
83 | 1 | usort($this->list, $this->sorter->compare(...)); |
|
84 | 1 | $this->list = array_reverse($this->list); // internal sort is largest at the end |
|
85 | 1 | $this->isSorted = true; |
|
86 | } |
||
87 | |||
88 | 1 | end($this->list); |
|
89 | do { |
||
90 | 1 | if (current($this->list) === $item) { |
|
91 | 1 | unset($this->list[key($this->list)]); |
|
92 | |||
93 | 1 | return; |
|
94 | } |
||
95 | 1 | } while (prev($this->list) !== false); |
|
96 | } |
||
97 | |||
98 | 54 | public function removePackedItems(PackedItemList $packedItemList): void |
|
99 | { |
||
100 | 54 | foreach ($packedItemList as $packedItem) { |
|
101 | 53 | end($this->list); |
|
102 | do { |
||
103 | 53 | if (current($this->list) === $packedItem->item) { |
|
104 | 53 | unset($this->list[key($this->list)]); |
|
105 | |||
106 | 53 | break; |
|
107 | } |
||
108 | 16 | } while (prev($this->list) !== false); |
|
109 | } |
||
110 | } |
||
111 | |||
112 | /** |
||
113 | * @internal |
||
114 | */ |
||
115 | 102 | public function extract(): Item |
|
116 | { |
||
117 | 102 | if (!$this->isSorted) { |
|
118 | 2 | usort($this->list, $this->sorter->compare(...)); |
|
119 | 2 | $this->list = array_reverse($this->list); // internal sort is largest at the end |
|
120 | 2 | $this->isSorted = true; |
|
121 | } |
||
122 | |||
123 | 102 | return array_pop($this->list); |
|
124 | } |
||
125 | |||
126 | /** |
||
127 | * @internal |
||
128 | */ |
||
129 | 101 | public function top(): Item |
|
130 | { |
||
131 | 101 | if (!$this->isSorted) { |
|
132 | 60 | usort($this->list, $this->sorter->compare(...)); |
|
133 | 60 | $this->list = array_reverse($this->list); // internal sort is largest at the end |
|
134 | 60 | $this->isSorted = true; |
|
135 | } |
||
136 | |||
137 | 101 | return $this->list[array_key_last($this->list)]; |
|
138 | } |
||
139 | |||
140 | /** |
||
141 | * @internal |
||
142 | */ |
||
143 | 21 | public function topN(int $n): self |
|
144 | { |
||
145 | 21 | if (!$this->isSorted) { |
|
146 | 1 | usort($this->list, $this->sorter->compare(...)); |
|
147 | 1 | $this->list = array_reverse($this->list); // internal sort is largest at the end |
|
148 | 1 | $this->isSorted = true; |
|
149 | } |
||
150 | |||
151 | 21 | $topNList = new self(); |
|
152 | 21 | $topNList->list = array_slice($this->list, -$n, $n); |
|
153 | 21 | $topNList->isSorted = true; |
|
154 | |||
155 | 21 | return $topNList; |
|
156 | } |
||
157 | |||
158 | /** |
||
159 | * @return Traversable<Item> |
||
160 | */ |
||
161 | 98 | public function getIterator(): Traversable |
|
162 | { |
||
163 | 98 | if (!$this->isSorted) { |
|
164 | 43 | usort($this->list, $this->sorter->compare(...)); |
|
165 | 43 | $this->list = array_reverse($this->list); // internal sort is largest at the end |
|
166 | 43 | $this->isSorted = true; |
|
167 | } |
||
168 | |||
169 | 98 | return new ArrayIterator(array_reverse($this->list)); |
|
170 | } |
||
171 | |||
172 | /** |
||
173 | * Number of items in list. |
||
174 | */ |
||
175 | 105 | public function count(): int |
|
176 | { |
||
177 | 105 | return count($this->list); |
|
178 | } |
||
179 | |||
180 | /** |
||
181 | * Does this list contain items with constrained placement criteria. |
||
182 | */ |
||
183 | 99 | public function hasConstrainedItems(): bool |
|
184 | { |
||
185 | 99 | if (!isset($this->hasConstrainedItems)) { |
|
186 | 99 | $this->hasConstrainedItems = false; |
|
187 | 99 | foreach ($this->list as $item) { |
|
188 | 99 | if ($item instanceof ConstrainedPlacementItem) { |
|
189 | 3 | $this->hasConstrainedItems = true; |
|
190 | 3 | break; |
|
191 | } |
||
192 | } |
||
193 | } |
||
194 | |||
195 | 99 | return $this->hasConstrainedItems; |
|
0 ignored issues
–
show
Bug
Best Practice
introduced
by
Loading history...
|
|||
196 | } |
||
197 | |||
198 | /** |
||
199 | * Does this list contain items which cannot be rotated. |
||
200 | */ |
||
201 | 99 | public function hasNoRotationItems(): bool |
|
202 | { |
||
203 | 99 | if (!isset($this->hasNoRotationItems)) { |
|
204 | 99 | $this->hasNoRotationItems = false; |
|
205 | 99 | foreach ($this->list as $item) { |
|
206 | 99 | if ($item->getAllowedRotation() === Rotation::Never) { |
|
207 | $this->hasNoRotationItems = true; |
||
208 | break; |
||
209 | } |
||
210 | } |
||
211 | } |
||
212 | |||
213 | 99 | return $this->hasNoRotationItems; |
|
0 ignored issues
–
show
|
|||
214 | } |
||
215 | } |
||
216 |